Ülesanne SOE-KÜLM

Kaks venda armastavad koos kõikvõimalikke mänge mängida. Viimasel ajal meeldib neile mängida klassikalise mängu "soojem-külmem" uut varianti. Seda mängtakse tühjas toas, mille põrand on jagatud ühikruutudeks. Seega võib tuba vaadelda N rea ja M veeruga ristkülikukujulise tabelina. Igal ruudul on koordinaadid (x,y), kus x on ruudu rea- ja y veerunumber (read on nummerdatud ülalt alla 1..N ja veerud vasakult paremale 1..M).

Mängitakse kahekesi. Esimene mängija seisab mingile ruudule. Teine mängija seob esimese silmad kinni ja märgib mingi teise ruudu ristiga.

Edasi hakkab esimene mängija liikuma. Igal sammul võib ta astuda oma asukoharuudust selle naaberruutu üle nende ühise serva (toast välja minna muidugi ei või). Iga sammu järel ütleb teine mängija esimesele ühe sõna:

• "soe", kui minimaalne esimesel mängijal ristiga ruudule jõudmiseks vajalik sammude arv on nüüd väiksem kui enne;
• "külm", kui minimaalne esimesel mängijal ristiga ruudule jõudmiseks vajalik sammude arv on nüüd suurem kui enne;
• "sama", kui minimaalne esimesel mängijal ristiga ruudule jõudmiseks vajalik sammude arv ei muutunud.

Esimese mängija eesmärk on jõuda märgitud ruudule võimalikult väikese arvu sammudega. Seejärel mäng lõpeb ja esimene mängija saab punkte vastavalt kulutatud sammude arvule. Kirjutada programm, mis aitab esimesel mängijal võimalikult väikese sammude arvuga märgitud ruudule jõuda.

Teek

Selleks on kasutada teek Second, mis emuleerib teise mängija käitumist. Teegis on järgmised funktsioonid:

void Init(long *N, long *M, long *X, long *Y);

Init() -> N, M, X, Y

int[] Second.Init() -> {N, M, X, Y}

long Move(long X, long Y);

Move(X, Y) -> R

int Second.Move(X, Y)

void Finish();

Finish()

void Second.Finish()

Teegi kasutamine

Oma lahenduse oma arvutis selle teegiga testimiseks tuleb:

1. Kaasata teek oma programmi:
   C/C++: failid: Second.h ja Second.o; kasutamine: #include "Second.h"
   Python: fail: Second.pyc; kasutamine: from Second import *
   Java: fail: Second.class
2. Panna sisendi kirjeldus faili input.txt. Faili esimesel real peavad olema kuus tühikutega eraldatud täisarvu N, M, X₁, Y₁, X₂, Y₂, kus N ja M on toa mõõdud ning (X₁,Y₁) esimese mängija algasukoha ja (X₂,Y₂) märgitud ruudu koordinaadid.
3. Programmi töö lõppedes tekib väljundfail output.txt, milles on kõigi lahenduse tehtud käikude kirjeldus ja viimasel real mängu tulemus:
   Ok, kui lahenduse vastus oli õige,
   Wrong Answer, kui vastus ei olnud õige,
   Presentation Error, kui lahendus rikkus teegi kasutamise reegleid.

Kompileerimisel ja testimisel peavad lahenduse lähtetekst, teegi failid ja input.txt olema samas kataloogis. Lahendus ei või ise otse faile avada.

Hindamine

Lahendus, mis rikub teegi kasutamise reegleid, saab testi eest 0 punkti.

Lahendus, mis kasutab funktsiooni Finish, kui esimene mängija ei ole märgitud ruudul, saab testi eest 0 punkti.

Lahendus, mis teeb rohkem kui 10⁶ käiku, saab testi eest 0 punkti.

Muidu saab lahendus P*A/S punkti, kus P on testi väärtus, S lahenduse käikude (funktsiooni Move väljakutsete) arv ja A=|X₁-X₂|+|Y₁-Y₂|.

5 7 2 2 4 6

Init(N = 5, M = 7, X = 2, Y = 2)
Move(X = 3, Y = 2) = -1
Move(X = 4, Y = 2) = -1
Move(X = 4, Y = 3) = -1
Move(X = 4, Y = 4) = -1
Move(X = 4, Y = 5) = -1
Move(X = 4, Y = 6) = -1
Finish()
Ok
    

3 2 3 1 3 2

Init(N = 3, M = 2, X = 3, Y = 1)
Move(X = 2, Y = 1) = 1
Move(X = 2, Y = 2) = -1
Move(X = 3, Y = 2) = -1
Move(X = 2, Y = 2) = 1
Move(X = 3, Y = 2) = -1
Move(X = 2, Y = 2) = 1
Move(X = 3, Y = 2) = -1
Finish()
Ok
    

Teegid

C/C++

GCC jaoks kompileeritud tgz (Linux, 64-bitine x86)
lähtetekst ise kompileerimiseks tgz, zip

Python

Python 2.6.8 jaoks kompileeritud tgz
lähtetekst ise kompileerimiseks tgz, zip

Java

JRE 1.5+ jaoks kompileeritud tgz
lähtetekst ise kompileerimiseks tgz, zip

Testid

Linux

tgz

Windows

zip