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 BR 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, 103 é uma fração irredutível, pois 10 e 3 não têm nenhum divisor em comum. Mas 106 não é, pois ela pode ser simplificada para 53, dividindo-se 10 e 6 por 2.

Dados quatro inteiros a, b, c, d, escreva um programa que calcule ab + cd 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;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 3 7 3

Output

x
+
cmd
3 1

#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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 3 7 3

Output

x
+
cmd
3 1

#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)
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 3 7 3

Output

x
+
cmd
3 1
Advertisements

Demonstration


Previous
#2442 Beecrowd Online Judge Solution 2442 Plantação Solution in C, C++, Java, Js and Python
Next
#2444 Beecrowd Online Judge Solution 2444 Volume da TV Solution in C, C++, Java, Js and Python