e-olymp 58. Биллиард

05/08/2018 by Александр Дьяченко

Задача

Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

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

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

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

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные	Выходные данные
2 1	1 2
5 6	9 4
12 33	13 2
156 156	0 3
654 236	443 4

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

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long m, n;
    cin >> m >> n;
    long g = __gcd(m, n);
    m /= g;
    n /= g;
    cout << (n + m - 2) << " ";
    if(n % 2 == 0 and m % 2 != 0) cout << 4;
    if(n % 2 != 0 and m % 2 != 0) cout << 3;
    if(n % 2 != 0 and m % 2 == 0) cout << 2;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long m, n;

cin >> m >> n;

long g = __gcd(m, n);

m /= g;

n /= g;

cout << (n + m - 2) << " ";

if(n % 2 == 0 and m % 2 != 0) cout << 4;

if(n % 2 != 0 and m % 2 != 0) cout << 3;

if(n % 2 != 0 and m % 2 == 0) cout << 2;

return 0;

}

Решение

Чтобы решить эту задачу, необходимо найти НОД значений $M$ и $N$ из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во $2$ строке. Далее, в $8$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

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

Related Images:

e-olymp 949. Двузначное из четырёхзначного

21/12/2017 by Мырза Дмитрий

Задача

Из заданного четырёхзначного натурального числа образовать двузначное, состоящее из его средних цифр.

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

Одно четырёхзначное натуральное число.

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

Полученное двузначное число.

Тесты

#	Входные данные	Выходные данные
1	4765	76
2	7999	99
3	2514	51
4	9423	42
5	8234	23

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

#include <iostream>
using namespace std;

int main() {
    int a;
    cin >> a;
    a /= 10;
    cout << a % 100;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a;

cin >> a;

a /= 10;

cout << a % 100;

return 0;

}

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

Первым делом мы используем деление на 10 с присваиванием, чтобы избавиться от последней цифры числа. Дальше используем остаток от деления на 100, чтобы избавиться от первой цифры числа.

Ссылки

Задача на сайте e-olymp

Код решения Ideone

Related Images:

e-olymp 63. Анфиса и цветы

14/09/2015 by Кудымовская Вика

Задача. Анфиса и цветы

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

Мурзик одну из цветочных клумб сделал в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex], в каждой клеточке которой растет какой-то цветок. Иногда на эту клумбу он выводит на прогулку Анфису (да, не удивляйтесь, они действительно друзья). Анфиса, начиная всегда с верхнего левого угла передвигается по клумбе к правому нижнему и собирает цветы, причем таким образом, чтобы каждый раз проходить новым маршрутом, а Мурзик на выходе вручает ей кусочек сыра.

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

h4″>Входные данные

В одной строке заданы два числа m и n [latex]\left( n, 0 < m, n ≤ 2\cdot 10^9 \right)[/latex].

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

Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.

Также условие задачи можно посмотреть здесь.

Реализация

#include <iostream>     
using namespace std;
int main () {
    long m, n, p;
    cin >> m >> n;
    p = (m * n - (m + n - 1)) + 1;
    cout << p << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main () {

long m, n, p;

cin >> m >> n;

p = (m * n - (m + n - 1)) + 1;

cout << p << endl;

return 0;

}

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

№	Входные данные (m, n)	Выходные данные
1	2, 3	3
2	3, 3	5
3	3, 4	7
4	4, 3	7
6	5, 7	25

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

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему, съедает latex\cdot(n-1)[/latex] цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot(n-1)+1[/latex], где p — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

Ссылка на засчитанное решение.

Для запроса на выполнение нажать здесь.