Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2443
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2443
Soma de Frações
Por OBI - Olimpíada Brasileira de Informática 2013 
Brazil
Timelimit: 1
Joãozinho está aprendendo a somar frações na escola e quer sua ajuda para escrever um programa que dadas duas frações imprima a soma delas em sua forma irredutível. Assim ele vai poder conferir as respostas dos exercícios que está fazendo.
A forma irredutível de uma fração é quando o divisor (número de baixo) é o menor possível. Por exemplo, 10⁄3 é uma fração irredutível, pois 10 e 3 não têm nenhum divisor em comum. Mas 10⁄6 não é, pois ela pode ser simplificada para 5⁄3, dividindo-se 10 e 6 por 2.
Dados quatro inteiros a, b, c, d, escreva um programa que calcule a⁄b + c⁄d na sua forma irredutível.
Entrada
A única linha da entrada contém quatro inteiros a, b, c, d, (1 ≤ a, b, c, d ≤ 100) respectivamente dividendo e divisor da primeira fração e dividendo e divisor da segunda fração.
Saída
Seu programa deve imprimir uma única linha contendo dois inteiros, dividendo e divisor da fração irredutível formada pela soma das duas frações dadas.
| Exemplos de Entrada | Exemplos de Saída |
|
2 3 7 3 |
3 1 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int numerador, denominador;
void soma(int, int, int, int);
int mdc(int, int);
int mmc(int, int);
int main (void)
{
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
soma(a, b, c, d);
int tmp = mdc(numerador, denominador);
printf("%d %d\n", numerador / tmp, denominador / tmp);
}
void soma(int a, int b, int c, int d)
{
numerador = a * d + c * b;
denominador = b * d;
}
int mdc(int a, int b)
{
int resto = a % b;
while (resto != 0)
{
a = b;
b = resto;
resto = a % b;
}
return b;
}
int mmc(int a, int b)
{
return (a / mdc(a , b)) * b;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
using namespace std;
int gcd(int x, int y) {
if (x < y) swap(x, y);
if ((x % y) == 0) return y;
return gcd(y, x % y);
}
int main() {
int n1, d1, n2, d2;
scanf("%d %d %d %d", &n1, &d1, &n2, &d2);
int cima = n1 * d2 + n2 * d1;
int debaixo = d1 * d2;
int mdc = gcd(cima, debaixo);
printf("%d %d\n", cima / mdc, debaixo / mdc);
return 0;
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
def div(n):
d, m = [], n // 2
d.append(n)
for i in range(m, 1, -1):
if n % i == 0: d.append(i)
return d
a, b, c, d = [int(w) for w in input().split()]
y = b * d
x = int((y/b*a) + (y/d*c))
c = True
while c:
dx, dy = div(x), div(y)
p = 0
for e in dx:
if e in dy:
p = e
break
if p:
x //= p
y //= p
else: c = False
print(x, y)
Input
Output