Подразделы

Другие разделы

Дата и время

28/09/2022 07:54:43

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

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

printA. Антиарифметическая последовательность

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Антиарифметическая последовательность формируется следующим образом:
`S_0=0`
`S_1=N`
`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

printB. Взрывающиеся пузырьки

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На игровом поле находится несколько пузырьков одинакового радиуса, которые, когда взрывная волна достигает их поверхности, приходят в неустойчивое состояние и взрываются через секунду. Взрыв пузырька может привести к цепной реакции взрыва других пузырьков, которые находятся на расстоянии действия взрывной волны от взорвавшегося пузырька.
Цель игры – выбрать целые координаты начального взрыва, чтобы взорвать прямо или в результате цепочки взрывов максимальное количество пузырьков.
Напишите программу, которая определяет координаты центра начального взрыва, позволяющего взорвать максимальное количество пузырьков.
Формат ввода
Первая строка ввода содержит четыре целых числа: количество пузырьков `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

printC. Credit Check

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
Input Format
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.
Output Format
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".

Sample Input

2
5181271099000012
5181271099000017

Sample Output

Invalid
Valid

printD. Взаимно простые числа

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Два натуральных числа `a` и `b` называются взаимно простыми, если они не имеют никаких общих делителей, кроме 1.
Напишите программу, вычисляющую вероятность того, что два случайных натуральных числа (с дискретным равномерным распределением в диапазоне от 1 до `N`) будут взаимно простыми.
Формат ввода
Ввод содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^6`).
Формат вывода
В первой строке вывести вероятность с точностью `10^{-12}`, что два натуральных числа, случайно выбранных из диапазона от 1 до `N`, будут взаимно простыми.

Пример ввода

10

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

0.630000000000

printE. Головоломка

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Пример ввода

6

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

3

printF. Прямоугольники

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Напишите программу, определяющую количество различных прямоугольников с заданной площадью `S`, вершины которых имеют целые координаты. Прямоугольники считаются различными, если их нельзя совместить с помощью переноса и/или поворота. На рисунке показаны 5 различных прямоугольников, имеющих площадь 10.
21205.png
Формат ввода
Ввод содержит одно целое число `S` (`1\ ≤\ S\ ≤\ 10^9`).
Формат вывода
Вывести одно целое число – количество различных прямоугольников.

Пример ввода

10

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

5

printG. Игра

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Двое играют в следующую игру. Начиная с числа 0, игроки по очереди добавляют значение из некоторого набора возможных слагаемых-ходов к текущей сумме. Выигрывает тот, кому удастся первым получить сумму, кратную числу `N`.
Напишите программу, определяющую победителя по набору ходов и числу `N` при безошибочной игре игроков.
Формат ввода
Первая строка ввода содержит два целых числа: `N` (`2\ ≤\ N\ ≤\ 100`) и `K` (`2\ ≤\ K\ ≤\ 10`). Вторая строка содержит `K` различных целых чисел в диапазоне от 1 до 100 – возможные ходы-слагаемые.
Формат вывода
Вывести число 1, если выигрывает игрок, делающий первый ход, или число 2, если выигрывает игрок, делающий второй ход, или число 0, если ни один из игроков не может выиграть.

Пример ввода

100 2
4 7

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

1

printH. Строительство дорог

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В королевство Ксант добрался технический прогресс, и король решил построить сеть двухсторонних автомобильных и железных дорог, связывающую все города страны. На случай забастовок водителей автобусов или машинистов паровозов король решил, что между любыми городами страны можно будет проехать, двигаясь только по автомобильным дорогам или только по железным дорогам. Кроме того, железная дорога не должна дублировать автомобильную и наоборот, т.е. если из города `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

printI. Ферзь

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

21254.png

Дана позиция ферзя на пустой бесконечной доске, необходимо определить минимальное количество ходов, необходимое ферзю для достижения новой позиции на доске.
Формат ввода
Ввод содержит четыре целых числа `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

1 2 4 2

Пример вывода #1

1

Пример ввода #2

5 5 4 3

Пример вывода #2

2

Пример ввода #3

0 0 0 0

Пример вывода #3

0

printJ. Числа

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (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.

printK. Encoding

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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`.
Input Format
The input contains two strings `s`, `t` of alphanumeric ASCII characters separated by whitespace. Length of strings is from 1 to 100.
Output Format
The output consists of the string "Yes", if `s` is a subsequence of `t`, otherwise "No".

Sample Input #1

sequence subsequence

Sample Output #1

Yes

Sample Input #2

VERDI vivaVittorioEmanueleReDiItalia

Sample Output #2

Yes

Sample Input #3

person compression

Sample Output #3

No

Sample Input #4

caseDoesMatter CaseDoesMatter

Sample Output #4

No
loading