David's expedition

Points: 100

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

After successfully conquering the South Pole, David is preparing for new challenges. Next up is the Arctic expedition to Siberia, Greenland and Norway. He begins his travels on 31 December 2018, and needs to collect $N$ ~N~ pesos by then. In order to do this, he has decided to put away $X (X \le 100)$ ~X (X \le 100)~ pesos every Monday to his travel fund, $X + K$ ~X + K~ pesos every Tuesday, $X + 2 K$ ~X + 2 K~ every Wednesday, and so on until Sunday, when he will put away $X + 6 K$ ~X + 6 K~ pesos. This way, he will collect money for 52 weeks, starting with 1 January 2018 (Monday) until 30 December 2018 (Sunday).

If we know the amount of money $N$ ~N~ , output the values $X$ ~X~ and $K$ ~K~ so that it is possible to collect the exact money amount in the given timespan. The solution will always exist, and if there are multiple, output the one with the greatest $X$ ~X~ and smallest $K$ ~K~.

Input

The first line of input contains the integer $N (1456 \le N \le 145600)$ ~N (1456 \le N \le 145600)~, the number from the task.

Output

The first line of output must contain the value of $X ( 0 < X \le 100 )$ ~X ( 0 < X \le 100 )~ , and the second the value of $K (K > 0 )$ ~K (K > 0 )~.

Samples

Input 1

Output 1

1
1

Input 2

Output 2

14
1

Input 3

Output 3

99
4

Comments

3

linkyless commented on Dec. 4, 2022, 2:58 p.m.

Comentaré mi solución aquí porque me pareció interesante el problema (no sé si será ilegal).

En primer lugar, analicemos el problema y veamos cómo podemos plantearlo.

Se nos da un número $N$ ~N~, que representa la cantidad de dinero que David tiene que reunir al final del año. También sabemos que irá ahorrando dinero cada día de la semana, empezando por el lunes y terminando el domingo, con cantidades crecientes. La cantidad que ahorre el lunes será $X$ ~X~ pesos, la cantidad del martes será $X + K$ ~X + K~ pesos, y así sucesivamente hasta el domingo, cuando ahorrará $X + 6K$ ~X + 6K~ pesos (resumen del problema).

Necesitamos encontrar los valores de $X$ ~X~ y $K$ ~K~ que permitan a David reunir la cantidad exacta de dinero $N$ ~N~ en 52 semanas.

Una forma de abordar este problema es utilizar un algoritmo de fuerza bruta, en el que probamos todos los valores posibles de $X$ ~X~ y $K$ ~K~ y vemos cuáles permiten a David reunir la cantidad exacta de dinero $N$ ~N~ en 52 semanas.

Para ello, podemos empezar por recorrer todos los valores posibles de $X$ ~X~, de $0$ ~0~ a $100$ ~100~. Para cada valor de $X$ ~X~, podemos recorrer todos los valores posibles de $K$ ~K~, de $1$ ~1~ a $N / 52$ ~N / 52~ (ya que la cantidad máxima de dinero que David puede ahorrar en una semana es $X + 6K$ ~X + 6K~, y queremos asegurarnos de que no superamos la cantidad de dinero $N$ ~N~ que necesita reunir).

Para cada par de valores ( $X, K$ ~X, K~), podemos calcular la cantidad total de dinero que David reunirá en 52 semanas sumando la cantidad de dinero que ahorrará en cada día de la semana. Si esta cantidad total es igual a $N$ ~N~, hemos encontrado una solución y podemos detener la búsqueda. En caso contrario, seguimos probando con diferentes valores de $X$ ~X~ y $K$ ~K~.

Una vez que hayamos encontrado una solución, tenemos que asegurarnos de que es la que tiene la mayor $X$ ~X~ y la menor $K$ ~K~, como requiere el problema. Para ello, podemos simplemente mantener un registro de la mejor solución actual y actualizarla cada vez que encontremos una mejor.

Complejidad: $O(N^2)$ ~O(N^2)~, donde N es la cantidad de dinero que David necesita recaudar.