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 165. Симметрия

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

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

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

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

 

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]10[/latex] [latex]2[/latex]
2 [latex]116[/latex] [latex]3[/latex]
3 [latex]1[/latex] [latex]1[/latex]
4 [latex]454[/latex] [latex]2[/latex]
5 [latex]12301230[/latex] [latex]2[/latex]

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

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

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

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

Mif 2. Максимум из трех

Задача

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]max (x, y, z)[/latex].

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

Действительные числа $latex x,y,z$.

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

[latex]max (x, y, z)[/latex]

Тесты

x y z max
8 3 5 8
9 16 7 16
5 125 150 150

Решение

Пусть даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Нужно получить [latex]max(x,y,z)[/latex]. Для этого вводим [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Предполагаем, что $latex z$ хранит максимальное значение. Затем, используя оператор if, сравниваем $latex y, x$. Выводим максимальное значение.

Пример работы программы можно увидеть на ideone.

Mif 1

Постановка задачи

Даны действительные числа [latex]x, y[/latex]. Получить [latex]max(x,y)[/latex].

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

Два действительных числа — [latex]x[/latex] и [latex]y[/latex].

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

Число, являющееся максимумом из двух чисел — [latex]maxOfTwo[/latex]

Тесты

Входные данные Выходные данные
1 3 4 4
2 -3 -5 -3
3 0 12 12

 

Решение:

Альтернативное решение:

 

Описание решения:

Объявляем три переменные типа  int  —  x, y, maxOfTwo . Вводим с клавиатуры значения для  x и  y . После чего с помощью условного оператора  if-else  проверяем  x>y . Если истинно, присваиваем переменной  maxOfTwo  значение переменной  x , а иначе  MaxOfTwo = y . Выводим значение  MaxOfTwo  с помощью функции  System.out.println() .

Описание альтернативного решения:

Объявляем три переменные типа  int  —  x, y, maxOfTwo . Вводим с клавиатуры значения для  x и  y . Используя тернарный оператор  ?: проверяем истинность выражения  x>y и присваиваем результат операции переменной  maxOfTwo . Выводим значение  MaxOfTwo  с помощью функции  System.out.println() .

 

 

 

 

Mif 5

Постановка задачи

Даны действительные числа [latex]x, y, z[/latex]. Вывести наименьшее и наибольшее из них. Если наименьших или наибольших чисел окажется несколько, то укажите в скобках количество.

Входные данные: действительные числа [latex]x, y, z.[/latex]

Выходные данные: Максимальное значение (Highest value), количество максимальных значений (Count of highest values), минимальное значение (Lowest value), количество минимальных значений (Count of lowest values)

Тесты

Входные данные Выходные данные
 [latex]x, y, z[/latex] Максимум Количество максимумов Минимум Количество минимумов
1 10 20 1 10 2
2 10
3 20

Решение

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для нахождения нахождения найбольшего max и найменьшего min значений используем цикл for. Если текущее число больше максимального, то ставим счетчик countMax на 1 и сохраняем новое максимальное значение max. Если последующее число равно текущему максимальному max, то увеличиваем счетчик countMax. Аналогично и для поиска найменьшего min значения.

ML36. Движение катера

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

Катер движется по течению реки из пункта A в пункт B и обратно с собственной скоростью $latex v$ км/час. Скорость течения постоянна — $latex u$ км/час. Расстояние между пунктами составляет $latex s$ км. Для любых действительных неотрицательных значений расстояния и скоростей вычислить время в пути $latex t_{boat}$.

Тесты

Входные данные: физические величины $latex v$, $latex u$, $latex s$

Выходные данные: физическая величина $latex t_{boat}$

Входные данные Выходные данные
1 3 2 10 12.0
2 1.4 0.4 3.6 5.6
3 3 6 10 Infinity
4 2 1 0 0.0

Код

Код доступен на ideone

Пояснение

Скорость катера, когда он идет по течению, равна $latex (v+u)$, а когда против — $latex (v-u)$. Время $latex t$ вычисляется по формуле $latex t = \frac{s}{v}\\ $, где $latex s$ — расстояние, $latex v$ — скорость, соответственно общее время  пути катера составит  $latex t_{boat} = {\frac{s}{v+u}\\+\frac{s}{v-u}\\} $. При этом время — величина неотрицательная, а делитель дроби не должен быть нулевым, соответственно имеем ограничение $latex v-u > 0, v > u $.

 

А136и

Задача: Даны натуральное число n, действительные числа [latex]k_{1}, k_{2}, \dots, k_{n}[/latex] Вычислить [latex]\frac{k_{1}}{0!} + \frac{k_{2}}{1!} + \dots + \frac{k_{n}}{(n-1!)} [/latex]

Тесты

Число-n Действительные числа Результат
5 4 5 6 7 8 13,5
7 5 4 7 9 2 8 3 14,1542
3 6 9 3 16,5

Код:

Решение:

  1. Вводим n, k (действительные числа);
  2. Получаем очередное действительное число k.
  3. Делим на факториал и суммируем;

Решение на Ideone

A278

Задача A278

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

Даны натуральные числа n_{1},\dots,n_{m}, действительные числа x_{1},\dots,x_{m}. Вычислить \frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}.

Тестирование

Входные данные Выходные данные
1. 1 2 4 -1 -0.4
2. 1 2 3 4 5 0.6 1.88889
3. 5 -2 1 0.2 3 -3 2 0 -1.70909
4. 10 3.3 4 0.4 6 0.01 8 1 1 8 1.7469
5. 3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1 4.58095

 

Код

Алгоритм решения (потоковая обработка)

Считываем числа до конца входного потока и поочередно записываем их в переменные n и n соответственно.
Пока вводятся данные:

  1. Вычисляем значение выражения n_1\cdot x_1+\dots+n_m\cdot x_m, накапливая сумму в числитель n.
  2. Вычисляем значение выражения n_1+\dots+n_m, накапливая сумму  в делителе n.
  3. Находим результат n от деления n на  n

Код на ideone.com