Задача
Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок «три — чотири» хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час $t_1$, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робить те ж саме за час $t_2$.
Весь цей час викладач настільки захоплений доведенням теореми, що взагалі нічого не чує. І тільки коли обидві бульбашки лопнуть одночасно, викладач почує шум і обернеться. І тоді вже точно студентам попаде на горіхи, а більше усього тому, хто приніс на пару жувальні гумки.
Визначте, скільки часу хлопці можуть насолоджуватись надуванням бульбашок, не замічені викладачем.
Наприклад, якщо $t_1 = 2$, $t_2 = 3$, то буде відбуватись наступне:
Степан надуває бульбашку з моменту часу $t = 0$ до моменту часу $t = 2$, потім бульбашка лопається, і він надуває бульбашку знову — з моменту часу $t = 2$ до моменту часу $t = 4$, а потім ще раз — з моменту часу $t = 4$ до $t = 6$.
Товариш Степана надуває бульбашку з $t = 0$ до $t = 3$ і ще раз з $t = 3$ до $t = 6$.
В момент часу $t = 6$ бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: «Все, Степан! Ти мене дістав!».
Формат вхідних даних
Перший рядок вхідного файлу містить два цілих числа $t_1, t_2 (1 \leqslant t_1, t_2 \leqslant 10^9).$
Формат вихідних даних
Вихідний файл повинен містити одне ціле число — час, протягом якого Степан з товаришем можуть насолоджуватись надуванням бульбашок.
Тести
| № | Вхідні дані | Вихідні дані |
| 1 | 2 3 | 6 |
| 2 | 1 16 | 16 |
| 3 | 10 10 | 10 |
| 4 | 100000000 150000000 | 300000000 |
| 5 | 17 41 | 697 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> using namespace std; long nod (int a, int b) { return b == 0 ? a : nod (b, a % b); } int main() { int t1, t2; cin >> t1 >> t2; cout << t1 * (t2 / nod (t1, t2)); return 0; } |
Розв’язання
-
Задача зводиться до пошуку НСК (найменше спільне кратне). Формула для знаходження $НСК$: $НСК(a, b)={{a\cdot b}\over{НСД(a, b)}}$, де НСД — найбільший спільний дільник. Для його знаходження скористуємось алгоритмом Евкліда, У даному розв`язку реалізованим за допомогою рекурсії у функції $nod$.
Посилання
- Задача на e-olymp
- Код на ideone
- Зараховане розв’язання на e-olymp
— По требованиям к оформлению после условия задачи должны быть тесты, потом код программы и только после этого пояснения к алгоритму решения.
— В ходе решения было бы неплохо записать формулу в формате дроби 🙂
Исправлено
Еще можно решить так:
А в чем разница?
— В условии лучше писать так — $t_1.$
— Неравенства должны выглядеть так $\leqslant$.
— Почитайте, что-нибудь о правилах оформления кода.
Исправлено
— А зачем заводить переменную и записывать в него НОД просто, чтобы один раз разделить?
— Текст «алгоритм Эвклида» должен быть гиперссылкой на статью Википедии. И описать как вы его реализовали.
Исправлено
— Пожалуйста, возьмите деление в скобки и сделайте все переменные типа int.
— В постоянной ссылке не стоит использовать символы кириллицы.
Тип int не подходит по диапазону данных (протестировано). Постоянная ссылка, в которой используются символы кириллицы — это ссылка на Википедию. Исправлено скобки при делении
Света, пожалуйста, серьезнее отнеситесь к моим замечаниям. Каждый мой комментарий отнимает у Вас день времени и один балл. Но мне не сложно описать детальнее. Тогда Вам не придется смотреть работы других студентов на сайте.
1. Все данные и промежуточные вычисления не выходят за пределы типа данных int для компилятора га сайте e-olymp.com. Конечный результат, который вы печатает может выходить за пределы int, но Вы его нигде не храните, значит переменная для него не понадобится.
2. В арифметическом выражении при печати результата, вы берете умножение в скобки и только потом делите на НОД. Это лишнее. Более того, поскольку это НОД, логичнее было бы взять в скобки деление, чтобы оперировать с менее длинными числами. В вашем случае, это существенного значения не имеет, но лучше привыкнуть поступать логично, чем алогично.
3. Когда вы редактируете свою работу, у вас есть поле «постоянная ссылка» в которой вы можете выбрать как будет выглядеть адрес вашей работы — постоянная ссылка на вашу статью. Сейчас Ваша работа имеет такой адрес — https://cpp.mazurok.com/e-olymp-7239-%d0%b2%d1%81%d0%b5-%d1%81%d1%82%d0%b5%d0%bf%d0%b0%d0%bd-%d1%82%d0%b8-%d0%bc%d0%b5%d0%bd%d0%b5-%d0%b4%d1%96%d1%81%d1%82%d0%b0%d0%b2. Это создает некоторые проблемы при экспорте и цитировании. Пожалуйста, сделайте этот адрес таким https://cpp.mazurok.com/e-olymp-7239. Такой адрес будет коротким, уникальным и достаточно информативным.
4. В вашей функции вычисления НОД все эти минимумы и максимумы являются абсолютно излишними. У нас на сайте есть много вариантов нахождения НОД. Можете выбрать что-то лаконичное или вызвать стандартную функцию.
5. Линейными мы назвали программы с простой структурой последовательных вычислений. Программами с ветвлением мы назвали чуть более сложные программы с условными операторами, но без циклов. Кроме всего прочего, об этом написано еще и в описании категорий. Ваш выбор категорий содержит противоречие.
Хорошо. Я правда думал, что Вы так напишите