|
Чётность
(Время: 3 сек. Память: 64 Мб Сложность: 70%)
Вы играете со своим другом в следующую игру. Ваш друг записывает последовательность, состоящую из нулей и единиц. Вы выбираете непрерывную подпоследовательность (например, подпоследовательность от третьей до пятой цифры включительно) и спрашиваете его, чётное или нечётное количество единиц содержит эта подпоследовательность. Ваш друг отвечает, после чего вы можете спросить про другую подпоследовательность, и так далее.
Ваша задача – угадать всю последовательность чисел. Но вы подозреваете, что некоторые из ответов вашего друга могут быть неверными, и хотите уличить его в обмане. Вы решили написать программу, которая получит наборы ваших вопросов вместе с ответами друга и найдет первый ответ, который гарантированно неверен. Это должен быть такой ответ, что существует последовательность, удовлетворяющая ответам на предыдущие вопросы, но никакая последовательность не удовлетворяет этому ответу.
Входные данные
Входной файл INPUT.TXT содержит несколько тестов. Первая строка каждого теста содержит одно число N, равное длине последовательности нулей и единиц, 1 ≤ N ≤ 109. Во второй строке теста находится одно неотрицательное целое число M – количество заданных вопросов и ответов на них, M ≤ 5000. Суммарное количество вопросов по всем тестам не превышает 5×105. Остальные M строк теста содержат вопросы и ответы. Каждая строка содержит один вопрос и ответ на этот вопрос: два целых числа (позиции первой и последней цифр выбранной подпоследовательности) и одно слово – “even” или “odd” – ответ, сообщающий чётность количества единиц в выбранной подпоследовательности, где “even” означает чётное количество единиц, а “odd” означает нечётное количество. Ввод заканчивается строкой, содержащей −1.
Выходные данные
Каждая строка выходного файла OUTPUT.TXT должна содержать одно целое число X. Число X показывает, что существует последовательность нулей и единиц, удовлетворяющая первым X условиям чётности, но не существует последовательности, удовлетворяющей X + 1 условию. Если существует последовательность нулей и единиц, удовлетворяющая всем заданным условиям, то число X должно быть равно количеству всех заданных вопросов.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
-1 | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
