ŽUPANIJSKO NATJECANJE 2014. / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Pojavom tableta i mobitela s ekranima osjetljivima na dodir, fizičke tipkovnice lagano odlaze u zaborav. Međutim, jedan problem s tipkovnicama na ekranima je veća mogućnost pogreške prilikom tipkanja, posebno kada je riječ o relativno malenim ekranima.

Za ovu priliku pretpostavimo da se tipkovnica sastoji od skupa pravokutnika u standardnom koordinatnom sustavu (koordinata \(X\) raste s lijeva na desno, koordinata \(Y\) raste odozdo prema gore) kao na slici gore. Tipkovnica je definirana na sljedeći način:

• Svaki pravokutnik je širine \(300\) te visine \(200\).
• Između svaka dva pravokutnika u istom ‘redu’ se nalazi horizontalni razmak od točno \(20\).
• Između dva susjedna reda je vertikalni razmak od točno \(20\).
• Donji lijevi kut pravokutnika koji sadrži slovo Q je na koordinatama \((0, 440)\).
• Donji lijevi kut pravokutnika koji sadrži slovo A je na koordinatama \((150, 220)\).
• Donji lijevi kut pravokutnika koji sadrži slovo Z je na koordinatama \((470, 0)\).

Na temelju ovih pravila i rasporeda tipaka danog u slici gore, mogu se odrediti koordinate pravokutnika za svako slovo. Tako su, na primjer, donji-lijevi i gornji-desni kutovi pravokutnika koji sadrži slovo J jednaki \((2070, 220)\) i \((2370, 420)\) redom. Središte pravokutnika definiramo kao polovište dužine između dva suprotna kuta pravokutnika. Tako je, na primjer, središte pravokutnika koji sadrži slovo J točka \((2220, 320)\). Primijetite da kutovi svih pravokutnika imaju parne \(X\) i \(Y\) koordinate, pa stoga središte svakog pravokutnika ima cjelobrojne koordinate.

Zadan je niz od \(N\) točaka u koordinatnom sustavu - to su koordinate gdje je korisnik redom dodirnuo ekran. Za svaki dodir kažemo da je korisnik stisnuo slovo ako se točka nalazi unutar ili na rubu odgovarajućeg pravokutnika.

Podzadatak A.

Napiši program koji će za svaku od \(N\) točaka odrediti koje je slovo korisnik stisnuo te ispisati ili nađeno slovo ili znak ? ako točka ne odgovara niti jednom slovu.

Podzadatak B.

Dodatno, zadan je rječnik koji se sastoji od \(M\) riječi, a svaka riječ od najviše \(10\) velikih slova engleske abecede. Vaš program treba odrediti koja je riječ iz rječnika najbliža zadanom nizu točaka.

Udaljenost niza točaka od riječi je najmanja ukupna cijena niza transformacija kojima se niz točaka može prevesti u neki niz od točno \(N\) točaka u kojemu se \(i\)-ta točka nalazi unutar ili na rubu pravokutnika \(i\)-tog slova te riječi, za svaki \(i\) od \(1\) do \(N\). Pritom dozvoljene transformacije i njihove cijene su redom:

• Možemo izbrisati proizvoljnu točku iz niza točaka - cijena transformacije je zadani prirodni broj \(D\).
• Možemo dodati proizvoljnu točku na proizvoljno mjesto u nizu - cijena je zadani prirodni broj \(A\).
• Možemo točku iz niza \((X, Y)\) promijeniti tj. pomaknuti na koordinate središta pravokutnika proizvoljnog slova. Cijena ove transformacije je kvadrat euklidske udaljenosti između točke i središta pravokutnika gdje smo točku pomaknuli. Drugim riječima, ukoliko točku \((X_1, Y_1)\) pomaknemo na središte pravokutnika koje se nalazi na koordinatama \((X_2, Y_2)\) onda je cijena transformacije jednaka \((X_1 - X_2)^2 + (Y_1 - Y_2)^2\). Točka ostaje na istom mjestu u nizu.

Nikakve druge transformacije niza (npr. zamjena mjesta dviju točaka) nisu dozvoljene. Dozvoljeno je da prilikom transformacija niz ostane prazan.

Ukoliko zadani niz točaka već odgovara nekoj riječi iz rječnika onda, naravno, nije potrebno raditi transformacije te je udaljenost niza točaka do te riječi jednaka nuli.

Ukoliko ima više najbližih riječi, potrebno je ispisati onu koja se ranije pojavljuje u rječniku.

Ulazni podaci

U prvom redu nalaze se četiri prirodna broja, \(N\), \(M\), \(A\) i \(D\) \((N \leq 10, M \leq 100, A \leq 1 000 000, D \leq 1 000 000)\) međusobno odvojena razmakom - broj točaka, broj riječi u rječniku, cijene dodavanja i brisanja točke.

Nakon toga slijedi \(N\) redova od kojih svaki sadrži dva cijela broja \(X\), \(Y\) \((-5000 \leq X, Y \leq 5000)\) - koordinate odgovarajuće točke.

Nakon toga slijedi \(M\) redova, svaki sadrži jednu riječ od najviše \(10\) velikih slova engleske abecede. Sve riječi će biti različite i bit će poredane abecedno.

Izlazni podaci

U prvi red potrebno je ispisati niz od \(N\) znakova (bez razmaka između pojedinih znakova) gdje je svaki znak ili veliko slovo engleske abecede ili znak ? - rješenje podzadatka A.

U drugi red izlaza potrebno je ispisati jednu od riječi iz rječnika - rješenje podzadatka B.

Bodovanje

Ukoliko je prvi red ispravan natjecatelj dobiva \(40\%\) bodova za određeni test podatak, čak i ako drugi red neispravan ili nije uopće ispisan.

Ukoliko je drugi red ispravan natjecatelj dobiva \(60\%\) bodova za određeni test podatak, čak i ako je prvi red neispravan (međutim, prvi red mora biti ispisan u ispravnom formatu).

Primjeri test podataka

Ulaz

4 3 100 80000
900 -8
1458 292
2181 202
3252 769
XGJP
XGNO
XGNP

Izlaz

?G??
XGNO

Ulaz

00 5500
1143 436
633 541
1500 427
2058 643
1143 433
2061 55
717 511
DZEERUN
EDTZRN
RETURN
RZETURNZ
TRZZZTT
ZRETURN

Izlaz

??????E
RETURN

Objašnjenje

Udaljenost riječi RETURN od zadanog niza točaka se dobiva sljedećim optimalnim nizom transformacija:

1. Pomicanje točke \((1143, 436)\) u središte tipke R uz cijenu \(11905\).
2. Brisanje idućih \(5\) točaka.
3. Iduću točku nije potrebno pomicati jer je već unutar slova E.
4. Dodavanje \(4\) točke u središta tipaka T, U, R i N.

Ukupna cijena je niza transformacija \(11905+5*5500+4*10500=81405\). Sve riječi imaju udaljenosti redom

• RETURN \(81405\)
• EDTZRN \(85500\)
• ZRETURN \(91905\)
• DZEERUN \(96000\)
• RZETURNZ \(102405\)
• TRZZZTT \(107905\)

Dakle, od svih riječi iz rječnika RETURN je najbliža zadanom nizu točaka.

Ulaz

4 2 100 80000
627 46
470 0
2460 100
2271 97
YZN
ZYMN

Izlaz

ZZMN
ZYMN