Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Vpeta drevesa
  3. Prenos

Prenos

Completion requirements
Due: Sunday, 12 November 2023, 11:59 PM

Prenesti želimo podatke o $K$ zemljevidih, ki so oblike pravokotne mreže z $N$ vrsticami in $M$ stolpci. Vsi zemljevidi so enakih dimenzij, razlikujejo pa se po svoji vsebini. Vsebino vsake celice zemljevida bomo predstavili z nekim ascii znakom s kodo med 33 in 126 (printable characters).

Zemljevide bomo pošiljali enega za drugim v poljubnem vrstnem redu. Pri tem lahko zemljevid $z$ pošljemo na dva načina. Pošljemo lahko celoten opis zemljevida $z$, kar zahteva prenos $NM$ bajtov. Druga možnost je, da izberemo nek že prenesen zemljevid $z'$ in pošljemo samo podatke o tem, kako se nov zemljevid $z$ razlikuje od $z'$. Za tako pošiljanje potrebujemo $d(z,z') X$ bajtov, kjer je $X$ vnaprej podana cena pošiljanja posamezne spremembe, $d(z,z')$ pa število istoležnih celic, v katerih se zemljevida $z$ in $z'$ razlikujeta.

Omejitve podatkov:

  • $1 \leq K \leq 1000$
  • $1 \leq N,M \leq 10$
  • $1 \leq X \leq 100$

Vhodni in izhodni podatki:

V prvi vrstici so s presledkom ločena števila $K$, $N$, $M$ in $X$. Sledijo opisi vseh $K$ zemljevidov, ki se začnejo s prazno vrstico, čemur sledi $N$ vrstic z nizi dolžine $M$.

Izpišite najmanjšo ceno prenosa vseh zemljevidov.

Primer vhoda:

6 2 3 2

AA.
.BC

BAC
CBC

...
...

.A.
.BC

BA.
.BC

A..
...

Pravilen izhod:

22

Eden od načinov prenosa je sledeč:

  • Prenesemo tretji zemljevid (cena 6).
  • Prenesemo šesti zemljevid kot razliko do tretjega (cena 2).
  • Prenesemo prvi zemljevid (cena 6).
  • Prenesemo četrti in peti zemljevid kot razliko do prvega (obakrat cena 2).
  • Prenesemo drugi zemljevid kot razliko do petega (cena 4).
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah