Задачи Южно-Уральского командного чемпионата 2012

Антиарифметическая последовательность формируется следующим образом:

`S_k` для всех `k>1` вычисляется как наименьшее целое число, такое что `S_k\ >\ S_{k-1}` и среди элементов последовательности с номерами от 0 до `k` нет трех последовательных членов арифметической прогрессии, т.е. не существует `i,\ j` таких, что `0\ ≤\ i\ <\ j\ <\ k` и `S_k\ -\ S_j\ =\ S_j\ -\ S_i`.

Напишите программу, которая для заданного элемента последовательности `S_1=N` находит элементы антиарифметической последовательности с номерами от `A` до `B`.

Ввод содержит три целых числа `N` (`1\ ≤\ N\ ≤\ 1000`), `A` и `B` (`1\ ≤\ A\ <\ B\ ≤\ 3000`, `B-A\ <\ 100`).

В первой строке вывести элементы антиарифметической последовательности с номерами от `A` до `B`, разделяя их пробелами. Гарантируется, что величина элементов последовательности при заданных ограничениях не будет превышать `10^6`.

2 1 10

2 3 5 9 11 12 14 27 29 30

На игровом поле находится несколько пузырьков одинакового радиуса, которые, когда взрывная волна достигает их поверхности, приходят в неустойчивое состояние и взрываются через секунду. Взрыв пузырька может привести к цепной реакции взрыва других пузырьков, которые находятся на расстоянии действия взрывной волны от взорвавшегося пузырька.

Цель игры – выбрать целые координаты начального взрыва, чтобы взорвать прямо или в результате цепочки взрывов максимальное количество пузырьков.

Напишите программу, которая определяет координаты центра начального взрыва, позволяющего взорвать максимальное количество пузырьков.

Первая строка ввода содержит четыре целых числа: количество пузырьков `N` (`1\ ≤\ N\ ≤\ 1000`), радиус пузырьков `A`, радиус взрыва пузырьков `B` и радиус начального взрыва `C` (`1\ ≤\ A\ <\ B\ <\ C\ ≤\ 1000`). Далее следует `N` строк, содержащих координаты центров пузырьков `X_i` и `Y_i` (`0\ ≤\ X_i,\ Y_i\ ≤\ 1000`).

В первой строке вывести максимальное количество взорвавшихся пузырьков. Во второй строке вывести два целых числа – координаты центра начального взрыва `X` и `Y` через пробел. Если существует несколько вариантов решения для позиции начального взрыва, то можно вывести любой из них.

7 1 2 3
2 1
2 7
2 10
5 4
11 2
10 7
12 8

5
6 7

These days, it has become commonplace to make purchases over the internet using a credit card. However, because credit card numbers are relatively long, it is easy to make a mistake while typing them in. In order to quickly identify errors like typos, most e-commerce websites use a checksum algorithm to verify credit card numbers.

One popular checksum algorithm is the Luhn algorithm, which can detect any single-digit error as well as many common multiple-digit errors:

Starting with the second-last digit and moving backwards, double every other digit to obtain a list of numbers. Add up the digits of these numbers, then add the undoubled digits from the original number. Sum the two results. If the total ends in a 0, the credit card number is valid, and it is invalid otherwise.

For example, using the number `5181271099000012`:

Double the appropriate digits to obtain the values: `10,\ 16,\ 4,\ 2,\ 18,\ 0,\ 0,\ 2`. Add up the digits of these values to get `(1+0)\ +\ (1+6)\ +\ 4\ +\ 2\ +\ (1+8)\ +\ 0\ +\ 0\ +\ 2\ =\ 25`. The sum of the undoubled digits is `1+1+7+0+9+0+0+2\ =\ 20`, so the total is `20+25=45`. 45 does not end in a 0, so this credit card number is invalid.

For this problem, you must write a program that checks the validity of credit card numbers according to the Luhn algorithm.

The input begins with a number `N` (`1\ ≤\ N\ ≤\ 100`) on a single line, followed by `N` lines each containing a single credit card number. Each credit card number consists of 16 decimal digits.

The output consists of one line for each input credit card number. If the credit card number is valid, this line consists of the string "Valid", otherwise it reads "Invalid".

2
5181271099000012
5181271099000017

Invalid
Valid

Два натуральных числа `a` и `b` называются взаимно простыми, если они не имеют никаких общих делителей, кроме 1.

Напишите программу, вычисляющую вероятность того, что два случайных натуральных числа (с дискретным равномерным распределением в диапазоне от 1 до `N`) будут взаимно простыми.

Ввод содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^6`).

В первой строке вывести вероятность с точностью `10^{-12}`, что два натуральных числа, случайно выбранных из диапазона от 1 до `N`, будут взаимно простыми.

10

0.630000000000

Стартовав с числа 1, нужно получить некоторое заданное число `N`. На каждом шаге можно добавлять к текущему числу один из его делителей, чтобы получить новое число. Например, для первого шага у нас только один вариант: добавить 1 к 1 и получить 2. На втором шаге можно выбрать один из двух делителей и получить число 2+1=3 или 2+2=4. От числа 4 на третьем шаге можно перейти к числам 5, 6 или 8 в зависимости от выбранного делителя.

Напишите программу, определяющую минимальное количество шагов для получения заданного числа `N`.

Ввод содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^5`).

Вывести одно целое число – минимальное количество шагов.

6

3

Напишите программу, определяющую количество различных прямоугольников с заданной площадью `S`, вершины которых имеют целые координаты. Прямоугольники считаются различными, если их нельзя совместить с помощью переноса и/или поворота. На рисунке показаны 5 различных прямоугольников, имеющих площадь 10.

Ввод содержит одно целое число `S` (`1\ ≤\ S\ ≤\ 10^9`).

Вывести одно целое число – количество различных прямоугольников.

10

5

Двое играют в следующую игру. Начиная с числа 0, игроки по очереди добавляют значение из некоторого набора возможных слагаемых-ходов к текущей сумме. Выигрывает тот, кому удастся первым получить сумму, кратную числу `N`.

Напишите программу, определяющую победителя по набору ходов и числу `N` при безошибочной игре игроков.

Первая строка ввода содержит два целых числа: `N` (`2\ ≤\ N\ ≤\ 100`) и `K` (`2\ ≤\ K\ ≤\ 10`). Вторая строка содержит `K` различных целых чисел в диапазоне от 1 до 100 – возможные ходы-слагаемые.

Вывести число 1, если выигрывает игрок, делающий первый ход, или число 2, если выигрывает игрок, делающий второй ход, или число 0, если ни один из игроков не может выиграть.

100 2
4 7

1

В королевство Ксант добрался технический прогресс, и король решил построить сеть двухсторонних автомобильных и железных дорог, связывающую все города страны. На случай забастовок водителей автобусов или машинистов паровозов король решил, что между любыми городами страны можно будет проехать, двигаясь только по автомобильным дорогам или только по железным дорогам. Кроме того, железная дорога не должна дублировать автомобильную и наоборот, т.е. если из города `i` в город `j` ведет автомобильная дорога, то между этими городами не должно быть железной дороги, и наоборот. Король хочет минимизировать расходы на строительство сети дорог. Стоимости строительства километра автомобильной и железной дороги равны. Дороги могут начинаться и заканчиваться только в городах, дороги вне городов волшебным образом проходят друг над другом без пересечения.

Напишите программу, которая определяет между какими городами какой вид дороги должен быть построен, чтобы суммарная стоимость строительства сети дорог была минимальной.

Первая строка ввода содержит одно целое число `N` (`4\ ≤\ N\ ≤\ 1000`) – количество городов в стране. Далее следует `N` строк содержащих по два целых числа `X_i` и `Y_i` (`0\ ≤\ X_i,\ Y_i\ ≤\ 1000`) – координаты городов. Никакие три города в стране не расположены на одной прямой.

Вывести `(N-1)` строку, содержащих по два числа – номера городов, соединяемых автомобильной дорогой. Затем вывести `(N-1)` строку, содержащих по два числа – номера городов, соединяемых железной дорогой.

4
0 0
100 100
0 100
100 0

1 2
2 3
3 4
1 3
1 4
2 4

Ферзь – самая сильная шахматная фигура. Ферзь может перемещаться на любое число полей по вертикали, горизонтали и диагонали (при условии, что на его пути нет фигур). На рисунке белыми точками отмечены клетки, который ферзь может достичь за один ход:

Дана позиция ферзя на пустой бесконечной доске, необходимо определить минимальное количество ходов, необходимое ферзю для достижения новой позиции на доске.

Ввод содержит четыре целых числа `X_1`, `Y_1`, `X_2` и `Y_2` (`-10^9\ <\ X_1,\ Y_1,\ X_2,\ Y_2\ <\ 10^9`). Ферзь находится на клетке `(X_1,\ Y_1)` и должен добраться до клетки `(X_2,\ Y_2)`. Колонки на доске нумеруются слева направо, а строки – снизу вверх. Клетка в колонке `X` и строке `Y` имеет координаты `(X,\ Y)`.

Ваша программа должна вывести одно целое число – минимальное количество ходов ферзем от начальной позиции на доске до конечной.

1 2 4 2

1

5 5 4 3

2

0 0 0 0

0

Напишите программу, определяющую количество различных натуральных чисел, которые можно составить из заданного набора цифр.

Первая строка ввода от 1 до 50 десятичных цифр без пробелов.

Вывести остаток от деления на `10^9+7` количества различных натуральных чисел из заданных цифр.

3103

25

Примечание: из заданного набора цифр можно составить числа 1, 3, 10, 13, 30, 31, 33, 103, 130, 133, 301, 303, 310, 313, 330, 331, 1033, 1303, 1330, 3013, 3031, 3103, 3130, 3301, 3310.

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.

Given two strings `s` and `t`, you have to decide whether `s` is a subsequence of `t`, i.e. if you can remove characters from `t` such that the concatenation of the remaining characters is `s`.

The input contains two strings `s`, `t` of alphanumeric ASCII characters separated by whitespace. Length of strings is from 1 to 100.

The output consists of the string "Yes", if `s` is a subsequence of `t`, otherwise "No".

sequence subsequence

Yes

VERDI vivaVittorioEmanueleReDiItalia

Yes

person compression

No

caseDoesMatter CaseDoesMatter

No