PKU 1395 - Cog-Wheels

Autor da análise: tmadeiratmadeira

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1395

Resumo

(Essa explicação só funciona pois os testes dos juízes estão fracos!)

É dado um conjunto $A = \{ a_1, a_2, ..., a_n \} \subset \mathbb{Z}$ de $n$ elementos assumindo valores de 1 a 20 (na verdade os elementos vão de 5 a 100, mas há um menor elemento $m$ que divide todos os outros, então dividindo todos os números por $m$ obtem-se este conjunto com elementos de 1 a 20).

O problema é, dado um número racional $\frac{p}{q}$ ($1 \leq p, q \leq 10000$), determinar se ele pode ser escrito como produto dos números do conjunto $A$, i.e., determinar se existem $e_i \in \mathbb{Z}$ (i = 1, 2, …, n), tais que $\displaystyle \frac{p}{q} = \Pi_{i = 1}^{n} a_i^{e_i}$

Solução

Primeiramente removemos fatores repetidos. Para cada par $a_i, a_j$ de números do conjunto A, se $a_j | a_i$ então $a_i = \frac{a_i}{a_j}$. O motivo disto é que $\frac{a_i}{a_j}$ e os números que possuem ele e qualquer outro inteiro de A como fatores podem ser feitas. Por exemplo, se $A = \{ 1, 2, 6 \}$, eu consigo fazer $\frac{1}{3} = \frac{2}{6}$, $\frac{1}{3^2} = \frac{2^2}{6^2}$, $\frac{1}{3^3} = \frac{2^3}{6^3}$, etc.

Então criamos um vetor $M$ de 10000 posições, tal que $M_i = 1$ se e somente se é possível escrever $i$ como a multiplicação de números de $A$ por outros números que é possível escrever (senão, $M_i = 0$).

Para preencher esse vetor, iniciamos com $M_1 = 1$ e para cada número $i$ já marcado (por ordem crescente), marcamos $i \cdot A_j$ ($j = 1, 2, ..., n$).
(marcar $u$ significa realizar a atribuição $M_u = 1$).

Agora, dado o racional $\frac{p}{q}$, basta tirar o MDC entre $p, q$ e dividir ambos pelo MDC (para ter a fração reduzida) e então testar $\forall k >= 0$ (enquanto $p \cdot k, c \cdot k \leq 10000$) se $p \cdot k$ e $q \cdot k$ estão no conjunto. Se estiverem, este número pode ser feito.

Nota: Este $k$ é importante por causa do segundo cenário abaixo. Provavelmente há uma solução mais bonita (tirando MDCs ao processar cada par de números ou algo do gênero), mas essa funciona.

Testes

Entrada

2
3
7 14 42
3
2 6
1 7
1 6561
3
1 4 10
1
4 10

Saída

Scenario #1:
Gear ratio 2:6 can be realized.
Gear ratio 1:7 cannot be realized.
Gear ratio 1:6561 can be realized.

Scenario #2:
Gear ratio 4:10 can be realized.

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License