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

Решение

Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент массива меньше [latex]min[/latex], то [latex]min[/latex] присваивается значение этого элемента, и так пока не найдено наименьшее число. Каждый минимальный элемент мы перемещаем в начало, меняя его местами с предыдущим (который записывается во временную переменную [latex]prev[/latex]). В худшем случае наименьший элемент находитcя в конце, поэтому всего менять местами элементы нужно [latex]n[/latex] раз.

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

Ссылки

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

Переставить соседние

Задача

Задан массив из $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. Кількість різних елементів

Задача

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

Вхідні дані

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

Вихідні дані

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

Тести

 

Вхідні дані Вихідні дані
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

Код

Решение

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

Ссылки

 

 

 

 

e-olymp 1290. Номерной знак

Задача

Международный номерной регистрационный знак легкового автомобиля состоит из $A$ арабских цифр и $B$ больших букв латинского алфавита. Будем считать, что для обеспечения уникальности номера разрешено использовать любую последовательность букв и цифр.

Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

Тесты

Входные данные Выходные данные
1 3 3 17576000
2 2 5 67600000
3 7 1 80318101760
4 1 1 260
5 26 26 615611958020715731079667428840020377600000000000000000000000000

Код

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Сложность задачи заключается скорее не в формуле вычисления, а в реализации кода, поскольку большинство значений уже на этапе возведения в степень не помещаются даже в самые большие типы данных. Именно поэтому код состоит не из пяти строк и встроенной операции возведения в степень, а из более сложных операций, подходящих для работы с большими числами. По сути, у нас возникает проблема, связанная с перемножением больших чисел, которые не помещаются в стандартные типы данных С++. Для решения этой проблемы я выбрала модель представления, в которой числа записываются в виде массивов в десятичной системе, и каждая цифра числа является элементом массива. Младший разряд числа находится в нулевом элементе массива, а старший в $n-1$-ом соответственно. Далее была реализована функция «MULT», которая фактически осуществляет алгоритм умножения поэлементно с сохранением остатка от деления на $10$ в соответствующем элементе массива и добавлением частного от деления на $10$ к следующему элементу массива. Следует отметить, что данная функция принимает два числа, записанные в выше указанной модели представления (в виде массивов), и характеристиками этих чисел является пара: сам массив и количество разрядов в числе (размер массивов иными словами). На выходе функция возвращает количество разрядов полученного произведения. Сам же результат умножения сохраняется в виде массива, который является одним из параметров функции. В коде данная функция внесена в цикл для многократного перемножения чисел, то есть для возведения в нужную степень. Домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

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

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 9036. Комбинация игральных костей

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

Входные данные  Выходные данные
1 1 1
2 3 4
3 5 16
4 6 32
5 8 123

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

Первый способ (выполняется быстрее, но использует больше памяти)

Второй способ (использует меньше памяти, но выполняется дольше)

 

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$  . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается  $a_{5}$  и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на  $a_{7}$ и уменьшится на  $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

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

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

e-olymp 9410. Студенческая любовь

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношенияКоэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

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

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

1
2
-3 -5
3 5
0
2 1
5
-2
0
3 5
-5 -2 -1 0 4
5 4 0 0 -1
4
4 9
1000 -22 333 -56 1 2 -77 -650 10
-7 166 -333 90 -565 12 788 -800 111
523

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

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

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

Код решения ideone

e-olymp 972. Сортировка времени

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

Входные данные Выходные данные
1 [latex]\begin{matrix}
4 & & \\
10 &20 &30 \\
7 &30 &00 \\
23&59 &59 \\
13&30 &30
\end{matrix}[/latex]
[latex]\begin{matrix}
7 & 30 &00 \\
10&20 &30 \\
13&30 &30 \\
23& 59 & 59
\end{matrix}[/latex]
2 $\begin{matrix}
6\\
12 &55 &59 \\
8 &33 &34 \\
6 &56 &46 \\
10 &23 &52 \\
3 &20 &00 \\
19 &31 &0\\
10&23&52
\end{matrix}$
$\begin{matrix}
3 &20 &0 \\
6 &56 &46 \\
8 &33 &34 \\
10 &23 &52 \\
12 &55 &59 \\
19 &31 &0
\end{matrix}$

Решение

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

Ссылки

e-olymp
ideone

e-olymp 2667. Змейка

Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n × m$, которая заполнена змейкой:

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

Даны натуральные числа $n, m, x, y (1 \leqslant x \leqslant n \leqslant 50, 1 \leqslant y \leqslant m\leqslant 50)$. Здесь $n$- количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

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

Вывести элемент из строки $x$ и столбца $y$.

Решение

Для решения создаётся матрица в представлении массива размера $n* m$, который заполняется следующим образом: если текущая строка матрицы нечётная, то элемент массива принимает значение номера строки, умноженного на количество $m$ столбцов матрицы плюс номер текущего столбца,  а если текущая строка — чётная, то текущему элементу массива присваивается значение, равное произведению увеличенного на единицу номера $n$ строки на количество $m$ столбцов матрицы минус увеличенный на единицу номер текущего столбца. Для вывода значения матрицы по двум координатам мы используем элемент массива с индексом равным сумме координаты $y$ на произведение координаты $x$ на количество столбцов $m$, которое используется для «прыжка» через необходимое количество строк.

Тесты

Ввод Вывод
1 5 2 3 1 4
2 4 5 3 1 10
3 50 48 45 20 2131

Код

Ссылки

 

e-olymp 4749. Выручка театра

Задача

В театре $n$ рядов по $m$ мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ($1$ — соответствующий билет продан, $0$ — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число $n$, затем число $m$ $(n, m \le 500)$. После задана матрица стоимостей билетов ($n$ строк по $m$ чисел, каждое из чисел от $0$ до $10000$). Далее задана матрица проданных билетов — снова $n$ строк по $m$ чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

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

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

Решение

Считаем выручку, суммируя цену каждого билета, умноженную на $1$ либо $0$ в зависимости от того продан он или нет соответственно.

Ссылки

Ideone
e-olymp

e-olymp-8577. Супер платформи

Условие

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається $\left|y_2–y_1\right|$енергії, де $y_2$ та $y_1$ – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається $3·|y_2–y_1|$ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від $k_{min}$ до $k_{max}$ разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому $k_{min}$ та $k_{max}$. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ $n (1 \leq n ≤ 10000)$. Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа $k_{min}$ та $k_{max}$ $\left(0 ≤ k_{min} ≤ k_{max} ≤ \frac{n–1}{2}\right)$.

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Тесты

Ввод Вывод
1 3
1 5 10
0 1
9
2 9
1 3 2 3 8 10 25 17 25
2 4
24

Код

Решение

В решении суперприёмы из условия для удобства буду называть суперпрыжками.
Решим эту задачу динамически. На каждом шаге будем искать масив, где записано сколько минимально надо потратить энергии что б добраться до каждой платформы, сделав ровно $j$ суперпрыжков. Легко получить рекурсивную зависимость: для того, что бы попасть на $i$ платформу нам надо либо прыгнуть с предыдущей $(a_{j (i-1)}+|p_i-p_{i-1}|)$ либо сделать суперпрыжок с платформы под номером $i-2$ $( a_{(j — 1)(i — 2)} + 3|p_{i — 2} — p_i| )$. Не забудем про то, что не всегда можно прыгнуть с предыдущей так как мы могли бы и не попасть на нее за $j$ суперпрыжков. Таким образом для некоторых платформ( а именно первых в каждом масиве) мы будем делать суперпрыжок с платформы под номером $i-2$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.

Оптимизация

поскольку для генерации нового масива используется только предыдущий можно не хранить всю матрицу. Это позволит нам не засорять память.

Ссылки

e-olymp 972. Сортировка времени

Задача

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

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

Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно).

Тесты

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

1

4
10 20 30
7 30 00
23 59 59
13 30 30
7 30 0
10 20 30
13 30 30
23 59 59

2

5
12 40 45
23 56 12
7 45 34
8 23 34
2 56 45
2 56 45
7 45 34
8 23 34
12 40 45
23 56 12

3

3
23 56 45
21 45 54
6 45 23
6 45 23
21 45 54
23 56 45

Код 1

Код 2

Решение задачи (код 1)

Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().

Решение задачи (код 2)

Для решение задачи вторым способом создадим структуру unsortedtime. Каждый элемент в этой структуре будет соответствовать часу, минуте, секунде. После чего создадим оператор > , в котором будем сравнивать моменты времени. В случае необходимости будем менять их местами, используя функцию swap(). В результате выведем с помощью цикла моменты времени, упорядоченные в порядке неубывания.

Ссылки

  • Условие задачи на 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

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 4749. Выручка театра

Задача

В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). После задана матрица стоимостей билетов ([latex]n[/latex] строк по [latex]m[/latex] чисел, каждое из чисел от [latex]0[/latex] до [latex]10000[/latex]). Далее задана матрица проданных билетов — снова [latex]n[/latex] строк по [latex]m[/latex] чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

Входные данные Выходные данные
1 3 3 25
1 2 3
4 5 6
7 8 9
1 0 1
0 1 0
1 0 1
2 2 2 0
1 1
2 2
0 0
0 0
3 4 5 380
15 16 17 18 19
19 18 17 16 15
19 20 21 22 23
23 22 21 20 19
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

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

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

Описываем целочисленный одномерный массив x [500*500] для хранения матрицы стоимостей билетов. Описываем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] (количество строк и столбцов матрицы) и считываем их. Описываем целочисленную переменную [latex]nm[/latex] (количество мест в зале) и инициализируем ее произведением [latex]n \cdot m[/latex]. Цикл инициализирует [latex]nm[/latex] элементов массива [latex]x[/latex]. Описываем целочисленную переменную [latex]k[/latex], которая принимает значения [latex]0[/latex] или [latex]1[/latex] (билет не продан или продан), и целочисленную переменную [latex]v[/latex] — стоимость проданных билетов ([latex]v[/latex] имеет тип long long int, так как максимальное значение, которое она может принять, составляет [latex]500 \cdot 500 \cdot 10000=2500000000[/latex]). Цикл считывает значения [latex]k[/latex] и увеличивает [latex]v[/latex] на k*x[i].

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

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

По условию заданы количество строк [latex]n[/latex] и количество столбцов [latex]m[/latex] матрицы стоимости театральных билетов ( [latex] n,m\leqslant 500[/latex], каждое из чисел от [latex]0[/latex] до [latex]10000[/latex] ). Описываем целочисленную матрицу x[500][500]. Объявляем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] и вводим их значения с клавиатуры. Считываем матрицу x. Объявляем переменную unsigned long long v = 0 — стоимость проданных билетов. Целочисленная переменная [latex]p = 1[/latex], если билет на ( [latex]i,j[/latex] )-е место продан, и [latex]p = 0[/latex] — в противном случае. Во вложенных циклах считываем значение [latex]p[/latex] из матрицы проданных билетов. Проверяем [latex]p[/latex] на положительность и увеличиваем [latex]v[/latex] на стоимость билета на ( [latex]i,j[/latex] )-е место.

Ссылки

e-olymp
ideone (код с одномерными массивами)
ideone (код с многомерными массивами)

e-olymp 2524. Строки Фибоначчи

Задача

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $n$ растет очень быстро, поэтому задача нахождения всех символов строки $F_{n}$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F_{n}$.

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

Первая строка содержит количество тестов $t$ ($1 ≤ t ≤ 100$). Каждая из следующих $t$ строк содержит два целых числа $n$ и $k$ ($0 ≤ n ≤ 45$, $1 ≤ k ≤ |F_{n}|$, через $|F_{n}|$ обозначена длина строки $F_{n}$, позиции символов в строке нумеруются с единицы).

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

Выведите $t$ строк, каждая из которых содержит $k$-ый символ строки $F_{n}$.

Тесты

Входные данные Выходные данные
4
0 1
1 1
3 2
7 7
a
b
a
a
1
10 15
a
6
45 6
38 30
6 5
24 40
0 1
2 2
b
a
b
b
a
b

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

Решение

Воспользуемся тем, что длина $i$-той строки Фибоначчи будет равна $i$-тому числу Фибоначчи, так как для них справедливо одно и то же рекуррентное соотношение. Заводим массив fib[45]; , куда мы вычислим первые ($n ≤ 45$) числа Фибоначчи. Функция solve(int n, int k)  находит $k$-ый символ строки $F_{n}$: так как $F_{i} = F_{i-2}F_{i-1}$, то если $k ≤ |F_{n-2}|$, то $k$-ый символ строки следует искать в $F_{n-2}$, в другом случае следует искать $(k — F_{n-2})$-ый символ в $F_{n-1}$. Таким образом, постепенно углубляясь в рекурсию, программа будет иметь дело с задачами все меньших размеров, пока наконец не выйдет на одну из единичных строк ( n == 0  или n == 1 ), и не выведет $a$ или $b$ соответственно.

Ссылки

Условие задачи на 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 8173. Большинство

Задача

Голоса собраны! Были опрошены математики по всему миру, и каждый из них выбрал свой любимый номер между [latex]1[/latex] и [latex]1000[/latex]. Ваша цель — подсчитать голоса и определить самый популярный номер.

Если существует несколько голосов с наибольшим количеством, то выберите наименьшее число с максимальным количеством голосов.

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

Первая строка содержит количество тестов, от [latex]1[/latex] до [latex]100[/latex] включительно. Первая строка каждого теста содержит количество голосов [latex]V (1 \leq V \leq 1000)[/latex], за которой следуют [latex]V[/latex] строк — каждая из них содержит одно число от [latex]1[/latex] до [latex]1000[/latex].

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

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

Тесты

Входные данные Выходные данные
1 2
3
42
42
19
4
7
99
99
7
42
7
2 1
5
11
12
13
14
15
11
3 2
2
1000
1000
1
3
1000
3

Код

Решение

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

Ссылки

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