ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98693
Тема:    [ Циклы (прочее) ]
Сложность: 2
Классы: 8,9,10,11
Название задачи: Билетики.
В корзину
Прислать комментарий

Условие

Максимальное время работы на одном тесте: 1 секунда

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

Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N ³ K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки - считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 - на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.

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

Формат входных данных

В первой строке входного файла d.in записаны числа N и K (1 £ N £ 50000, 1 £ K £ 1000, K £ N). Во второй строке записано N чисел, каждое из которых является 0 или 1 - информация, считанная с билета.

Формат выходных данных

В первой строке выходного файла d.out должно быть записано одно из двух сообщений - OK или FAIL (первое сообщение обозначает, что билет признан подлинным, второе - поддельным). В случае, если билет подлинный, во второй строке выведите 0, если все числа были считаны правильно, или номер числа, в котором при считывании произошла ошибка. Если возможных ответов несколько, выведите любой из них (в частности, если для признания билета подлинным можно считать, что ошибок при считывании не было, а можно считать, что была ошибка в одном из чисел - правильным является любой из вариантов ответа).

Примеры

d.in

d.out

6 2

1 0 1 0 1 0

OK

0

6 2

1 1 1 0 1 0

OK

2

6 2

1 1 1 0 0 0

FAIL


Также доступны документы в формате DOC

Решение

Тесты и проверяющая программа

Пусть дана последовательность чисел A1, :, AN, состоящая из 0 и 1. Пару чисел (Ai, Aj), таких что i < j, j - i = K и Ai ¹ Aj, назовем неправильной. Индексом неправильности последовательности (ИНП) назовем количество неправильных пар (Ai, Aj) в ней. ИНП легко посчитать за один проход по массиву, в котором хранятся элементы последовательности: переберем все i от 1 до N - K и сравним их с соответствующими j = i + K.

Если ИНП равен 0, то ответ в задаче OK и никаких чисел менять в ней не нужно. Иначе для каждого из элементов последовательности найдем ИНП после изменения этого элемента. При изменении одного числа в последовательности нулей и единиц может измениться только правильность пар (Ai-K, Aj) и (Ai, Ai+K), если они, конечно, существуют. Дело в том, что i - K может быть меньше 1, или i + K - больше N. В этих случаях соответствующая пара отсутствует. Значит в результате изменения одного числа, ИНП может измениться на -2, -1, 0, +1 или +2. Если в результате изменения какого-то из чисел ИНП станет равным 0 - то ответ OK и номер измененного элемента, иначе - ответ FAIL. Данный алгоритм работает за линейное относительно длины последовательности время.


Также доступны документы в формате DOC

Источники и прецеденты использования

олимпиада
Название Московская городская олимпиада по информатике
год
Название 2005 год
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .