#1661

Суперстрока

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача B ]

Суперстрока состоит из символов латинского алфавита. Гласными считаются буквы: a,e,i,o,u,y,A,E,I,O,U,Y. Требуется посчитать количество способов разбиения заданной суперстроки на слова. Словом считается последовательность букв, содержащая хотя бы одну гласную букву. Ограничения. Длина строки не превышает 200 символов. Количество разбиений не превышает 2.000.000.000. Размер входного файла не превышает 3,5 Мбайт.

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

В первой строке дано число N (1 ≤ N ≤ 50000). Далее записаны N суперстрок.

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

N чисел – количество возможных вариантов разбиения соответствующей суперстроки.

Примеры

Входные данные

5
aa
bbb
aba
bb
aba

Выходные данные

#1662

Суперквадрат

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача C ]

Суперквадратом порядка N называется таблица размером N*N , каждая строка и каждый столбец ко-торой содержат все числа от 1 до N. Дан суперквадрат порядка N. Требуется найти все суперквадраты, содержащиеся в данном, порядок которых отличен от 1 и от N.

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

Первая строка содержит число N (1 ≤ N ≤ 250). Далее следует N строк, содержащих по N чисел.

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

В первую строку вывести число K – количество найденных суперквадратов. Далее следует K строк, описывающих эти суперквадраты в произвольном порядке. Каждая строка содержит 3 числа, разде-ленные пробелами: координаты левого верхнего угла суперквадрата в порядке “строка, столбец” и по-рядок данного суперквадрата.

Примеры

Входные данные

Выходные данные

3

1 2 3

2 3 1

3 1 2

0

8

5 6 7 8 1 2 3 4

6 7 8 5 2 1 4 3

7 8 5 6 3 4 2 1

8 5 6 7 4 3 1 2

1 4 2 3 5 6 7 8

2 1 3 4 6 7 8 5

3 2 4 1 7 8 5 6

4 3 1 2 8 5 6 7

4

1 5 2

1 5 4

3 7 2

5 1 4

#1663

Суперминимум

Темы: [Дерево отрезков, RSQ, RMQ] [Дек]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача D ]

Дано N чисел. Для каждых K подряд идущих чисел найти минимальное среди них.

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

В первой строке даны числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N), разделенные пробелом. Во второй строке записано N целых чисел через пробел. Числа находятся в диапазоне от -32768 до 32767.

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

Для каждых К подряд идущих чисел вывести минимальное из них.

Пример

Входные данные

Выходные данные

11 3

8 764 1 3 85 2 4 5 77 1 5

1 1 1 2 2 2 4 1 1

#1664

Суперсумма

Темы: [Бинарный поиск в массиве]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача E ]

Дано \(N\) натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

Входные данные

В первой строке дано число \(N\) ( 1 ≤ \(N\) ≤ 10000). Далее заданы \(N\) натуральных чисел, не превосходящих \(10^9\). Для каждого числа количество разбиений меньше 2³¹.

Выходные данные

Вывести \(N\) чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры

Входные данные

Выходные данные

#1665

Суперкалькулятор

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача F ]

Суперкалькулятор выполняет только одну арифметическую операцию – умножение натуральных чисел. Верхняя граница диапазона представления натуральных чисел в калькуляторе неизвестна. Обозначим эту границу \(P\). Если результат умножения превосходит или равен \(P\) (\(a\)*\(b\) ≤ \(P\) , \(a\), \(b\) - множители), то возможны две ситуации:

1) Ответ равен (\(a\)*\(b\)) mod \(P\) .
2) Ответ – случайное число из диапазона допустимых значений (произошел сбой в работе калькулятора).
Даны значения множителей (a, b) и результат (c). Требуется написать программу анализа работы калькулятора, результатом которой является одно число, формируемое по следующему принципу:
1) 0, если c = a*b ;
2) 1, если произошел сбой;
3) минимальное значение \(P\).

Входные данные

Строка содержит числа \(a\), \(b\) и \(c\) разделенные пробелами, \(a\) и \(b\) – множители, \(c\) – результат.

Выходные данные

Вывести одно число.

Примеры

Входные данные

1 1 1

Выходные данные

Входные данные

2 2 2

Выходные данные

Входные данные

2 8 6

Выходные данные

Входные данные

11 11 21

Выходные данные