e-olymp 7233. Путишествия в космосе

Задача

Инфраструктура космической галактики состоит из [latex]N[/latex] планет и [latex]M[/latex] прямых межпланетных маршрутов, каждый из которых связывает ровно две разные планеты. Расстояния в космосе достаточно большие, поэтому, если планеты не имеют прямого сообщения, то во время перелетов используют транзитные планеты.

Популярностью планеты [latex]k[/latex] будем считать количество пар различных планет [latex]i[/latex] и [latex]j[/latex], перелет между которыми возможен только при использовании планеты [latex]k[/latex] [latex](i, j, k = 1..N)[/latex]. Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.

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

В первой строке натуральные числа [latex]N[/latex] и [latex]M[/latex] ([latex]1 \leq N \leq 1000[/latex], [latex]1 \leq M \leq 5000[/latex]). В следующих [latex]M[/latex] строках по два натуральных числа, описывающие маршрут между планетами [latex]i[/latex] и [latex]j[/latex] [latex](i, j, k = 1..N)[/latex].

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

Ответ к задаче.

Тесты

Входные данные Выходные данные Объяснение
1 4 4
1 2
1 3
1 4
2 3
5 1 Простой пример графа с двумя структурами
2 14 14
1 2
2 3
2 4
3 5
1 6
6 7
7 8
8 6
1 9
9 10
10 11
9 12
1 13
13 14
75 1 Граф с четырьмя структурами для проверки правильности перемножения нескольких структур и их обхода
3 4 4
1 2
2 3
3 4
4 1
3 4 Закольцованный граф с несколькими наиболее популярными вершинами

Код

 

 

Решение

Для начала представим полученный граф из планет в виде списка смежности(список, где каждой вершине соответствует список смежных ей других вершин). Так как нам надо получить значение наибольшей популярности, будем поочередно убирать(по сути заранее отмечать ее как посещенную) каждую из вершин и смотреть, между сколькими парами вершин нельзя составить маршрут. Для этого воспользуемся depth-first search. Его суть состоит в том, что мы берем любую вершину и начинаем рекурсивно проходить по всем ее соседям, а потом по их соседям и так далее. Каждую посещенную вершину мы отмечаем, чтобы при попадании на посещенную ранее вершину выйти из рекурсии. Таким образом, мы запускаем рекурсивную функцию пока остаются не посещенные вершины. В конце мы получим список структур графа и количество вершин в каждой из них. Чтобы получить популярность искомой вершины, мы суммируем кол-во остальных вершин(так как у них нет маршрута к убранной вершине) и поочередное произведение кол-ва вершин полученных структур.

Ссылки

e-olymp 8946. Шаблон

Условие

По заданному натуральному числу $n$ вывести изображение размером $n\times n$, образованное символами звездочка и пробел как показано в примере.

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

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

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

Вывести изображение $n \times n$.

Тесты

Входные данные  Выходные данные
1 2
2 3
3 4
4 5
5 6

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

Решение

Для того, чтобы вывести изображение как на рисунке достаточно заметить, что выводятся строки только двух видов и то поочерёдно. Первый вид — первым символом строки является $\ast$ и затем чередуется $\ast$ и пробел. Второй вид — первым символом строки является пробелом и затем чередуется $\ast$ и пробел. Мы заполняем две строки, по одной каждого вида. Нам остается только выводить строку необходимого нам вида, сделаем это в цикле.

Ссылки

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

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

e-olimp 9536. Сумма матриц

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

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

3

5
1 5
4 3 7 2 1

3 2 2 1 6

7 5 9 3 7
2 2
0 4
2 3

5 4
1 6

5 8
3 9
3 4
3 4 5 6
1 2 3 4
7 6 5 4

0 0 -3 -2
-1 3 4 5
5 6 1 2

3 4 2 4
0 5 7 9
12 12 6 6
3 3
2 -128 47
-365 5 56
243 42 12

678 43 76
4 345 -23
97 -453 18

680 -85 123
-361 350 33
340 -411 30

Код

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olymp 9066. Кружок стрельбы

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

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

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 5
1 3 3
5 1 2
8 2 3
10 1 2
11 3 2
2
2 6
1 3 5
4 2 2
7 4 3
10 1 2
11 3 2
13 4 3
1

Код

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

  • Условие задачи на e-olymp
  • Код на Ideone
  • Засчитанное решение на e-olymp 

e-olymp 8956. Вывести массив 4

Задача

Задан массив из [latex]n[/latex] целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

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

Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

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

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 7
-2 5 4 -3 7 -1 0
3
-1 -3 -2
2 5
2 1 0 1 5
NO
3 3
-1 -2 -3
3
-3 -2 -1

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

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

Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― [latex]n[/latex] и [latex]count[/latex]. Переменная [latex]n[/latex] считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной [latex]count[/latex] обязательно присваиваем значение [latex]0[/latex], ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

e-olymp 8963. Наименьшие влево

Условие

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

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

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

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

Выведите элементы обновленного массива.

Тесты

Ввод Вывод
1 7
6 -3 -7 4 -7 -4 5
-7 -7 6 -3 4 -4 5
2 2
100 -100
-100 100
3 6
-2 -2 7 3 99 -2
-2 -2 -2 7 3 99
4 5
1 1 1 1 1
1 1 1 1 1

Решение

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

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

Ссылки

решение на E-olymp
код на ideone

e-olymp 8666. Коровий котильон

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

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

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

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

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

Входные данные Выходные данные
1 2
6 >><<><
4 ><<>
legal

illegal

2 3
8 <>><><><
6 ><>><<
9 >><>><<><
illegal
legal
illegal
3 5
4 ><><
10 >>><<>><<<
8 >><<<>><
3 >><
12 ><>><>>><<<<
legal
legal
illegal
illegal
legal

Код

 

Решение

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

Ссылки

e-olimp 7848. Переставить соседние

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

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

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

Вывести обновленный массив.

Тесты

Входные данные Выходные данные
7
3 5 -7 7 5 -9 -4
5 3 7 -7 -9 5 -4
8
-9 81 27 -38 2 6 -56 -21
81 -9 -38 27 6 2 -21 -56
2
25 -76
-76 25
3
55 44 33
44 55 33
1
99
99

Код

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olymp 7847. Кількість різних елементів

Задача

Дано масив з [latex]N[/latex] цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

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

Вихідні дані

Кількість різних елементів в масиві.

Тести

 

Вхідні дані Вихідні дані
1. 7
3 5 -7 7 5 -9 -4
6
2. 5
1 25 59 75 100
5
3. 6
1 2 3 1 2 4
4

Код 1

Код 1(without break)

Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

Ссылки

Код 2

Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно [latex]n.[/latex] Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

Ссылки

e-olymp 2098. Переворачиватель

Условие

Заданы [latex]n[/latex] чисел. Выведите их в обратном порядке.

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

Сначала задано число [latex]n[/latex] ([latex]0 \lt n \lt 100[/latex]), за ним идут [latex]n[/latex] целых чисел.

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

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

Тесты

Ввод Вывод
1 7
2 4 1 3 5 3 1
1 3 5 3 1 4 2
2 1
5
5
3 10
1 1 1 9999 5 -1 7 3 0 9
9 0 3 7 -1 5 9999 1 1 1

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

Решение

Введём переменную [latex]n[/latex], затем создадим массив из [latex]n[/latex] элементов. С помощью цикла for от [latex]0[/latex] до [latex]n[/latex] запишем в него числа. Теперь с помощью другого цикла от [latex]n-1[/latex] до [latex]-1[/latex] выводим их в обратном порядке.

e-olymp 6388. Муха Фон-Неймана

Задача

Следующая задача была предложена Джону Фон-Нейману:

Два велосипедиста [latex]a[/latex] и [latex]b[/latex] начинают поездку навстречу друг другу в одно и то же время с мест, находящихся на расстоянии [latex]250[/latex] друг от друга, [latex]a[/latex] движется со скоростью [latex]10[/latex] миль в час, [latex]b[/latex] движется со скоростью [latex]15[/latex] миль в час. В это же время муха взлетает с колеса велосипедиста [latex]a[/latex] и движется навстречу к [latex]b[/latex], затем разворачивается и летит обратно. Пока велосипедисты приближаются друг к другу, муха продолжает летать между ними, касаясь каждый раз переднего колеса велосипедистов, пока, наконец, не будет раздавлена колесами встретившихся велосипедов. Так как муха летает быстрее каждого из велосипедистов, она совершает бесконечное количество полетов, при этом пройдя конечное расстояние (бесконечный ряд сходится). Какое расстояние пролетела муха?

Фон-Нейман немедленно вычислил бесконечный ряд (в уме!), и получил верный ответ: [latex]200[/latex] миль.

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

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

Первая строка содержит количество тестов [latex]p (1 \leqslant p \leqslant 1000)[/latex].

Каждый тест состоит из одной строки, содержащей пять чисел: номер теста [latex]n[/latex] и четыре действительных числа: начальное расстояние между велосипедистами [latex]d (10 \leqslant d \leqslant 1000)[/latex], скорость первого велосипедиста [latex]a (1 \leqslant a \leqslant 30)[/latex] в милях в час, скорость второго велосипедиста [latex]b (1 \leqslant b \leqslant 30)[/latex] в милях в час и скорость мухи [latex]f (a \leqslant b < f \leqslant 50)[/latex] в милях в час.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5
1 250 10 15 20
2 10.7 3.5 4.7 5.5
3 523.7 15.3 20.7 33.3
4 1000 30 30 50
5 500 15 15 25
1 200.00
2 7.18
3 484.42
4 833.33
5 416.67

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

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

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

Согласно условию, велосипедисты [latex]a[/latex] и [latex]b[/latex] двигаются навстречу друг другу, а следовательно их скорость сближения (общая скорость) будет равна сумме скоростей каждого из велосипедистов: [latex]a + b[/latex]. По знакомой из школьного курса математики формуле [latex]S = V \times t[/latex] (тогда [latex]t = \frac { S }{ V }[/latex]), разделив расстояние между велосипедистами [latex]d[/latex] на их скорость сближения, найдем время [latex]t[/latex], спустя которое велосипедисты встретятся: [latex]t = d / (a + b)[/latex]. Муха, перелетающая с одного колеса на другое со скоростью [latex]f[/latex] достигнет момента своей погибели ровно тогда же, когда встретятся велосипедисты, то есть спустя то же время [latex]t[/latex]. Тогда, умножив скорость мухи на это время, то есть [latex]f\times t[/latex], получим расстояние [latex]flyDist[/latex], преодолённое мухой.
Для корректной реализации кода задачи сначала считываем количество тестов [latex]p[/latex], затем создаём цикл, внутри которого считываем все необходимые для вышеописанных действий переменные, производим нужные вычисления и, с помощью функции cout.precision и замечания fixed, выводим номер теста и его результат с точностью до двух десятичных знаков.

Конечно, данную задачу можно решить и используя сумму ряда, однако этот способ получился бы намного более сложным и громоздким. Поэтому такое удивительное высказывание, скорее всего, было лишь тонкой шуткой остроумного Фон-Неймана. Сам же он мог решить задачу в уме простым путем, описанным выше, но назвать более сложный, чтобы удивить современников и последователей.

e-olymp 8546. Найдите сумму

Задача

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

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+ … +\frac{1}{n\cdot(n+1)}$

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

Одно натуральное число $n$ ($n$ $⩽$ $1000$).

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

Выведите сумму с $6$ десятичными знаками.

Тесты

Входные данные Выходные данные
1 1 0.500000
2 5 0.833333
3 12 0.923077

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

Решение

Для вычисления данной суммы необходимо сложить $n$ слагаемых вида

$\frac{1}{i \cdot (i + 1)}$

начиная с $i = 1$ и с шагом в единицу до $i = n$.

Ссылки

Условие задачи на 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 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 6387. Острова в потоке данных

Задача

Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

prb6387

Напишите программу, на вход которой поступает последовательность из $15$ неотрицательных целых чисел, где каждое число отличается от предыдущего не более чем на $1$, и выводит количество островов в последовательности.

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

Первая строка содержит количество тестов $p \ (1 \leqslant p \leqslant 1000)$.

Каждый тест состоит из одной строки. Она содержит номер теста $k$, за которым следует $15$ неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны $0$. Каждое число отличается от предыдущего не более чем на $1$.

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

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

Тесты

Входные данные Выходные данные
1 4
1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0
2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0
3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0
1 4
2 7
3 7
4 7
2 3
1 0 1 2 3 2 1 0 1 2 3 4 3 2 1 0
2 0 0 1 2 2 2 1 1 1 0 0 1 1 0 0
3 0 1 1 1 2 2 2 2 3 4 3 2 2 1 0
1 7
2 3
3 4
3 6
1 0 1 2 2 2 3 4 5 6 5 4 3 2 1 0
2 0 1 0 0 0 0 1 1 1 0 1 2 1 1 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0
5 0 1 0 1 2 1 0 1 2 2 2 1 0 0 0
6 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0
1 6
2 4
3 0
4 7
5 5
6 2

Код

Решение

Для решения задачи следует выявить закономерность образования острова в последовательности. Рассмотрим подробно.
Начнем с набора наибольших чисел в последовательности. С двух сторон от него идут числа, меньшие на $1$, которые образуют между собой уже другой остров. И так пока по краям не будут нули. Соответственно, чтобы узнать количество островов в последовательности, необходимо посчитать сколько раз элемент последовательности (подпоследовательности) больше предыдущего.

Ссылки

e-olymp 798. Платформы

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

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

Первая строка содержит количество платформ $n  (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

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

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

Ввод Вывод
1 4
1 2 3 30
29
4
1 2 3 4
2 2
7 23
16
2
1 2
3 5
0 1 0 1 0
0
3
1 3 5

Код

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

  1. Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
  2. Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

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

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

e-olymp 1966. Большой плюс

Условие

На сайте в таблице результатов соревнований, проводимых по правилам ACM (Association for Computing Machinery), верно решённая задачка оценивается плюсом. Но он какой-то маленький. Выведите большой плюс из звёздочек.

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

Целое число [latex]n[/latex] ([latex]1 \leqslant n \leqslant 100[/latex]).

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

Выведите соответствующий большой квадратный «плюс» из точек и звёздочек — см. примеры входных и выходных данных.

Ввод Вывод
1 1
2 2

Решение

Задача задана немного нетривиально: не указано, каким образом число [latex]n[/latex] должно влиять на выходные данные. Однако по приведённым в условии примерам легко понять, что [latex]2n+1[/latex] — это ширина и высота плюса из звёздочек.

Печатать будем по строкам, для этого создадим главный цикл. Существует два случая: когда нужно вывести полную строку звёздочек (если [latex]u=n[/latex], то есть мы находимся в середине плюса) и когда нужно вывести обычную строку, состоящую из [latex]2n[/latex] точек и звёздочки посередине. В первом случае распечатываем [latex]2n+1[/latex] звёздочек. Во втором с помощью условия в цикле выводим звёздочку, если [latex]i=n[/latex] (центр строки), при других [latex]i[/latex] точки.

Тесты

Ввод Вывод
1 4
2 6

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

e-olimp 1658. Факториал

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные Выходные данные
3 6
0 1
20 2432902008176640000

Код № 1

Решение № 1

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

Код № 2

Решение № 2

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

e-olymp 8688. Количество чисел без 8

Задача

Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные Вывод программы
10 9
25833798135522720 4918510377816614
88888888888888 20334926626631

Continue reading