# Problem

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.

# Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines.

# Output

For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.

# Tests

 № Input Output 1 3 2 0 1 1 0 3 1 1 0 5 1 2 5 3 1 3 0 43 2 0 1 1 0 3 1 1 0 5 1 2 5 3 2 3 0 40 YES NO 2 5 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 54 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1435 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 4 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1430 YES NO 3 1 2 21 2 40 NO YES 4 9 1 5 7 9 10 6 3 3 6 10 2 0 5 10 4 3 3 5 7 10 4 1 4 0 4 4 2 5 4 0 1 7 0 5 3 2 7 0 6 1 7 5 2 2 2 7 4 0 1 1 8 6 6 3 0 4 9 2 1 8 0 3 7 8 7 7 3 5 0 10 8 2 1 0 5 8 8 8 3 3 1 287 178 173 129 293 196 195 180 134 182 123 203 174 287 214 150 143 144 202 143 163 158 261 150 126 128 148 125 78 153 108 182 137 82 89 109 156 141 157 108 183 149 120 120 105 166 145 166 147 192 199 157 161 147 207 159 98 105 176 141 159 149 81 243 232 270 182 300 197 184 192 201 213 152 128 61 176 142 160 147 1000 YES

# Solution

The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$  between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.

Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.

# Задача

Задан массив целых чисел. Выведите все его элементы, которые больше предыдущего.

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

В первой строке записано количество чисел $N$ в массиве. В следующей строке записано $N$ целых чисел. Все числа по модулю не превышают $100$.

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

Выведите элементы массива, которые больше предыдущих.

# Тесты

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

# Решение

Перед циклом for считываем количество заданных чисел и первый элемент. Далее в цикле считываем следующий элемент и сравниваем с предыдущим. Выводим элемент, который больше предыдущего. Присвоим переменной a значение b, чтобы иметь возможность сравнивать и далее.

# Задача

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

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

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

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

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

# Тесты

 № Входные данные Выходные данные 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

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

Для решения этой задачи необходимо объявить вектор, который будет хранить все числа, введенные пользователем, например, array.
Сортировку будем проводить с помощью функции sort. Для правильного упорядочивания чисел, напишем функцию компаратор comp, для сравнения чисел и решения, стоит ли их менять местами.
В конце выводим вектор array.

# Ссылки

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

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

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

# Умова задачі

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

# Вхідні дані

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

# Вихідні дані

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

# Тести

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

# Розвязок №1

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

# Розвязок №2

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

# Посилання

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

# Задача

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

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

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

В первой строке вводятся два числа $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

# Задача

Найти количество нулей в конце записи факториала числа $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

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

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

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

Натуральное число $n$.

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

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

# Тесты

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

# Решение

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

# Условие

Задана последовательность из $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

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

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

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

В первой строке задано количество элементов последовательности $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.

# Задача

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

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

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

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

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

# Тесты

Входные данные Выходные данные
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

# Решение

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

# Ссылки

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

# ﻿Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $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$ или $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

# Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $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.

# Задача

Для заданного целого $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
• Засчитанное решение

# Задача

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

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

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

Пример №1.

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

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

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

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

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

# Тесты

 № Вхлодные данные Выходные данные 1 3 21121 10 2 2 12 2 3 2 211 4

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

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

# Ссылки

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

# Задача

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

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

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

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

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

# Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
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

# Задача

## Условие

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

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

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

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

Первая строка содержит количество тестов $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, выводим соответствующие результаты.

# Задача

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

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

Первая строка содержит количество чисел $n \left(1 \lt n \lt 101\right).$ Во второй строке через пробел заданы $n$ натуральных чисел, каждое из которых не превышает 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 чисел. В цикле читаем $n$ чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

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

# Задача

Пусть 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$ ($1000 \le a \le b \le 9999$).

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

Выведите в одной строке все числа от $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

#### Решение

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

Ideone

e-olymp