e-olymp 6350. Изированная вода

Задача

Изированная вода

В Бердичеве ещё в советские времена продавалась знаменитая изированная вода. Собственно это была обычная газировка на разлив, но продавал её Изя, поэтому и воду все называли изированной. Продавец газировки был человеком не только очень умным и добродушным, но и очень сообразительным. О складе его ума говорит хотя бы тот факт, что у него было $2$ диплома о высшем образовании: он закончил физмат пединститута и мехмат университета, а о сообразительности – то, что имея два диплома, он продавал газировку и довольно успешно. Старожилы утверждают, что попить его газировки прилетали в те времена даже с самой Москвы…

Изя, герой задачи

С постоянными покупателями, и не только с ними, Изя был очень общительным человеком, и иногда, как говорится «под настроение клиента», задавал им свои задачки на сообразительность, которых у него в запасе было великое множество. Одна из подобных его задачек приведена в задаче «Покупка воды». Задав подобную задачку, он ждал от клиента быстрого, сообразительного и, главное, верного ответа на неё, если же ответ запаздывал, или был не верным, Изя всегда говорил что-то типа: «Молодой человек, придёте завтра – Вы сегодня не заслужили на обслуживание». Естественно, это была шутка и клиент всё равно имел возможность приобрести очень вкусную изированную воду.

Перед тем как сформулировать наш вопрос, напомним задачку, упоминаемую выше: «Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет $1$ руб. $20$ коп., а стоимость пустой бутылки – $20$ коп. Сколько бутылок воды можно выпить на $N$ руб., учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды?».

Нас же будет интересовать ответ на следующий вопрос: «А сколько покупателей услышали сегодня от Изи фразу «Приходите завтра!»?».

Входные данные
В первой строке входных данных находится единственное число $N(1≤N≤106)$  — количество покупателей, которым Изя задавал упоминаемую в условии задачку.

В последующих $N$ строках задано через пробел $N$ пар чисел, первое из которых — количество денег в кошельке перед началом операции «Покупка ГазВоды», а второе — ответ покупателя.

Все входные данные — целые неотрицательные числа, не превышающие $10^6$.

Выходные данные
Вывести единственное число — количество покупателей, услышавших от продавца ответ «Придёте завтра» и при этом ответили неправильно. Подсчитывать же тех, кто долго думал, не обязательно, за Вас это сделает проверяющая система вердиктом TL (Time Limited).

Тесты

Входные данные Выходные данные
5
2 1
2 2
1 2
1 1
2 1
3
3
45 45
38 37
12 10
2
3
5 4
7 6
3 2
0
2
1280 1280
1900 1899
1
7
1 1
2 2
3 2
6 5
6 6
7 3
2 2
5

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

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

Для решения этой задачи необходимо решить задачу «Покупка воды». Решение очень простое: количество бутылок воды, которое можно выпить на $n$ грн. равно $n — 1$.

Используем это в цикле для проверки на правильность ответа покупателя. Если ответ неправильный, то увеличиваем переменную  j , которая считает количество неправильных ответов, на один, и, после завершения цикла, выводим ее значение.

Так же для реализации задачи на Java нам необходимо ускорить ввод и вывод данных. Метод, который использовался, приведен в одной из статей на сайте – Ввод данных: Scanner vs StreamTokenizer.

Ссылки

Код задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 2669. Поворот

Поворот

Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 2

1 2

3 4

2 2

3 1

4 2

2 3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

4 1 2

5 4

2 1

5

4

5 1 1

2

1 1

2

 

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

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

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

e-olymp 921. Отрицательные элементы

Отрицательные элементы

Задан одномерный массив вещественных чисел длины [latex]n[/latex]. Определить сумму и количество отрицательных элементов в массиве.

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

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

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

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

Тесты

# ВХОДНЫЕ ДАННЫE: ВЫХОДНЫЕ ДАННЫЕ:
1 5

6 -7.5 2.1 -2.0 0

2 -9.50
2 2
-1 -2
2 -3.00
3 6

1 1 1 1 1 1

0 0.00
4 7
-1.99 -5.34 9 6.43 -6.32 0 -7.43
4 -21.08
5 3
-1.992345 -5.334224 9
2 -7.33

 

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

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

Для решения данной задачи я описал две переменные: [latex]m[/latex] типа [latex]int[/latex] и [latex]k[/latex] типа [latex]double[/latex], которые изначально равны [latex]0[/latex]. Цикл ищет в массиве элементы которые меньше [latex]0[/latex]. C каждым найденным отрицательным элементом, [latex]m[/latex] увеличиваться на [latex]1[/latex], а к числу [latex]k[/latex] прибавляется сам элемент.

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

e-olymp 519. Сумма квадратов

Условие задачи
Найти сумму квадратов двух чисел.
Входные данные
Два целых числа $a$ и $b$. Числа не превышают $10^9$ по абсолютной величине.
Выходные данные
Выведите одно целое число $a^2+b^2$
Тесты

Входные данные Выходные данные
2 2
8
5 5
50
-5 -2
29
500 500
500000
1210 1250
3026600

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

Решение задачи
Создаем 2 переменные a и b, в которые записываем данные, дальше выводим на экран одно целое число, которое равно $a^2+b^2$.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 4475. Часы

Задача

Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

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

Входной файл содержит в единственной строке натуральные числа $S, M, H, K$ (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно), причем:

  • $S, M, H ≤ 60$;
  • $S+M+H-2≤K≤1000$

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

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

Тесты

Входные данные Выходные данные
$5$ $12$ $12$ $30$ $380$
$7$ $10$ $40$ $70$ $5610$
$60$ $60$ $60$ $500$ $4560840$
$60$ $30$ $5$ $1000$ $4970$

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

Алгоритм решения

  1. Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
  2. Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
    $\begin{pmatrix}
    1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\
    1& 5& 8& 2& 4& 3& 7& 7& 6& 10
    \end{pmatrix}$
  3. Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Примечание

Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 1611. Реверс подстроки

Задача

Дана строка $s$, в которой выделили подстроку, состоящую из символов с $i$-го по $j$-ый включительно (символы строки $s$ нумеруются с единицы) и поменяли местами $i$-ый символ с $j$-ым и так далее (конвертировали подстроку). Выведите строку $s$ после внесенных изменений.

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

В первой строке содержится строка $s$ длиной не более $1000$ символов, во второй — два числа $i$ и $j$ $\left ( i \leq j \right ).$

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

Выведите строку $s$ после внесенных изменений.

Тесты

Входные данные Выходные данные
$zbbg \\ 2 \ 3$ $zbbg$
$gaqipkajibk \\ 5 \ 6$ $gaqikpajibk$
$helloworld \\ 5 \ 7$ $helloworld$
$eolymp1611 \\ 7 \ 8$ $eolymp6111$

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

Решение

Для решения задачи вводим строку $str$ и преобразуем её в массив символов $(char)$. Далее в цикле конвертируем подстроку и выводим строку $s$ после внесенных изменений.

Ссылки

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

Код решения задачи ideone

e-olymp 2667. Змейка

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
$5 \ 2 \ 3 \ 1$ $4$
$6 \ 3 \ 4 \ 3$ $9$
$10 \ 5 \ 10 \ 2$ $48$

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

Решение

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.

Ссылки

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

Код решения задачи ideone

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

Задача

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

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

В первой строке задано количество элементов массива $n\left ( 0 < n \leq 100 \right )$. В следующей строке задано $n$ вещественных чисел.

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

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

Тесты

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

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

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

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

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

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

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

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

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

Ссылки

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

Код решения с помощью потоковой обработки на ideone

Код решения с помощью массивов на ideone

e-olymp 7368. Средний балл для фигуристов

Задача


Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей [latex](0 < n \leqslant 10, 0 < m \leqslant 100)[/latex] для каждого из фигуристов.

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

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

Тесты

# Входные данные Выходные данные
1 5 4
7 8 9 8 10
6 5 5 4 7
9 9 10 7 7
7 7 10 9 8
8.33 5.33 9.00 8.50
2 6 3
6 7 6 5 4 3
9 8 5 5 6 5
7 6 4 1 2 2
5.25 7.00 3.50
3 4 5
6 7 8 6
9 8 5 4
7 6 7 5
4 3 9 3
7 8 7 6
7.00 6.50 6.00 4.00 7.00
4 4 4
7 7 2 3
9 8 3 3
5 4 9 7
4 3 2 6
3.00 8.00 6.00 3.50
5 8 5
4 5 6 7 7 4 9 8
3 5 6 6 7 8 5 9
7 6 3 9 3 7 9 7
5 6 4 3 7 7 5 7
9 8 4 6 7 9 9 4
6.60 6.17 6.75 5.00 7.00

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

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

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные [latex]a[/latex] и [latex]b[/latex] — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной [latex]x,[/latex] и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле [latex]n — a — b.[/latex] А затем вычисляем среднее арифметическое для оставшихся значений по формуле [latex]\displaystyle\frac{sum}{n — a — b}[/latex] и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

AA19

Задача

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

Тесты

Входные данные Выходные данные
the more I code … better my coding becomes the more I code the better my coding becomes
…what am I supposed to do? …what am I supposed to do?
abc…….. abcabcabc..

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

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

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

Ссылки

Код решения