Всеукраинская олимпиада по информатике
Всеукраинская олимпиада по информатике
Первый тур
Забавный конфуз
Пусть А - массив, состоящий из N элементов A1,...,AN. Обозначим его максимальное и минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S=A1+A2+…+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1ЈiЈN. Такое преобразование массива A назовем операцией Confuse.
Задание
Напишите программу CONFUSE, которая по массиву B, полученному в результате K-кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).
Входные данные
Первая строка входного файла CONFUSE.DAT содержит целые числа N и K, где N - количество элементов массива B (2Ј NЈ10000), а K - количество применений операции Confuse к начальному массиву A, 1 ЈKЈ100. Вторая строка файла содержит N элементов массива B. Элементы массива B - целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.
Выходные данные
Единственная строка выходного файла CONFUSE.SOL должна содержать целое число, которое есть разностью max(A) и min(A).
Пример входных и выходных данных
| CONFUSE.DAT | CONFUSE.SOL |
| 4 2 45 52 47 46 |
7 |
Соревнование
В спортивном турнире принимает участие N человек, с номерами от 1 до N. Турнир проходит по круговой системе: каждый участник должен сыграть с каждым другим участником по одной партии, которая заканчивается победой одного из игроков. Считается, что по окончании турнира участник занимает место P, если:
- у него выиграли (P-1) участников, и ему проиграли все остальные;
- все участники, которые победили его, выиграли свои партии у всех участников, которые ему проиграли.
Для остальных участников итоговое место определить нельзя.
Задание
Напишите программу CONTEST, которая получает на вход число N и результаты сыгранных на данный момент партий турнира, и определяет количество участников, для которых по окончании турнира нельзя будет определить итоговое место, в независимости от результатов тех партий, которые еще будут сыграны.
Входные данные
В первой строке CONTEST.DAT задаются два натуральных числа: N - количество участников турнира (1ЈNЈ100) и M - количество сыгранных партий. Следующие M строк описывают сыгранные партии. В строке задается два числа: номер победителя и номер проигравшего.
Выходные данные
В единственной строке выходного файла CONTEST.SOL должно быть целое число - искомое количество участников.
Пример входных и выходных данных
| CONTEST.DAT | CONTEST.SOL |
| 6 8 1 5 1 4 5 2 5 6 3 2 2 6 6 4 4 3 |
4 |
Абракадабра
Во время своей работы алгоритм сжатия данных методом «сортировки блока» применяет к блокам данных преобразование, которое определяется следующим образом.
| a | a | b | r | a | k |
|---|---|---|---|---|---|
| a | b | r | a | k | a |
| a | k | a | a | b | r |
| b | r | a | k | a | a |
| k | a | a | b | r | a |
| r | a | k | a | a | b |
Строка P называется ротацией строки S, если она образована циклическим сдвигом символов S, т.е. если S=a1,a2...aN, где ai- i-ый символ строки S, то P= apap+1…aNa1…ap-1, где 1Ј p ЈN. Рассмотрим таблицу M размера NґN, строками которой есть все ротации строки S, отсортированные в лексикографическом (словарном) порядке по возрастанию.
Пусть строка L есть последний столбик таблицы M. Прямое преобразование получает на вход строку S, выдает строку L и число K - номер строки таблицы M, который содержит строку S. (Если таких строк несколько, выдается номер любой из них).
Для S='abraka' таблица M изображена на рисунке. Строка S находится во второй строке таблицы M, L='karaab'.
Задание
Напишите программу ABRAKA, которая выполняет обратное преобразование, т.е. получает на вход строку L и число K, и выдает строку S.
Входные данные
Первая строка входного файла ABRAKA.DAT содержит два целых числа: K и N, 1 ЈNЈ30000, 1ЈKЈN. Вторая строка содержит N символов строки L - маленьких латинских букв.
Выходные данные
Единственная строка выходного файла ABRAKA.SOL должна содержать строку S.
Пример входных и выходных данных
| ABRAKA.DAT | ABRAKA.SOL |
| 2 6 karaab |
abraka |
Циферблат
На циферблате записана последовательность чисел в двоичной системе счисления. Линии разбиения могут проходить как между числами, так и между цифрами одного числа, разбивая его на два или больше чисел. Для каждого сектора можно посчитать сумму чисел, которые в нем расположены.
Каждое число в последовательности не равно 0, и его запись начинается с единицы. Количество цифр в двоичной записи числа не превышает 25. Общее количество цифр на циферблате не больше чем 100.
Циферблат может быть разбит на сектора. На рисунке изображен привычный нам циферблат с числами от 1 до 12 (в немного непривычном виде). Он разбит на 4 сектора. Суммы в секторах будут 1, 15, 18 и 36.
Задание
Напишите программу DIAL, которая по заданной последовательности определяет количество разных разбиений циферблата на сектора, таких что сумма чисел во всех секторах одинакова.
Входные данные
В единственной строке входного файла DIAL.DAT задана последовательность чисел. Числа последовательности разделены пробелом.
Выходные данные
В единственной строке выходного файла DIAL.SOL должно находиться натуральное число - количество искомых разбиений циферблата на сектора.
Пример входных и выходных данных
| DIAL.DAT | DIAL.SOL |
| 101 1 1101 | 9 |
|
© Всеукраинский виртуальный центр олимпиад школьников "ОЛІМП"