Входной файл: стандартный вход Выходной файл: стандартный выход Время на тест: 1 секунда Ограничение на память: 64MB Тесты к задаче:Скачать
В стаде фермера Джона находятся N пронумерованных от 1 до N (1 £ N £ 50) и похожих коров. Когда фермер Джон ставит корову в стойло, он должен знать, какую корову он туда ставит.
Коровы различаются по P признакам, пронумерованным от 1 до P (1 £ P £ 8), каждый из которых имеет по три возможных значения. Например, цвет метки на ухе коровы может быть желтым, зеленым или красным. Значения каждого признака определяются одной из букв ‘X’, ‘Y’ или ‘Z’. Любая пара коров фермера Джона отличается по крайней мере одним признаком.
Напишите программу, которая по заданным признакам коров поможет фермеру Джону определить номер коровы, которую он ставит в стойло. Ваша программа может задать Джону не более 100 вопросов вида: “Принадлежит ли значение некоторого признака T у коровы некоторому множеству значений S?”.
Задайте как можно меньше вопросов для определения номера коровы.
Входной файл признаков: guess.in
Первая строка входного файла содержит два целых числа N и P, разделенных пробелом.
Каждая из последующих N строк описывает признаки коровы, используя P букв, разделенных пробелами. Первая буква каждой строки – значение признака 1 и так далее. Вторая строка во входном файле описывает корову с номером 1, третья строка – корову с номером 2 и т.д.
Пример входного файла признаков:
4 2
X Z
X Y
Y X
Y Y
Интерактивность: стандартный ввод и стандартный вывод
Шаг “вопрос/ответ” осуществляется через стандартный ввод и стандартный вывод.
Ваша программа задает вопрос о корове посредством записи в стандартный вывод строки следующего вида: буква ‘Q’, номер признака, значения признака (одно или более), разделенные пробелами. Например, строка “Q 1 Z Y” соответствует вопросу: “Имеет ли первый признак коровы значение ‘Z’ или ‘Y’?”. Признак может быть целым числом в пределах от 1 до P. Значения признака должны быть только ‘X’, ‘Y’ или ‘Z’ и не должны повторяться в одной строке.
После задания вопроса ваша программа должна читать одну строку, содержащую одно из целых чисел — 0 или 1. Число 1 обозначает, что корова обладает одним из указанных значений признака. Число 0 означает, что ни одним из указанных значений признака корова не обладает.
Последняя строка вывода программы должна содержать букву ‘C’, пробел и одно число (номер коровы).
Пример диалога: (для вышеуказанного примера)
Ввод
Вывод
Комментарий
Q 1 X Z
0
Может быть корова 3 или корова 4
Q 2 Y
1
Должна быть корова 4!
C 4
Завершение работы программы
СИСТЕМА ОЦЕНКИ
Корректность: 30% от баллов
Программа, которая выводит правильный номер коровы, получит полный балл за корректность, если существует единственная корова, соответствующая полученным ответам. Программа, которая задает больше 100 вопросов, баллов за тест не получит.
Зависимость от количества вопросов: 70% от баллов
Оставшиеся баллы будут определены в зависимости от количества вопросов, заданных для корректного определения коровы. Система оценки устроена так, чтобы оценить минимальное количество вопросов, которые задает ваша программа в худшем случае. Близкие к оптимальному решения получат частичные баллы. Интервью про производство межкомнатных дверей, производство межкомнатных дверей. . Великолепная водосточные системы только на заказ. . У нас можно заказать диссертацию на любую тему . Разнообразные бассейны г москва для любителей активного образа жизни