#1660

Суперчисла

Темы: [Простые числа и разложение на множители]

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

Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…\(B\)]. Требуется найти все суперчисла из заданного диапазона [\(A\)…\(B\)].

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

Во входном файле даны два числа \(A\) и \(B\) (2 ≤ \(A\) ≤ \(B\) ≤ 40000), определяющие диапазон [\(A\)…\(B\)].

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

В выходной файл вывести все найденные суперчисла из заданного диапазона в возрастающем порядке.

Примеры

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

3 10

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

#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\) чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры

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

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