OCI2020: Prueba 4 de Entrenamiento

Con esta prueba terminamos el 2019. Les deseamos muchas felicidades y éxitos a todos los estudiantes de preuniversitario que se preparan para participar en los Concursos Provinciales y Nacionales del presente curso escolar.

El temario consta de cuatro problemas tratando de que existen ejercicios para todos los estudiantes según el nivel de preparación que posean. La competencia tendrá una duración de 3 horas pero la podrán realizar en cualquier momento del periodo que esté activa en el sitio.

Problems

Problem	Points	AC Rate	Users
Clasificando fracciones	100p	8.4%	20
Máximo de Islas	100p	3.5%	15
Intercambio de bolígrafos	100p	25.9%	218
Tres Rectas	100p	3.6%	21

Comments

0

Sekai02 commented on Dec. 25, 2019, 12:48 a.m.

Muchas gracias por la solucion de "Maximo de Islas", me gustaría saber como podría resolver "Tres Rectas".

0

Leonardo commented on Dec. 26, 2019, 7:42 p.m.

No recuerdo bien el problema pero la cosa es que suponiendo que solo tengas tres rectas que pasen por todos los puntos solo hay 4 formas posibles.Las dos primeras son que sean rectas paralelas tanto en el eje x como el y, este caso es facil de ver, solo tienes que ver si la cantidad de posiciones en el eje x o y son menor o igual que 3. Los otros dos casos son que dos rectas sean paralelas y una perpendicular a estas, esto ultimo hay varias formas de hacerlo.

0

aniervs commented on Dec. 27, 2019, 3:25 a.m.

El problema se torna más difícil cuando son K rectas horizontales y/o verticales, $1\le K\le N$ ~1\le K\le N~. En este caso se puede reducir a hallar el MVC de un grafo bipartito.

0

aniervs commented on Dec. 27, 2019, 3:21 a.m.

Si, para el caso donde son dos horizontales y una vertical puedes iterar por la vertical (todas las columnas) y contar la cantidad de filas que tienen vértices en otra Columna que no sea la actual, si hay 2 o menos de estas filas entonces esa es una solución. Algo similar para el caso cuando hay 2 verticales y una horizontal.

0

Sekai02 commented on Dec. 27, 2019, 2:36 a.m.

Leonardo muchas gracias por la explicacion

2
aniervs commented on Dec. 24, 2019, 9:54 p.m.
“Máximo de islas”: Este problema lo que estaba difícil de entender. Por lo demás es sencillo. El agua cae y va subiendo al mismo nivel por todos los montículos de tierra. Entonces, los montículos de tierra son cubiertos en orden creciente de sus alturas, los montículos de la misma altura son cubiertos al mismo tiempo. Entonces sólo tenemos que simular este proceso. Si un montículo se va a cubrir en el momento actual: pueden pasar varias cosas:

Los montículos adyacentes a él están cubiertos ya. En ese caso ese montículo constituía una sola isla, y por tanto al ser cubierto la cantidad de islas disminuye en 1.

Ninguno de sus montículos adyacentes estaban cubiertos. En este caso la isla donde estaba ese montículo se divide en 2, por tanto la cantidad de islas aumenta en 1.

Tiene un montículo adyacente cubierto y otro no cubierto. En este caso solamente estamos reduciendo el tamaño de la isla donde se encuentra, por tanto la cantidad de islas de mantiene igual.

1

dmesadiaz commented on Dec. 24, 2019, 9:43 p.m.

Muchas gracias por la explicacion.

-2

dmesadiaz commented on Dec. 22, 2019, 2:27 p.m.

Buena sol yo no hice de esa forma. Yo lo hice asumiendo q el maximo de la cantidad de cifras despues de la coma era menor q 10^4. Pero como podria demostrar q eso se cumple?

0

aniervs commented on Dec. 24, 2019, 4:13 p.m.

De hecho, son muchas menos. Fíjate que en la solución que explico, multiplicamos la fracción por $10^K$ ~10^K~ donde $K$ ~K~ es la cantidad de cifras después de la coma. Tenemos además que $B=2^x5^y$ ~B=2^x5^y~, por tanto $K=max(x,y)$ ~K=max(x,y)~, el peor caso es cuando $B$ ~B~ es una potencia de 2, entonces $K=log_2(B)$ ~K=log_2(B)~. Así que a lo más hay $log_2(10^{12})=12*log_2(10)<12*4=48$ ~log_2(10^{12})=12*log_2(10)<12*4=48~ cifra después de la coma. Entonces una solución posible era simular la división hasta obtener 48 cifras después de la coma.

0

Primervirgen commented on Dec. 21, 2019, 7:48 p.m.

Lo mejor es que pongan una semana entera de ejercicios antes del Nacional

0

Sekai02 commented on Dec. 21, 2019, 7:27 p.m.

¿El año siguiente seguirán haciendo este tipo de contest hasta que llegue la fecha del nacional?

-1

elRubiusOMG commented on Dec. 14, 2019, 3:56 a.m.

Fracciones y Maximo de Islas

1

aniervs commented on Dec. 22, 2019, 1:57 a.m.

"Clasificando fracciones". Problema: Nos dan dos enteros A y B, y nos piden clasificar la fracción A/B en finita o infinita periódica. Solución:A es muy grande para guaradarlo en algún tipo de dato de c++, así que tenemos que guardarlo en un arreglo. Digamos que A = B*Q + R, (con 0 <= R < B) donde Q es el cociente de A/B, R = A % B.Entonces $\displaystyle \frac{A}{B}=Q+\frac{R}{B}$ Como Q es entero, nos basta con saber si (A % B)/B es finita o infinita. A%B < B <= $10^{12}$ ~10^{12}~, por tanto si lo podemos guardar en un entero de 64 bits, y lo podemos computar fácilmente con una pasada lineal sobre el arreglo en el que guardamos a A. Ahora, tenemos una fracción $\frac{R}{B}$ ~\frac{R}{B}~ y queremos saber si es finita o infinita periódica, primero volvamos la fracción irreducible dividiendo numerador y denominador por el gcd de ambos, o sea: el numerador y el denominador se vuelven coprimos. Digamos que la fracción es finita y tiene k cifras después de la coma: $\frac{R}{B}=a0,a_1a_2...a_k$ ~\frac{R}{B}=a0,a_1a_2...a_k~. Multiplicamos por $10^k$ ~10^k~ y nos queda que $\frac{10^kR}{B}$ ~\frac{10^kR}{B}~ es entero, como B es coprimo con R, B debe ser divisor de $10^k$ ~10^k~, lo cual solo pasa si B es múltiplo de 2 y 5 solamente. Para chequear esto último, dividimos B por 2 todo lo que sea posible y luego lo dividimos por 5 todo lo que sea posible; si después de esto B > 1, es porque B es múltiplo de algún primo diferente de 2 y de 5, y por tanto, la fracción es infinita.

-1

aniervs commented on Dec. 14, 2019, 5:38 p.m.

Todavía no ha acabado el contest.

1

Primervirgen commented on Dec. 14, 2019, 1:35 a.m.

Eso suena bien...

0

Sekai02 commented on Dec. 12, 2019, 5:42 p.m.

Por favor, si fuese posible publicar los análisis de solución de los ejercicios al acabar el concurso.

-1

aniervs commented on Dec. 14, 2019, 2:55 a.m.

comenten en el contest del que quieran discutir las soluciones y ya

1

aniervs commented on Dec. 14, 2019, 1:18 a.m.

Podemos discutir las soluciones una vez acabo el contest