1. Задача 3n + 1 [Вальядолид, 100]. Рассмотрим следующий алгоритм:
1. ввести n;
2. вывести n;
3. если n = 1, то остановиться;
4. если n нечетное, то n = 3 * n + 1;
5. иначе n = n / 2;
6. перейти на 2;
При n = 22 будет напечатана следующая последовательность чисел: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. По утверждению Коллатса приведенный алгоритм всегда остановится для любого значения n. Хотя утверждение до сих пор не доказано. Для заданного n можно определить количество чисел, которое будет напечатано алгоритмом. Это количество называется длиной цикла. Например, для n = 22 длина цикла равна 16. В задаче следует найти максимальное значение среди всех длин циклов чисел от i до j включительно.
Вход. Состоит из последовательности целых пар чисел i и j, каждое из которых больше 0 и меньше 10000. Каждая пара чисел задается в отдельной строке.
Выход. Для каждой входной пары чисел i и j вывести ее, а также максимальную длину цикла среди всех чисел между i и j включительно.
-
Пример входа
Пример выхода
1 10
1 10 20
100 200
100 200 125
201 210
201 210 89
900 1000
900 1000 174
2. Сила криптографии [Вальядолид, 113]. По заданным числам n 1 и p 1 вычислить значение
, положительный n - ый корень числа p. Известно, что всегда существует такое целое k, что kn = p.
Вход. Состоит из последовательности пар чисел n и p, каждое число задается в отдельной строке. Известно, что 1 n 200, 1 p < 10101, 1 k 109.
Выход. Для каждой пары чисел n и p вывести значение
.
-
Пример входа
Пример выхода
2
4
16
3
3
1234
27
7
4357186184021382204544
3. Однородный генератор [Вальядолид, 408]. Псевдослучайные числа можно сгенерировать при помощи формулы:
seed(x + 1) = (seed(x) + STEP) % MOD,
где % – операция взятия остатка. Недостаток такого метода получения случайных чисел состоит в том, что циклически будет генерироваться одна и та же последовательность. Например, если STEP = 3 и MOD = 5, то циклически будет повторяться последовательность 0, 3, 1, 4, 2. Если STEP = 15 и MOD = 20, то получим серию чисел 0, 15, 10, 5.
Выяснить, можно при помощи такого генератора получить все числа от 0 до MOD – 1.
Вход. Каждая строка содержит два числа: STEP и MOD (1 STEP, MOD 100000).
Выход. Для каждого теста вывести значение STEP в колонках от 1 до 10, выровненное справа, значение MOD в колонках от 11 до 20, выровненное справа, и фразу ‘Good Choice‘ или ‘Bad Choice‘, начиная с колонки 25. Если по входным STEP и MOD будут сгенерированы все числа от 0 до MOD – 1, то выводить фразу ‘Good Choice‘. Иначе следует выводить фразу ‘Bad Choice‘. После вывода результата для каждого теста выводить пустую строку.
-
Пример входа
Пример выхода
3 5
3 5 Good Choice
15 20
63923 99999
15 20 Bad Choice
63923 99999 Good Choice
4. Коробка с кирпичами [Вальядолид, 591]. Играя с кирпичами, Боб выстраивает стопки разной высоты. Алиса хочет переложить минимальное количество кирпичей так, чтобы все стопки имели одинаковую высоту.
Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество стопок n. Во второй строке следуют n чисел – высоты стопок hi . Известно, что 1 n 50, 1 hi 100. Общее количество кирпичей всегда делится на количество стопок. Признак конца входных данных n = 0.
Выход. Для каждого теста вывести его номер и сообщение ‘The minimum number of moves is k.’, где k – минимальное количество кирпичей которое надо переложить, чтобы уравнять стопки. После каждого теста выводить пустую строку.
-
Пример входа
Пример выхода
6
Set #1
5 2 4 1 7 5
The minimum number of moves is 5.
0
5. Задача Коллатса [Вальядолид, 694]. Пусть имеется некоторое положительное целое число A. Будем производить с ним следующие действия:
Шаг 1. Если A = 1, то остановиться.
Шаг 2. Если A четное, то заменить A на A/2 и перейти к шагу 1.
Шаг 3. Если A нечетное, то заменить A на 3*A + 1 и перейти к шагу 1.
По заданному A необходимо подсчитать количество чисел, которое будет порождено алгоритмом до его остановки на шаге 1, либо сколько чисел будет порождено пока его текущее значение не превысит заданного лимита L.
Вход. Каждая строка содержит два числа A и L, не больших 2,147,483,647. Известно, что A < L. Признаком конца входных данных будут отрицательные значения A и L.
Выход. Для каждого теста вывести его номер, двоеточие, исходное значение A, лимит L и количество шагов вычисления до остановки или до достижения значения, превышающего L.
-
Пример входа
Пример выхода
3 100
Case 1: A = 3, limit = 100, number of terms = 8
34 100
Case 2: A = 34, limit = 100, number of terms = 14
75 250
Case 3: A = 75, limit = 250, number of terms = 3
27 2147483647
Case 4: A = 27, limit = 2147483647, number of terms = 112
101 304
Case 5: A = 101, limit = 304, number of terms = 26
101 303
Case 6: A = 101, limit = 303, number of terms = 1
-1 -1
6. Простая арифметика [Вальядолид, 10035]. Вычислить количество переносов при сложении двух целых чисел.
Вход. Каждая строка содержит два целых числа, состоящих из не более, чем 10 знаков. Последняя строка содержит два нуля и не обрабатывается.
Выход. Для каждого теста вывести количество переносов при сложении входных чисел в соответствии с форматом, приведенном ниже.
-
Пример входа
Пример выхода
123 456
No carry operation.
555 555
3 carry operations.
123 594
1 carry operation.
0 0
7. Хашмат – смелый воин [Вальядолид, 10055]. Хашман – смелый воин. В начале битвы он подсчитывает разницу между числом его воинов и воинов противника. В зависимости от значения этой разницы Хашмат решает – начинать битву или нет.
Вход. Каждая строка содержит два целых числа – количество воинов армии Хашмата и число воинов армии его оппонента. Входные числа не более 232.
Выход. Для каждого теста вывести положительную разницу между количеством воинов армии Хашмата и армии врага.
-
Пример входа
Пример выхода
10 12
2
10 14
4
100 200
100
8. Назад к школьной физике [Вальядолид, 10071]. Некоторая частица обладает постоянным ускорением. В некоторый момент времени t ее скорость равна v. Какое расстояние пройдет частица, когда наступит момент времени 2t?
Вход. Каждая строка содержит скорость частицы v (-100 v 100) и время t (0 t 200), за которое частица достигла этой скорости.
Выход. Для каждого теста вывести расстояние, на которое переместится частица через время 2t.
-
Пример входа
Пример выхода
0 0
0
5 12
120
9. Числа Бангла [Вальядолид, 10101]. В языке Бангла обычно используют слова 'kuti' (10000000), 'lakh' (100000), 'hajar' (1000), 'shata' (100) при преобразования числа в его текстовое представление. Найти текстовые представления заданных слов.
Вход. Каждая строка содержит положительное число, не большее 999999999999999.
Выход. Для каждого входного числа вывести его текстовое представление. В начале каждой строки должен стоять номер теста, выровненный справа до четырех знаков. Далее следует точка и текстовое представление числа, как показано в ниже приведенном примере.
-
Пример входа
Пример выхода
23764
1. 23 hajar 7 shata 64
45897458973958
2. 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58
10. Экологическая премия [Вальядолид, 10300]. Фермер владеет полем, на котором пасутся животные. Известен размер поля a, количество животных b на нем и уровень средств производства c. Из государственного бюджета фермер получает помощь, которая вычисляется следующим образом: за каждое животное фермер получает количество денег, равное среднему количеству занимаемых животным метров на поле, умноженному на уровень средств производства. Вычислить сумму общей государственной помощи для всех фермеров.
Вход. Первая строка содержит количество тестов n (n < 20). Первая строка каждого теста содержит число фермеров f (0 < f < 20) в стране. Следующие f строк содержат значения a, b, c (0 a, b, c 10000) для каждого фермера.
Выход. Для каждого теста вывести сумму общей государственной помощи для всех фермеров.
-
Пример входа
Пример выхода
2
38
5
86
1 1 1
2 2 2
3 3 3
2 3 4
8 9 2
3
9 1 8
6 12 1
8 1 1
11. Суммирование полиномов [Вальядолид, 10302]. Для заданного x вычислить сумму 1 + 8 + 27 + ... + x3.
Вход. Каждая строка содержит число x (1 x 50000).
Выход. Для каждого x вывести в отдельной строке значение указанной выше суммы.
-
Пример входа
Пример выхода
1
1
2
9
3
36
12. Больше среднего [Вальядолид, 10370]. В классе учится n учеников. Известны их аттестационные оценки по 100 бальной шкале (от 0 до 100 включительно). Вычислить процент учеников, имеющих бал выше среднего.
Вход. Первая строка содержит количество тестов. Каждый тест располагается в отдельной строке. Первым числом каждого теста является количество учеников в классе n (1 n 1000). Далее следуют n чисел – аттестационные оценки учеников.
Выход. Для каждого теста вывести в отдельной строке процент учеников, имеющих бал выше среднего. Ответ округлять до 3 десятичных знаков.
-
Пример входа
Пример выхода
5
40.000%
5 50 50 70 80 100
57.143%
7 100 95 90 80 70 60 50
33.333%
3 70 90 80
66.667%
3 70 90 81
55.556%
9 100 99 98 97 96 95 94 93 91
40.000%
13. Коты в и без шляп [Вальядолид, 10493]. Кот носит шляпу тогда и только тогда, когда в шляпе находится n котов. Существует только один кот, который находится не в шляпе. Если m котов не имеют шляп, то сколько всего котов?
Вход. Каждая строка содержит два числа n и m (1 n 100000, 1 m 100000). Последний тест содержит n = 0 и не обрабатывается.
Выход. Для каждого теста вывести n, m. Далее в этой же строке вывести общее количество котов (если оно определяется однозначно). Если решения нет, то вывести “Impossible”. Если имеется бесконечное количество решений, то вывести “Multiple”.
-
Пример входа
Пример выхода
2 5
2 5 9
3 4
3 4 Impossible
3 3
3 3 4
0 0
следующая страница>