e-olymp 1610. Зайцы в клетках

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

Задача

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] (1[latex]n[/latex], [latex]m[/latex] ≤ [latex]\ 10^{9}[/latex]).

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

# Входные данные Выходные данные
1 3 4 2
2 15 144 10
3 1 7 7
4 100 123456 1235
5 222 222 1

Код

Решение

Распределяя всех [latex] m [/latex] зайцев равномерно по клеткам [latex] n [/latex] получаем что максимальное количество зайцев в одной клетке равно [latex]\lceil \frac{m}{n}\rceil[/latex]

Ссылки

ideone
e-olymp

Руслан Масальский

Прикладная математика. Одесский национальный университет им. Мечникова

И опять «низкая» таблица

Задача

В тридевятом государстве новое соревнование. Организаторы поняли, что предыдущая задача «Низкая таблица» была слишком простой и решили усложнить жизнь нашей Аленушке. Она совсем растерялась и снова умоляет Вас о помощи. Итак, вот новое условие: каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из $n$ строк и $n$ столбцов. В каждой строке и столбце выбрано по одной ячейке, для которой указана минимальная площадь, которую должна занимать эта ячейка — $S_i$ для ячейки, расположенной в $i$-ой строке. Остальные могут иметь площадь $0.$ Задача участников аналогична предыдущей — начертить таблицу наименьшей высоты.

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

В первой строке содержится единственное натуральное число $n \leqslant 20.$
Во второй строке содержатся $n$ натуральных чисел $S_{1}, \ldots, S_{n}$, не превышающие $10^{4}.$

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

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

Тесты

Входные данные Выходные данные
3
1 2 3
17191
19
2899 338 8846 5896 3325 9199 6493 211 7878 6083 2074 8493 2889 3743 133 5725 9453 7890 3594
1548340398
18
3823 5708 1356 9979 8801 5310 2123 4575 566 5039 9367 26 1966 6540 1514 7193 7667 994
1252560358
8
8283 8769 3568 869 8285 4494 7185 4519
340953967
9
6375 3059 6206 4221 6027 2064 6278 1347 996
301905233
17
2765 8226 4472 1139 9080 675 3712 7735 9566 223 8899 9716 6594 9631 8871 6176 313
1414903854
10
2654 7458 2284 8767 6061 1149 7243 607 757 8532
385237635
6
6429 9121 9490 7035 6352 2021
231968881
8
52 6380 8169 5689 367 2403 3112 2850
185108459
2
8063 3128
21235115
9
9226 7811 4279 68 5976 1418 9721 6784 8580
418145363
13
8987 3714 247 679 1416 3489 1501 7654 2164 9101 7347 4043 3289
591377417
18
9349 9854 4308 1799 1501 8647 6300 9379 1123 7369 1164 3083 1207 2754 2933 1051 8566 4016
1324052855
3
1311 2984 9564
35581065
16
3460 6135 8911 5656 5496 5463 9566 8473 7575 7444 2717 8241 9868 6698 849 7118
1576424119
15
2264 4988 4454 726 17 9279 422 7916 698 5780 2517 9352 6291 2954 4775
763779068
10
3625 7189 773 7283 2952 7865 588 1670 1013 2982
305484098
18
2741 2630 4163 4926 9431 2212 6978 1607 9489 6746 4947 3333 3144 4809 3352 207 1919 1918
1207862952
5
4320 8413 1175 4527 1519
88794894
6
9534 5380 2500 683 4281 4803
145815522
14
1458 1341 6248 8840 8877 6891 409 5853 6726 6401 4932 9007 5710 745
905996755

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

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

Поменяем местами строки таблицы так, чтобы ячейки, для которых указана минимальная площадь, лежали на главной диагонали. От этого не изменится ни ширина, ни высота таблицы. Обозначим эти ячейки $S_{ii}$ для ячейки, лежащей на пересечении $i$-ой строки и $i$-ого столбца.
Докажем, что минимальная площадь указанной в условии таблицы $S = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}} \right )^2.$ Воспользуемся методом математической индукции.
База индукции. Случай при $n=2$ был доказан здесь.
Предположение индукции. Пусть утверждение верно $\forall n \leq k, \ k \geq 2.$
Шаг индукции. Докажем, что утверждение верно для $n = k+1.$ Рассмотрим подтаблицу $T_1$ нашей таблицы $T$, которая состоит из первых $k$ столбцов и $k$ строк исходной таблицы. По предположени индукции ее минимальная площадь $S_{T_1} = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2.$ Теперь можем рассматривать таблицу $T$ как таблицу, состоящую из двух строк и двух столбцов, так, что таблица $T_1$ будет верхней левой ячейкой. Тогда, учитывая утверждение, доказанное в базе индукции находим минимальную площать таблицы $T$ $$\begin{multline}S_{T} = \left (\sqrt{S_{T_1}}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left (\sqrt{\left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}}+\sqrt{S_{k+1k+1}}\right )^2.\end{multline}$$ Что и требовалось доказать. Заметим, что для тривиального случая $n = 1$ формула также остается в силе. Пусть $h$ высота таблицы, а $l$ — ее ширина. Учитывая, что по условию $l = 1,$ а $S = hl,$ находим, что минимальное значение высоты таблицы $h_{min} = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}}\right )^2.$

Ссылки

Код решения на Ideone

«Низкая» таблица

Задача

В тридевятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из двух столбцов и двух строк. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Известно, что для правой верхней и левой нижней ячейки это значение равно $0.$ Но вот незадача: значения минимальных площадей для левой верхней — $S_{11}$ и правой нижней — $S_{22}$ ячеек могут быть какими угодно (в пределах разумного, конечно, хотя кто их этих сказочных персонажей разберет). Задача участников — начертить таблицу наименьшей высоты. Аленушка очень хочет победить, но она плохо знает математику, поэтому просит Вас помочь ей в этом непростом деле.

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

В единственной строке содержатся два натуральных числа: $S_{11}, \ S_{22},$ не превышающие $10^{14}.$

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

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

Тесты

Входные данные Выходные данные
1 2 5828
466 1194 3151849
8067 2659 19988861
5125 6755 23647646
3317 2652 11900840
25 9293 10282002
7081 7189 10282002
8192 1042 15077308
6795 1568 14891264
680 4510 8692456
9107 4760 27035040
7095 7846 29863113
6142 3794 19590583
9347 3639 24650258
8495 5394 27427394
2179 8718 19613999
1187 778 3886963
71 5592 6923209
100000000000000 100000000000000 400000000000000000

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

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

Пусть $h$ и $l$ — высота и ширина таблицы соответственно. Тогда ее площадь $S=hl.$ В силу того, что $l=1,$ задача о нахождении минимальной высоты таблицы сводится к нахождению ее минимальной площади. Обозначим высоту $i$-ой строки $h_i$, ширину $j$-го столбца $l_j$, а площадь ячейки таблицы, находящейся на пересечении $i$-ой строки и $j$-го столбца — $S_{ij}.$ Тогда $$\begin{multline}S = S_{11} +S_{12}+S_{21}+S_{22}=S_{11}+l_2 h_1+l_1 h_2+S_{22}= \\ =S_{11}+S_{11} \frac{l_2}{l_1} +S_{22} \frac{l_1}{l_2}+S_{22} = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22},\end{multline}$$ где $y=\frac{l_2}{l_1}.$ Зафиксируем теперь $S_{11}$ и $S_{22}$ и рассмотрим функцию площади $S \left( y \right ) = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22}.$ Найдем наименьшее значение данной функции. $\frac{\mathrm{d} S \left( y \right )}{\mathrm{d} y} = S_{11}-\frac{S_{22}}{y^{2}}.$ Приравнивая производную функции к нулю, находим, что функция имеет единственную стационарную точку $y_{0} = \sqrt{\frac{S_{22}}{S_{11}}}.$ Легко убедиться, что $y_0$ – точка глобального минимума, тогда $\min\limits_{y \in D\left(S\right)}S\left( y \right ) = S \left(y_0\right) = S_{11} + S_{22} + 2 \cdot \sqrt{S_{11} \cdot S_{22}} = \left( \sqrt{S_{11}} + \sqrt{S_{22}} \right )^2.$ Очевидно теперь, что минимальное значение площадь таблицы будет принимать при $S_{11}={S_{11}}’, \ S_{22}={S_{22}}’$ где ${S_{11}}’, \ {S_{22}}’$ – данные в условии минимальные значения площадей соответствующих ячеек. Отсюда имеем минимальное значение высоты таблицы $h_{min}=\left( \sqrt{{S_{11}}’} + \sqrt{{S_{22}}’} \right )^2.$

Ссылки

Код решения на Ideone

e-olymp 5868. A xor B

Задача

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

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

2 натуральных числа [latex]A, B ≤ 10^9[/latex] в десятичной системе счисления, разделённые пробелом.

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

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

Тесты

# Входные данные Выходные данные
1 3 7 4
2 12 11 7
3 15 9 6
4 8 10 2
5 10 10 0

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

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

Введем два числа и применим операцию исключающего или.В языке программирования С++ данная операция выглядим так как показано в коде программы.

Ссылки

e-olymp
ideone

e-olymp 7944. Площадь прямоугольника

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex]  [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]1[/latex] [latex]1[/latex] [latex]1[/latex]
2 [latex]2[/latex] [latex]4[/latex] [latex]8[/latex]
3 [latex]511[/latex] [latex]428[/latex] [latex]218708[/latex]
4 [latex]5555[/latex] [latex]4444[/latex] [latex]24686420[/latex]
5 [latex]11[/latex] [latex]11[/latex] [latex]121[/latex]

 

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

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 920. Использование функций min и max

Задача

Задано три вещественных числа [latex]x, y[/latex] и [latex]z[/latex]. Определить [latex]\min\left(\max\left(x,y\right), \max\left(y,z\right), x+y+z\right)[/latex], воспользовавшись вспомогательными функциями для вычисления минимального и максимального элементов из двух заданных.

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

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

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

Вывести ответ с двумя десятичными знаками.

Тесты

# Входные данные Выходные данные
1  5 6 7  7.00
2  1.05 2.25 -2.15  1.15
3  3 3 3  3
4  8.85 5.67 7.33  7.33
5  12 -15 13  10

 

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

  1. Находим максимум из [latex]x[/latex] и [latex]y[/latex].
  2. Находим максимум из [latex]y[/latex] и [latex]z[/latex].
  3. Находим минимум из найденных максимумов.
  4. Находим минимум из найденного минимума и суммы данных чисел.

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

e-olymp 949. Двузначное из четырёхзначного

Задача

Из заданного четырёхзначного натурального числа образовать двузначное, состоящее из его средних цифр.

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

Одно четырёхзначное натуральное число.

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

Полученное двузначное число.

Тесты

# Входные данные Выходные данные
1 4765 76
2 7999 99
3 2514 51
4 9423 42
5 8234 23

 

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

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

Первым делом мы используем деление на 10 с присваиванием, чтобы избавиться от последней цифры числа. Дальше используем остаток от деления на 100, чтобы избавиться от первой цифры числа.

Ссылки

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

Код решения Ideone

e-olymp 7367. Спортсмен

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9 1
2 45 4
3 324 16
4 1234 28
5 213213123 153

Код программы №1 (с использованием цикла):

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

  • Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]

 

Ссылки

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

Код программы №2(с использованием линейных вычислений):

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

  • Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]

Ссылки

e-olymp 1474. Сломанные часы

Задача

В электронных часах произошел сбой, и теперь каждую секунду увеличивается не счетчик секунд, а счетчик часов. При переполнении счетчика часов (то есть при достижении [latex]24[/latex]) он сбрасывается в [latex]0[/latex] и увеличивается счетчик минут. Аналогично, при переполнении счетчика минут происходит его сброс и увеличивается счетчик секунд. При переполнении счетчика секунд он также сбрасывается в [latex]0[/latex], а остальные счетчики так и остаются равными [latex]0[/latex]. Известно, что сбой произошел в [latex]h_1[/latex] часов [latex]m_1[/latex] минут [latex]s_1[/latex] секунд. В этот момент часы показывали правильное время.

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

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

В первой строке задаются три целых числа [latex]h_1[/latex], [latex]m_1[/latex], [latex]s_1[/latex], определяющие время поломки часов. Во второй строке записаны три числа [latex]h_2[/latex], [latex]m_2[/latex], [latex]s_2[/latex], которые определяют показания часов в текущий момент времени ( [latex]0\;\le\;h_1,\;h_2\;\lt\;24[/latex], [latex]0\;\le m_1,\;m_2,\;s_1,\;s_2\;\lt\;60[/latex] ).

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

В единственной строке выведите правильное время (т.е. число часов, минут и секунд) в момент, когда сломанные часы будут показывать [latex]h_2[/latex] часов [latex]m_2[/latex] минут [latex]s_2[/latex] секунд.

Тесты

Входные данные Выходные данные
[latex]12 \; 0 \; 0\\12 \; 1 \; 0[/latex] [latex]12 \; 0 \; 24[/latex]
[latex]13 \; 59 \; 59\\12 \; 59 \; 59[/latex] [latex]13 \; 59 \; 58[/latex]
[latex]15 \; 12 \; 16\\15 \; 12 \; 16[/latex] [latex]15 \; 12 \; 16[/latex]
[latex]\;0 \;\;\; 0 \;\;\; 0\\23 \; 59 \; 59[/latex] [latex]23 \; 59 \; 59[/latex]
[latex]16 \; 0 \; 17\\16 \; 0 \; 18[/latex] [latex]16 \; 24 \;17[/latex]
[latex]11 \;\; 0 \;\; 53\\0 \;\;\; 0 \;\;\; 0[/latex] [latex]13 \; 48 \; 42[/latex]
[latex]1 \;\; 13 \; 18\\22 \; 51 \; 32[/latex] [latex]7 \;\;\; 4 \;\;\; 51[/latex]

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

 

Решение

Учитывая особенности хода сломанных часов, подсчитаем количество секунд в начальный и конечный моменты времени ( sum1 и sum2). Вычислим, сколько секунд прошло с момента поломки часов — для этого найдём разность sum2 - sum1, прибавим [latex]86400[/latex] —  количество секунд в сутках (поскольку мог произойти переход через момент времени [latex]0 \; : \; 0 \; : \; 0[/latex]) и найдём остаток от деления полученной суммы на [latex]86400[/latex].

Теперь найдём количество секунд, прошедших с начала суток, в которых поломались часы ( time1). Прибавим к нему количество секунд, прошедших с момента поломки часов и найдём остаток от деления на [latex]86400[/latex] полученного числа. Имеем time2 — правильное время в секундах. Далее, находим значения счётчиков часов [latex]h_3[/latex], минут [latex]m_3[/latex] и секунд [latex]s_3[/latex] которые соответствуют моменту времени time2.

Ссылки

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

e-olymp 51. К-домино

Задача

ДоминоРаботник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.

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

Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].

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

Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.

Входные данные Выходные данные
1 5 3
2 10 4
3 1000000 1414
4 555666777888 1054198
5 13 5

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

Решение

[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.
Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем:

[latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex]

[latex]k^2<=2s+1[/latex]

[latex]k=[\sqrt{2s+1}][/latex]

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

e-olymp 542. Поставка содовой воды

Задача

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

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

Три целых неотрицательных числа [latex]e[/latex], [latex]f[/latex], [latex]c[/latex], где [latex]e[/latex] ([latex]e < 1000[/latex]) — количество пустых бутылок, имеющихся у Тима в начале дня, [latex]f[/latex] ([latex]f < 1000[/latex]) — количество пустых бутылок, найденных в течение дня, и [latex]c[/latex] ([latex]1 < c < 2000[/latex]) — количество пустых бутылок, необходимых для покупки новой бутылки.

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

Сколько бутылок содовой воды смог выпить Тим, когда его замучила жажда?

Тесты

Входные данные Выходные данные
[latex]9[/latex] [latex]0[/latex] [latex]3[/latex] [latex]4[/latex]
[latex]5[/latex] [latex]5[/latex] [latex]2[/latex] [latex]9[/latex]
[latex]0[/latex] [latex]8[/latex] [latex]4[/latex] [latex]2[/latex]
[latex]22[/latex] [latex]0[/latex] [latex]4[/latex] [latex]7[/latex]

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

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

Можно считать, что изначально у Тима имеется [latex]e+f[/latex] пустых бутылок. Допустим, у него есть хотя бы [latex]c[/latex] бутылок, необходимых для покупки новой, Тим идет и меняет их на одну полную бутылку. Затем выпивает её, после чего общее количество пустых у него уменьшается на [latex]c-1[/latex]. То есть за [latex]e+f[/latex] пустых бутылок он сможет выпить [latex]\frac{e+f}{c-1}[/latex] бутылок содовой воды. Нам также следует добавить к [latex]c-1[/latex] маленькую константу [latex]a = 0.0001[/latex] для корректировки значения, чтобы в случае когда количество бутылок кратно [latex]c-1[/latex], Тиму нельзя было взять новую бутылку с недостающим количеством пустых бутылок для этого, следовательно, он должен выпить на одну бутылку меньше. В результате выводим целое число бутылок содовой воды, которые Тим смог выпить, когда его замучила жажда.

Ссылки

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

e-olymp 7612. Алекс и квадраты оригами

Задача

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

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

В одной строке два целых числа [latex]h[/latex] и [latex]w[/latex] ([latex]1 ≤ h, w ≤ 1000[/latex]) — высота и ширина куска бумаги.

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

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

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

Тесты

Входные данные Выходные данные
$100$ $100$ $50.000$
$10$ $80$ $10.000$
$50$ $76$ $25.333$
$60$ $27$ $20.000$
$8$ $3$ $2.667$

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

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

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за [latex]a[/latex] меньшую сторону листа бумаги, а за [latex]b[/latex] — большую. Если [latex]a[/latex] не больше [latex]\frac{b}{3}[/latex], то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги [latex]a[/latex]. В противном случае рассмотрим два варианта:

  1. Если [latex]\frac{a}{2}<\frac{b}{3}[/latex], то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число [latex]\frac{a}{2}[/latex].
  2. Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число [latex]\frac{b}{3}[/latex].

Таким образом, в случае [latex]a>\frac{b}{3}[/latex] ответом будет служить большее из двух чисел [latex]\frac{a}{2}[/latex] и [latex]\frac{b}{3}[/latex].
Минимальное из [latex]\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex] и [latex]a[/latex] число и будет ответом.
Проверим нашу формулу:если [latex]a<\frac{b}{3}[/latex], то [latex] \max\left(\frac{b}{3},\frac{a}{2}\right)=\frac{b}{3} [/latex], и тогда [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=a[/latex]. Иначе [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex], что нам и требуется.

Ссылки

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

e-olymp 2860. Сумма чисел на промежутке

Задача

Найти сумму целых чисел на промежутке от $a$ до $b$.

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

Два целых числа $a$ и $b$, по модулю не превышающих $10^9$.

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

Сумма целых чисел на промежутке от $a$ до $b$.

Тесты

Входные данные Выходные данные
2 5 14
249 318 19845
23 69 2162
124 200 12474
478 653 99528

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

Решение

Для того, что бы найти ответ, нам необходимо знание формул прогрессии, так как решением данной задачи является сумма $n$ первых членов арифметической прогрессии. Вычислить её можно по формуле $\displaystyle S_n = \frac{a_1 + a_n}{2} \cdot n$, где $a_1$ — это a из входного потока, а $a_n$ — это b. Тем не менее, мы все ещё не можем применить вышеприведенную формулу, так как нам неизвестно $n$. Выведем же его из формулы $n$-ого члена арифметической прогрессии: $a_n = a_1 + d \cdot (n-1)$, где $d$ — это разность арифметической прогрессии, которая по условию (хоть и негласно) равна единице. Зная это, из последней формулы выведем, что $n = a_n-a_1 + 1$. Теперь же, когда мы знаем все необходимые значения, остается только подсчитать сумму арифметической прогрессии по ранее данной формуле и подать результат на выход.

Ссылки

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

e-olymp 7366. Сколько до Нового Года?

Задача

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

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

В единственной строке целое число [latex]N \left(0 < N ≤ 31500000\right)[/latex] – количество секунд, которые остались до наступления Нового Года.

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

В одной строке через пропуск четыре целых числа – количество полных дней, часов, минут и секунд. После последнего числа пробел отсутствует.

Тесты

# Входные данные Выходные данные
1 5217656 60 9 20 56
2 7999 0 2 13 19
3 30123456 348 15 37 36
4 7841186 90 18 6 26
5 899650 10 9 54 10

Код

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

Вспомним, что:
1 сутки = 86400с;
1 час = 3600с;
1 минута = 60с.

Сперва рассчитаем кол-во полных суток в данном кол-ве секунд [latex]n[/latex]: [latex]\frac{n}{86400}[/latex].
Затем уберём кол-во секунд в полных сутках из исходного числа, а из оставшихся вычислим кол-во полных часов: [latex]\frac{n\bmod86400}{3600}[/latex].
Далее снова уберём кол-во секунд в полных часах и найдём кол-во полных минут: [latex]\frac{\left(n\bmod8640\right)\bmod3600}{60}[/latex].
Остаток от деления общего кол-ва секунд на 60 и будет искомым кол-вом секунд: [latex]n\bmod60[/latex].

Ссылки

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

e-olymp 932. Высота треугольника

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа: [latex]S (0 < S ≤ 100), и[/latex] [latex]a[/latex] ([latex]\left | a \right |[/latex] ≤ 100).

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

Искомая высота с точностью до сотых.

Тесты

# Входные данные Выходные данные
1 20 7 3.73
2 35 3 7.00
3 12 4 3.29
4 67 9 7.92
5 135 13 11.17

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

Алгоритм решения задачи

  1. Формула для вычисления площади треугольника [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot c[/latex], где [latex]h[/latex] – высота, а [latex]c[/latex] – сторона, к которой высота проведена.
  2. В задаче сказано, что основание больше высоты на величину [latex]a[/latex]. Значит вместо [latex]c[/latex] мы можем подставить в формулу [latex]h+a[/latex]. Теперь формула приобретает следующий вид: [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot \left (h+a \right )[/latex]
  3. Cовершив некоторые преобразования приходим к квадратному уравнению [latex]h^{2}+a\cdot h-2\cdot S = 0[/latex]
  4. Далее находим дискриминант по формуле [latex]D = a^{2}+4\cdot2\cdot S[/latex]. Находим корень квадратный из дискриминанта [latex]\sqrt{D}[/latex]
  5. Находим высоту по формуле [latex]h=\frac{-a+\sqrt{D}}{2}[/latex]
  6. Второй корень нам не подходит, потому что он меньше [latex]0[/latex], а длина не может быть отрицательной.
  7. Подставляем исходные данные в формулы, получаем результат.

Также подробное описание представлено в коде программы.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 3609. Стартовая скорость

Задача

Кристина Стуй, Олеся Повх, Елизавета Брызгина, Мария Ремень

Женская олимпийская сборная Украины в эстафете 4×100 метров на олимпийских играх в Лондоне в составе (Кристина Стуй, Олеся Повх, Елизавета Брызгина, Мария Ремень)


Несмотря на то, что женская сборная Украины в эстафете [latex]4 \times 100[/latex] метров на олимпийских играх в Лондоне в составе Кристины Стуй, Олеси Повх, Елизаветы Брызгиной и Марии Ремень выступила очень достойно и завоевала бронзовые медали, подобная мысль назойливо мучила и программиста Васю.

Как показали тщательные экспериментальные проверки, модель, построенная им в задаче «Крейсерская скорость» оказалась не совсем точной. Многочасовые наблюдения, проведённые им на тренировках как украинских спортсменок, так и спринтеров из других стран, показали, что некоторые спортсмены во время старта разгоняются, а некоторые притормаживают. Но всё равно, после [latex]25[/latex] стартовых метров дистанции они движутся далее равномерно.

Феномен с «притормаживанием» Васе удалось с точки зрения физики пояснить довольно просто. Во время старта каждый из спортсменов имеет некоторую стартовую скорость, приобретённую в результате мощного отталкивания от стартовых колодок. Эта скорость может быть либо меньше «крейсерской», либо больше. В первом случае спортсмену нужно работать над наращиванием мышц ног для увеличения силы отталкивания. Во втором – мышцы уже наращены, но в результате того, что сила сопротивления воздуха зависит от площади соприкосновения тела спортсмена с ним, во время распрямления спортсмена во время старта эта сила сопротивления возрастает и становится постоянной только после указанных выше [latex]25[/latex] стартовых метров дистанции.

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

Ваша задача помочь в этом Васе, считая, что на первых [latex]25[/latex] метрах дистанции движение легкоатлета является равноускоренным, независимо от того, ускоряется он или замедляется.

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

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

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

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

Тесты

Входные данные Выходные данные
[latex]9.63[/latex] [latex]19.32[/latex] [latex]10.844104[/latex]
[latex]9.77[/latex] [latex]19.59[/latex] [latex]10.606721[/latex]
[latex]9.69[/latex] [latex]19.40[/latex] [latex]10.469771[/latex]
[latex]10.02[/latex] [latex]20.12[/latex] [latex]10.548908[/latex]
[latex]9.88[/latex] [latex]19.85[/latex] [latex]10.781564[/latex]

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

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

Со школы знаем формулу скорости, [latex]v=\frac{l}{t}[/latex]. Найдем из неё [latex]l=vt[/latex].
Пусть [latex]l_1[/latex] и [latex]l_2[/latex] — это расстояния, на которых спортсмен бежит с «крейсерской» скоростью соотвественно на дистанциях в [latex]100[/latex] и [latex]200[/latex] метров, где [latex]l_1=l-l_p[/latex], где [latex]l[/latex] — это длина дистанции, а [latex]l_p[/latex] — длина разгона (известно из условия задачи). Аналогично для [latex]l_2[/latex]. Заменим [latex]t[/latex] на [latex]t_1-t_p[/latex], где [latex]t_1[/latex] — время, за которое спортсмен пробегает всю дистанцию, а [latex]t_p[/latex] — время разгона на первых [latex]25[/latex]-ти метрах дистанции. Получаем формулы: [latex]l_1=v(t_1-t_p)[/latex] и [latex]l_2=v(t_2-t_p)[/latex]. Из отношения этих формул [latex]\frac {l_1}{l_2}=\frac {v(t_1-t_p)}{v(t_2-t_p)}[/latex], найдем [latex]t_p[/latex]. Имеем [latex]t_p=\frac{l_1t_2-l_2t_1}{l_2-l_1}[/latex]. Подставляем [latex]l_1=v(t_1-t_p)[/latex]. Находим «крейсерскую» скорость спортсмена, [latex]v=\frac{l_1}{t_1-t_p}[/latex]. Из уравнения равноускоренного движения
[latex]x=v_0t \times \frac{at^2}{2}[/latex], где [latex]x=25[/latex] метров (длина разгона). Находим [latex]v_0[/latex] — это и есть стартовая скорость спортсмена. Для этого заменим [latex]a[/latex] на [latex]\frac{v-v_0}{t_p}[/latex]. Приводим подобные и выражаем [latex]v_0[/latex]. В итоге получаем формулу стартовой скорости спортсмена, [latex]v_0=\frac{50-vt_p}{t_p}[/latex]. Задача решена.

Ссылки

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

e-olymp 112. Торт

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

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

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

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

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

TESTS

$t_1$

$t_2$

$t_3$

$t$

3 3 3 1.00
4 67 50 3.51
228.22 8 2.28 1.76
1577 157.7 15.77 14.21

C ветвлением:

Без ветвления:

 

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

Ссылки

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

e-olymp 2071. Три грибника

Задача

Три грибника

Три грибника


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

Сначала Пётр дал Васе и Николаю по столько грибов, сколько у них уже было. Николай быстро понял, что так будет не по-братски, и дал Василию и Петру по столько грибов, по сколько у них стало. Василий не мог отстать от сотоварищей и также дал каждому из друзей по столько грибов, сколько у них этому моменту имелось. И тут друзья с удивлением обнаружили, что у всех стало грибов поровну.

Сколько грибов было у каждого перед привалом, если известно, что все вместе они собрали [latex]n[/latex] грибов?

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

В единственной строке находится единственное натуральное число [latex]n[/latex] ([latex]n ≤ 30000[/latex]).

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

В единственной строке вывести через пробел количество грибов перед привалом у Петра, Василия и Николая, соответственно. Гарантируется, что все входные данные корректны.

Тесты

Входные данные
Выходные данные
[latex]24[/latex] [latex]13[/latex] [latex]4[/latex] [latex]7[/latex]
[latex]48[/latex] [latex]26[/latex] [latex]8[/latex] [latex]14[/latex]
[latex]72[/latex] [latex]39[/latex] [latex]12[/latex] [latex]21[/latex]
[latex]96[/latex] [latex]52[/latex] [latex]16[/latex] [latex]28[/latex]
[latex]120[/latex] [latex]65[/latex] [latex]20[/latex] [latex]35[/latex]
[latex]144[/latex] [latex]78[/latex] [latex]24[/latex] [latex]42[/latex]

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

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

Представим нашу задачу в форме таблицы, строки которой будут соответствовать грибникам, а столбцы — количеству грибов у соответствующего грибника между обменами:

П.
[latex]x_{1}[/latex] [latex]x_{2} = x_{1} — y_{1} — z_{1}[/latex] [latex]x_{3} = 2 \cdot x_{2}[/latex] [latex]x_{4} = 2 \cdot x_{3}[/latex]
В.
[latex]y_{1}[/latex] [latex]y_{2} = 2 \cdot y_{1}[/latex] [latex]y_{3} = 2 \cdot y_{2}[/latex] [latex]y_{4} = y_{3} — x_{3} — z_{3}[/latex]
Н.
[latex]z_{1}[/latex] [latex]z_{2} = 2 \cdot z_{1}[/latex] [latex]z_{3} = z_{2} — x_{2} — y_{2}[/latex] [latex]z_{4} = 2 \cdot x_{3}[/latex]

По условию задачи [latex]x_{4} = y_{4} = z_{4} = \frac n 3[/latex]. Тогда выражением нужных корней и подстановкой известных считаем [latex]x_{1}[/latex], [latex]y_{1}[/latex] и [latex]z_{1}[/latex] начиная с правого столбца и двигаясь налево:

[latex]x_{3} = \frac {x_{4}}{2} = \frac {n}{6}[/latex]
[latex]z_{3} = \frac {z_{4}}{2} = \frac {n}{6}[/latex]
[latex]y_{3} = y_{4} + x_{3} + z_{3}= \frac {n}{3} + \frac {n}{6} + \frac {n}{6} = \frac {2 \cdot n}{6}[/latex]
[latex]x_{2} = \frac {x_3}{2} = \frac {n} {12}[/latex]
[latex]y_{2} = \frac {y_3}{2} = \frac {n}{3}[/latex]
[latex]z_{2} = z_{3} + y_{2} + x_{2} = \frac {n}{6} + \frac {n}{12} + \frac {n}{3} = \frac {7 \cdot n}{12}[/latex]
[latex]y_{1} = \frac {y_{2}}{2} = \frac {n}{6}[/latex]
[latex]z_{1} = \frac {z_2}{2} = \frac {7 \cdot n}{24}[/latex]
[latex]x_{1} = x_{2} + y_{1} + z_{1} = \frac {n}{12} + \frac {n}{6} + \frac {6 \cdot n}{12} = \frac {13 \cdot n}{24}[/latex]

Получили ответы: [latex]x_{1} = \frac {13 \cdot n}{24}[/latex],  [latex]y_{1} = \frac {n}{6}[/latex] и [latex]z_{1} = \frac {7 \cdot n}{24}[/latex]. Это и будет количество грибов соответственно у Пети, Васи и Николая в самом начале. Отсюда получаем итоговую формулу решения, указанную в коде программы.

Ссылки

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

e-olymp 926. Формула Герона

Задача

Герон Александрийский

Герон Александрийский

Задано стороны [latex]a, b, c, d[/latex] и диагональ [latex]f[/latex] выпуклого четырехугольника. Определить площадь четырехугольника, используя вспомогательную функцию вычисления площади треугольника по формуле Герона.

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

В одной строке задано 5 действительных чисел [latex] a, b, с, d, f[/latex] [latex](0 < a, b, c, d, f ≤ 100)[/latex], как показано на рисунке.

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

Вывести площадь четырехугольника с точностью 4 знака после десятичной точки.

Тесты

# Входные данные Выходные данные
1 2 2 2 2 2 3.4641
2 7 7 5 6 2 11.6120
3 9 5 3 2 4 2.9047
4 5 7 2 3 4 12.7027
5 7 8 6 2 5 22.0043

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

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

Дано

Фигура, состоящая из двух треугольников;

Цель

Посчитать площадь данной фигуры;

Идея

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

Способ решения

  1. Вспомним формулу Герона [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)}[/latex].
  2. Поймем, что нам не хватает некоторых данных, а именно [latex]p[/latex].
  3. Понимаем, что [latex]p[/latex] — это полупериметр, который находится по формуле [latex]p=\frac{P}{2}[/latex].
  4. Возникает вопрос, что такое [latex]P[/latex] ? Приходим к выводу, что это периметр.
  5. Находим формулу периметра, который равен [latex]P=a+b+c[/latex]. Данная формула была подведена под условие нашей задачи.
  6. После того как мы вывели формулы, можем приступать к решению задачи.
  7. Подставляя исходные данные в формулы, которые были представлены выше, получаем результат.
  8. Более подробное описание каждого действия представлено выше в коде. Это сделано для того, чтобы пользователь получал ответы на интересующие его вопросы непосредственно в момент их возникновения.

Ссылки

Задача на e-olymp

Код задачи на ideone

e-olymp 2059. Озеро с лилиями

Задача

На лесном озере начали цвести лилии. В первый день расцвела одна лилия, а потом каждый день количество цветущих лилий удваивалось. На [latex]n[/latex]-ый день всё озеро было покрыто цветущими лилиями. А на какой день была покрыта цветущими лилиями половина поверхности озера?

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

Номер дня [latex]n[/latex](1 < [latex]n[/latex] ≤ 200), на который вся поверхность озера была покрыта цветущими лилиями.

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

День, на который была покрыта лилиями половина поверхности озера.

Тесты

Входные данные Выходные данные
3 2
4 3
185 184

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

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

Так как количество лилий увеличивалось вдвое с каждым днем, то половина поверхности озера была покрыта лилиями на предпоследний день [latex](n — 1)[/latex].

Ссылки

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