e-olymp 1462. Хитрая сортировка

Задача

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

Входные данные

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

Выходные данные

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

Входные данные Выходные данные
1 7
12 15 43 13 20 1 15
20 1 12 13 43 15 15
2 10
82 22 19 90 34 17 588 921 200 121
90 200 121 921 22 82 34 17 588 19
3 4
162 9801 37 14
9801 162 14 37

Код программы

 

Решение задачи

Для решения этой задачи необходимо объявить массив, с размером [latex] n [/latex], который будет хранить все числа, введенные пользователем.
Сортировку будем проводить в циклах for для сравнения соседних чисел и смены их позиции с помощью функции swap. Если последняя цифра следующего числа меньше предыдущего, то эти числа меняются местами. Если их последние цифры одинаковые, то сравниваются сами числа.
В конце выводим массив array[n].

Ссылки

Условие на e-olymp

Решение на e-olymp

Решение на ideone.com

e-olymp 8851. Число навпаки

Умова задачі

Записати чотиризначне натуральне число в зворотному порядку.

Вхідні дані

Задане чотиризначне натуральне число.

Вихідні дані

Відповідь до задачі.

Тести

Входные данные Выходные данные
1 1234 4321
2 1984 4891

Розвязок №1

Для отримання потрібного числа, відділимо кожну цифру та привласнемо до неї змінну. Виводимо у потрібному порядку.

Розвязок №2

Представимо вводиме число як строку. Виводимо у циклі від третього до останньго елемента.

Посилання

Задача на e-olymp
Зарахований розв’язок №1
Зарахований розв’язок №2
Код на ideone №1
Код на ideone №2

e-olymp 4020. Культ-орки на лестнице

Задача

В Летней Кинематографической Школе пришло время обеда и эльф Коля поспешил в столовую. Однако для того, чтобы попасть в столовую, Коле нужно подняться по длинной лестнице, а на каждой её ступеньке в это время суток стоит по культ-орку. Каждый культ-орк разрешает Коле пройти по своей ступеньке только после того, как Коля запишется на мероприятие, которое этот культ-орк организует. При этом никакие два культ-орка не проводят одно и то же мероприятие, и все мероприятия проходят в разное время.

Коля — честный эльф, и если уж он запишется на какую игру или конкурс, то потом обязательно придёт поучаствовать. Однако Коля хочет потратить как можно меньше времени на развлечения, ведь иначе ему некогда будет дорешивать кинематографические задачки. К счастью, Коле не надо наступать на каждую ступеньку, он может перепрыгнуть через несколько. Коля хочет узнать, какое минимальное количество времени ему придётся распланировать за один проход по лестнице до столовой.

Входные данные:

В первой строке вводятся два числа $n$ и $k$ $(1 \leqslant n \leqslant 10000, 0 \leqslant k \leqslant 20)$, $n$ — количество ступенек на лестнице, $k$ — максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на $(k + 1)$-ую или более низкие ступеньки). Во второй строке вводятся $n$ чисел: $i$-ое число указывает на длительность в минутах того мероприятия, которое проведёт культ-орк, стоящий на $i$-ой ступеньке. Каждое мероприятие не может длиться более $24$ часов. Ступеньки нумеруются снизу вверх, ступенькой номер $n$ считается весь этаж столовой.

Выходные данные:

Выведите одно число — минимальное количество минут, которое Коле придётся распланировать.

Тесты

Входные данные  Выходные данные
1 5 2
7 3 9 2 11
14
2 6 1
59 32 4 21 5 1
42
3 10 3
40 55 85 29 158 105 115 281 320 10
144
4 15 4
67 20 85 12 345 9 234 115 190 47 5 17 23 89 130
156
5 4 0
100 20 31 49
200

Код программы

Решение

Для каждой ступеньки будем считать минимальное время, которое она отнимет у эльфа, учитывая сколько ступенек можно пропустить (от $0$ до $k + 1$). То есть будем прыгать со ступенек пониже (если это возможно) и сравнивать значения на каждой. Под значением подразумевается сумма уже найденного значения на более низкой ступеньке и времени, которое отнимет мероприятие $i$-ой ступеньки. Таким образом мы узнаем, какие ступеньки выгодно перепрыгнуть. $0$-я ступенька займет $0$ минут, так как эльф не потратит время. Изначально за минимум на ступеньках до $k + 1$ включительно можно взять время мероприятия соответствующей ступеньки, для остальных — сумму значения предыдущей ступеньки и времени мероприятия данной ступеньки. В случае, если эти значения не минимальные, они заменятся на подходящие.
Ответом будет значение на последней ступеньке, так как к ней будет проложен путь, который «займет» минимум времени эльфа на развлечения.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

e-olymp 123. Количество нулей у факториала

Задача

Найти количество нулей в конце записи факториала числа $n$.

Входные данные

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

Выходные данные

Количество нулей в конце записи $n!$

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 0
 2 7 1
 3 12 2
 4 100 24
 5 306 75
 6 5000 1249

Код

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

Условие задачи на e-olymp

Код на Ideone

Засчитанное решение на e-olymp 

 

e-olymp 8916. Первые парные

Первые парные

Программа должна ввести с консоли натуральное число [latex] n [/latex] и вывести в порядке возрастания [latex] n [/latex] первых четных натуральных чисел.

Входные данные

Натуральное число [latex] n [/latex].

Выходные данные

В одной строке через пробел [latex] n [/latex] первых четных натуральных чисел.

Тесты

Входные данные Выходные данные
1 3 2 4 6
2 8 2 4 6 8 10 12 14 16
3 5 2 4 6 8 10

Код программы

Решение

Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].

Ссылки

Условие на e-olymp
Решение на e-olymp
Решение на ideone.com

e-olymp 7841. Нечетные элементы

Условие

Задана последовательность из $n$ целых чисел. Выведите все ее нечетные элементы.

Входные данные

Первая строка содержит число $n$. Следующая строка содержит $n$ ($n$ $⩽$ $100$)  целых чисел, которые по модулю не превосходят $100$.

Выходные данные

Вывести все нечетные элементы последовательности в том же порядке как они встречаются на входе.

Тесты

Входные данные Выходные данные
1 7
14 17 16 3 7 19 9
17 3 7 19 9
2 5
2 4 3 11 5
3 11 5

Код

Решение

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

Ссылки

  • Задача на e-olymp
  • Код программы на Ideone

e-olymp 8680. Чётные соседи

Условие задачи

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

Входные данные

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

Выходные данные

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

Входные данные Выходные данные
1 6
1 2 3 4 5 6
2
2 9
3 6 3 5 2 9 1 2 5
0
3 3
2 1 2
1
4 6
13 24 54 66 44 77
2
5 4
100 224 666 222
2

Программный код

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

e-olymp 8544. Квадраты чисел

Задача

Выведите квадраты всех натуральных чисел не больших [latex]n[/latex] в возрастающем порядке.

Входные данные

Одно натуральное число [latex]n[/latex] [latex](n \leqslant 10^9)[/latex]

Выходные данные

Выведите список квадратов всех натуральных чисел не больших [latex]n[/latex] в возрастающем порядке.

Тесты

Входные данные Выходные данные
1 1
16 1 4 9 16
93 1 4 9 16 25 36 49 64 81
100 1 4 9 16 25 36 49 64 81 100

Код

Решение

Воспользуемся циклом, в котором заведем переменную [latex]i[/latex]  и будем перечислять числа [latex]1, 4, 9, …, i^2[/latex], пока [latex]i^2[/latex] не будет больше [latex]n[/latex]. Выводим последовательно квадраты натуральных чисел в одной строке.

Ссылки

Задача на e-olymp
Код решения на ideone

e-olymp 8283. Музыка

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

Входные данные

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

Выходные данные

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

Входные данные Выходные данные
1 11 3 5
2 6 2 0
3 13 13 3
4 9 8 0
5 5 5 5

Код

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

  1. Если пользователь вводит разные числа.
  2. Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

  • Условие задачи на e-olymp
  • Код программы на ideone.com
  • Засчитанное решение на e-olymp

e-olymp 5041. Синтаксический анализ вещественных чисел

Задача

Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $ e $ или $ E $), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $ 1000 $ символов.

Входные данные

Первая строка содержит количество тестов $ t $. Дальше следует $ t $ строк, каждая из которых содержит одно число.

Выходные данные

Вывести $ t $ строк, каждая из которых содержит слово $ LEGAL $ или $ ILLEGAL $.

Тесты

Входные данные Выходные данные
1. 2
1.5e+2
3.
LEGAL
ILLEGAL
2. 4
752.45e+24
0.762e.
-0.355.6432e
LEGAL
ILLEGAL
ILLEGAL
3. 1
-652.32e+45
LEGAL
4. 3
542.512e+3
123.456E+42
123.456.789
LEGAL
LEGAL
ILLEGAL

Код

Решение

Для решения задачи нам понадобится функция idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через cin они игнорируются.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

e-olymp 566. Письмо почтальона Печкина

Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

Входные данные

В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

Выходные данные

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

Тесты

Входные данные Выходные данные
1. 1
3 2
8 10
2. 2
4 4
2 2
30 70
5 4
3. 4
3 3
25 46
100 100
1 1
14 22
12350 338975
338350 25164150
1 0

Код программы

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

Пояснение к первому тесту

Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера.  Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.

Ссылки

Условие на e-olymp.

Код на ideone.

 

e-olymp 4142. Большой XOR

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

  • $ a $ xor $x > x $
  • $ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

Входные данные

Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.

Выходные данные

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

Тесты

Входные данные Выходные данные
1 2
2
10
1
5
2 3
13
3
16
2
0
15
3 5
1
7
4294967295
42
451
0
0
0
21
60

Код

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

  • Задача на e-olymp
  • Код программы на ideone
  • Засчитанное решение
  • e-olymp 6264. Энергетический магнат

    Задача

    Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

    Правила игры достаточно просты:

      • Доска содержит [latex]n[/latex] слотов, расположенных в линию.
      • Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
      • Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
      • После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.

    Пример №1.

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

    Входные данные

    Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

    Выходные данные

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

    Тесты

    Вхлодные данные Выходные данные
    1 3

    21121

    10
    2 2

    12

    2
    3 2

    211

    4

    Код программы

    Решение задачи

    Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

    Ссылки

    • Условие задачи на e-olymp
    • Код программы ideone

    e-olymp 2507. Граница

    Задача

    В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

    Входные данные

    Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.

    Выходные данные

    Выведите одно целое число — длину границы между государствами в километрах.

    Тесты

    # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    1 5 6
    AAABB
    ABBBB
    AAABB
    AAAAB
    AAAAB
    AABBB
    13
    2 4 3
    AAAA
    AAAA
    AAAB
    2
    3 5 9
    BBBBB
    ABBBB
    AABBB
    AAABB
    AAAAB
    AAABB
    AABBB
    ABBBB
    BBBBB
    15
    4 2 1
    AB
    1
    5 6 5
    AABBBB
    BBBBBB
    BBBAAA
    AAAAAA
    AAAAAA
    10

    Код

    Решение

    Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.

    Запустить код (ideone) можно здесь
    Задача на E-olymp

    e-olymp 1215. Камень, ножницы или бумага?

    Задача

    Условие

    Камень > ножницы > бумага > камень > ножницы > ...

    Камень > ножницы > бумага > камень > ножницы > …

    В игру Камень, Ножницы, Бумага играют двое. Каждый игрок на счет три одновременно выбирает один из трех предметов. Игра длится определенное наперед установленное количество раундов. Игрок, который выиграет большую часть раундов, объявляется победителем. По заданному количеству раундов и их исходам следует определить победителя.
    Следующие правила описывают правила победы:

    • Камень всегда побеждает Ножницы (Камень раздавливает Ножницы)
    • Ножницы всегда побеждают Бумагу (Ножницы режут Бумагу)
    • Бумага всегда бьет Камень (Бумага покрывает Камень)

    Входные данные

    Первая строка содержит количество тестов $t$ ($0 < t < 1000$). Первая строка каждого теста содержит количество раундов $n$ ($0 < n < 100$), сыгранных в игру Камень, Ножницы, Бумага. Каждая из следующих $n$ строк содержит одну из заглавных букв $R$ (Камень), $P$ (Бумага) или $S$ (Ножницы), пробел и снова заглавную букву $R$, $P$ или $S$. Первая буква обозначает выбор первого игрока, вторая буква — выбор второго игрока.

    Выходные данные

    Для каждого теста в отдельной строке вывести имя победителя (Player 1 или Player 2). Если игра заканчивается вничью, вывести TIE.

    Тесты

    Входные данные Выходные данные
    1 3
    2
    R P
    S R
    3
    P P
    R S
    S R
    1
    P R
    Player 2
    TIE
    Player 1
    2 1
    1
    S P
    Player 1
    3 2
    3
    S P
    P S
    R R
    2
    P R
    S R
    TIE
    TIE
    4 4
    1
    R P
    2
    R P
    S R
    3
    R P
    S R
    P S
    4
    P R
    R S
    P S
    S S
    Player 2
    Player 2
    Player 2
    Player 1

    Решение

    Для решения задачи необходимо сравнить выбор первого и второго игрока в каждом раунде каждого теста.
    Подсчитываем количество побед для игроков во всех раундах теста. Получаем победителя для каждого теста.
    В данной реализации используем вложенные циклы. Вводим переменную $t$ — количество тестов. Затем задаём цикл, в котором вводим новую переменную $n$ — количество раундов для каждого теста. Этот цикл будет работать, пока не проверим все тесты. Так же заводим два счётчика sum1 и sum2, которые будут подсчитывать победы первого и второго игрока. Задаём ещё один цикл, который будет выполняться, пока не проверим все раунды для каждого теста. В нём вводим выбор первого игрока и выбор второго игрока. Сравниваем данные значения согласно правилам победы, которые описаны в условии. В случае победы первого игрока увеличиваем переменную sum1 на единицу, в случае победы второго — sum2 на единицу. После завершения циклов сравниваем переменные sum1 и sum2, выводим соответствующие результаты.

    Код программы

    Ссылки

    e-olymp 137. НОД

    Задача

    Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

    Входные данные

    Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

    Выходные данные

    НОД заданных чисел.

    Тесты

    # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    1 2
    15 25
    5
    2 3
    99 358 2
    1
    3 5
    81 99 72 108 36
    9
    4 2
    25 50
    25
    5 4
    132 36 66 18
    6

    Код

    Решение

    Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

    Запустить код (ideone) можно здесь
    Задача на E-olymp

    e-olymp 8653. Прибавить вычесть и умножить

    Задача

    Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

    • add a: прибавить значение a к x;
    • subtract a: вычесть значение a из x;
    • multiply a: умножить x на a;

    Входные данные

    Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

    Выходные данные

    Выведите результирующее значение переменной x.

    Тесты

    Ввод Вывод
    1 add 2
    subtract 5
    subtract 1
    multiply -3
    12
    2 subtract 5
    multiply -5
    add 5
    30
    3 add 6
    add 543
    multiply 23
    12627
    4 multiply 45678
    add 3
    3
    5 subtract 58
    add 38
    multiply -1
    add 100
    120

    Код программы

    Решение задачи

    Инициализировав основную переменную x, через поток ввода считываем все действия, которые неоходимо применить по отношению к переменной. Во время этого ничего не выводим, дожидаясь, пока поток команд закончится. Заметим, что процесс ввода может длиться сколько угодно долго. В конце концов, на выходе получаем уже «преобразованный» x — результат проделанных дейсвтий.

    Ссылки

    e-olymp 8533. Числа с разными цифрами

    Задача

    Выведите все четырехзначные числа от $a$ до $b$, содержащие разные цифры.

    Входные данные

    Два целых числа $a$ и $b$ ([latex]1000 \le a \le b \le 9999[/latex]).

    Выходные данные

    Выведите в одной строке все числа от $a$ до $b$ с разными цифрами.

    Тесты

     Входные данные Выходные данные
     2000 2015  2013 2014 2015
     9875 9999  9875 9876
     1000 1234  1234
     3612 3612  3612
     8800 8888  Standart output is empty
     1000 1000  Standart output is empty

    Код программы

     

    Решение

    Для каждого числа из заданного промежутка [latex][a;b][/latex] выделяем его цифры и сравниваем их между собой. Искомые числа будут состоять из неравных между собой цифр.

    Ссылки

    Ideone

    e-olymp

    e-olymp 1119. Пирамида из символов

    Задача

    Вася хочет напечатать на принтере пирамиду из какого-то символа высоты $h$. Напишите программу, которая поможет ему в этом, не забывая, что программа должна быть «экономически выгодной», т.е печатать наименьшее количество символов.

    Примеры пирамид приведены в примерах входных и выходных данных. Для большей наглядности печатаемые пробелы заменены на точки.

    Входные данные

    В одной строке задан сначала символ, при помощи которого должна быть напечатана пирамида, а затем через пробел натуральное число, задающее высоту пирамиды $h (h ≤ 50)$.

    Выходные данные

    В первой сроке выведите общее количество напечатанных «печатных» символов а ниже саму пирамиду.

    Тесты

    Входные данные Выходные данные
    A 3 12
    A
    AAA
    AAAAA
    M 9 117
    M
    MMM
    MMMMM
    MMMMMMM
    MMMMMMMMM
    MMMMMMMMMMM
    MMMMMMMMMMMMM
    MMMMMMMMMMMMMMM
    MMMMMMMMMMMMMMMMM

    Код программы

    Решение

    Для решения данной задачи потребуется выводить пробелы для отступов в каждой строке и заданный символ в виде пирамиды. Для этого напишем цикл, который будет перебирать строки. Для нахождения количества символов в пирамиде используем формулу: по арифметической прогрессии, где первый элемент это $1$, а каждый следующий больше предыдущего на $2$. В вывод пишется столько пробелов, сколько нужно для правильного расположения (с каждой следующей строчкой пробелов на $1$ меньше, в первой строке $b$ пробелов).

    Ссылки

    e-olymp
    Ideone

    e-olymp 7623. Счастливые случаи

    Счастливые случаи

    Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
    Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

    Входные данные

    В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
    Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

    Выходные данные

    Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

    Тесты

    # ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
    1 $1$ $1$
    $4$
    $4$
    2 $2$ $4$
    $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$
    $12$
    3 $3$ $2$
    $10$ $10$ $10$ $10$ $4$ $5$
    $13$
    4 $2$ $2$
    $1$ $2$ $3$ $4$
    $12$
    5 $0$ $0$ $0$

     

    Код программы

    Решение задачи

    Решение данной задачи состоит в том, чтобы создать цикл, который будет сравнивать все элементы массива. Изначально у нас будут четыре переменных, которые отвечают за каждую из сторон массива, равные единице. Далее мы сравниваем каждый элемент строки с последующими в нужном направлении и если он не является выигрышным, то соответствующей переменной задаем значение ноль. Просуммировав все «выигрышные случаи» мы узнаем количество выигрышных направлений.

    Ссылки

    • Задача на e-olymp.

    • Решение на сайте ideone.