OCI2020: Prueba 1 de Entrenamiento

Ya comenzamos con la Primera Prueba de Entrenamiento para los estudiantes de preuniversitario que se preparan para participar en el Concurso Nacional de Cuba a celebrarse en el mes de Febrero del 2020 sobre un Jurado Online. El temario es de cuatro problemas tratando de que existen ejercicios para todos los estudiantes según el nivel de preparaió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
Salvando al planeta	100p	4.4%	20
El leñador Pablo	100p	15.4%	103
El gusanillo	100p	40.0%	319
Cortar el césped	100p	2.9%	2

Comments

0
aniervs commented on Dec. 22, 2019, 3:00 a.m.
Disculpen, anteriormente había escrito la solución del problema "Clasificando fracciones" de la prueba 4. Ahí va "Salvando al planeta”: Problema: Nos dan dos números $A$ ~A~ y $B$ ~B~ en sus representaciones en binario, nos piden calcular $A\%2^B$ ~A\%2^B~. $A$ ~A~ tiene tamaño $N$ ~N~ y $B$ ~B~ tiene tamaño $M$ ~M~ ( $N, M <= 10^6$ ~N, M <= 10^6~) . Solución: Lo primero es que no podemos convertir estos números a decimal porque necesitaríamos al menos $O(2^N)$ ~O(2^N)~ bits de memoria; por tanto necesitamos trabajar con ellos en binario. Para llegar a la solución haremos sencillas observaciones:

$2^B$ ~2^B~ en binario es todo cero excepto el bit $B$ ~B~, o sea: $00...0100...0$ ~00...0100...0~ ( $B$ ~B~ ceros a la derecha, recordemos que las cifras se enumeran de derecha a izquierda desde $0$ ~0~).

Sabemos que $A <= 2^N – 1$. Si $N < B$ ~N < B~, entonces $A < 2^B$ ~A < 2^B~, por lo que $A \% 2^B = A$ ~A \% 2^B = A~.

Si $N >= B$ ~N >= B~, entonces existe al menos un bit activo de A mayor o igual que B. Digamos que los bits activos de $A$ ~A~ que son mayores o iguales que $B$ ~B~ son { $x_1, x_2, ..., x_k$ ~x_1, x_2, ..., x_k~}. Digamos que los bits activos de $A$ ~A~ que son menores que $B$ ~B~ son { $y_1, y_2, ..., y_p$ ~y_1, y_2, ..., y_p~}. Entonces $\displaystyle A = (2^{x_1} + 2^{x_2} + ... 2^{x_k}) + (2^{y_1} + 2^{y_2} + ... + 2^{y_p})$ La primera parte es múltiplo de $2^B$ ~2^B~ puesto que todos los $x_i$ ~x_i~ son mayores o iguales que $B$ ~B~, y la segunda parte es menor que $B$ ~B~. Por tanto $\displaystyle A = 2^BQ + (2^{y_1} + 2^{y_2} + ... + 2^{y_p}) -> A \% 2^B = (2^{y_1} + 2^{y_2} + ... + 2^{y_p})$ Es decir: $A \% 2^B$ ~A \% 2^B~ es el número formado por los bits de $A$ ~A~ menores que $B$ ~B~.

Entonces, la solución sería: Si $B <= N$ ~B <= N~, imprimimos los $B$ ~B~ bits menos significativos de $A$ ~A~. Si $B > N$ ~B > N~, imprimimos todos los bits de $A$ ~A~. Para comparar $B$ ~B~ y $N$ ~N~ convertimos $N$ ~N~ a binario (lo guardamos en un arreglo) y los comparamos (el que tenga menor tamaño es el menor, y si tienen el mismo tamaño, los comparamos lexicográficamente); si resulta que $B > N$ ~B > N~, entonces imprimimos $A$ ~A~ completo; si $B<=N$ ~B<=N~, entonces convertimos $B$ ~B~ a decimal (sabemos que cabe en un entero de 32 bits porque N <= 10^6) e imprimimos los $B$ ~B~ bits más a la derecha de $A$ ~A~.

0

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

"Salvando al planeta". 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.

0

aniervs commented on Dec. 19, 2019, 2:21 a.m.

"el gusanillo". Problema: nos dicen que hay una rama de longitud L, que las hojas consecutivas están a distancia P, y que el gusano se mueve D unidades en cada momento. Si cae en una hoja, se la come. Nos dicen además que siempre hay una hoja en la posición 0 y que el gusano empieza en la posición 0. Cuántas hojas se come? Solución: Obviamente, las hojas están en las posiciones múltiplos de P. Y el gusano cae (al moverse) en todos los múltiplos de D, entonces lo que queremos saber es cuántas posiciones 0 <= x <= L son múltiplos de D y de P a la vez. Un número x es múltiplo de P y D si y solo si x es múltiplo de lcm(D,P) -el mínimo común múltiplo de D y P. Entonces la solución es la cantidad de múltiplos no negativos de lcm(D,P) menores o iguales que L, esta cantidad es la parte entera inferior de: $\displaystyle 1+\frac{L}{lcm(D,P)}$ $$\displaystyle 1+\frac{L}{lcm(D,P)}$$Para computar lcm(P,D), usamos lo siguiente: $\displaystyle lcm(a,b)=\frac{a}{gcd(a,b)}*b$ donde gcd(a,b) es el máximo común divisor de a y b. En c++ está implementada una función que computa el gcd de dos números: __gcd(a,b), toma tiempo O(log(min(a,b))), usa el algoritmo de Euclides.

0

aniervs commented on Dec. 19, 2019, 2:00 a.m.

algunos han hablado de que publiquen las editoriales. La verdad es que no todos los problemas tienen editoriales redactadas. Entonces, la alternativa es discutir aquí. Comenzaré explicando esta prueba y seguiré después con las demás.

-1

josemagotrue commented on Nov. 15, 2019, 5:07 p.m.

Seria bueno que publicaran los editoriales al final del contest !!!...

0

dmesadiaz commented on Nov. 13, 2019, 2:54 p.m.

seria bueno q ya acabado el contest publicaran editoriales para los problemas

0

dmesadiaz commented on Nov. 13, 2019, 2:53 p.m.

seria bueno q ya acabado el contest publicaran editoriales para los problemas

0

dmesadiaz commented on Nov. 13, 2019, 2:53 p.m.

seria bueno q ya acabado el contest publicaran editoriales para los problemas

0

dmesadiaz commented on Nov. 13, 2019, 2:53 p.m.

seria bueno q ya acabado el contest publicaran editoriales para los problemas

-3

Alf2 commented on Oct. 30, 2019, 3:16 p.m.

Salve el planeta!!!!

-5

Primervirgen commented on Oct. 30, 2019, 2:45 p.m.

Esta bueno el cuestionario....

This comment is hidden due to too much negative feedback. Show it anyway.

-6

Alf2 commented on Oct. 30, 2019, 12:11 p.m.

Se fue el contest
ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORA ORAAAA!!!

This comment is hidden due to too much negative feedback. Show it anyway.

-6

Primervirgen commented on Oct. 25, 2019, 4:30 a.m.

Este sera un set de problemas mixtos o de una temática especifica?

This comment is hidden due to too much negative feedback. Show it anyway.

5

leocar commented on Oct. 21, 2019, 10:09 p.m.

Vamos concursantes ya comenzamos con los concursos para que vallan preparándose con vista al Concurso Nacional y la Copa Regional del 2020....

6

arciel commented on Oct. 31, 2019, 1:47 a.m.

leocar entonces hay copa regional este año?