e-olymp 8372. Составить треугольник

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

Задача

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

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 6 7 YES
2 3 7 4 NO
3 16 24 32 YES
4 54 1 100 NO
5 1 1 1 YES

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

Код программы (Линейные вычисления)

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

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

Код программы на ideone (Линейные вычисления)

Код программы на ideone (Ветвление)

e-olymp 4718. Привет, Гарри!

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

Задача

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

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

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

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

В первой строке выведите приветствие.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 Harry Hello, Harry
2 Peter Hello, Peter
3 Emily Hello, Emily
4 Anna-Maria Hello, Anna-Maria
5 Zhao Yun Hello, Zhao Yun

Код

Решение

Для того, чтобы задать переменную-строку, воспользуемся библиотекой string. Далее, введём переменную, к примеру name (имя). В строке вывода зададим неизменную часть фразы Hello, и саму переменную.

Ссылки

ideone
e-olymp

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

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