e-olymp 2691. Проходной балл

Задача

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

Формат входных данных

В первой строке дано число $N$ ($1 \leqslant N \leqslant 10000$), количество учащихся в списке. Каждая из следующих $N$ строк имеет вид: фамилия и имя, затем число $M_i$ ($1 \leqslant M_i \leqslant 50$) — количество предметов, которые изучал ученик, а затем годовые оценки по каждому из этих предметов.
В последней строке дано единственное число $K$ — проходной балл. Фамилия и имя — строки, состоящие не более чем из $20$ латинских букв. Все числа во входном файле натуральные и не превышают $10^9$.

Формат выходных данных

Требуется вывести список ребят, которые могут быть зачислены.

Тесты

Входные данные Выходные данные
1 3
Ivanov Ivan 2 7 9
Petrov Petr 1 7
Sidorov Sidor 2 10 8
4
Ivanov Ivan
Petrov Petr
Sidorov Sidor
2 1
Ivanov Ivan 1 6
5
Ivanov Ivan
3 4
Petrov Petr 10 1 2 3 4 5 6 7 8 9 10
Sidorov Sidor 5 8 8 8 4 4
Ivanov Ivan 0
Darienko Dasha 3 10 3 9
6
Sidorov Sidor
Darienko Dasha
4 2
Petrov Petr 10 1 2 3 4 5 6 7 8 9 10
Darienko Dasha 3 10 3 9
11
5 5
Petrov Petr 10 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000
Darienko Dasha 5 500000000 500000000 500000000 700000000 800000000
Sidorov Sidor 20 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 500000000 500000000 500000000 700000000 800000000 500000000 500000000 500000000 700000000 800000000
Ivanov Ivan 8 600000000 600000000 600000000 800000000 200000000 1000000000 300000000 300000000
Sergeev Alexandr 1 700000000
600000000
Darienko Dasha
Sergeev Alexandr

Код

Оптимальное решение:

Более структурированное решение:

Решение

Введем данные в соответствующие структуры (см. комментарии в коде), вычислим средние баллы для каждого ученика и выведем фамилии и имена всех тех и только тех, чей средний балл выше проходного.
Т. к. все исходные данные натуральные и не превышают $10^9$ используем для их ввода тип int. При этом сумма оценок может выйти за пределы типа int ($50\cdot10^9 > 2 147 483 647$), поэтому для переменной sum используем тип long. Также заметим, что среднее арифметическое натуральных чисел может быть дробным числом, но в данном случаи средний проходной балл $K$ по условию являет натуральным числом, поэтому будет уместно отбросить дробную часть при сравнении, т. е. использовать целочисленных тип данных в вычислениях.

Ссылки

  • Задача на e-olymp
  • Код оптимального решения на ideone
  • Код решения со структурами на решения со структурами на ideone
  • Засчитанное оптимальное решение на e-olymp
  • Засчитанное структурированное решение на e-olymp
  • e-olymp 6941. Сумма НОД

    Задача

    Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

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

    В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

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

    Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

    Тесты

    Входные данные Выходные данные
    1 3
    4 10 20 30 40
    3 7 5 12
    3 125 15 25
    70
    3
    35
    2 2
    3 12 7 8
    4 5 14 25 11
    6
    10
    3 4
    4 5 6 7 8
    4 8 6 2 9
    3 2 15 6
    5 12 25 29 19 11
    7
    11
    6
    10

    Код

    Решение

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

    Ссылки

    E-Olymp 568. Средняя зарплата

    Условие

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

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

    Заработные платы работников (не обязательно в одной строке) в гривнах.

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

    Средняя зарплата на предприятии в гривнах с точностью 2 знака после десятичной точки.

    Тесты

    Входные данные Выходные данные
    1 100.50 300.50  200.50
    2 800 950 600.25 200.50  637.69
    3 1000 1200.50 790 600 980  914.10

    Код

    Решение

    Для того чтобы посчитать среднюю зарплату, нам нужно знать сумму зарплат всех работников sum  и количество работающих n. Прибавляем к сумме зарплаты z  до тех пор, пока есть что считывать из вводных данных. В тоже время считаем количество раз, чтобы узнать, сколько всего работников на предприятии. Выводим среднее арифметическое и указываем количество цифр после запятой.

    e-olymp 1602. НОК двух натуральных чисел

    Задача

    Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

    Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

    Вывести $НОК$ чисел $a$ и $b$.

    Тесты

    Входные данные Выходные данные
    1 42 24 168
    2 32 14 224
    3 101 45 4545

    Код

    Решение

    Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
    $1$. Большее число делится на меньшее.
    $2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
    $3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
    После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

    Ссылки

    E-Olymp 7029. Поликлиника

    Задача

    На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени $t_1$ минут и заканчивает прием в момент времени $t_2$ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты $t_1, t_1 + 1, …, t_2 − 1$. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент $t$, он ожидает первый момент времени $s ≥ t$ такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента $t$. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

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

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

    В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема $t_1$ и время завершения приема $t_2$, больший чем $t_1$.

    Во второй строке перечислены $n$ чисел $a_1, a_2, …, a_n$ — время, когда в поликлинику зашли соответственно первый, второй, $…, n$-ый желающий попасть к доктору. Числа $a_1, a_2, …, a_n$ попарно различны и расположены в порядке возрастания.

    В третьей строке перечислены n чисел $b_1, b_2, …, b_n$ — время, необходимое доктору на осмотр соответственно первого, второго, $…, n$-го пациента.

    Все входные числа натуральные. Количество пациентов $n$ не больше $10^5$, остальные числа не превосходят $10^9$.

    Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема $t_1$, время завершения приема $t_2$, а также числа $a_1, a_2, …, a_n$ и $b_1, b_2, …, b_n$ могут быть большими чем 1440 — количество минут в земных сутках.

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

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

    Тесты

    Входные данные Выходные данные
    1 3 10 20
    7 14 18
    5 2 1
    17
    2 5 10 20
    4 9 12 16 22
    4 10 10 9 2
    9
    3 1 10 20
    5
    15
    5

    Код

    Решение

    Создаём два массива, удовлетворяющих условия, a — время прихода пациентов и b — время на их приём. Инициализируем все необходимые переменные: t_1 и t_2 — время приёма, t — время в которое Петя должен прийти, n- кол-во пациентов, i и j — счётчики, l — время между приходом пациента и началом его приёма.

    Проверяем приходит ли первый пациент в самое начало приёма или после начала приёма, если в начало приёма — то приходим тогда.

    В цикле while определяем минимальное время, в которое Петя может прийти на приём к врачу. Проверяем приходит ли следующий пациент до завершения приёма предыдущего. Если приходит во время завершения, или через некоторое время, то заходим после приёма предыдущего. (Нам уступают) Если нет, цикл продолжается, проверяет, является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разницы. Если да — записывает её и время прихода данного пациента, и переходит к следующему пациенту.       

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

    e-olymp 1243. Наименьшее общее кратное

    Условие

    Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

    Вам необходимо найти $НОК$ $m$ заданных чисел.

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

    Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

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

    Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

    Тесты

    ввод вывод
    1 2
    3 5 7 15
    6 4 10296 936 1287 792 1
    105
    10296
    2 3
    1 36
    5 2 2 2 2 2
    5 987 1597 2584 4181 6765 10946 17711
    36
    2
    38400890173772280
    3 0

    Код

    Код с алгоритмом Евклида

    Решение

    $\DeclareMathOperator{\lcm}{lcm}$
    $НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

    $НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

    Ссылки

    e-olymp 1679. Честная цепочка

    Условие

    В подземных норах в долине рядом со скалами Крейд-Моор долгое время жили в мире и согласии два гномьих племени. Гномы обоих племен работали в шахтах, добывая драгоценные камни. Первое племя добывало исключительно изумруды, а второе племя — рубины. Однажды в честь великого праздника Файрвинд гномы решили принести в дар своей богине Мирабель цепочку из изумрудов и рубинов. Самые искусные кузнецы обоих племен работали над созданием этой цепочки, собирая на ней один за одним драгоценные камни. Но как только работа была окончена, решили вожди племен пересчитать камни каждого вида. Ведь если каких-то камней окажется меньше, то богиня может отвернуться от племени, которое пожадничало. Чтобы избежать подобных последствий, было решено подарить некоторый непустой фрагмент цепочки (то есть цепь, состоящую из нескольких камней, расположенных друг за другом в исходной цепочке), в котором будет рубинов ровно столько же, сколько и изумрудов. Возможно это может быть сделано несколькими способами. Для того, чтобы узнать сколько таких способов существует, гномы обратились за помощью к вам.

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

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

    В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

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

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

    Тесты

    ввод вывод
    1 REER 3
    2 REERREER 12
    3 RRRRRRRR 0
    4 EREREERERERREREREEERERERERERRREREREERERERERE 273
    5 REEERREE 7

    Код

    Компактный код

    Решение

    Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

    Наглядный пример такого массива для пятого примера (подписан как cnt)

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

    Выделенные в том же примере фрагменты с началом и концом в 0 и -2

    Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
    Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

    Ссылки

    e-olymp 7095. Факторіали

    Задача

    Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

    Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

    • при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
    • при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

    За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

    Вхідні дані

    Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

    Вихідні дані

    Вихідний файл має містити рівно три цифри — шуканий код.

    Тесты

    Входные данные Выходные данные
    1 7 504
    2 17 096
    3 50 512
    4 1000000000 144

    Код

    Решение

    Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:

    Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

    Ссылки

    e-olymp 7213. Шашка на кубе

    Условие

    Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

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

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

    Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

    Вывести искомое количество способов.

    Тесты

    l m вывод
    3 3 1
    3 4 0
    3 5 25
    51 199 4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
    3 199 11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

    Код

    Решение

    Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
    Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

    Раскладка шести граней куба с переходами между границами

    Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

    Оптимизированный вариант хранения куба

    Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

    Ссылки

    e-olymp 7023. Тасование Ханафуда

    Задача

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

    Card shuffling example

    Имеется колода из $n$ карт. Начиная с $p$-ой карты сверху, $c$ карт вынимаются и кладутся на вершину колоды, как показано на рисунке. Такую операцию назовем операциею срезки.

    Напишите программу, которая моделирует перетасовку Ханафуда, и выведет номер карты, которая в конце будет находиться наверху.

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

    Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два натуральных числа $n$ $(1 ≤ n ≤ 50)$ и $r$ $(1 ≤ r ≤ 50)$ — количество карт в колоде и количество операций срезания.

    Каждая из следующих $r$ строк описывает операцию срезания. Они выполняются в перечисленном порядке. Каждая строка содержит два натуральных числа $p$ и $c$ $(p + c ≤ n + 1)$. Начиная с $p$-ой карты сверху, c карт вытаскиваются и кладутся наверх.

    Последняя строка содержит два нуля.

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

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

    Тесты

    Входные данные Выходные данные
    1 5 2
    3 1
    3 1
    10 3
    1 10
    10 1
    8 3
    0 0
    4
    4

    Код

    Решение

    Решить данную задачу можно несколькими способами. Первая мысль, которая мне пришла в голову — поместить все числа в строку и совершать тасование с помощью методов работы со строками, такими как $erase$ и $substr$. В течении решения стало понятно, что просто записывать числа в строку будет неправильно, так как возможны и двузначные числа. Так как неизвестно какое число будет следующим (однозначное или двузначное), особенно после нескольких перестановок, появляется идея хранить в строке числа, разделенные между собой запятыми. И в дальнейшем, если мне понадобится вытащить 5 карт из колоды начиная с 17, то я дойду до 16 запятой и возьму все, что хранится после нее, до 17+5 запятой и переставлю эти числа в начало строки (наверх колоды). Также в процессе поиска позиции необходимой запятой мне нужно получить ее позицию в строке, поэтому я решил создать структуру $Comma$, которая будет хранить номер запятой в строке и ее позицию относительно всех символов в данной строке, чтобы использовать ее во время каждой перестановки.

    Таким образом, получаем рабочее решение данной задачи.

    Ссылки

    e-olymp 4739. Решето Эратосфена

    Задача

    По заданным числам $a$ и $b$ вывести все простые числа в интервале от $a$ до $b$ включительно.

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

    Два числа $a$ и $b \ (1 \leqslant a \leqslant b \leqslant 100000)$.

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

    Вывести в одной строке все простые числа в интервале от $a$ до $b$ включительно.

    Тесты

    Входные данные Выходные данные Объяснение
    1 2 2 2
    2 1 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
    3 50 100 53 59 61 67 71 73 79 83 89 97
    4 10 2 Неправильно, так как противоречит условию ($a \leqslant b$)
    5 99900 100000 99901 99907 99923 99929 99961 99971 99989 99991
    6 -15 -6 -13 -11 -7 Неправильно, так как противоречит условию ($1 \leqslant a \leqslant b \leqslant 100000$)

    Код

    Решение

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

    Это решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых.

    Рассуждение:
    — Все четные числа, не считая двойки, — составные, то есть не являются простыми, так как делятся не только на себя и единицу, а также еще на $2$.
    — Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на $3$.
    — Число $4$ уже выбыло из игры, так как делится на $2$.
    — Число $5$ простое, так как его не делит ни один простой делитель, стоящий до него.
    — Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

    В моем коде, указанном выше, была реализована функция-фильтр, которая, по большей части, реализовывает метод перебора делителей и проверяет: есть ли делители числа, кроме его самого, вплоть до корня из этого числа. И если остатки от деления не равны $0$, то мы возвращаем истину, что означает: число простое.

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

    Ссылки

    e-olymp 7240. Степан — бізнесмен

    Задача

    Ужляндія, як відомо, країна з розвиненими торговими відносинами.

    Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп’ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.

    Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [latex]N[/latex] продавців, вартість комп’ютера у [latex]i[/latex]-го з них дорівнює [latex]A_{i}[/latex] Ужляндських монет, причому ціни можуть відрізнятися у різних продавців. Крім того, він знайшов для себе [latex]M[/latex] потенційних покупців, кожен з яких хоче купити комп’ютер за [latex]B_{i}[/latex] монет. При цьому сам Степан може купити і продати будь-яку кількість комп’ютерів.

    Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас — кращому програмісту Ужляндії.

    Формат вхідних даних

    Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа [latex]N, M (1 \leqslant N, M \leqslant 10^{5})[/latex] — кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
    Другий рядок містить [latex]N[/latex] цілих чисел [latex]A_{i} (0 \leqslant A_{i} \leqslant 10^{9})[/latex] — вартості, за якими продавці готові продавати комп’ютери.
    Третій рядок містить [latex]M[/latex] цілих чисел [latex]B_{i} (0 \leqslant B_{i} \leqslant 10^{9})[/latex] — суми, які потенційні покупці готові віддати при покупці комп’ютера.

    Формат вихідних даних

    Перший рядок вихідного файлу має містити одне ціле число [latex]S[/latex] — розмір максимальної вигоди в монетах, яку може отримати Степан.

    Тести

    Вхідні дані Вихідні дані Пояснення до прикладів
    1 2 3
    1 1
    3 3 3
    4 Степан купує комп’ютери у 1-го і 2-го
    продавців і продає їх будь-яким
    двом покупцям.
    2 6 5
    5 10 8 4 7 2
    3 1 11 18 9
    27 Степану найбільш вигідно купити комп’ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям.
    3 4 5
    6 7 9 8
    3 3 5 1 2
    0 Степану невигідно закуповувати техніку, адже ціни продавців перевищують суми, які готові віддати покупці.
    4 4 5
    4 4 4 4
    6 4 3 9 2
    7 Степану байдуже в кого купувати комп’ютери, але продати вигідно їх він зможе лише 1-му і 4-му покупцям.
    5 3 3
    5 1 3
    9 8 6
    14 Степан купує всі комп’ютери, адже всіх їх він зможе вигідно продати.
    6 4 1
    2 5 4 6
    8
    6 Покупець лише один, тому Степан має купити комп’ютер тільки у 1-го продавця.
    7 3 6
    1 7 4
    0 0 0 0 0 0
    0 Клієнти є, але ніхто з них не збирається платити, тож Степан не отримає прибутку.
    8 4 2
    0 7 4 6
    0 3
    3 Перший продавець віддає свій комп’ютер безкоштовно, а другий покупець готовий заплатити. Отже, Степан може заробити.
    9 1 5
    5
    5 7 9 3 4
    4 Хоча покупців багато, але продавець лише один. Степан має продати комп’ютер 3-му клієнту.

    Код

    Розв’язок

    Щоб отримати маскимальну вигоду, Степан має купувати комп’ютери за найменшою ціною, а продавати якомога дорожче. Отже, потрібно створити масиви і відсортувати їх: масив вартостей, за якими продавці готові продавати комп’ютери — за зростанням; масив сум, які потенційні покупці готові віддати при покупці комп’ютера — за спаданням. Далі створюємо цикл, за допомогою якого розраховуємо вигоду від реалізації кожного комп’ютера. Оскільки масиви відсортовані, то, як тільки прибуток стане від’ємним або нульовим, можемо припинити розрахунки і вивести розмір максимальної вигоди.

    Посилання

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

    e-olymp 7110. Весы

    Задача


    Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из $7$ гирь весом $1$ г, $3$ г, $9$ г, $27$ г, $81$ г, $243$ г и $729$ г можно измерить вес любого предмета с целым весом от $1$ до $1093$ г единственным способом. Например, для измерения предмета весом $4$ г необходимо на одну чашу положить гири в $1$ и $3$ г, а на другую сам предмет, а, скажем, для предмета весом $68$ г на чашку с ним добавляются гири в $1$, $3$ и $9$ г, а на другую — гиря в $81$ г.

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

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

    Одно натуральное число $x \ (1 \leqslant x \leqslant 1000)$ — вес предмета.

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

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

    Тесты

    Входные данные Выходные данные
    1 4 2
    2 68 4
    3 27 1
    4 555 5
    5 1000 4

    Код

    Решение

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

    Ссылки

    e-olymp 8538. Калькулятор

    Условие

    Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

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

    Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

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

    Выведите наименьшее количество операций.

    Тесты

    Входные данные Выходные данные
    1 1447 16
    2 18 3
    3 111 6

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

    Решение

    Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $9$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.

    e-olymp 7843. Больше предыдущего

    Задача

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

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

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

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

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

    Тесты

     

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

    Код

    Решение

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

    Ссылки

    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-olimp 8536. Заповнення смуги $3 \times n$

    Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

    Задача

    Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

    Вхідні дані

    Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

    Вихідні дані

    Вивести кількість способів, якими можна заповнити смугу.

    Тести

    Вхідні дані Вихідні дані
    1 1
    5 4
    12 60
    50 122106097

    Код № 1

    Рішення 1

    Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

    Код № 2

    Рішення 2

    Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

    Посилання

    Умова задачі на E-Olymp
    Зараховане рішення № 1 на E-Olymp
    Зараховане рішення № 2 на E-Olymp
    Код задачі № 1 на Ideone
    Код задачі № 2 на Ideone

    e-olimp 8234. Сходинки

    Задача

    Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

    Вхідні дані

    Одне число $n$ — номер сходинки $(n \leqslant 60)$.

    Вихідні дані

    Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

    Тести

    Вхідні дані Вихідні дані
    0 1
    5 13
    15 5768
    32 181997601
    60 4680045560037375

    Код № 1

    Рішення

    Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
    arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
    Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

    Код № 2

    Посилання

    Умова задачі на E-Olymp
    Зараховане рішення № 1 на E-Olymp
    Зараховане рішення № 2 на E-Olymp
    Код задачі № 1 на Ideone
    Код задачі № 2 на 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