e-olymp 6. Путёвки

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

e-olymp 6. Путёвки

Туристическая фирма не успела из-за больших морозов продать [latex]n[/latex] ([latex]n < 15[/latex]) путёвок на горнолыжные базы, срок действия которых уже наступил. С целью уменьшения убытков, было решено с 1 февраля все такие путёвки, которым осталось [latex]d_k[/latex] ([latex]d_k \le 30[/latex]) дней, продавать по номинальной стоимости – по [latex]c_k[/latex] ([latex]c_k \le 100[/latex]) грн за день только за те дни, что остались со дня продажи ([latex]k = 1..n[/latex]).

На какую наибольшую сумму можно реализовать эти путёвки, если каждый день продавать по одной путёвке?

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

Первая строка содержит количество путёвок [latex]n[/latex]. Каждая из следующих [latex]n[/latex] строк содержит два числа – количество дней [latex]d_k[/latex] и стоимость дня [latex]c_k[/latex].

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

Максимальная сумма прибыли.

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

Решим эту задачу полным перебором (методом грубой силы). Для этого необходимо перебрать все возможные варианты реализации. К примеру, дано три путевки:

Первая путёвка

  • срок действия: 2
  • номинальная стоимость: 13

Вторая путёвка

  • срок действия: 1
  • номинальная стоимость: 33

Третья путёвка

  • срок действия: 3
  • номинальная стоимость: 7

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

Путевки Перебор всех возможных вариантов
Вариант 1 Вариант 2
Очередность Результат Очередность Результат
Первая 1 20 1 20
Вторая 2 3
Третья 3 2
Вариант 3 Вариант 4
Очередность Результат Очередность Результат
Первая 2 53 2 20
Вторая 1 3
Третья 3 1
Вариант 5 Вариант 6
 Очередность Результат Очередность Результат
Первая 3 40 3 7
Вторая 1 2
Третья 2 1

Теперь очевидно, что максимальная сумма прибыли равна 53. Таким образом можно решить данную задачу при любых входных данных. Но возникает проблема, когда путевок слишком много (или даже не очень). Количество перестановок для [latex]n[/latex] элементов равно [latex]n![/latex]. Это значит, что при количестве путевок, равном [latex]14[/latex] (максимальное возможное количество в данной задаче), количество перестановок равно [latex]14! = 87178291200[/latex], а ведь для каждой необходимо подсчитать сумму за реализованые путевки. Современные компьютеры не могут справиться с этой задачей за короткий промежуток времени, поэтому явным решением является оптимизация программы.

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

Тесты

Входные данные Выходные данные
4
2 37
3 45
1 46
4 30
232
3
1 1
2 2
3 3
11
4
1 2
3 4
5 6
7 8
84

Реализация

ideone: ссылка
Засчитаное решение: ссылка

e-olymp 912. Количество предложений

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

e-olymp 912. Количество предложений

Определить количество предложений в заданном фрагменте текста.

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

В единственной строке задан фрагмент текста на английском языке, количество символов в котором не превышает 250. Гарантируется, что в тексте отсутствуют тире, дефисы, цифры и числа.

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

Единственное число — количество предложений в фрагменте.

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

Нужно заметить, что каждое предложение может заканчиваться точкой, восклицательным знаком или вопросительным знаком. Значит, если в тексте мы нашли какой-то из этих символов, то мы нашли и предложение. Но возникает проблема. Предложение может заканчиватся несколькими знаками препинания (к примеру, многоточием). Так как многоточие — это три поставленых рядом точки, то, если считать количество предложений как количество знаков препинания, которыми может заканчиваться предложение, мы, вероятнее всего, допустим ошибку. Это решается легким путем: при встрече таких знаков, идущих подряд, мы берем во внимание только один из них, игнорируя остальные. Таким образом мы можем подсчитать количество предложений.

Тесты

Входные данные Выходные данные
Hello, World! 1
Those lips that Love’s own hand did make
Breathed forth the sound that said ‘I hate,’
To me that languish’d for her sake:
But when she saw my woeful state,

Straight in her heart did mercy come,
Chiding that tongue that ever sweet
Was used in giving gentle doom,
And taught it thus anew to greet:

‘I hate’ she alter’d with an end,
That follow’d it as gentle day
Doth follow night, who like a fiend
From heaven to hell is flown away;

‘I hate’ from hate away she threw,
And saved my life, saying — ‘not you.’

1
Winter… 1
Winter 0

Реализация

ideone: ссылка
Засчитаное решение: ссылка

e-olymp 7. Римские числа

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

e-olymp 7. Римские числа

Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления.
M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000.

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

В строке записано два числа в римской системе счисления, между которыми стоит знак + .

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

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

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

Считываем два числа и представляем каждое из них в десятичной системе счисления. Чтобы перевести число из римской системы в десятичную, нужно изначально считать, что в десятичной системе оно равно нулю. Это число будет нашим результатом. Далее, нужно перебрать все цифры римского числа, следуя таким правилам:

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

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

Вспомогательные числа
В римской системе счисления В десятичной системе счисления
1 I
4 IV
5 V
9 IX
10 X
40 XL
50 L
90 XC
100 C
400 CD
500 D
900 CM
1000 M

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

Тесты

Входные данные Выходные данные
I+I II
IV+VIII XII
MM+CXC MMCXC
CXCIX+I CC

Реализация

ideone: ссылка
Засчитаное решение на e-olymp: ссылка

 

MLoops 14

MLoops14.

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

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр [latex]k < n[/latex].
Замечание 2. Многоточие означает продолжение последовательности.

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

Легко заметить, что строки с номерами [latex]1 + i \left( k + 1 \right), i \in \mathbb{N}_0[/latex] состоят из натуральных чисел от 1 до k. Также в таблице есть столбцы, совпадающие с первой строкой. Все остальные клетки заполнены символом «+».

Тесты

Входные данные Выходные данные
[latex]n[/latex] [latex]m[/latex] [latex]k[/latex]
1 2 1
5 5 1
3 4 2
10 10 4
33 22 11

Реализация

ideone: ссылка

 

MLoop 16

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

MLoop16.

Вычислите с точностью [latex]\epsilon[/latex] значение функции [latex]f\left( x \right) = \frac{\sin 2x}{x}[/latex]. При вычислениях допустимо использовать только арифметические операции.

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

Разложим [latex]g \left( x \right) = \sin x[/latex] по формуле Тейлора с опорной точкой [latex]x_0 = 0[/latex] и остаточным членом в форме Лагранжа:
[latex]g \left( x \right) = P_n \left( x_0 ; x \right) + R_n \left( x_0 ; x \right)[/latex],
[latex]P_n \left( x_0 ; x \right) = g \left( x_0 \right) + \sum_{k = 1}^{n} \frac{g^{\left( k \right)} \left( x_0 \right) }{k!} \left( x — x_0 \right) ^k[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{g^{\left( n + 1 \right)} \left( \xi \right)}{\left( n + 1 \right) !}\left( x — x_0 \right) ^{n + 1} , x_0 < \xi < x[/latex].

Найдем производные [latex]g \left( x \right)[/latex]:
[latex]g’ \left( x \right) = \cos x = \sin \left( x + \frac{\pi}{2} \right)[/latex],
[latex]g» \left( x \right) = \cos \left( x + \frac{\pi}{2} \right) = \sin \left( x + 2 \frac{\pi}{2} \right)[/latex],
[latex]g»’ \left( x \right) = \cos \left( x + 2 \frac{\pi}{2} \right) = \sin \left( x + 3 \frac{\pi}{2} \right)[/latex],
[latex]\cdots[/latex]
[latex]g^{\left( k \right)} \left( x \right) = \cos \left( x + \left( k — 1 \right) \frac{\pi}{2} \right) = \sin \left( x + k \frac{\pi}{2} \right)[/latex].

Вычислим значение функции и ее производных в точке [latex]x_0[/latex]:
[latex]g \left( x_0 \right) = \sin x_0 = \sin 0 = 0[/latex],
[latex]g’ \left( x_0 \right) = \sin \left( x_0 + \frac{\pi}{2} \right) = \sin \frac{\pi}{2} = 1[/latex],
[latex]g» \left( x_0 \right) = \sin \left( x_0 + 2 \frac{\pi}{2} \right) = \sin \pi = 0[/latex],
[latex]g»’ \left( x_0 \right) = \sin \left( x_0 + 3 \frac{\pi}{2} \right) = \sin \frac{3 \pi}{2} = -1[/latex],
[latex]\cdots[/latex]
[latex]g ^{ \left( 2k — 1 \right) } \left( x_0 \right) = \sin \left( x_0 + \left( 2k — 1 \right) \frac{\pi}{2} \right) = \sin \left( \pi k + \frac{\pi}{2} \right) = \left( -1 \right) ^{k — 1}[/latex],
[latex]g ^{ \left( 2k \right) } \left( x_0 \right) = \sin \left( x_0 + 2k \frac{\pi}{2} \right) = \sin \pi k = 0[/latex].

Тогда
[latex]P_n \left( x_0 ; x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! }[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]g \left( x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]f \left( x \right) = \frac{ g \left( 2x \right) }{ x } = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! }[/latex].

Осталось найти такое [latex]n \in \mathbb{N}[/latex], чтобы выполнялось неравенство
[latex]\left| \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! } \right| \le \left| \frac{ \left( 2x \right) ^ {n + 1} }{ x \left( n + 1 \right) ! } \right| < \epsilon[/latex].

Для ускорения вычислений зададим реккурентную формулу для слагаемых суммы
[latex]\sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Представим каждое слагаемое суммы в виде
[latex]\alpha_k = \alpha_{k — 1} \cdot b_k = \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Выразим [latex]b_k[/latex]:
[latex]b_k = \frac{ \alpha_k }{ \alpha_{ k — 1 } } = \frac{ \left( -1 \right) ^ {k — 1} \cdot \left( 2x \right) ^ {2k — 1} \cdot x \left( 2 \left( k — 1 \right) — 1 \right) ! }{ x \left( 2k — 1 \right) ! \cdot \left( -1 \right) ^ { \left( k — 1 \right) — 1 } \cdot \left( 2x \right) ^ {2 \left( k — 1 \right) — 1} } = — \frac{4x^2}{\left( 2k — 2 \right) \left( 2k — 1 \right)}[/latex].
Тогда
[latex]\alpha_k = \begin{cases} 2 & k = 1, \\ \alpha_{k-1} \cdot b_k & k > 1. \end{cases}[/latex]

Тесты

Входные данные Выходные данные
[latex]x[/latex] [latex]\epsilon[/latex] [latex]f\left( x \right) = \frac{\sin 2x}{x} + \lambda, \lambda\in\left( -\epsilon;\epsilon \right)[/latex]
[latex]\frac{5\pi}{2}[/latex]  [latex]0[/latex]  [latex]\frac{2}{5\pi}[/latex]
 [latex]\pi[/latex]  [latex]0.01[/latex]  [latex]0[/latex]
 [latex]0[/latex]  [latex]0.1[/latex]  [latex]\emptyset[/latex]

Реализация

ideone: ссылка

e-olymp 111. Часы

Часы.

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

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

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

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

Тесты

Входные данные Выходные данные
Начальное время Конечное время Количество ударов
13:30 15:10 7
0:00 23:59 180
12:30 12:30 1
22:08 22:22 0

Реализация

ideone: ссылка
Засчитаное решение на e-olymp: ссылка