 # A unidade da soma de duas razões

## Recommended Posts Descrição & objectivo: Considerem todos os dígitos inteiros de 0 a 9, inclusive. É dada a seguinte equação:

`A/B + C/D = 1`

O desafio é simples: utilizando todos os dígitos, sem repetição e sem exclusão, descubram os números inteiros A, B, C e D que satisfazem esta condição.

Restrições: Os números não podem ser construídos com qualquer cálculo. A=123, por exemplo, e nunca A=1+2+3.

Knowledge is free!

##### Share on other sites Hmmmm ... "simplificando" a expressao obtem-se

A/B + C/D = 1

Usando esta ultima "simplificacao" tenho um brute force a correr ... que encontrou coisas como

9/12 + 876/3504 = 1

... deve acabar la para as 6 da manha What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites não estou a perceber a restrição ... poderias dar um exemplo melhor ?

ps : eu sei um método, mas pelas restrições não sei ...

- A/B + C/D = 1 <=> AD + BC = BD

- como A/B + C/D == 1, então A < B e C < D para todos os A, B, C, D

- um número nunca será maior que 9999999 (sete dígitos, com 3 para cada um dos outros valores)

temos então:

como, B - A = X, então A/B + X/B == 1

então temos, para A pertencente a [1 .. 9999999], e B para [a+1 .. 9999999]

basta multiplicar X/B por valores entre [1 ... 99999999/B] e verificar com AD + BC = BD

e claro, verificar a duplicação de dígitos Edited by HappyHippyHippo

 IRC : sim, é algo que ainda existe >> #p@p

##### Share on other sites @pmg Alguma coisa não deves estar a fazer bem. Imagina o caso:

`A = 1`

B = 2

C = 3

D = 6

Se só considerarmos um dígito por variável, há 18 soluções. Cheira-me que alguma coisa não está bem explicada no exercício.

Edited by KTachyon

`“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”`

-- Tony Hoare

##### Share on other sites Se só considerarmos um dígito por variável, há 18 soluções. Cheira-me que alguma coisa não está bem explicada no exercício.
utilizando todos os dígitos, sem repetição e sem exclusão

Isto é, tens que usar os 10 dígitos para construir os 4 números.

"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

##### Share on other sites Acho que a confusão é se cada variável só pode ter um digito, ou se cada variável pode ter mais do que um dígito desde que não repetido, ou se cada variável pode ter mais do que um dígito mas este não pode ser repetido mesmo entre variáveis.

##### Share on other sites Isto é, tens que usar os 10 dígitos para construir os 4 números.

Realmente... faz muito mais sentido `“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”`

-- Tony Hoare

##### Share on other sites ```#include <stdio.h>
#include <string.h>

// brute force

#define A(n) (n)
#define B(n) (n)
#define C(n) (n)
#define D(n) (n)

#define MIN 1
#define MAX 9999

void populate_digits(int number, char * digits) {
while (number != 0) {
digits[number % 10]++;
number /= 10;
}
}

int check_cond(int * numbers) {
char digits;
int i = 0;

if (A(numbers) * D(numbers) + C(numbers) * B(numbers) != D(numbers) * B(numbers))
return 0;

memset(digits, 0, 10);

for (i = 0; i < 4; i++)
populate_digits(numbers[i], digits);

for (i = 0; i < 10; i++) {
if (digits[i] != 1)
return 0;
}

return 1;
}

int main() {
int numbers;
int a, b, i, count = 0;
FILE * file = NULL;

if ((file = fopen("sol.txt", "w")) == NULL)
{
return -1;
}

for (a = MIN, A(numbers) = a; a < MAX; a++, A(numbers) = a) {
printf("A = %d\n", A(numbers));
for (b = a + 1, B(numbers) = b; b < MAX; b++, B(numbers) = b) {
for (i = 1; i < MAX/B(numbers); i++)
{
C(numbers) = (B(numbers) - A(numbers)) * i;
D(numbers) = B(numbers) * i;
if (check_cond(numbers))
fprintf(file, "solution (%d), >> A(%d) / B(%d) + C(%d) / D(%d)\n", ++count, numbers, numbers, numbers, numbers);
}
}
}

fclose(file);

return 0;
}
```

```solution (1), >> A(1) / B(2) + C(3485) / D(6970)
solution (2), >> A(1) / B(2) + C(3548) / D(7096)
solution (3), >> A(1) / B(2) + C(3845) / D(7690)
solution (4), >> A(1) / B(2) + C(4538) / D(9076)
solution (5), >> A(1) / B(2) + C(4685) / D(9370)
solution (6), >> A(1) / B(2) + C(4835) / D(9670)
solution (7), >> A(1) / B(2) + C(4853) / D(9706)
solution (8), >> A(1) / B(2) + C(4865) / D(9730)
solution (9), >> A(1) / B(4) + C(7365) / D(9820)
solution (10), >> A(1) / B(6) + C(7835) / D(9402)
solution (11), >> A(1) / B(7) + C(4362) / D(5089)
solution (12), >> A(2) / B(7) + C(5940) / D(8316)
solution (13), >> A(2) / B(7) + C(6810) / D(9534)
solution (14), >> A(2) / B(9) + C(5803) / D(7461)
solution (15), >> A(3) / B(6) + C(1485) / D(2970)
solution (16), >> A(3) / B(6) + C(2079) / D(4158)
solution (17), >> A(3) / B(6) + C(2709) / D(5418)
solution (18), >> A(3) / B(6) + C(2907) / D(5814)
solution (19), >> A(3) / B(6) + C(4851) / D(9702)
solution (20), >> A(3) / B(127) + C(496) / D(508)
solution (21), >> A(4) / B(5) + C(1278) / D(6390)
solution (22), >> A(4) / B(5) + C(1872) / D(9360)
solution (23), >> A(5) / B(104) + C(693) / D(728)
solution (24), >> A(7) / B(9) + C(1208) / D(5436)
solution (25), >> A(7) / B(9) + C(1352) / D(6084)
solution (26), >> A(7) / B(54) + C(893) / D(1026)
solution (27), >> A(9) / B(12) + C(876) / D(3504)
solution (28), >> A(9) / B(351) + C(684) / D(702)
solution (29), >> A(17) / B(89) + C(504) / D(623)
solution (30), >> A(19) / B(58) + C(273) / D(406)
solution (31), >> A(21) / B(96) + C(375) / D(480)
solution (32), >> A(24) / B(63) + C(507) / D(819)
solution (33), >> A(36) / B(81) + C(405) / D(729)
solution (34), >> A(36) / B(81) + C(540) / D(972)
solution (35), >> A(38) / B(61) + C(207) / D(549)
solution (36), >> A(39) / B(51) + C(204) / D(867)
solution (37), >> A(42) / B(87) + C(315) / D(609)
solution (38), >> A(45) / B(61) + C(208) / D(793)
solution (39), >> A(54) / B(87) + C(231) / D(609)
solution (40), >> A(57) / B(92) + C(140) / D(368)
solution (41), >> A(74) / B(89) + C(105) / D(623)
solution (42), >> A(79) / B(83) + C(60) / D(1245)
solution (43), >> A(93) / B(107) + C(56) / D(428)
solution (44), >> A(95) / B(104) + C(63) / D(728)
solution (45), >> A(97) / B(104) + C(56) / D(832)
```

 IRC : sim, é algo que ainda existe >> #p@p

##### Share on other sites ```...
solution (45), >> A(97) / B(104) + C(56) / D(832)
```

Ha muito mais que 45 solucoes.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites Ha muito mais que 45 solucoes.

sim, mas como não queria dar resultados como :

A(42) / B(87) + C(315) / D(609)

e

A(315) / B(609) + C(42) / D(87)

isto porque na realidade é a mesma coisa ...

 IRC : sim, é algo que ainda existe >> #p@p

##### Share on other sites 5 exemplos com A = 2 (na tua mensagem aparecem 3)

```2/4 + 3079/6158 is 1 <= oops
2/6 + 3190/4785 is 1 <= oops
2/7 + 5940/8316 is 1
2/7 + 6810/9534 is 1
2/9 + 5803/7461 is 1
```

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites 5 exemplos com A = 2 (na tua mensagem aparecem 3)

```2/4 + 3079/6158 is 1 <= oops
2/6 + 3190/4785 is 1 <= oops
2/7 + 5940/8316 is 1
2/7 + 6810/9534 is 1
2/9 + 5803/7461 is 1
```

tens razão ... necessito de reduzir a fracção A/B primeiro

ps : já me apresenta os elementos que faltavam ... mas o tempo que leva para calcular aumentou exponencialmente solução actual :

```#include <stdio.h>
#include <string.h>

#define A(n) (n)
#define B(n) (n)
#define C(n) (n)
#define D(n) (n)

#define Ared(n) (n)
#define Bred(n) (n)

#define MIN 1
#define MAX 9999

int populate_digits(int number, char * digits) {
int count = 0;

while (number != 0) {
digits[number % 10]++;
number /= 10;
count++;
}

return count;
}

int check_cond(int * numbers) {
char digits;
int i = 0, count = 0;

if (A(numbers) * D(numbers) + C(numbers) * B(numbers) != D(numbers) * B(numbers))
return 0;

memset(digits, 0, 10);

for (i = 0; i < 4; i++)
count += populate_digits(numbers[i], digits);

if (count != 10)
return 0;

for (i = 0; i < 10; i++) {
if (digits[i] != 1)
return 0;
}

return 1;
}

void reduce(int * numbers)
{
int a_cum = 1, b_cum = 1;
int a_red = A(numbers), b_red = B(numbers);

while (a_red != b_red) {
if (a_red > b_red) {
b_cum++;
b_red += B(numbers);
} else {
a_cum++;
a_red += A(numbers);
}
}

Ared(numbers) = b_cum;
Bred(numbers) = a_cum;
}

int main() {
int numbers;
int a, b, i, count = 0;
FILE * file = NULL;

if ((file = fopen("sol.txt", "w")) == NULL)
return -1;

for (a = MIN, A(numbers) = a; a < 100; a++, A(numbers) = a) {
for (b = a + 1, B(numbers) = b; b < MAX; b++, B(numbers) = b) {
reduce(numbers);

C(numbers) = 0;
D(numbers) = 0;
for (i = 1; i < MAX/Bred(numbers); i++) {
C(numbers) += Bred(numbers) - Ared(numbers);
D(numbers) += Bred(numbers);
if (C(numbers) > A(numbers) &&
check_cond(numbers))
fprintf(file, "solution (%d), >> A(%d) / B(%d) + C(%d) / D(%d)\n", ++count, numbers, numbers, numbers, numbers);
}
}
}

fclose(file);

return 0;
}
```

Edited by HappyHippyHippo

 IRC : sim, é algo que ainda existe >> #p@p

##### Share on other sites Brute Force FTW ```#include <stdio.h>
#include <string.h>

#define DUMMY 0

int main(void) {
int min = {DUMMY, 1, 10, 102, 1023, 10234, 102345, 1023456};
int max = {DUMMY, 9, 98, 987, 9876, 98765, 987654, 9876543};
int nda, ndb, ndc, ndd; /* number of digits of a, b, ... */
int a, b, c, d;

for (nda = 1; nda < 8; nda++) {
for (ndb = nda; ndb < 8; ndb++) {
for (ndc = 1; ndc < 8; ndc++) {
ndd = 10 - nda - ndb - ndc;
if (ndd > 7) continue;
if (ndd < 1) continue;
for (a = min[nda]; a <= max[nda]; a++) {
for (b = min[ndb]; b <= max[ndb]; b++) {
if (b <= a) continue;
for (c = min[ndc]; c <= max[ndc]; c++) {
if (c <= a) continue;
for (d = min[ndd]; d <= max[ndd]; d++) {
if (d <= c) continue;
if (a*d + b*c == b*d) {
char buff;
if (sprintf(buff, "%d%d%d%d", a, b, c, d) != 10) continue;
if (!strchr(buff, '0')) continue;
if (!strchr(buff, '1')) continue;
if (!strchr(buff, '2')) continue;
if (!strchr(buff, '3')) continue;
if (!strchr(buff, '4')) continue;
if (!strchr(buff, '5')) continue;
if (!strchr(buff, '6')) continue;
if (!strchr(buff, '7')) continue;
if (!strchr(buff, '8')) continue;
if (!strchr(buff, '9')) continue;
printf("%d/%d + %d/%d = 1\n", a, b, c, d);
}
}
}
}
}
}
}
}
return 0;
}
```

... ao fim de 6 minutos e 49 segundos

```1/2 + 3485/6970 = 1
1/2 + 3548/7096 = 1
1/2 + 3845/7690 = 1
1/2 + 4538/9076 = 1
1/2 + 4685/9370 = 1
1/2 + 4835/9670 = 1
1/2 + 4853/9706 = 1
1/2 + 4865/9730 = 1
1/4 + 7365/9820 = 1
1/6 + 7835/9402 = 1
1/7 + 4362/5089 = 1
2/4 + 3079/6158 = 1
2/6 + 3190/4785 = 1
2/7 + 5940/8316 = 1
2/7 + 6810/9534 = 1
2/9 + 5803/7461 = 1
3/6 + 1485/2970 = 1
3/6 + 2079/4158 = 1
3/6 + 2709/5418 = 1
3/6 + 2907/5814 = 1
3/6 + 4851/9702 = 1
4/5 + 1278/6390 = 1
4/5 + 1872/9360 = 1
7/9 + 1208/5436 = 1
7/9 + 1352/6084 = 1
7/54 + 893/1026 = 1
8/10 + 729/3645 = 1
8/10 + 927/4635 = 1
9/12 + 876/3504 = 1
3/127 + 496/508 = 1
4/356 + 792/801 = 1
5/104 + 693/728 = 1
6/324 + 795/810 = 1
6/534 + 792/801 = 1
8/512 + 693/704 = 1
9/351 + 684/702 = 1
10/28 + 369/574 = 1
10/45 + 287/369 = 1
10/45 + 728/936 = 1
10/96 + 473/528 = 1
12/54 + 609/783 = 1
12/60 + 748/935 = 1
12/96 + 357/408 = 1
12/96 + 735/840 = 1
13/26 + 485/970 = 1
13/52 + 678/904 = 1
15/30 + 486/972 = 1
16/32 + 485/970 = 1
17/89 + 504/623 = 1
18/90 + 276/345 = 1
18/90 + 372/465 = 1
19/57 + 308/462 = 1
19/58 + 273/406 = 1
21/96 + 375/480 = 1
24/63 + 507/819 = 1
24/96 + 531/708 = 1
27/54 + 309/618 = 1
27/81 + 306/459 = 1
27/81 + 630/945 = 1
29/58 + 307/614 = 1
29/87 + 310/465 = 1
31/62 + 485/970 = 1
32/48 + 169/507 = 1
32/80 + 417/695 = 1
34/51 + 269/807 = 1
35/70 + 148/296 = 1
35/70 + 481/962 = 1
36/81 + 405/729 = 1
36/81 + 540/972 = 1
38/61 + 207/549 = 1
38/76 + 145/290 = 1
38/76 + 451/902 = 1
38/95 + 426/710 = 1
39/51 + 204/867 = 1
39/65 + 284/710 = 1
42/87 + 315/609 = 1
45/61 + 208/793 = 1
45/90 + 138/276 = 1
45/90 + 186/372 = 1
45/90 + 381/762 = 1
46/92 + 185/370 = 1
48/96 + 135/270 = 1
48/96 + 351/702 = 1
54/87 + 231/609 = 1
56/84 + 109/327 = 1
56/84 + 307/921 = 1
57/92 + 140/368 = 1
70/96 + 143/528 = 1
74/89 + 105/623 = 1
34/578 + 96/102 = 1
56/428 + 93/107 = 1
56/832 + 97/104 = 1
57/204 + 98/136 = 1
59/236 + 78/104 = 1
63/728 + 95/104 = 1
87/435 + 96/120 = 1
60/1245 + 79/83 = 1
```

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites Acho que não está completo, até porque A,B e C,D podem trocar. Claro que basta fazer os dois prints com a troca.

`if (ndb - nda > 1 && ndd - ndc > 1) continue;`

Já agora, se arranjarem uma explicação matemática para nunca precisares das 3 últimas ranges, o teu algoritmo deverá correr em segundos.

Edited by KTachyon

`“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”`

-- Tony Hoare

##### Share on other sites Já agora, se arranjarem uma explicação matemática para nunca precisares das 3 últimas ranges, o teu algoritmo deverá correr em segundos.

- como A/B + C/D == 1, então A < B e C < D para todos os A, B, C, D

como A, B, C e D são positivos, a única maneira de que A/B e C/D serem 1 é os dois serem < do que 1.

para que os dois serem menores do que 1, A < B e C < D

se A ou C tiverem 5 dígitos, B ou D também terá de ter 5 ou mais dígitos, o que invalida o a cláusula de 10 dígitos no total.

se B ou D tiverem 5 dígitos, tens os seguintes casos:

```A    C
--- -----
BBB DDDDD

ou

A   CC
-- -----
BB DDDDD

ou

A  CCC
- -----
B DDDDD
```

mesmo sem olhar para as restrições de dígitos diferentes, podes verificar que (no segundo caso, mas podes extrapolar para os outros) tens um valor máximo para A/B de 9/10, mas o teu valor máximo de C/D = 99/10000 < 100/10000 = 1/10

logo 9/10 + (<1/10) será sempre menor que 1

para casos em que tens divisores com mais de 5 dígitos, ainda se torna mais claro

 IRC : sim, é algo que ainda existe >> #p@p

##### Share on other sites Ok. De qualquer forma existe outra questão que também aumenta bastante a performance do brute force. Tendo em conta a fórmula:

`A*D + B*C = B*D`

Se considerarem que, ao incrementarem `D`, o lado direito da equação `B*D`, sabendo à partida que `B > A`, vai aumentar relativamente ao lado esquerdo. Ou seja, a partir do momento em que `B*D` é maior que `A*D + B*C`, escusamos de continuar a incrementar o `D` porque não nos leva a lado nenhum.

Isto faz com que o algoritmo do @pmg passe a demorar 7 segundos na minha máquina.

Edited by KTachyon

`“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”`

-- Tony Hoare

##### Share on other sites Não olhei com atenção para o vosso código, pelo que vai uma sugestão que podem já estar a usar ou eventualmente não trazer grandes benefícios.

Assumindo que o objectivo é brute-force, a forma mais rápida de resolver estes problemas raramente é iterar nos N números (neste caso 4) mas sim nos N-1, resolver em ordem ao que falta e ver se cumpre as restrições.

Por exemplo, iterar para A, B e C e obter o D que respeita a equação (resolver em ordem a D). De seguida verificamos se o D que obtivemos cumpre a restrição de não repetir digitos, o que pode ser feito "instantaneamente" se mantiverem várias representações de A, B e C. Uma representação possível em C/C++:

Se A, B, C e D forem números tais que o bit "i" é 1 se o número possuir o dígito "i", então a seguinte expressão indica se o conjunto {A, B, C, D} não repete dígitos:

if (!A&B && !A&C && !A&D && !B&C && !B&D && !C&D && A|B|C|D == (1<<10 - 1)) // são válidos

Eventualmente pode precisar de uns parenteses em torno de !(A&B) etc., não sei de cabeça a ordem dos operadores ! e &.

Se já tiverem garantido que A, B e C não repetem dígitos, então é ainda mais simples:

if (!A&D && !B&D && !C&D && A|B|C|D == (1<<10 - 1)) // D é válido

Edited by Warrior

##### Share on other sites ... iterar para A, B e C e obter o D que respeita a equação (resolver em ordem a D) ...

Se reparares bem isso é o que eu faço para o número de digitos de d.

Não o fiz para o d propriamente dito por causa das restrições (que não compreendi lá muito bem): "Os números não podem ser construídos com qualquer cálculo. A=123, por exemplo, e nunca A=1+2+3"

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites Já vi que as restrições não foram bem percebidas. Vamos lá então ver.

Os números A, B, C e D devem ser um número e não um cálculo. A primeira vez que me deram o desafio eu pensei que seria algo como pegar nos números de 0 a 9 e fazer contas com eles, construído os números de A a D. Mas não, os números devem ser utilizados para construir directamente A, B, C e D.

Exemplo:

```ERRADO - pegar nos números de 1 a 9 e fazer contas (neste caso, somas):
A = 1+6
B = 5+3+7
C = 9+0+2+4
D = 8

CERTO - construir os números directamente com os dígitos:
A = 16
B = 537
C = 9024
D = 8
```

Espero já me ter feito entender Edited by thoga31

Knowledge is free!

##### Share on other sites Mas posso fazer `A = A + 1`, ou `D = (B - A) / (B*C)`?

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites Mas posso fazer `A = A + 1`, ou `D = (B - A) / (B*C)`?

A restrição aplica-se ao modo de como "tratas" os dígitos de 0 a 9. Desde que não faças coisas como...

```let A = sum [1,4,5]  -- o mesmo que A = 1+4+5
```

... considerando que já utilizaste, então, os dígitos 1, 4 e 5, então tudo bem. Podes pegar à vontade na expressão inicial do problema e transformá-la de modo a obter uns números em função dos outros.

Em suma:

```let A = sum [1,4,5]  -- dígitos 1, 4 e 5 foram utilizados: não é permitido.
let D = (B-A) `div` (B*C)  -- é permitido, desde que no fim sejam utilizados todos os dígitos e que não se repitam.
```

Vocês andam a confundir técnicas matemáticas de obter os números, e o modo de como pegam nos dígitos para construir os números. Edited by thoga31

Knowledge is free!

##### Share on other sites Segunda versao (bastante mais rapido ... e com grandes possibilidades de melhorar o tempo ainda mais).

Os resultados sao os mesmos (por outra ordem)

```#include <stdio.h>
#include <stdlib.h>

/* see http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order */
int permnext(char *p, int n) {
int kh, k = -1;
int lh, l = -1;
char tmp;

for (kh = 0; kh < n - 1; kh++) {
if (p[kh] < p[kh + 1]) k = kh;
}
if (k == -1) return 1;
for (lh = k + 1; lh < n; lh++) {
if (p[k] < p[lh]) l = lh;
}
if (l == -1) {
fprintf(stderr, "This didn't happen.\n");
exit(EXIT_FAILURE);
}
tmp = p[k]; p[k] = p[l]; p[l] = tmp;
l = k + 1;
lh = n - 1;
while (l < lh) {
tmp = p[l]; p[l] = p[lh]; p[lh] = tmp;
l++;
lh--;
}
return 0;
}

void check(const char *p, int nda, int ndb, int ndc, int ndd) {
int a = 0, b = 0, c = 0, d = 0;
if (p[nda] == '0') return;
if (p[nda + ndb] == '0') return;
if (p[nda + ndb + ndc] == '0') return;
while (nda--) { a *= 10; a += *p - '0'; p++; }
while (ndb--) { b *= 10; b += *p - '0'; p++; }
if (b < a) return;
while (ndc--) { c *= 10; c += *p - '0'; p++; }
if (c < a) return;
while (ndd--) { d *= 10; d += *p - '0'; p++; }
if (d < c) return;
if (a*d + b*c == b*d) {
printf("%d/%d + %d/%d = 1\n", a, b, c, d);
}
}

int main(void) {
char perm[] = "1023456789";
do {
check(perm, 1, 1, 1, 7);
check(perm, 1, 1, 2, 6);
check(perm, 1, 1, 3, 5);
check(perm, 1, 1, 4, 4);
check(perm, 1, 2, 1, 6);
check(perm, 1, 2, 2, 5);
check(perm, 1, 2, 3, 4);
check(perm, 1, 3, 1, 5);
check(perm, 1, 3, 2, 4);
check(perm, 1, 3, 3, 3);
check(perm, 1, 4, 1, 4);
check(perm, 1, 4, 2, 3);
check(perm, 1, 5, 1, 3);
check(perm, 1, 5, 2, 2);
check(perm, 1, 6, 1, 2);
check(perm, 1, 7, 1, 1);
check(perm, 2, 2, 2, 4);
check(perm, 2, 2, 3, 3);
check(perm, 2, 3, 2, 3);
check(perm, 2, 4, 2, 2);
} while (permnext(perm, 10) == 0);
return 0;
}```

Podes ver o codigo a correr no ideone.

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

##### Share on other sites Eu uso bitmasks para marcar os digitos já usados. O pre-processamento gera os números possíveis, sabendo que alguns digitos já foram usados.

migueloliveira\$ g++ -Wall -O2 a.cpp -o a && time ./a

real 0m0.699s

```// A/B + C/D = 1
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define two(n) (1<<(n))

vector<int> numerosDisponiveis;
char used;

int i , j , k, p;
for (i = 0 ; i < 10 ; i++)
used[i] = (mask & two(i)) != 0;
for (i = 1 ; i < 10 ; i++)
if (!used[i]) {
used[i] = 1;
for (j = 0; j < 10 ; j++)
if (!used[j]) {
used[j] = 1;
numMask[i*10 +j] = two(i) | two(j);
for (k = 0; k < 10; k++)
if (!used[k]) {
used[k] = 1;
numMask[i*100 +j*10 + k] = two(i) | two(j) | two(k);
for (p = 0; p < 10; p++)
if (!used[p]) {
numMask[i*1000 +j*100 + k*10 + p] = two(i) | two(j) | two(k) | two(p);
numerosDisponiveis[mask].push_back(i*1000 + j*100 + k*10 + p);
}
used[k] = 0;
}
used[j] = 0;
}
used[i] = 0;
}
}
int main() {
unsigned n, k, p, i, j, A , B , C , D, mask_a, mask_ab, mask_abc, target = two(10)-1;
for (i = 0 ; i < two(10); i++) // 2^10
geraNumeros(i);
sort(numerosDisponiveis.begin(), numerosDisponiveis.end());
n = numerosDisponiveis.size();
for (i = 0 ; i < n; i++) {
A = numerosDisponiveis[i];
for (j = 0 ; j < numerosDisponiveis[mask_a].size(); j++) {
if (B < A)
continue;
for (k = 0; k < numerosDisponiveis[mask_ab].size(); k++) {
for (p = 0; p < numerosDisponiveis[mask_abc].size(); p++) {
// A/B + C/D = 1 <=> AD + BC = BD , ignorar repetidos.
if ( (mask_abc|numMask[D])== target && A*D + B*C == B*D && (A*D < B*C || (A*D == B*C && A < C)))
printf("%u/%u + %u/%u = 1\n", A, B, C, D);
}
}
}
}
return 0;
}
```

edit: A indentação está a dar-me problemas, nao sei porquê.. depois corrijo.

Edited by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

##### Share on other sites Pensando um pouco melhor, a parte do D pode ser melhorada se guardar os números que usam exactamente os digitos representados numa bitmask. Assim, o D tem de usar todos os digitos que faltam na bitask dos digitos de A, B e C.

migueloliveira\$ g++ -Wall -O2 a.cpp -o a && time ./a

real 0m0.257s

```// A/B + C/D = 1
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define two(n) (1<<(n))

vector<int> numerosDisponiveis;
vector<int> numerosRestantes;
char used;

int i , j , k, p, num;
for (i = 0 ; i < 10 ; i++)
used[i] = (mask & two(i)) != 0;
for (i = 1 ; i < 10 ; i++)
if (!used[i]) {
used[i] = 1;
numerosRestantes[two(i)].push_back(i);
for (j = 0; j < 10 ; j++)
if (!used[j]) {
used[j] = 1;
num = i*10 + j;
for (k = 0; k < 10; k++)
if (!used[k]) {
used[k] = 1;
num = i*100 +j*10 + k;
numMask[num] = two(i) | two(j) | two(k);
for (p = 0; p < 10; p++)
if (!used[p]) {
num = i*1000 +j*100 + k*10 + p;
numMask[num] = two(i) | two(j) | two(k) | two(p);
}
used[k] = 0;
}
used[j] = 0;
}
used[i] = 0;
}
}
int main() {
unsigned n, k, p, i, j, A , B , C , D, mask_a, mask_ab, left, target = two(10)-1;
for (i = 0 ; i < two(10); i++) // 2^10
geraNumeros(i);
sort(numerosDisponiveis.begin(), numerosDisponiveis.end());
n = numerosDisponiveis.size();
for (i = 0 ; i < n; i++) {
A = numerosDisponiveis[i];
for (j = 0 ; j < numerosDisponiveis[mask_a].size(); j++) {
if (B < A)
continue;
for (k = 0; k < numerosDisponiveis[mask_ab].size(); k++) {
if (C > A)
continue;
for (p = 0; p < numerosRestantes[left].size(); p++) {
D = numerosRestantes[left][p];
// A/B + C/D = 1 <=> AD + BC = BD
if (A*D + B*C == B*D ) {
printf("%u/%u + %u/%u = 1\n", A, B, C, D);
}
}
}
}
}
return 0;
}
```

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

##### Share on other sites Fiz um melhoramento adicional para avançar os numeros B menores que A, ordenando e usando o lower_bound.

migueloliveira\$ g++ -Wall -O2 a.cpp -o a && time ./a

real 0m0.184s

```// A/B + C/D = 1
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define two(n) (1<<(n))

vector<int> numerosDisponiveis;
vector<int> numerosRestantes;
char used;

int i , j , k, p, num;
for (i = 0 ; i < 10 ; i++)
used[i] = (mask & two(i)) != 0;
for (i = 1 ; i < 10 ; i++)
if (!used[i]) {
used[i] = 1;
numerosRestantes[two(i)].push_back(i);
for (j = 0; j < 10 ; j++)
if (!used[j]) {
used[j] = 1;
num = i*10 + j;
for (k = 0; k < 10; k++)
if (!used[k]) {
used[k] = 1;
num = i*100 +j*10 + k;
numMask[num] = two(i) | two(j) | two(k);
for (p = 0; p < 10; p++)
if (!used[p]) {
num = i*1000 +j*100 + k*10 + p;
numMask[num] = two(i) | two(j) | two(k) | two(p);
}
used[k] = 0;
}
used[j] = 0;
}
used[i] = 0;
}
}
int main() {
unsigned n, k, p, i, A , B , C , D, mask_a, mask_ab, left, target = two(10)-1;
vector<int>::iterator it;
for (i = 0 ; i < two(10); i++) { // 2^10
geraNumeros(i);
sort(numerosDisponiveis[i].begin(), numerosDisponiveis[i].end());
}
n = numerosDisponiveis.size();
for (i = 0 ; i < n; i++) {
A = numerosDisponiveis[i];
for (; it != numerosDisponiveis[mask_a].end(); it++) {
B = *it;
for (k = 0; k < numerosDisponiveis[mask_ab].size(); k++) {
if (C > A)
break;
for (p = 0; p < numerosRestantes[left].size(); p++) {
D = numerosRestantes[left][p];
// A/B + C/D = 1 <=> AD + BC = BD
if (A*D + B*C == B*D ) {
printf("%u/%u + %u/%u = 1\n", A, B, C, D);
}
}
}
}
}
return 0;
}```

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Restore formatting

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...