e-olymp 1619. Ограбление домов

Задача

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

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

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

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 106)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

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

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

Тесты

Входные данные Выходные данные
1 5
6 1 2 10 4
16
2 10
4 1 29 0 14 8 31 12 7 5
85
3 2
1 3
3

Код

Решение

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

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

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

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

Следовательно, значения начальных состояний будут такими:
— Для первого дома — количество денег в нем.
— Для второго — максимальное количество денег из первых двух домов.

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

Ссылки

e-olymp 6975. Магический Множитель

Задача

Ельфійські раси Середзем’я вважали, що деякі числа є більш важливими, ніж інші. При використанні конкретного кількості $n$ металу для виплавки меча, вони вважають, що меч буде найбільш потужним, якщо його товщина $k$ обрана відповідно до наступного правила:

Визнач невід’ємне ціле число $n$. Знайти найменше $k$, для якого десяткове представлення чисел в послідовності

$n, 2n, 3n, 4n, 5n,\ldots, kn$

містить всі десять цифр (від $0$ до $9$) як мінімум один раз?

Лорд Елронд з Рівенделл доручив Вам розробити алгоритм, який знайде оптимальну товщину $k$ для будь-якого заданого кількості металу $n$.

Вхідні дані

Кожен рядок містить одне число $n$ $(1 \leqslant n  \leqslant 200000000)$.

Вихідні дані

Для кожного тесту вивести в окремому рядку необхідне значення $k$ — таке що кожна цифра від $0$ до $9$ зустрічається хоча б один раз.

Тести

Вхідні дані Вихідні дані
1 1

10

123456789

3141592

10

9

3

5

2 200000000 45

Код

Рішення

Для знаходження числа $k$ треба всі отриманні цифри (від $0$ до $9$), які зустрічаються в числовій послідовності $n, 2n, 3n, 4n, 5n,\ldots, kn$, відзначати як знайдені. Для цього було використано масив з $10$ елементів, де поіндексово (відповідно до цифри) відзначалася знайденна цифра, яка зустрічалося в числовій послідовності хоча б один раз. Пошук числа $k$ здійнувався за допомогою циклу, де методом поступового збільшення $k$, здійснювалася перевірка числа. Перевірка рахувалося успішною і завершувала цикл, якщо в масиві було відзначено всі цифри. В разі неуспішної перевірки цикл продовжувався.

Посилання

  • Задача на e-olymp.
  • Код рішення на Replit.
  • Код рішення на Ideone.

e-olymp 7241. Transit

Задача

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі $N$ днів. Згідно з новим договором має обратися певне число $m$ – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує $A_i$ обігрівачів, буде відвантажено рівно $ A_i -m $ одиниць іноземної продукції (звичайно, якщо $A_i > m$ , інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за $N$ днів обігрівачів повинна бути не менша $K$, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із $N$ днів (ця інформація надається за умовами контракту). Знайдіть максимальне число $m$, при якому Ужляндія не зазнає економічних збитків.

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

В першому рядку записано два числа $N$, $K$ ($1 \leqslant N \leqslant 10^6$, $1 \leqslant K \leqslant 2 \cdot 10^9$). В наступному рядку задано $N$ чисел – кількість обігрівачів у потязі в кожен з $N$ днів, що не перевищує $10^9$.

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

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

Пояснення до прикладу

Всього територією Ужляндії пройде $4$ потяги з $11, 6, 1$ та $8$ обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше $7$ обігрівачів. Очевидно, що максимальне можливе $m$, яке задовольнить цю умову, буде рівне $6$, тоді з потягів буде відвантажено відповідно $5, 0, 0, 2$ обігрівачів, що в сумі дорівнює $7$ і задовольняє умову.

Тести

Вхідні дані Вихідні дані
1 4 7
1 8 6 11
  6
2 10 20
1 8 6 11 16 14 21 10 13 4
  11
3 5 10
12 4 3 6 9
  5
4 6 11
5 8 6 9 4 7
  4
5 2 1
2 2
  1

Код

Рішення

Для знаходження числа $m$ я використовував бінарний пошук, перед цим зробивши сортування по зростанню елементів в масиві. Отже, вся задача зводиться до використання бінарного пошуку, та функції яка рахує $\sum\limits_{i=0}^{n-1} A_i — m$, при $A_i > m$ ($m$ — значення mid; $n$ — кількість елементів в масиві; $A_i$ — значення $i$-го елемента масиву). Далі ця сума порівнюється з $K$ для подальшої роботи пошуку та знаходження числа $m$. Якщо такого числа $m$ не існує ми шукаємо найближче, при якому країна не зазнає збитків.

Посилання

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 7232. Комплектация компьютеров

Задача

В наличии есть такие системные блоки: $a_1$ поддерживают только VGA интерфейс, $a_2$ поддерживают только DVI и $a_3$ поддерживают оба интерфейса VGA и DVI. Аналогично по мониторам: $b_1$ поддерживают только VGA, $b_2$ — только DVI, $b_3$ — оба интерфейса.

Какое наибольшее количество компьютерных комплектов возможно собрать, если в каждом комплекте у системного блока с монитором должен быть совместимый графический интерфейс?

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

В первой строке три числа $a_1, a_2$ и $a_3$ и во второй строке три числа $b_1,b_2$ и $b_3$ — целые неотрицательные.

Причем $ 0 \leqslant a_1, a_2, a_3, b_1, b_2, b_3 \leqslant 100$ и $a_1+a_2+a_3$ $=$ $b_1+b_2+b_3$.

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

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

Тесты

Входные данные Выходные данные
1 5 1 6
4 8 0

11
2 0 0 3
1 3 6
3
3 4 2 0
1 3 6
6

Код

Решение

Составим все комбинации системных блоков с мониторами, у которых есть совместимый графический интерфейс. Порядок составления комплектов важен. Сначала посчитаем сколько можно составить комплектов $а_1$ с $b_1$ и $a_2$ с $b_2$, так как они поддерживают только один тип интерфейса. Далее посчитаем возможные комплекты $а_1$ с $b_3$, $a_2$ с $b_3$ и $a_3$ с $b_3$ $a_3$ с $b_1$ и $a_3$ с $b_2$ из оставшегося оборудования. Выведем общее количество компьютерных комплектов.

Ссылки

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

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 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 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 1206. f91

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $f_{91}$, которая определена для всякого натурального числа $n$ следующим образом:

Если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;

Если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.

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

Натуральное число $n$, не большее $1000000$.

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

Значение $f_{91}\left(n\right)$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 5 91
 2 27 91
 3 91 91
 4 100 91
 5 102 92
 6 180 170

Код

Решение

Для решения задачи создадим функцию $f_{91}\left(n\right)$ которая в зависимости от значения $n$ будет выдавать нам разные значение, а имеено:
если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;
если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.
Так же, мы можем проследить законномерность того, что если $n\leqslant100$ функция $f_{91}\left(n\right)$ будет выдавть $91$, заметив это можно будет заменить сложную, но при этом красивую рекурсивную функцию на более простое и практичное решение и получить следущие соотношение:
$f_{91}\left(n\right) = \begin{cases} 91, & n\leqslant100;\\ n-10, & n\geqslant101; \end{cases}$

Ссылки

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

e-olymp 4439. Возведение в степень

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 100 1
 2 2 10 1024
 3 3 7 2187
 4 8 9 134217728
 5 10 10 10000000000
 6 100 9 1000000000000000000

Код

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

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

e-olymp 8671. Представимые суммой квадратов

Задача

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

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

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

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

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

Тесты

Входные данные  Выходные данные
1 5 5
2 10 5 10
3 13 5 10 13
4 20 5 10 13 17 20
5 30  5 10 13 17 20 25 26 29

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

Решение

Для решения задачи создадим функцию check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $,  потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.

Ссылки

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

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

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 913. Используй подпрограмму

Задача

Вычислить сумму и произведение $n$ пар заданных вещественных чисел, воспользовавшись подпрограммой $SumDob$ для вычисления суммы и произведения двух вещественных чисел.

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

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

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

В $n$ строках вывести через пробел по два числа: сначала сумму, а потом произведение очередной пары чисел. Результат выводить с точностью $4$ знака после десятичной точки.

Тесты

# Входные данные Выходные данные
1 2
6 7.5
2.1 2.0
13.5000 45.0000
4.1000 4.2000
2 4
2 5
3 5
4 5
5 5
7.0000 10.0000
8.0000 15.0000
9.0000 20.0000
10.0000 25.0000
3 2
100 100
56 65
200.0000 10000.0000
121.0000 3640.0000
4 6
10 10
20 20
40 40
50 50
70 70
80 80
20.0000 100.0000
40.0000 400.0000
80.0000 1600.0000
100.0000 2500.0000
140.0000 4900.0000
160.0000 6400.0000
5 1
2 2
4 4

Решение

Как и было указано в условии задачи, при решении задачи использовалась подпрограмма $SumDob$, которая возвращает сумму и произведение двух вещественных чисел $a$ и $b$. Потом мы с помощью цикла выводим пару чисел, полученных из подпрограммы $SumDob$ $n$ раз с $n$ пар введенных значений.

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

e-olymp 7504. Три прямоугольника

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

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 1
1 1 2 2
0 0 2 2
4
2 2 -2 -2 2
-1 -1 1 1
40 40 41 41
17
3 -1 2 2 -1
1 0 4 2
1 0 3 6
21
4 -100 -100 -99 -99
100 100 99 99
-100 -100 100 100
40000
5 3 0 4 1
1 0 3 3
1 0 3 3
7

Решение

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

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

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

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

Решение. Многомерные массивы

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

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

e-olymp 137. НОД

Задача

Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

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

НОД заданных чисел.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2
15 25
5
2 3
99 358 2
1
3 5
81 99 72 108 36
9
4 2
25 50
25
5 4
132 36 66 18
6

Код

Решение

Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

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

e-olymp 1519. Коды Грея

Задача

Френк Грей. Bell Lab 1930

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

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

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

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

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

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

e-olymp 273. Возведение в степень

Задача

По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].

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

Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].

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

Вывести [latex]a^b\mod m[/latex].

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 2 100 1
2 100 2 1000000 10000
3 2 3 50 8
4 9 2 1 0
5 9 2 25 6

Код с циклом

Код с ветвлением

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

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

e-olymp 338. Моя любимая, несократимая…

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

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

Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].

Тесты

 

Входные данные Выходные данные
1 0
10000 30397485
5 9
80 1965
37 431
5168 8119803
9973 30237929

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

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

описание функции Эйлера на Wikipedia

e-olymp 1489. Шоколад

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные Выходные данные
2 3
1 1 2
3 3 2
Yes
5 6
1 2 2 3 3 4
1 5 6 7 7 4
8 5 6 9 10 10
8 11 11 9 12 13
14 14 15 15 12 13
No
4 7
1 1 2 5 8 11 6
2 14 4 7 3 9 5
3 7 10 6 13 2 3
4 3 8 12 5 7 7
Yes

Код решения

 

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

Условие решения на e-olymp.com
Код решения на ideone.com

e-olymp 4812. Функция

Задача

Функция [latex]f(x)[/latex] определена следующим образом:
[latex]f\left(x\right)= \sin x + \sqrt{\log_{4}3x}+ \lceil 3e^x \rceil[/latex] Вычислите значение [latex]f(x)[/latex] для заданного [latex]x[/latex].

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

Каждая строка содержит действительное значение [latex]x (x ≥ 1)[/latex].

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

Для каждого значения x выведите в отдельной строке [latex]f(x)[/latex] с 6 десятичными знаками.

Тесты

Входные данные Выходные данные
1
2.3
2.56
7.123456
10.731685
31.926086
40.762019
3725.231017

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

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

График функции

График функции $f\left(x\right) = \sin x + \sqrt{\log_{4}3x}+ \lceil 3e^x \rceil$

Для решения этой задачи я считывал каждое число из потока ввода и передавал значение в функцию, которая возвращало нужное значение, после чего выводил на экран полученное значение с округлением до 6-го знака после запятой. Использовал стандартную библиотеку <cmath>, для вычисления синуса, корня, логарифма, нахождения экспоненты и округления вверх.

Ссылки

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