tz
Играта TZIANSITZI, което в превод означава "вземи камъчета", е популярна игра от Китай. Двама играчи един след друг вземат камъчета от две купчинки. При всеки ход, играчът може да вземе или еднакъв брой камъчета от двете купчинки или произволен брой камъчета, но само от едната купчинка. Победител е играчът, който вземе последното камъче.
Задача
Напишете
програма,
която
определя
дали за дадена
конфигурация
първият
играч има печеливша
стратегия
или не. Ако
първият играч
има
печеливша
стратегия,
програмирайте
неговите
ходове,
предполагайки,
че ходовете
на втория
играч ще се
въвеждат от
клавиатурата.
Вход
Програмата
не чете данни
от някакъв
файл.
Изход
Програмата
не записва
данни в
някакъв файл.
Взаимодействие
Програмата
ще
взаимодейства
с програмата
на журито,
работейки
паралелно. За
всеки тест (т.е.
изпълнение)
програмата
ще трябва да
играе
няколко
отделни игри.
За всяка игра
взаимодействието
е в следния
формат:
1. Вашата
програма
чете от
стандартния
вход ред,
съдържащ две
цели
положителни
числа n m, разделени
с интервал (n е
броя на
камъчетата в
първата
купчинка, а m – броя
на
камъчетата
във втората
купчинка. Ако
n и m са
нули, това
означава, че
няма повече
игри.
2. Ако започва
нова игра,
програмата
трябва да
определи
дали
съществува
печеливша стратегия
за първия
играч. Ако
отговорът е
положителен
трябва да се
изведе ред,
съдържащ
числото 1. В
противен
случай,
когато
първият
играч няма
сигурна
печеливша
стратегия,
трябва да се
изведе ред
съдържащ
само 0
(нула), а на
следващия
ред да се
изведе думата
DONE.
3. Ако първият
играч има
печеливша
стратегия,
програмата
трябва да
изпълни
последователност
от кръгове.
За всеки
кръг,
отначало на
стандартния
изход се
извежда ред,
описващ хода
на първия
играч за този
кръг. Ходът се
описва като
се задава
номер на
купчинка (1 за
първата
купчинка, 2 за
втората и 3 за
двете
купчинки),
следван от
интервал и цяло
положително
число,
представляващо
броя на
взетите
камъчета.
След това
трябва да се
прочете ред
от
стандартния
вход, описващ
хода на
втория играч
(зададен по
същия начин).
Когато
Вашата
програма
изпълни
последния
ход, тя
извежда
специален
ред, съдържащ
само думата DONE.
Оценяване
Вашата
програма ще
получи точки
за даден тест,
само ако се
справи
успешно с
всичките игри,
включени в
този тест.
Програмата
ще получи
нула точки в
следните
случаи:
- по време на
ход извежда
брой
камъчета, които
не могат да
бъдат взети в
този момент;
- извежда, че
има
печеливша
стратегия,
когато няма
(или обратно);
- когато има
печеливша
стратегия,
програмата
не успява да
победи;
- не е спазен формата
на изхода.
Инструкции за програмиране
В
програмите
на C/C++ трябва да
се изпълнява flush след
извеждането
на всеки ред
на стандартния
изход. Това
се отнася и
за реда,
съдържащ DONE.
За
програми на C++, използващи
iostream,
трябва да се
използва следната
последователност
за четене от
стандартния
вход и писане
на
стандартния
изход:
cin>>x;
cout<<op<<'\n'<<flush;
За
програми на C,
използващи scanf и printf,
трябва да се
използва
следната
последователност
за четене от
стандартния
вход и писане
на стандартния
изход:
scanf ("%d", &x);
printf("%d\n",op);
fflush
(stdout);
За
програми на Pascal
трябва да се
използва
следната
последователност
за четене от
стандартния
вход с
използване
на readln и за
извеждане на
ред с writeln:
readln(x);
writeln(op);
Ограничения
1 <= n <= 1016
В един тест
няма повече
от 7 игри.
Пример на взаимодействие
Ход |
Значение |
Прочита
1 2 |
n=1, m=2 |
Ограничение за време: 0.1 секунди на тест
prof. Emanuela
Cerchez
"Grigore
Moisil"
Iaşi
IT High School
За връзка :emanuela.cerchez@gmail.com