e-olymp 7239. «Все, Степан! Ти мене дістав!»

23/12/2020 by Жук Світлана

Задача

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок «три — чотири» хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час $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

Код

#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;
}

#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;

}

Розв’язання

алгоритмом Евкліда,

Посилання

Задача на e-olymp
Код на ideone
Зараховане розв’язання на e-olymp

Related Images:

e-olymp 1602. НОК двух натуральных чисел

22/12/2020 by Федяєва Євгенія

Задача

Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

Вывести $НОК$ чисел $a$ и $b$.

Тесты

№	Входные данные	Выходные данные
1	42 24	168
2	32 14	224
3	101 45	4545

Код

#include <iostream>
using namespace std;
 
long int GCD(int num1, int num2) 
{
    if(num1 == num2) return num1;
    while(num1 && num2)
    {
        if(num1 > num2) num1 %= num2;
        else num2 %= num1;
    }
    return num1+num2;
}
 
int main() {
    long int num1, num2, gcd;
    cin >> num1 >> num2;
    gcd = GCD(num1, num2);
    cout << num1*num2/gcd;
    return 0;
}

#include <iostream>

using namespace std;

long int GCD(int num1, int num2)

{

if(num1 == num2) return num1;

while(num1 && num2)

{

if(num1 > num2) num1 %= num2;

else num2 %= num1;

}

return num1+num2;

}

int main() {

long int num1, num2, gcd;

cin >> num1 >> num2;

gcd = GCD(num1, num2);

cout << num1*num2/gcd;

return 0;

}

Решение

Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
$1$. Большее число делится на меньшее.
$2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
$3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 1151. Кладоискатель

16/12/2018 by Юлиана Боурош

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $b$ дней. Каждый день Рома находит $a$ закопанных в окрестности монет. Таким образом, в конце первого дня у него было $a$ монет, в конце второго — $2a,$ а по окончании практики у Ромы должно накопиться $b\cdot a$ монет.

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

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

Первая строка входного файла содержит два целых числа $a$ и $b$ ($1 \le a, b \le 10^9$).

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

В выходной файл выведите число съеденных Ромой пирожков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2	1
2	2 2	2
3	10 5	5
4	56000 35	35
5	300 1000000000	100

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

#include <iostream>
using namespace std;
int GCD(int a, int b){
  if (b == 0) return a;
  else return GCD(b, a % b);
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << GCD(a,b);
  return 0;
}

#include <iostream>

using namespace std;

int GCD(int a, int b){

if (b == 0) return a;

else return GCD(b, a % b);

}

int main() {

int a, b;

cin >> a >> b;

cout << GCD(a,b);

return 0;

}

Решение

Нам заданы $a$ и $b$.
Существует 3 случая их отношения между собой:

$a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
Существует такое $k, k \in (1; b), k \in N.$ При котором: $k \cdot a$ кратно $b.$ $\frac{ka}{b} = c, c \in N$. Тогда у $b$ и $a$ есть НОД. $(b, a) = p, p > 1, p \in N$. $a = \tilde a \cdot p$, $b = \tilde b \cdot p.$ Тогда в последовательности $a, 2a, 3a,\ldots, b \cdot a$, а кратным $b$ будет каждый $k$-ый элемент данной последовательности. $c = \frac{ka}{b} = \frac{k \cdot \tilde a \cdot p}{\tilde b \cdot p} = \frac{k\tilde a }{\tilde b },$ $k$ обязан равняться $\tilde b $так как $\tilde a $и $\tilde b$ взаимно простые исходя из определения НОД и $c \in N.$ Отсюда $\frac{b}{k} = \frac{\tilde b p}{\tilde b}=p$ — количество кратных элементов последовательности.
Не существует такого $k, k \in (1; b), k \in N$. При котором: $k \cdot a$ кратно $b$. И $a$ не кратно $b.$ Тогда в последовательности $a, 2a, 3a,\dots,b\cdot a$ кратным $b$ будет только последний элемент последовательности. Так как числа взаимно простые, то НОД равен $1.$

Исходя из этих рассуждений решение задачи сводится к нахождению НОД для $a$ и $b.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

Код на ideone.com
Задача на e-olymp.com

Related Images:

e-olymp 571. НОД

27/12/2017 by Яна Колчинская

Задача

Найти НОД (наибольший общий делитель ) $n$ чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 < n < 101\right)[/latex]. Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает [latex]30000[/latex].

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

НОД заданных чисел.

Тесты

#	Входные данные	Выходные данные
1	3 5 7 2	1
2	2 45 10	5
3	4 27 90 15 9	3
4	2 40 64	8
5	3 8 8 8	8

Код

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    while (a!=0 && b!=0) {
        if (a>b) {
            a=a%b;
        }
        else b=b%a;
    }
    return a+b;
}

int main () {
    int t, a, b;
    cin>>t>>b;
    for (int i=2; i<=t; ++i) {
        cin>>a;
        b=gcd (a, b);
    }
    cout<<b;
    return 0;
}

#include <iostream>

using namespace std;

int gcd (int a, int b) {

while (a!=0 && b!=0) {

if (a>b) {

a=a%b;

}

else b=b%a;

}

return a+b;

}

int main () {

int t, a, b;

cin>>t>>b;

for (int i=2; i<=t; ++i) {

cin>>a;

b=gcd (a, b);

}

cout<<b;

return 0;

}

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

Для решения данной задачи воспользуемся алгоритмом Евклида — алгоритмом нахождения наибольшего общего делителя (НОД) пары целых чисел, т.е. самого большого числа, на которое можно без остатка разделить оба числа, для которых ищется НОД.

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

Related Images:

e-olymp 1154. Кружок хорового пения.

30/09/2015 by Радик Сиденко

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

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex], где [latex]\left( 1 \le N, M \le {10}^{3} \right).[/latex]

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

Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».

Тесты:

n	m	answer
4	1	YES
6	3	NO

Решение:

Для начала нам надо найти наибольший общий делитель(НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице то все ученики распоются и мы выводим «YES» в другом случае мы выводим «NO».

Код:

#include <iostream> 
using namespace std; 
int main() { 
    int n, m, p; 
    while(cin >> n >> m) {
        if (m > n) { 
            p = n; 
            n = m; 
            m = p; 
        } 
        while (m > 0) { 
            p = n % m; 
            if (p != 0) {
                n = m; 
                m = p; 
            } 
            else break; 
        } 
        cout<<(m==1?"YES": "NO")<<endl;
    } 
    return 0; 
}