Числа Смита (Smith)  (юниоры)

Понятие числа Смита было введено Альбертом Вилански из Университета Лехай в 1982 году. Просматривая свою телефонную книжку, математик обратил внимание на то, что телефонный номер его зятя Гарольда Смита (493-7775) обладал тем интересным свойством, что сумма его цифр равнялась сумме цифр всех его простых сомножителей.  Число 4937775 раскладывается на простые сомножители следующим образом: 4937775=3×5×5×65837. Сумма цифр телефонного номера равна 4+9+3+7+7+7+5=42 и сумма цифр его разложения на простые множители также равна 3+5+5+6+5+8+3+7=42. Вилански назвал такой тип чисел по имени своего зятя. Так как этим свойством обладают все простые числа, Вилански не включил их в определение. Помогите Альберту найти еще числа Смита. Для каждого числа из заданного набора найдите минимальное превышающее его число Смита.

Формат ввода-вывода:  Программа Smith читает с клавиатуры (стандартного устройства ввода) натуральное число N (1≤N≤10) – количество чисел в наборе, а также N натуральных чисел a_i (1≤ a_i <2³¹). Программа Smith выводит на экран (стандартное устройство вывода) N найденных чисел через пробел.

Пример входных и выходных данных

Ввод                                      Вывод

2 4937774 234                  4937775 265

Обнуление массива (Zeroing) (юниоры+старшая лига)

Имеется массив, состоящий из N чисел. За один шаг разрешается уменьшить на 1 несколько (возможно один) подряд идущих равных элементов. Цель – сделать все элементы равными нулю. За какое минимальное количество шагов это может быть сделано?

Формат ввода-вывода:

Программа Zeroing читает с клавиатуры (стандартного устройства ввода) натуральное число N (1≤N≤2∙10⁵) – количество чисел в массиве, а со следующей строки N неотрицательных целых чисел, элементов массива, каждое из которых не превышает 2∙10⁹. Программа Zeroing выводит на экран (стандартное устройства вывода) единственное число – искомое количество шагов.

Пример входных и выходных данных

Ввод 1                      Вывод 1

3                                 4

3 4 1

Ввод 2                      Вывод 2

3                                 6

3 1 4          

Кооперация (Coop) (юниоры+старшая лига)

Гномы-великаны знамениты своими гигантскими размерами и любовью к золоту. В одном из поселений гномов живут целых N пар гномов, причём в i-й (1 ≤ i ≤ N) паре рост как мужа-гнома, так и жены-гнома равен i. Кроме того, крепкие мужчины-гномы обычно выступают в качестве опоры, в то время как хрупкие женщины-гномы ловко орудуют киркой.

Геологическая разведка обнаружила недалеко от поселения гномов вертикальную бесконечно высокую скалу. Гномы решили, что там с большой вероятностью будет золото, так что договорились утром отправиться на охоту за ним. Правда, дойдя до скалы, гномы обнаружили проблему: K семей не явились на встречу.

Гномы собираются долбить скалу таким образом: пусть некоторый мужчина-гном ростом A выступает опорой для некоторой женщины-гнома роста B. Вместе этот тандем способен долбить скалу только на высоте A + B. Для каждой высоты выбирается подходящий тандем, причём любой присутствующий гном может выступать (в разные моменты времени) в составе разных тандемов. Теперь гномов интересует, сколько же существует достижимых высот. Иными словами, для скольких высот найдётся подходящий тандем?

Формат ввода-вывода Программа Coop сначала считывает с клавиатуры (стандартного устройства ввода) два целых числа N (1 ≤ N ≤ 2·10⁹) и  K (1 ≤ K ≤ min{N, 10000}) – количество пар гномов в поселении и количество отсутствующих на добыче семей гномов. Затем со следующей строки считывается ровно K разных неотрицательных целых чисел – номера семей в произвольном порядке, не пришедших на добычу. Каждое число не превышает N. Программа Coop выводит на экран (стандартное устройство вывода) единственное целое число – количество достижимых высот.

Система оценки

30% баллов приходится на тесты, в которых N, K ≤ min{N, 1000}.

Ещё 40% баллов приходится на тесты, в которых N ≤ 10⁹, K ≤ min{N, 500}.

Пример входных и выходных данных

Ввод 1                      Вывод 1

6 2              9

3 6

Ввод 2                     Вывод 2

5 3              3

2 3 4

Ввод 3                     Вывод 3

10 4            15

2 3 4 5

Многоугольники (Numconv) (юниоры+старшая лига)

Задана клетчатая сетка. Сколько разных выпуклых многоугольников может быть на ней нарисовано, если все вершины должны лежать в узлах сетки, а стороны быть или горизонтальными, или вертикальными, или диагональными (под углом 45 градусов)?

Шириной сетки назовем количество узлов в каждом ее ряду, а высотой – количество узлов в каждом ее столбике. Многоугольники, которые надо найти, должны иметь такие свойства:

- их вершины должны лежать в узлах решетки;

- все стороны горизонтальные, вертикальные или диагональные (45 градусов);

- многоугольник выпуклый.

Два многоугольника считаются разными, если их стороны не совпадают, т.е. два одинаковых по форме многоугольника, которые находятся в разных позициях, надо считать за два. Однако добавление вершины в середину ребра не изменяет его формы и не создает новый (для подсчета) многоугольник.За заданными шириною и высотой поля найдите количество многоугольников.

Формат ввода-вывода: Программа Numconv читает с клавиатуры (стандартного устройства ввода) два натуральных числа a та b (2≤a,b≤100) – ширину и высоту сетки.Программа Numconv выводит на экран (стандартное устройство вывода) единственное число – количество возможных многоугольников.

Пример входных и выходных данных

Ввод 1                      Вывод 1

3 2                              19

Ввод 2                      Вывод 2

2 2                              5

Викторина (Quiz) (старшая лига)

Гномы-великаны решили принять участие в чемпионате игры «Что? Где? Когда?». Чемпионат состоит из t туров. Каждый тур содержит некоторое количество вопросов. Серия вопросов – это подпоследовательность вопросов одного тура от l-го по r-й включительно, причём l ≤ r и подпоследовательность непрерывна (берутся во внимание все подряд вопросы от l-го по r-й). Гномы будут считать серию вопросов удачной, если они дадут ответы не менее, чем на q процентов вопросов из этой серии. Для поднятия настроения команды, найдите для каждого тура количество удачных серий.

Формат ввода-вывода:

Программа Quiz читает с клавиатуры (стандартного устройства ввода) число t – количество туров в чемпионате, 1 ≤ t ≤ 10. В следующих t строках находится информация о каждом из туров в следующем виде: n q a₁...a_n, 0 ≤ q ≤ 100. a_i =  может быть 0, если команда не ответила на i-й вопрос, или же 1 в ином случае. Кроме того, всего на чемпионате было задано не более, чем 500000 вопросов. Все числа входных данных целые.

Программа Quiz выводит на экран (стандартное устройство вывода) ровно t чисел в одну строку через пробелы: i-е число равно количеству удачных серий вопросов i-го тура.

Система оценки

70% баллов приходится на тесты, в которых q_i = 50.

Пример входных и выходных данных

Ввод                                      Вывод

2                                             32 4

10 50 1 0 1 0 1 1 0 0 0 1

5 50 1 0 0 0 1