Входные данные: - Выходные данные: - Время на тест: 3 секунды Тесты к задаче:Скачать Библиотека:Скачать Автор задачи: Метельский И.С.
Однажды в полночь директора банка Макса Крейзи поднял с постели телефонный звонок. Звонил начальник охраны банка. Он сказал, что произошло крупное ограбление, но, к счастью, охране удалось задержать N подозреваемых. Видимо, грабители каким-то образом избавились от похищенных денег, потому что при обыске ни у кого из подозреваемых не было обнаружено крупной суммы денег. Теперь перед Максом стоит следующая задача: узнать, кто из подозреваемых - грабитель, а кто - нет?
Для этого Макс может устраивать подозреваемым очные ставки. В каждой очной ставке участвуют два человека. Первого из них спрашивают, является ли второй грабителем, а второго - является ли первый грабителем. Известно, что если человек не является грабителем, то он всегда правдиво отвечает на задаваемые ему вопросы. Если же человек - грабитель, то он может ответить как правду, так и неправду. Известно, что количество грабителей меньше N/2. Каждый подозреваемый знает, кто является грабителем, а кто - нет. Максу необходимо определить список всех грабителей как можно скорее.
Для решения этого задания вам предоставляется библиотека Crime.tpu для работающих на Паскале и Crime.obj для работающих на языке C. Она содержит 3 процедуры:
procedure Init(var N: LongInt);
procedure Test(i,j: LongInt; var res1,
res2: LongInt)
procedure Result(i: LongInt) void Init(long &N)
void Test(long i, long j, long &res1,
long &res2)
void Result(long i)
Процедура Init должна вызываться один раз в самом начале программы. Она возвращает значение N - количество подозреваемых. Процедура Test устраивает очную ставку i-му и j-му подозреваемым. Она возвращает res1 - ответ i-го подозреваемого (0 - грабитель, 1 - не грабитель) и res2 - ответ j-го подозреваемого (0 - грабитель, 1 - не грабитель). При вызове Test i должно быть не равно j. Процедура Result должна использоваться для возвращения результатов. Вызов процедуры Result означает, что i-й подозреваемый является грабителем. Процедура Result должна вызываться ровно один раз для каждого грабителя. После вызова процедуры Result запрещается вызывать процедуры Test и Init.
Работа с библиотекой.
Для корректной работы вашей программы включите в ее текст строку "uses Crime;" для программирующих на Паскале или "#include " для программирующих на С.
При отладке своей программы Вы можете экспериментировать с библиотекой, создавая файл "Input.Txt". Первая строка этого файла должна содержать число N. Следующие N строк должны содержать по одному числу каждая: 0 - если очередной подозреваемый является грабителем, 1 - в противном случае. Диалог вашей программы и библиотеки записывается в файл "Output.Txt". Результат работы (тест прошел / тест не прошел) записывается в файл "Result.Txt".
Пример.
Для файла Input.txt:
3
1
1
0
Если в Вашей программе на Паскале есть, например, следующие операторы:
Var N,res1,res2:longint;
…
begin
…
Init(N);
…
Test(1,2,res1,res2);
…
Test(1,3,res1, res2);
…
Result(3);
…
end. или если в Вашей программе на C есть, например, следующие операторы:
main()
{
long N,res1,res2;
…
Init(N);
…
Test(1,2,res1,res2);
…
Test(1,3,res1, res2);
…
Result(3);
…
} то диалог вашей программы и библиотеки (в файле Output.txt) может иметь вид:
Чтение входных данных...
Ok!
Init(3)
Test(1,2,1,1)
Test(1,3,0,1)
Result(3)
Ограничения. 1 <= N <= 10000; время на тест - 3 с; гарантируется, что суммарное время работы вызываемых вами процедур библиотеки не превысит 2 с.
Оценка. Если ваша программа вызывает Test более чем 20000 раз, или совершает какие-либо некорректные действия (например, вызывает Init два раза или вызывает Test после Result и т.д.), или результат ее работы не является правильным, она получает 0 баллов. Иначе, она получает полный балл за тест.
Замечания.
1) Ваша программа не должна содержать операторов чтения данных из файлов или записи данных в файлы. Если ваша программа пытается сделать это, она будет снята с тестирования.