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 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 8659. Байтик та шахи

Задача

Вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною $k(1 \leqslant k \leqslant n)$ можна розмістити на дошці розміру $n$.

Вхідні дані

Натуральне число $n$ $( n\leqslant 10000)$ розмір шахової дошки.

Вихідні дані

Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.

Тести

Входные данные Выходные данные
1 3 14
2 10 385
3 99 328350
4 999 332833500
5 10000 333383335000

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

Рішення

Вирішити цю задачу можна за допомогою квадратного пірамідального числа — числа, яке висловлює кількість квадратів з різними сторонами в сітці $n$*$n$. Загальна формула для пірамідального числа порядку $n$: $\sum\limits_{k = 1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}$. Використаємо виведену формулу для лінійного обчислення, щоб не використовувати цикли і зменшити час роботи програми.

Посилання

e-olymp-8841. Цифра 2

Цифра 2

На входе программы имеется натуральное число $n$ ($n \gt 9$). Нужно вывести предпоследнюю справа цифру (разряд десятков) числа $n$.

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

Натуральное число $n$ ($n \gt 9$).

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

Цифра разряда десятков числа $n$.

Тесты

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

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

1 27 2
2 102 0
3 1234 3
4 34867 6

Решение

Чтобы получить разряд десятков введенного числа надо поделить число на $10$ и взять остаток от деления на $10$.

Ссылки

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

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

e-olymp 8851. Число навпаки

Умова задачі

Записати чотиризначне натуральне число в зворотному порядку.

Вхідні дані

Задане чотиризначне натуральне число.

Вихідні дані

Відповідь до задачі.

Тести

Входные данные Выходные данные
1 1234 4321
2 1984 4891

Розвязок №1

Для отримання потрібного числа, відділимо кожну цифру та привласнемо до неї змінну. Виводимо у потрібному порядку.

Розвязок №2

Представимо вводиме число як строку. Виводимо у циклі від третього до останньго елемента.

Посилання

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

e-olymp 398. Торт для Серёжи

Задача

prb398Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его разрезать. У него в распоряжении есть достаточно длинный нож, позволяющий делать разрез по всему торту, однако так как общение с режущими инструментами всегда таит в себе определенные опасности, Серёжа хочет сделать минимальное количество разрезов так, чтобы всем гостям досталось хотя бы по одному кусочку. Естественно, при этом он должен не забыть, что и ему должен за праздничным столом достаться хотя бы один кусочек маминого торта, но при этом Серёжу абсолютно не интересует, какого размера и формы будут куски торта – для него главное, чтобы они все имели такую же толщину, как и испеченный мамой торт.

Учтите, что гостей к Серёже может придти достаточно много.

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

Одно число – количество гостей $n$ $(n < 210000001)$.

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

Искомое количество разрезов $k$.

Тесты

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

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

1
3
2
2 0 0
3 120 15
4 210000000 20494

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

Решение

Максимального количества кусков можно достичь в том случае, когда каждый новый разрез будет пересекать все предыдущие. Таким образом новым $k$-ым сечением мы разрежем $k$ кусков торта на две части, а к общему количеству кусочков прибавится ровно $k$ новых. Заметим, что имениннику всегда достанется кусок, который не считается новым. Множество всех новых кусков составит арифметическую прогрессию: $0,1, 2, 3 … k-1, k$ значит общее количество кусочков для гостей вычисляется как сумма арифметической прогрессии $\mathbf{n = \frac{i^{2}+k}{2}}$. Тогда $\mathbf{k =\left \lceil \frac{-1+\sqrt{1+8n}}{2} \right \rceil }$.

Эту формулу немного можно упростить, в результате получим $\mathbf{k =\left [ \sqrt{2n}\right ]}$

Ссылки

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

Код решения ideone

e-olymp 123. Количество нулей у факториала

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 1 0
 2 7 1
 3 12 2
 4 100 24
 5 306 75
 6 5000 1249

Код

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

Засчитанное решение на e-olymp 

 

e-olymp 7934. Коробка для свічок

Умова задачі

Маргарита любить свої дні народження. Вона дійсно щаслива, коли задуває свічки під мелодію «Happy Birthday». Кожного року, починаючи з досягнення нею чотирьохрічного віку, вона складає свої свічки з дня народження (по одній за кожен рік віку) в коробку для свічок. Її молодший брат Тео почав робити те ж саме у віці трьох років. Коробки Маргарити і Тео та свічки в них виглядають однаково.

Одного разу Маргарита вирішила порахувати, скільки свічок в неї у коробці:

  • Ні, ні, ні! Я молодша цього!

Вона щойно зрозуміла, що Тео кинув в її коробку декілька свічок з його днів народжень. Чи можете ви допомогти Маргариті виправити кількість свічок в її коробці?

Маючи різницю у віці між Маргаритою і Тео, кількість свічок в коробці Маргарити та число свічок в коробці Тео, визначте, скільки свічок Маргариті потрібно вийняти з її коробки, щоб в ній була потрібна кількість.

Вхідні дані

Перший рядок — число [latex] d (1 ⩽ d ⩽ 20) [/latex] — різниця у віці між Маргаритою і Тео.

Другий рядок — число [latex]m (4 ⩽ m < 1000)[/latex] — кількість свічок в коробці Маргарити.

Третій рядок — число [latex]t (0 ⩽ t < 1000)[/latex] — кількість свічок в коробці Тео.

Вихідні дані

Виведіть число свічок, яке Маргариті потрібно вийняти з її коробки, щоб в ній була правильна кількість.

Тести

ВХІДНІ ДАНІ ВИХІДНІ ДАНІ
1 2
26
8
4
2 4
48
3
9
3 7
110
14
11
4 10
568
78
139
5 13
800
37
211

Код програми

Розв’язання

Нехай [latex] x [/latex] — кількість років Маргарити в момент перевірки вмісту коробки зі свічками, тоді [latex] x — d [/latex] — вік Тео в цей момент. Правильна кількість свічок в коробці Маргарити — [latex] \frac{(4+x)(x-3)}{2} [/latex] та коробці Тео [latex] \frac{(3+x-d)(x-d-2)}{2} [/latex] (як суми членів арифметичної прогресії).  Правильна кількість свічок в обох коробках дорівнюватиме сумі свічок, що наявна в коробці Маргарити і Тео, відповідно [latex] m + t [/latex]. Складемо рівняння, яке після ряду перетворень набуде квадратного виду [latex] ax^2+bx+c=0 [/latex] — [latex]x^2 + (1 — d) x +  \frac{d^ 2 — d — 18 — 2 (m + t)}{2} = 0[/latex]. Знайдемо дискримінант [latex] b^2-4ac [/latex], а потім корінь рівняння за формулою [latex] \frac{-b+\sqrt{D}}{2a}[/latex], тому  [latex]x = \frac{(d-1) + \sqrt{D}}{2}[/latex], причому  [latex]\frac{-b — \sqrt{D}}{2a} [/latex] — не є потрібним розв’язком, адже набуватиме від’ємного значення. Тепер віднімемо від свічок, які Маргарита знайшла в коробці їx правильну кількість. Отже, зайвими будуть [latex]m — \frac{(4+x)(x — 3)}{2}[/latex] свічок.

Посилання

Задача на сайті e-olymp

Код розв’язання на ideone

Зараховаваний роз’язок

e-olymp 8638. Дописать тройку

Задача

Дано трёхзначное число $ n $. Дописать к нему слева и справа цифру $ 3 $.

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

Одно трехзначное число $ n $ .

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

Дописать к числу $ n $ слева и справа цифру $ 3 $. Вывести полученное число.

Тесты

Входные данные Выходные данные
1. 333 33333
2. 261 32613
3. 123 31233
4. 060 30603

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

Первый вариант

Второй вариант

Объяснение

Дано любое трёхзначное  число. Нужно  дописать $ 3 $ к нему слева и справа.

К первому варианту кода

Умножаем число на $ 10 $ и прибавляем $ 30003 $.

Ко второму варианту кода

Просто дописываем $ 3 $ слева и справа сразу в выводе.

Ссылки

e-olymp 8841. Цифра 2

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

На входе программы имеется натуральное число [latex]n (n > 9)[/latex]. Нужно вывести предпоследнюю справа цифру (разряд десятков) числа [latex]n[/latex].

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

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

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

Цифра разряда десятков числа [latex] n [/latex].

Тесты:

 

Входные данные Выходные данные
1 10 1
2 197 9
3 4638 3
4 72410 1
5 6543732 3

 

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

Решение:

Идея данного решения заключается в том, чтобы с помощью целочисленного деления числа [latex]n (n > 9)[/latex] на 10 избавиться от последней цифры в числе [latex]n[/latex]. Затем вычисляем остаток от деления для того, чтобы осталась последняя цифра полученного числа, которая и является предпоследней цифрой справа (разряд десятков) в числе [latex]n[/latex].

Ссылки:

Задача на e-olymp

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

Засчитанное решение на e-olymp

e-olymp 9406. Професор і батарейки

Умова  задачі

У професора на столі лежали упаковки батарейок. У кожній по [latex] a [/latex] штук. Коли професор взяв по [latex] b [/latex] батарейок з кожної упаковки — на столі залишилося всього [latex] c [/latex] батарейок.

Скільки упаковок з батарейками було на столі?

Вхідні дані

Три натуральні числа [latex] a [/latex], [latex] b [/latex], [latex] c [/latex].

Вихідні дані

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

Тести

ВХІДНІ ДАНІ ВИХІДНІ ДАНІ
1 6 3 15 5
2 12 10 6 3
3 150 130 220 11
4 60 56 512 128
5 702 67 3175 5

Код програми

Розв’язання

Нехай [latex] n [/latex] — кількість упаковок батарейок. [latex] a-b [/latex] — це  кількість батарейок, яка залишилась в кожній упаковці. Відомо, що всього залишилось [latex] c [/latex] батарейок, тоді [latex] n = \frac{c}{a-b} [/latex] — кількість упаковок батарейок.

Посилання

Задача на сайті e-olymp

Код розв’язання на ideone

Зараховаваний роз’язок

e-olymp 9405. Профессор и шары

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

Для праздника Профессор купил голубые, красные и жёлтые воздушные шары. Всего $n$ штук. Жёлтых и голубых вместе — $a$. Красных и голубых — $b$ штук.

Сколько голубых, красных и жёлтых шаров купил Профессор?

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

Три натуральных числа $n$, $a$, $b$.

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

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

Тесты

Входные данные Выходные данные
1 10 6 8 4 4 2
2 12 8 10 6 4 2
3 14 10 12 8 4 2
4 16 14 12 10 2 4

Программный код

Решение

Для решения задачи необходимо вывести формулу для вычисления количества жёлтых ($y$), синих ($u$) и красных ($r$) шаров. Из условия имеем, что:

$$\left.\begin{matrix}
&u&+&y&=a&\\
&r&+&u&=b&\\
&r&+&u&+&y&=n&
\end{matrix}\right\}$$

Выразим $r$ и $y$ через $u$:

$$\left.\begin{matrix}
r=&b&-&u&\\
y=&a&-&u&
\end{matrix}\right\}$$

Подставим эти значения в формулу $r+u+y=n$:

$n=b-u+u+a-u$

$u$ и $-u$ взаимоуничтожатся и мы получим, что:

$n=a+b-u$

Теперь выведем формулу для вычисления количества синих шаров:

$u=b+a-n$

Ссылки

e-olymp 8842. Цифра 3

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

На входе программы имеется натуральное число  [latex] n (n > 99) [/latex]. Нужно вывести третью цифру (разряд сотен) числа [latex] n [/latex].

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

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

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

Цифра разряда сотен числа [latex] n [/latex].

Тесты:

 

Ввод Вывод
1 512 5
2 7826 8
3 90285 2
4 12479056 0
5 18942793357 3

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

Решение:

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

  • разделим данное натуральное число на [latex] 100 [/latex] и получаем количество сотен в числе: либо однозначное число (цифру), либо многозначное;
  • так как мы хотим получить простую сотню (однозначное число), мы находим остаток от полученного числа при делении на [latex] 10 [/latex].

Ссылки:

Задача на E-Olymp

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

Засчитанное решение на E-Olymp

e-olymp 9080. Три богатыря

Задача

Три богатыря шли из Бразилии в Киевскую Русь. Шли они со скоростью [latex]n[/latex] метров в минуту и должны пройти расстояние [latex]r[/latex] километров. Сколько дней им понадобится для преодоления пути?

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

Два натуральных числа [latex]n[/latex] и [latex]r[/latex] [latex]\left(n, r \leqslant10^{4}\right)[/latex]

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

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

Тесты

Входные данные Выходные данные
1 1 10 7
2 2 8 3
3 4 70 13
4 5 68 10
5 3 12 3

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

Решение

Ответом к задаче будет количество дней, за которое богатыри проделают путь. То есть нам просто надо поделить путь на скорость. Но загвоздка задачи состоит в том, что скорость дана в метрах в минуту, а нам надо перевести в километры в сутки. В одних сутках [latex]1440[/latex] минут, в километре [latex]1000[/latex] метров. Выполнив математические преобразования, получаем, что надо заданное значение скорости умножить на [latex]1.44[/latex]. Выводим результат деления пути на скорость, умноженную на [latex]1.44[/latex]. Так как получится нецелый результат, округляем значение в сторону большего с помощью функции ceil() , предварительно подключив библиотеку cmath .

Ссылки

e-olymp 8254. Номера отеля

Задача

Отель имеет $n$ этажей. Лобби, ресторан и тренажерный зал расположены на первом этаже. Номера находятся со 2-го по $n$-ый этажи. На каждом этаже расположено $m$ стандартных номеров. Если каждый стандартный номер вмещает 3 гостя, какое наибольшее количество гостей может поместиться во всех стандартных номерах отеля?

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

Два натуральных числа $n$ и $m$ ($n, m\leqslant10^6$).

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

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

Тесты

Входные данные Выходные данные
1 5 10 120
2 3 1 6
3 2 5 15
4 7 2 36
5 20001 450000 270000000000

Код

Решение

Для решения данной задачи выводим формулу $(n-1) \cdot m \cdot 3$, первый из сомножителей — количество этажей, на которых располагаются номера, второй — количество номеров на каждом из указанных этажей, третий — максимальное количество гостей в каждом номере. Заметим, что по условию на первом этаже номера отсутствуют, поэтому первый сомножитель в формуле будет на единицу меньше, чем количество этажей в отеле.

Ссылки

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

e-olymp 9518. Точное движение

Задача

Амелия изучает моделирование. Она увлекается моделями с подвижными деталями.

В качестве своего первого задания она сделала прямоугольную коробку размером $2$ $×$ $n$, которая содержит две параллельные рейки и прямоугольный брусок на каждой из них. Короткий брусок имеет размер $1$ $×$ $a$, а длинный имеет размер $1$ $×$ $b$. Длинный брусок имеет стопор на каждом конце, а короткий всегда находится между этими двумя стопорами.

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

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

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

Три целых числа $a$, $b$ и $n$ $($$1$ $\leqslant$ $a$ $<$ $b$ $\leqslant$ $n$ $\leqslant$ $10$$7$$)$.

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

Вывести одно целое число — минимальное количество ходов, которое должна сделать Амелия.

Тесты

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

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

1 1 3 6 5
2 2 4 9 7
3 13 45 153 9
4 4 16 43 7

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

 

Решение

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

Длинный брусок, что бы он оказался в конце коробки, суммарно нужно переместить на $n$$-$$b$. Каждый раз мы перемещаем его на $b$$-$$a$ (необходимое расстояние что бы левые концы брусков совпали и дальше перемещать его было невозможно). Тогда количество перемещений длинного бруска это результат деления всего расстояния $n$$-$$b$ на шаг $b$$-$$a$. Так как в результате может выйти нецелое число, результат необходимо округлить до большего целого. Обозначим это число как $k$ $=$$\lceil $$\frac{n-b}{b-a}$$\rceil$.

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

Тогда суммарное количество ходов будет $2$$k$$+$$1$.

Ссылки

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

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

e-olymp 8701. Кузнечик-попрыгунчик

Задача

Кузнечик-попрыгунчик долго сидел на отметке [latex]0[/latex] числовой прямой, так долго, что придумал инновационную методологию своего перемещения. Такую, что за каждую итерацию движения он выполняет ровно два прыжка, перемещаясь сначала на [latex]a[/latex], а затем на [latex]b[/latex] единичных отрезков по числовой прямой, причем, если число положительное, то он движется вправо, а если отрицательное, то влево. Продолжительность прыжка в секундах равна соответствующему количеству единичных отрезков, на которое переместится кузнечик.

Например, если [latex]a = 3[/latex], а [latex]b = — 2[/latex], то через [latex]3[/latex] сек. он будет на отметке [latex]3[/latex], а через [latex]5[/latex] сек. от начала движения попадет на отметку [latex]1[/latex]. Далее, на [latex]8[/latex] секунде переместится на отметку [latex]4[/latex], а на [latex]10[/latex] секунде вернется на [latex]2[/latex].

При заданных [latex]a[/latex] и [latex]b[/latex] найти сколько необходимо времени в секундах, чтобы допрыгать до отметки x числовой прямой или вывести [latex]-1[/latex], если это невозможно.

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

Целочисленные значения [latex]a[/latex], [latex]b[/latex], [latex]x[/latex] — в одной строке через пробел. Значение по модулю не превышают [latex]10^{9}[/latex].

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

Ответ на задачу.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 3 -2 1 5
2 100 200 0 0
3 -10 -20 -900 900
4 5 -6 3 27
5 1 3 10 -1

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

Решение задачи (с использованием условных операторов)

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

  1. Сначала добравшись до точки x-a прыжками вида a+b, а после совершив один прыжок на дистанцию a
  2. Добраться до точки x исключительно прыжками вида a+b

Если одним из способов невозможно добраться, то присваиваем переменной соответствующей потраченному времени MAX, а после выводим минимум из переменных possible_ans1, possible_ans2(в случае, если обеими способами невозможно добраться, т.е. обе переменные равны MAX выводим -1).

Код программы (без использования условных операторов)

Решение задачи (без использования условных операторов)

Заранее вычислим значения s(пройденное расстояние за один прыжок вида a+b) и t(время, потраченное на один прыжок вида a+b). После поочередно проверим выполнение всех условий, описанных ранее. При выполнении какого-либо из условий, выводим соответствующее время, если ни одно из условий не выполнилось то выводим [latex]-1[/latex].

e-olymp 944. Площадь пирамиды

Задача

Треугольная пирамида задана координатами своих вершин [latex] A(x_1; y_1; z_1), [/latex] [latex] B(x_2; y_2; z_2), [/latex] [latex] C(x_3; y_3; z_3), [/latex] [latex] S(x_4; y_4; z_4). [/latex] Определить площадь полной поверхности пирамиды.

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

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

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

Вывести полную поверхность пирамиды с точностью до десятых.

Тесты

Входные данные Выходные данные
1 -3 0 0 69,8
0 6 0
3 0 0
0 2 5
2 2 4 8 159,1
2 -6 9
5 -4 0
1 3 0
3 5 0 1 107,3
4 1 7
-9 0 4
6 2 8

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

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

Для того, чтобы найти площадь полной поверхности пирамиды, необходимо найти площади треугольников, которые являются гранями пирамиды.
Для нахождения площади треугольника можно воспользоваться формулой Герона: [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)} [/latex],где [latex] p [/latex]-полупериметр треугольника, [latex] a,b,c [/latex] — стороны треугольника. Чтобы воспользоваться формулой Герона, необходимо предварительно найти длины сторон треугольников, используя формулу нахождения длин отрезков по координатам концов отрезка: [latex] |AB|=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2} [/latex], где [latex] А,В [/latex] — концы отрезка, [latex] x_a, y_a,z_a [/latex] — координаты [latex] А [/latex], [latex] x_b, y_b,z_b [/latex] — координаты [latex] В [/latex].
Найденные площади всех треугольников, из которых состоит пирамида, складываем и получаем искомую площадь полной поверхности пирамиды.

Ссылки

e-olymp
ideone

e-olymp 75. Пираты и монеты

Задача

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

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

 #  ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
 1  5 25  3
 2  3 24  4
 3  4 38  5
 4  5 55  6
 5  6 75  7

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

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

Код программы (с условным оператором)

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки