Day 1 Task 2: Hideg-meleg

Jack és Jill Hideg-meleg játékot játszik. Jill gondol egy számot 1 és N között, amit Jack megpróbál kitalálni. Jack a kérdésében egy 1 és N közötti számra kérdez rá, amire Jill válasza meleg, hideg vagy azonos. Jack első kérdésére Jill válasza azonos. A többi esetben Jill válasza:

• Meleg, ha ez a szám közelebb van a Jill által gondolt számhoz, mint az előző kérdésben kérdezett szám,
• Hideg, ha ez a szám távolabb van a Jill által gondolt számtól, mint az előző kérdésben kérdezett szám,
• Azonos, ha ez a szám azonos távolságra van a Jill által gondolt számhoz, mint az előző kérdésben kérdezett szám.

Ird meg Jack HC(N) kérdezését megvalósitó eljárást! Ez a Guess(G) függvényt hivja, ahol G 1 és N közötti szám. Guess(G) visszaadott értéke 1, ha a válasz meleg, -1, ha a válasz hideg, illetve 0, ha a válasz azonos. A HC(N) függvény visszaadott értéke a Jill által gondolt szám legyen!

Példa

N=5, és Jill a 2-re gondolt. Ha a HC az alábbi Guess hivásokat végzi, megkapja az eredményt:

Hivás	Visszadott érték	Magyarázat
Guess(5)	0	Azonos (első hivás)
Guess(3)	1	Meleg
Guess(4)	-1	Hideg
Guess(1)	1	Meleg
Guess(3)	0	Azonos

Ekkor Jack tudja, hogy Jill a 2-re gondolt, és a HC a 2-t adja vissza eredményül. Jack itt 5 kérdést tett fel, de a feladat ennél kevessebből is megoldható.

1. részfeladat [25 pont]

HC(N) a Guess(G)-t legfeljebb N-szer hivhatja. A HC(N)-t az értékelő legfeljebb 125 250-ször hivja, ahol N 1 és 500 közötti szám.

2. részfeladat [25 pont]

HC(N) a Guess(G)-t legfeljebb 18-szor hivhatja. A HC(N)-t az értékelő legfeljebb 125 250-ször hivja, ahol N 1 és 500 közötti szám.

3. részfeladat [25 pont]

HC(N) a Guess(G)-t legfeljebb 16-szor hivhatja. A HC(N)-t az értékelő legfeljebb 125 250-ször hivja, ahol N 1 és 500 közötti szám.

4. részfeladat [legfeljebb 25 pont]

Legyen W a legnagyobb olyan egész, amelyre 2^W≤3N. A pontszámok:

• 0 pont, ha HC(N) több mint 2W Guess(G) hivást végez,
• 25α pont (0<α<1): ha a HC(N) a Guess(G)-t legfeljebb 2W-αW-szer hivja,
• 25 pont: ha a HC(N) a Guess(G)-t legfeljebb W-szer hivja.

Az értékelő legfeljebb 1 000 000-szor hivja a HC(N)–t, ahol N 1 és 500 000 000 közötti egész szám.

Megvalósitás

• Use the RunC programming and test environment
• Implementation folder: /home/ioi2010-contestant/hottercolder/ (download prototype here)
• To be implemented by contestant: hottercolder.c or hottercolder.cpp or hottercolder.pas
• Contestant interface: hottercolder.h or hottercolder.pas
• Grader interface: grader.h or graderlib.pas
• Sample grader: grader.c or grader.cpp or grader.pas and graderlib.pas
• Sample grader input: grader.in.1 grader.in.2.
  Note: The input file contains several lines, each containing N and Jill's number.
• Expected output for sample grader input: the grader will create files grader.out.1 grader.out.2 etc.
• If the implementation correctly implements Subtask 1, one line of output will contain OK 1
• If the implementation correctly implements Subtask 2, one line of output will contain OK 2
• If the implementation correctly implements Subtask 3, one line of output will contain OK 3
• If T > 125 250 and the implementation correctly implements Subtask 4, one line of output will contain OK 4 alpha α
• Compile and run (command line): runc grader.c or runc grader.cpp or runc grader.pas
• Compile and run (gedit plugin): Control-R, while editing any implementation file.
• Submit (command line): submit grader.c or submit grader.cpp or submit grader.pas
• Submit (gedit plugin): Control-J, while editing any implementation or grader file.