Фильтр
Выбрано 3 задачи Убрать все задачи
У Буратино и Пьеро был велосипед, на котором они отправились в соседнюю деревню. Ехали по очереди, но всякий раз, когда один ехал, другой шёл пешком, а не бежал. При этом они ухитрились прибыть в деревню почти в 2 раза быстрее, чем если бы оба шли пешком. Как им это удалось?
РешениеМаксимальное время работы на одном тесте: 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 |
РешениеВ строчку выписано 10 целых чисел. Вторая строчка находится так: под каждым числом A первой строчки пишется число, равное количеству чисел первой строчки, которые больше A и при этом стоят правее A. По второй строчке аналогично строится третья строчка и т. д.
а) Докажите, что все строчки, начиная с некоторой –
нулевые (состоят из сплошных нулей).
б) Каково максимально возможное число ненулевых строчек (содержащих хотя бы одно число, отличное от нуля)?
Решение
Задачи
Задача 108251 (#М1421) |
|
|
В выпуклый четырёхугольник ABCD, у которого углы при вершинах B и D – прямые, вписан четырёхугольник с периметром P (его вершины лежат по одной на сторонах четырёхугольника ABCD).
а) Докажите неравенство P ≥ 2BD.
б) В каких случаях это неравенство превращается в равенство?
|
|
Решение |
Задача 98188 (#М1423) |
|
|
Три шахматиста A, B и C сыграли матч-турнир (каждый с каждым сыграл одинаковое число партий). Может ли случиться, что по числу очков A занял первое место, C – последнее, а по числу побед, наоборот, A занял последнее место, C – первое (за победу присуждается одно очко, за ничью – пол-очка)?
|
|
|
Решение |
Задача 98189 (#М1424) |
|
|
В строчку выписано 10 целых чисел. Вторая строчка находится так: под каждым числом A первой строчки пишется число, равное количеству чисел первой строчки, которые больше A и при этом стоят правее A. По второй строчке аналогично строится третья строчка и т. д.
а) Докажите, что все строчки, начиная с некоторой –
нулевые (состоят из сплошных нулей).
б) Каково максимально возможное число ненулевых строчек (содержащих хотя бы одно число, отличное от нуля)?
|
|
|
Решение |
Задача 108596 (#М1425) |
|
|
Дан невыпуклый несамопересекающийся четырёхугольник, который имеет три внутренних угла по 45°.
Докажите, что середины его сторон лежат в вершинах квадрата.
|
|
|
Решение |
Задача 98193 (#М1426) |
|
|
Через S(n) обозначим сумму цифр числа n (в десятичной записи).
Существуют ли три таких различных натуральных числа m, n и p, что m + S(m) = n+S(n) = p + S(p)?
|
|
|
Решение |
Страница: 1 2 3 >> [Всего задач: 15]
