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 2662. Метод минимума

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

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

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

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

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

Вывести количество перемещений первого элемента.

Тесты

Ввод Вывод
1 3

1 3 2

0
2 2

2 1

1
3 4

4 1 5 3

3
4 6

23 5 56 2 87 3

1
5 7
15 1 6 3 9 8 13
4

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

Решение

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

Подробное изложение алгоритма сортировки можно найти в  этой статье .

Ссылки

e-olymp 2663. Сортировка пузырьком

Условие

Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$$9$.

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

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

Ввод Вывод
1 3
1 3 2
1
2 2
2 1
1
3 4
4 1 5 3
3
4 5
5 4 1 100000 7
4
5 6
6 5 4 3 2 1
15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

Ссылки

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

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 7849. Обменять max и min

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

Задан массив из $n$ целых чисел. Замените все наибольшие его элементы на наименьший, а наименьшие элементы на наибольший.

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

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

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

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

Тесты

Входные данные Выходные данные
1 7
3 5 -7 7 5 -9 -4
3 5 -7 -9 5 7 -4
2 2
1 2
2 1
3 9
12 99 87 42 55 8 65 40 72
12 8 87 55 99 65 40 72
4 8
-9 0 7 -5 2 5 1 -2
7 0 -9 -5 2 5 1 -2

Код

Решение

Для начала нам надо найти максимум и минимум в массиве. Для этого введем переменные максимума и минимума равные  $-100$ и $100$. (Так как элементы массива по условию не должны превышать значения $|100|$ ). Проверяем. Если значение элемента массива больше значения переменной максимума, присваиваем переменной это значение. Аналогично и для минимума. Затем присвоим максимальному элементу массива минимальное, а минимальному — максимальное.

Ссылки

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

Код на Ideone

Засчитанное решение на 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 7534. Замкнутое сокровище

Задача взята с сайта e-olymp

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

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

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

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

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

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 4
3 2
5 1
10 7
5 3
3
1
210
10
2 2
5 3
3 2
10
3
3 6
2 1
7 2
3 1
5 4
3 2
9 2
1
7
1
10
3
9

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

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.
Для нахождения биномиальных коэффициентов воспользуемся треугольником Паскаля, который будем хранить в двумерном массиве.

Ссылки

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

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

Треугольник Паскаля на Wikipedia

e-olymp 682. Сумма на отрезке

Задача

Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$

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

В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.

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

Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.

Тесты

# Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 5
2 3
3 4
2 5
1 4
15
5
7
14
10
2 10
10 10 10 10 10 10 10 10 10 10
5
1 3
3 5
5 7
7 9
3 7
30
30
30
30
50
3 10
57 42 24 73 98 71 65 76 12 33
7
1 2
4 5
8 10
1 10
7 10
2 5
3 8
99
171
121
551
186
237
407
4 3
10 15 20
2
1 2
1 3
25
45
5 7
299 38924 2388 4399 7549 79475 57947
10
1 3
2 3
3 3
4 7
6 7
3 5
5 5
6 6
1 6
1 7
41611
41312
2388
149370
137422
14336
7549
79475
133034
190981

Решение

Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 2099. Два массива

Задача

Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.

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

Сначала подаётся количество [latex]n[/latex] элементов в первом массиве, затем [latex]n[/latex] чисел — элементы массива. Затем записано количество [latex]m[/latex] элементов во втором массиве. Далее заданы элементы второго массива. Количество элементов каждого массива не превышает [latex]100[/latex]. Все элементы — целые числа.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
1 7
3 1 3 4 2 4 12
6
4 15 43 1 15 1
4
3 3 2 12
2 5
12 16 17 45 68
6
1 93 45 68 34 38
3
12 16 17
3 10
15 47 68 59 75 25 35 61 21 86
10
15 47 69 58 75 26 36 61 21 89
5
68 59 25 35 86
4 10
15 47 68 59 75 25 35 61 21 86
10
15 47 68 59 75 25 35 61 21 86
0
0

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

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

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

Ссылки

e-olymp 2322. Столбцы

Столбцы

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

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

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 109. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 109 — числа в ячейках таблицы.

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

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1
2
0 1
0 0
NO
YES
2 23
3
23 0 23
21 12 23
11 13 23
YES
NO
YES
3 7
1
0
NO
4 13
3
13 33 75
23 45 31
13 13 13
YES
YES
YES

Код

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

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

e-olymp 8361. Робот

Задача взята с сайта e-olymp

Условие

Движение робота управляется программой. Программа состоит из следующих команд:

  • [latex]S[/latex] — сделать шаг вперед
  • [latex]L[/latex] — повернуться на [latex]90°[/latex] влево
  • [latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

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

Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

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

Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].

Тесты

Inputs Outputs
1 SSLSLSLSSRSRS 5
2 LSSSS -1
3 LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS 15
4 LLLLLLLL -1
5 SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL 7

Код

Решение

Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

Ссылки

e-olymp 5057. Спиралька

Задача

Выведите двумерный массив, размерами [latex]n \times n[/latex], заполненный числами от [latex]1[/latex] до [latex]n^2[/latex] по спирали. Числовая спираль начинается в левом верхнем углу и закручивается по часовой стрелке.

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

Одно число [latex]n (1 \leqslant n \leqslant 10)[/latex].

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

Выведите [latex]n^2[/latex] чисел – заполненный по спирали массив.

Тесты

Ввод Вывод
1 1 1
2 2 1 2
4 3
3 3 1 2 3
8 9 4
7 6 5
4 5 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
5 9 1 2 3 4 5 6 7 8 9
32 33 34 35 36 37 38 39 10
31 56 57 58 59 60 61 40 11
30 55 72 73 74 75 62 41 12
29 54 71 80 81 76 63 42 13
28 53 70 79 78 77 64 43 14
27 52 69 68 67 66 65 44 15
26 51 50 49 48 47 46 45 16
25 24 23 22 21 20 19 18 17

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

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

Все решение задачи сводится к тому, чтобы постепенно заполнять крайние квадраты, «окаймляя» внутренность массива и постепенно сужая диапазон заполнения и длину стороны заполняемого квадрата. В основном цикле вложенными циклами поочередно заполняем строки и столбцы: верхнюю, крайний справа, нижнюю, крайний слева. После «сворачиваем» вправо, когда вложенные циклы заканчиваются и во внешнем(основном) счетчик увеличивается на 1. Полный цикл на n действий делать смысла не имеет в силу того, что, дойдя до половины, массив уже будет полностью заполнен в строках ниже.

Ссылки

e-olymp 5282. Седловые точки

Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

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

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

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

Выведите количество седловых точек.

Тесты

Ввод Вывод
1 2 2
0 0
0 0
4
2 2 2
1 2
3 4
1
3 5 5
100 -100 100 1000 110
10 -1000 100 -1000 110
100 -1000 100 100 110
1000 -1000 1000 1000 100
1000 -1000 1000 1000 -1000
1
4 4 4
1000 1000 100 100
1000 1000 1000 1000
100 100 100 1000
100 1000 1000 1000
4
5 2 3
1 -1 1
0 -1 0
2
6 5 1
-1
0
-1
0
-1
2
7 4 2
1 2
-2 1
-1 2
-2 -1
1
8 3 3
5 1 3
3 1 2
1 1 2
3
7 3 3
5 2 3
3 4 2
1 8 2
0

Решение

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

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

e-olymp 2666. Половина

Задача

Напишите программу, заполняющую массив [latex]n \times n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

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

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

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

Выведите массив, заполненный по указанному правилу.

Тесты

# Входные данные Выходные данные
1 2 20
01
2 3 220
201
011
3 4 2220
2201
2011
0111
4 5 22220
22201
22011
20111
01111
5 10 2222222220
2222222201
2222222011
2222220111
2222201111
2222011111
2220111111
2201111111
2011111111
0111111111

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

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

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20[/latex]. Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

  • [latex]i + j = n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит на побочной диагонали;
  • [latex]i + j > n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит ниже побочной диагонали;
  • [latex]i + j < n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит выше побочной диагонали.

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 7809. Утренняя зарядка

Задача


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

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

Единственная строка входного файла содержит последовательность чисел, записанных через пробел, означающие цвет футболки. Цвет — число в диапазоне от [latex]0[/latex] до [latex]9[/latex]. Всего в строке не более, чем [latex]10^6[/latex] чисел.

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

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

Тесты

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

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

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

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

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 907. Первый не больший чем 2.5

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

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

В первой строке задано количество элементов массива [latex]n (0 < n ≤ 100)[/latex]. В следующей строке задано [latex]n[/latex] вещественных чисел.

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

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные Выходные данные
[latex]5 \\ 6 \; 7.5 \; 2.1 \; 2.0 \; 0[/latex] [latex]3 \; 2.10[/latex]
[latex]5 \\ 6 \; 7.5 \; 5.1 \; 7.0 \; 80[/latex] [latex]Not \; Found[/latex]
[latex]7 \\ 5 \; 4.7 \; 50 \; 8.9 \; 2.7 \; 3 \; 1.5[/latex] [latex]7 \; 1.5[/latex]

Решение задачи с помощью массивов

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

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

Введем обозначения: [latex]x[/latex] – имя массива, [latex]n[/latex] – количество элементов в массиве, [latex]i[/latex] – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести Not Found.

Решение задачи с помощью потоковой обработки

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

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

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найдененого первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, выводим на экран Not Found.

Ссылки

Условие задачи на e-olymp
Код решения с помощью массивов на ideone
Код решения с помощью потоковой обработки на ideone

e-olymp 2807. Кубики — 3

Задача

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

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

В первой строке задано количество найденных Витеком кубиков [latex]n (1 ≤ n ≤ 10^5)[/latex], а во второй строке [latex]n[/latex] символов, изображённых на каждом из кубиков.

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex] «Ok»[/latex], если Витек ошибся и ни один из кубиков не потерялся.

Тесты

# Входные данные Выходные данные
1 5 abcac b
2 8 ryirhiyh Ok
3 3 AVA V
4 6 DjkjDk Ok
5 7 LnCsCnL s

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

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Если условие выполняется, то выводим на экран сообщение с текстом [latex] «Ok»[/latex]. Если нет, то рассматриваем второй случай. Создаем массив, в котором будем хранить количество кубиков для каждой буквы. Обнуляем ячейки массива, в которых будут храниться данные. Далее мы будем считывать символы в соответствии с их числовыми кодами. После прочтения входного потока, найдем элемент массива с нечетным числом вхождений и выведем его на экран.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 4496. Приключение Незнайки и его друзей

Задача с сайта e-olymp.com.

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

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

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

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

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

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

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

Тесты

Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
3
2
2
0
2 2
1 2
3
1 4
2 1 10
1 4
2
0
3 2
999999999 1000000000
4
1 999999999
2 1 1000000000
1 999999999
1 1000000000
1
0
1

Код на C++

Код на Java

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.

A302. Количество различных цифр числа в его десятичной записи

Задача

Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?

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

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

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные Выходные данные
[latex]N[/latex] [latex]sum[/latex]
12345678900987654321 sum:10
302 sum:3

Код программы с использованием deque

 

Решение

Создадим дэк [latex]folder[/latex] в котором будем хранить различные цифры десятичной записи. Добавляем первую цифру числа [latex]N[/latex] в дэк и делим [latex]N[/latex] на [latex]10[/latex]. Следующие цифры мы будем добавлять после проверки на отсутствие таких же в [latex]folder[/latex], если цифры совпадают заканчиваем цикл. В конце выводим размер [latex]folder[/latex] который и является [latex]sum[/latex].

Код программы с использованием массива

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).

Душевая кабина

Разбор задачи F с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача

Степан приобрел душевую кабину, которую решил установить в дачном домике. Дачный домик представляет собой прямоугольник [latex]N \times M[/latex], разбитый на одинарные квадратики. Степан знает, что душевая кабина занимает ровно две клетки с общей стороной. Также Степану известно, что некоторые клетки дома заняты разными вещами. Помогите Степану узнать сколькими способами он может разместить душевую кабину в дачном домике.

 

Ввод

В первом ряду входных данных находятся два целых числа  [latex] N,M(1<=N,M<=1000)[/latex] — размеры дачного домика Степана. Каждый из следующих [latex] N[/latex] рядов содержит по  [latex] M[/latex] символов — описание дачного домика Степана. Символ «#» означает, что соответствующая клетка уже чем-то занята, а символ «.» — что она свободна и может стать одной из двух, занятых душевой кабиной.

Вывод

Одно число — количество способов расположить душевую кабину в дачном домике.

Тесты

Код

Решение

Считываем символы в массив . Размер такого массива всегда будет [latex]n \times m[/latex]. Зная это, заводим цикл, в котором проверяем наличие точки(‘.’). Затем проверяем первое условие: если следующий символ тоже точка и если мы не перешли на новую строку, увеличиваем счетчик. Зная количество символов в каждой строке, проверяем символ «под» точкой и если они совпадают опять же увеличиваем счетчик.