Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

День программиста

Целые числа Циклы Вложенные циклы

Перед празднованием Дня программиста офис IT компании украсили последовательностью чисел длины N, a = {a1, a2, a3, ..., aN}. Багз Хантер, сотрудник отдела тестирования, хотел бы поиграть с этой последовательностью. В частности, он хотел бы повторить следующую операцию как можно больше раз.
Для каждого i, удовлетворяющего 1<=i<=N, выполните одно из следующих действий: «разделить ai на 2» и «умножить ai на 3». Нельзя выполнять «умножить ai на 3» сразу для каждого i в течении одной операции, значение ai после любого действия должно быть целым числом. 
Одну операцию Багз Хантер делает за 1 секунду независимо от количества чисел в последовательности. Определите максимум через сколько секунд Багз Хантер вернется к своей работе?

Входные данные
В первой строке записано целое число N (1<=N<=10000). Во второй строке записаны N целых чисел ai (1<=ai<=109).

Выходные данные
Выведите одно число -  максимальное количество секунд, через которое Багз Хантер вернется к своей работе.
 

 

Примеры
№ Входные данные Выходные данные Пояснение
1 3
5 2 4		 3 Последовательность изначально 5,2,4.
Три операции можно выполнить следующим образом:
- сначала умножьте a1 на 3, умножьте a2 на 3 и разделите a3 на 2. Теперь последовательность 15,6,2;
- затем умножьте a1 на 3, разделите a2 на 2 и умножьте a3 на 3. Теперь последовательность 45,3,6;
- наконец, умножьте a1 на 3, умножьте a2 на 3 и разделите a3 на 2. Теперь последовательность 135,9,3.
Далее, с каждым числом можно выполнить только умножение на 3, но это действие недопустимо сразу для всех чисел ai.
Поэтому ответ 3.
2 4
631 577 243 199		 0  
3 10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776		 39  

 

Троллейбусы

Вложенные циклы Простые задачи на перебор

Троллейбусы одного маршрута проходят через остановку каждые k (1<=k<=500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем.
 
Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы:
1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально.
2) Максимальное из времен ожидания троллейбуса было минимально.
 
Входные данные
В строке записано сначала число k, затем - число N (0<=N<=100000). Затем идет N чисел, задающих времена прихода пассажиров 
на остановку. Каждое из этих чисел - целое от 0 до 100000.
 
Выходные данные
Запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно. 
Если решений несколько, выведите любое из них.

Примеры
№ Входные данные Выходные данные
1
100 5
0 210 99 551 99
10
51
 
 

Вывод

Вложенные циклы

По заданным числам N и m, выведите на экран число m в виде таблицы размером NxN.

Входные данные
На вход подается два натуральных числа N и m (N <= 100, m <= 100).

Выходные данные
Выведите на экран число m в виде таблицы размером NxN.
 

Примеры
№ Входные данные Выходные данные
1 3 5 5 5 5
5 5 5
5 5 5

Вывод

Вложенные циклы

По заданному числу N и M, выведите на экран числа в виде таблицы размером NxM (N строк по M чисел в каждой строке):
1 1 1 ... 1
2 2 2 ... 2
3 3 3 ... 3
...

Входные данные
На вход подается два натуральных числа N и M (N, M <= 100).

Выходные данные
Выведите на экран числа в виде таблицы размером NxM.
 

Примеры
№ Входные данные Выходные данные
1 3 5 1 1 1 1 1 
2 2 2 2 2 
3 3 3 3 3 

Вывод

Вложенные циклы

По заданному числу N и M, выведите на экран числа в виде таблицы размером NxM (N строк по M чисел в каждой строке):
10 10 10 ... 10
20 20 20 ... 20
30 30 30 ... 30
...

Входные данные
На вход подается два натуральных числа N и M (N, M <= 100).

Выходные данные
Выведите на экран числа в виде таблицы размером NxM.
 

Примеры
№ Входные данные Выходные данные
1 3 5 10 10 10 10 10 
20 20 20 20 20 
30 30 30 30 30  

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
12 12 12 12
22 22 22 22
32 32 32 32
...
82 82 82 82
 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
2 3 4 ... 20
2 3 4 ... 20
2 3 4 ... 20
2 3 4 ... 20
2 3 4 ... 20
2 3 4 ... 20
2 3 4 ... 20

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3
15 14 13 ... 3

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
0 0 0 0 0 0
0 0 0 0 0
0 0 0 0
0 0 0
0 0

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
8 7 6 5 4 3 2 1
8 7 6 5 4 3 2
8 7 6 5 4 3
...
8

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
2 3 4 5 6 7 8 9 10
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10
...
9 10
 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
2
2 3
2 3 4
2 3 4 5
...
2 3 4 5 6 7 8 9 10
 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
3 3 3 3 
4 4 4 4 4 
5 5 5 5 5 5 
6 6 6 6 6 6 6 
...
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
21
22 22
23 23 23
24 24 24 24
...
30 30 30 30 ... 30 30
 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
...
7 ... 7
 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
5 10 15 20 25 30 35 40
10 15 20 25 30 35 40
15 20 25 30 35 40
...
35 40
40
 

Вывод

Вложенные циклы

Используя в программе вложенные циклы, напечатайте числа в виде следующей таблицы:
51 52 53 ... 58
41 42 43 ... 48
...
11 12 13 ... 18

Лесенка

Вложенные циклы

Дано натуральное число n<=9. Выведите лесенку из n ступенек, i-я ступенька состоит из чисел от 1 до i без пробелов.

Входные данные
Вводится натуральное число.
 
Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 3 1
12
123

Число Громозеки

Целые числа Вложенные циклы

Пусть S(n) обозначает сумму цифр числа n в десятичной системе счисления. Например, S(123) = 1 + 2 + 3 = 6. Мы будем называть целое число n числом Громозеки, если для всех положительных целых чисел m таких, что m > n, выполняется условие \(\frac {n}{S(n)} <= \frac {m}{S(m)}\). По заданному целому числу K, перечислите K наименьших чисел Громозеки.

Входные данные
На вход подается целое число K (K>=1, K-ое наименьшее число Громозеки не больше 1015).

Выходные данные
Выведите K строк. В i-й строке должен быть указан i-й наименьший номер Громозеки.
 

 

Примеры
№ Входные данные Выходные данные
1 10 1
2
3
4
5
6
7
8
9
19

 

Сумма трех целых

Циклы Вложенные циклы

Вам даны два целых числа K и S. Три переменные X, Y и Z принимают целые значения, удовлетворяющие условию \(0<=X,Y,Z<=K\). Сколько существует различных значений X, Y и Z, таких что \(X+Y+Z=S\)?

Входные данные
На вход подается два целых числа K (\(2<=K<=2500\)) и S (\(0<=S<=3\cdot K\)).

Выходные данные
Выведите количество троек X, Y и Z, удовлетворяющих условию.
 

 

Примеры
№ Входные данные Выходные данные Пояснения
1 2 2 6 Есть шесть троек X, Y и Z, которые удовлетворяют условию:
Х = 0, Y = 0, Z = 2
Х = 0, Y = 2, Z = 0
Х = 2, Y = 0, Z = 0
Х = 0, Y = 1, Z = 1
Х = 1, Y = 0, Z = 1
Х = 1, Y = 1, Z = 0
2 5 15 1 Лишь одна тройка удовлетворяют условию задачи:
Х = 5, Y = 5, Z = 5

 

*Корень в корне

Вложенные циклы

По заданному натуральному числу m вычислите:

\(x =\sqrt{m+\sqrt{2 \cdot m+...+\sqrt{n \cdot m + ...}}}\).
Входные данные 
На вход программе подается натуральное число m<=100.
 
Выходные данные 
Выведите значение указанного выражения с точностью до 6 значащих цифр после десятичной точки (известно, что это выражение, состоящее из бесконечного числа вложенных корней, для всех указанных значений m конечно).
 
Примеры
№ Входные данные Выходные данные
1 2 2.158477

Пара с максимальной суммой

Системы счисления Вложенные циклы

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

Входные данные
На вход подается неизвестно количество строк. В каждой строке, кроме последней, записаны по 2 числа: N (1 <= N <= 107) и r (2 <= N <= 9). В последней строке записана пара 0 0 (признак окончания ввода).

Выходные данные
Выведите на экран ответ  пару чисел с максимальной суммой. Если таких пар несколько выведите первую из них.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 3 5
21 4
1 3
1 8
2 3
0 0		 3 9 В исходных данных имеем такие числа
35, 214, 13, 18, 23
Пары следующие:
(35, 214), (214, 13), (13, 18), (18, 23)
Пара с наибольшей суммой (35, 214). В десятичной системе счисления это числа (3, 9)
Ответ: 3 9

Большая шахматная доска

Вложенные циклы

Плитки выровнены по N горизонтальным строкам и N вертикальным столбцам. Каждая плитка имеет сетку с A горизонтальными рядами и B вертикальными столбцами. Все плитки образуют квадрат X с (A×N) горизонтальными строками и (B×N) вертикальными столбцами.
Для 1<= i, j<= N плитка (i, j) обозначает плитку в i-й строке сверху и в j-м столбце слева.

Каждый квадрат X окрашен следующим образом.

  • Каждая плитка представляет собой либо белую плитку, либо черную плитку.
  • Каждый квадрат в белой плитке окрашен в белый цвет; каждый квадрат в черной плитке окрашен в черный цвет.
  • Плитка (1, 1) - это белая плитка.
  • Две плитки, разделяющие одну сторону, имеют разные цвета. Плитка (a, b) и плитка (c, d), имеют одну общую сторону тогда и только тогда, когда |a-c|+|b-d|=1 (где |x| обозначает абсолютное значение x).
Распечатайте квадрат X в формате, указанном в формате.

Входные данные
Программа получает на вход три целых числа: N, A, B (1 <= N, A, B <= 10).

Выходные данные
Выведите на экран (A×N) строк S1,...,SAxN, которые удовлетворяют следующим условиям.
Каждая из строк S1,...,SAxN представляет собой строку длины (B×N), состоящую из . и #.
Для каждого значения i и j (1<= i <= A×N,1 <= j <= B×N) j-й символ строки Si является символом . ,если квадрат в i-й строке сверху и j-м столбце слева в квадрате X окрашен в белый цвет; символом #, если квадрат окрашен в черный цвет.
 
 
Примеры
№ Входные данные Выходные данные
1 
4 3 2
 
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
2 
5 1 5
 
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
3 
4 4 1
 
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
4 
1 4 4
 
....
....
....
....

Генератор степеней двойки

Вложенные циклы

Генератор степеней двойки работает следующим образом. Каждую секунду, начиная с первой, он печатает на экране все степени двойки, значение которых, не превосходит текущую секунду.
Пример первых чисел, которые выдает генератор:
1
1 2
1 2
1 2 4
...

По заданному числу n, выведите на экран первые n чисел, которые напечатает на экране генератор.

Входные данные
Программа получает на вход числу n (n <= 103).

Выходные данные
Выведите ответ на задачу.
 
 

Примеры
№ Входные данные Выходные данные
1 5 1 1 2 1 2 
2 1 1

Изображение перекрестка

Вложенные циклы Двумерные массивы

Необходимо изобразить в текстовом формате перекресток двух дорог.

Изображение должно иметь размер \(n \times n\), ширина дорог должна быть \(l\). Центр перекрестка должен быть в центре изображения. Для клеток дороги следует использовать символ <<*>>, для клеток вне дороги символ <<.>>.

Формат входных данных
На первой строке дано целое число \(n\). На второй строке дано первое число \(l\). (\(3 \le n \le 100\), \(1 \le l < n\), \(l\) и \(n\) имеют одинаковую четность)

Формат выходных данных
Выведите \(n\) строк, изображение перекрестка.