Državno natjecanje 2014. / Osnovna škola (8. razred) - 3. zadatak

Ovaj zadatak pomalo je neobičan.

Postoji mnogo rješenja, a od tebe se ne traži da ispišeš najbolje, nego što bolje rješenje. Svako razumno rješenje donijet će ti neki broj bodova.

Što trebaš učiniti? Trebaš samo prošetati. Točnije, ispisati niz koraka kojim se, počevši iz ishodišta (točke (0, 0)) krećeš po cjelobrojnim točkama koordinatnog sustava.

Svaki korak pomiče te za jednu točku u jednom od četiri osnovna smjera.

Korake predstavljamo znakovima U (gore), L (lijevo), R (desno) i D (dolje). Tvoja šetnja može biti bilo koje duljine, od 1 do 5000 koraka.

Pa dobro, u čemu je štos? Šetnja treba biti takva da čini što više skretanja, što manje puta posjećuje isto polje i što manje puta izlazi iz kvadrata kretanja (čija je veličina određena danim brojem N).

Preciznije:

A. Za svaki korak (osim prvog) koji skreće, što znači da nije jednak prethodnome koraku, osvajaš 2 punta.

B. Za svaki korak koji vodi u već posjećeno polje, ili u polje čija je apsolutna vrijednost x ili y koordinate veća od N, dobivaš kaznu od -3 punta.

Naravno, za korake koji zadovoljavaju i A) i B) primjenjuju se oba pravila.

U pojedinom test podatku, koji nosi 10 bodova, punti se pretvaraju u bodove na sljedeći način. Ako je autorovo rješenje na tom test podatku ostvarilo ukupno M punata, a tvoje ukupno P punata, osvajaš

(P / M) * 10

bodova za taj test podatak.

Pritom se ovaj broj pomiče na 0 ako je negativan, a na 10 ako je veći od 10.

Ako broj nije cijeli, zaokružuje se na najbliži cijeli broj.

ULAZNI PODATCI

U jedinome retku nalazi se prirodan broj N (1 ≤ N ≤ 20) koji određuje prostor kretanja, korišten u pravilu B.

IZLAZNI PODATCI

U jedini redak ispiši svoju šetnju – niz sastavljen od najviše 5000 znakova iz skupa {U, L, R, D}, bez razmaka.

PRIMJERI TEST PODATAKA

Ulaz

2

Izlaz

LDLUURRURRRDLU

Broj punata

9 * 2 + 3 * (-3) = 9

Skica primjera

Lokalno testiranje

Ako želiš, možeš testirati svoju šetnju, tj. provjeriti kako izgleda i koliko punata osvaja.

S Evaluatora preuzmi program setnja_test.exe.

On na ulaz prima u prvom retku broj N, a u drugom retku tvoju šetnju.

Na primjer: 2

LDLUURRURRRDLU

Na izlazu ćeš dobiti broj osvojenih punata (u obliku A 2 + B (-3) = P), a u datoteci “setnja.png” sliku svoje šetnje, koja će se i automatski prikazati na ekranu.