Contest.samsu.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача A. Игроки

Задачу добавил: alef

Успешно сдано решений: 33

Петя увидел объявление о том, что одна фирма, занимающаяся разработкой сайтов, приглашает на лето студента или старшеклассника поработать стажером. Предлагаемые условия ему понравились, он написал по указанному в объявлении адресу и его пригласили на собеседование.

            На собеседовании с ним сначала поговорили об учебе и его планах на будущее, потом предложили пройти небольшой тест. Некоторые вопросы требовали достаточно развернутого ответа, и Пете было ясно, что проверка теста не может быть выполнена автоматически. Закончив отвечать на вопросы теста, он поинтересовался, когда можно будет узнать результат.

            Сотрудник, проводивший собеседование, ответил, что на обработку ответов потребуется несколько дней. И добавил:

— Кроме Вас, у нас есть еще два претендента на эту вакансию. Они уже ответили на вопросы теста. И знаете, наш начальник немного необычно сравнивает соискателей. Он устраивает «игру на выбывание». Выглядит она так. Представьте себе, что все соискатели (все трое в нашем случае) одновременно получают одни и те же вопросы теста и отвечают на них. За каждый правильный ответ соискателю начисляется 1 балл. Но как только он ошибется, он выбывает из игры. Игра продолжается до тех пор, пока в ней участвует хотя бы один игрок — до тех пор, пока он не ошибется или пока не закончатся вопросы. Впрочем, и тот, кто выбыл из игры последним, необязательно будет принят на работу. Это произойдет лишь в том случае, если набранное им количество баллов, по мнению начальника, будет достаточно заметно отличаться от суммы, набранной лучшим из выбывших.

— А «достаточно заметно» — это сколько? — спросил Петя. Он пытался вспомнить номер первого из вопросов, в ответе на которые он не был уверен.

— Сложно сказать. Каждый раз по-разному, — вздохнул сотрудник. Однако спустя долю секунды он заговорчищески подмигнул Пете — Но Вы можете написать программу, которая по известным результатам тестирования всех трех соискателей сформирует такую последовательность номеров вопросов, при которой разрыв между Вами и более успешным игроком из двух других будет наилучшим из возможных.

            Петя несколько смутился. Сотрудник улыбнулся:

— Это третья часть собеседования. Тестовое задание. Конечно, Ваши ответы на вопросы теста будут проверены и учтены полностью. А наш начальник, определяясь с выбором, будет изучать код Вашей программы.

            Ваша задача — написать такую программу. Заметим, что возможна ситуация, при которой Петя в принципе не сможет стать самым лучшим из трех соискателей.

 

Формат входного файла input.txt

Первая строка — целое число N (1 <= N <= 10) — количество вопросов теста

Вторая строка — последовательность из N нулей и единиц — результаты ответов на вопросы (в порядке с 1-го по N-ый) первого соискателя — Пети.  Ноль означает неверный ответ, единица — верный.

Третья строка — последовательность из N нулей и единиц — результаты ответов на вопросы (в порядке с 1-го по N-ый) второго соискателя.

Четвертая строка — последовательность из N нулей и единиц — результаты ответов на вопросы (в порядке с 1-го по N-ый) третьего соискателя.

 

Формат выходного файла output.txt

Первая строка — целое число M — наилучший возможный отрыв, который может обеспечить себе Петя. Наилучший возможный отрыв вычисляется как разница между баллами, набранными Петей, и баллами, набранными лучшим из двух других игроков.

Вторая строка — N целых чисел через пробел — последовательность номеров вопросов, которая обеспечит Пете наилучший возможный отрыв. Если существует несколько вариантов, выведите любой.

 

Пример входного файла — 1

4

0111

0011

0001

 

Пример выходного файла — 1

3

2 4 3 1

 

 

Пример входного файла — 2

6

101111

111111

010101

 

Пример выходного файла — 2

-1

4 6 1 3 5 2

 

Пример входного файла — 3

5

11100

01111

11110

 

Пример выходного файла — 3

0

1 5 2 3 4

 

 


Сдать задачу

Задать вопрос жюри по этой задаче