3388 - Hugo's Homework 3388 - Haciendo la Tarea 3388 - Hugo's Homework

Statistics Sub: 451 | AC: 301 | AC%: 66,74 | Score: 0,62
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Fidel I. Schaposnik
Added by fidels (2015-10-12)
Limits
Total Time: 5000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Hugo goes to primary school, but he is convinced that not enough homework is being given to him. Specifically, he was recently taught how to subtract two numbers, but each day he is given a single subtraction to perform at home. Hugo knows that in order to master such a complex technique he should practice much more, so he has decided to take matters into his own hands and create his own homework.

It's not easy for Hugo to invent exercises about a subject he does not fully comprehend, so he has devised the following method to perform multiple subtractions. He starts by asking his mother for a number N, and then forms the number M containing the same digits as N in increasing order from left to right, after which he finally performs the subtraction N-M. For example, if his mother chooses the number N = 321 then M = 123 and the subtraction Hugo must perform is N - M = 321-123 = 198.

Hugo wouldn't want to bother his mother too often, so he will repeat this procedure using the result of the subtraction N-M in one step as the number N he starts with in the next step. This will end only when at some point he reaches the value N = 0, as this case is useless to practice subtractions because he would have M = 0: Hugo already knows perfectly well that if he has no candies he cannot eat any candies, and will therefore continue to not have or eat candies forever.

Now Hugo's mother would like to know, given a number N, how many subtractions Hugo can perform if she gives him that number to start his homework. In the previous example, in the second step Hugo would have N = 198 so that M = 189 and N - M = 198 - 189 = 9. Then in the third step N = 9, M = 9 and N - M = 0, so here the fun ends because in the fourth step he would have N = 0. Thus, starting with the number N = 321 Hugo will perform subtractions.
Hugo va a la escuela primaria, pero está convencido de que allí no le dan suficiente tarea para el hogar. En particular, recientemente le enseñaron a restar, pero cada día le dan solamente una resta para hacer en su casa. Hugo sabe que para aprender una técnica tan compleja debe practicar mucho más, de modo que ha decidido tomar cartas en el asunto y crear su propia tarea.

Como no es fácil para Hugo inventar ejercicios sobre un tema que no domina, se le ocurrió el siguiente método para poder hacer muchas restas. Empieza pidiéndole a su madre que le diga un número N, luego arma el número M que tiene los mismos dígitos que N pero ordenados de menor a mayor de izquierda a derecha, y finalmente realiza la resta N - M. Así, si por ejemplo su madre elige el número N = 321, entonces M = 123 y la resta que debe hacer Hugo es N - M = 321 - 123 = 198.

Como Hugo no quiere molestar a su madre muy seguido, va a repetir este procedimiento usando el resultado de la resta N - M de un paso como el número N para comenzar el paso siguiente. Esto terminará solamente cuando Hugo llegue en algún momento al valor N = 0, dado que este caso no sirve para practicar restas porque tendría M = 0 y él ya sabe que si no tiene ningún caramelo no puede comer ningún caramelo, por lo que seguirá no teniendo ni comiendo caramelos para siempre.

Ahora la madre de Hugo quiere saber, dado un número N, cuántas restas va a hacer Hugo si ella le da ese número para comenzar su tarea. En el ejemplo anterior, en el segundo paso Hugo tendrá N = 198, de modo que M = 189 y N - M = 198 - 189 = 9. Entonces, en el tercer paso N = 9, M = 9 y N - M = 9 - 9 = 0, por lo que aquí se termina la diversión, siendo que en el cuarto paso tendría N = 0. Por lo tanto, empezando con el número N = 321 Hugo debe hacer 3 restas.
Hugo goes to primary school, but he is convinced that not enough homework is being given to him. Specifically, he was recently taught how to subtract two numbers, but each day he is given a single subtraction to perform at home. Hugo knows that in order to master such a complex technique he should practice much more, so he has decided to take matters into his own hands and create his own homework.

It's not easy for Hugo to invent exercises about a subject he does not fully comprehend, so he has devised the following method to perform multiple subtractions. He starts by asking his mother for a number N, and then forms the number M containing the same digits as N in increasing order from left to right, after which he finally performs the subtraction N-M. For example, if his mother chooses the number N = 321 then M = 123 and the subtraction Hugo must perform is N - M = 321-123 = 198.

Hugo wouldn't want to bother his mother too often, so he will repeat this procedure using the result of the subtraction N-M in one step as the number N he starts with in the next step. This will end only when at some point he reaches the value N = 0, as this case is useless to practice subtractions because he would have M = 0: Hugo already knows perfectly well that if he has no candies he cannot eat any candies, and will therefore continue to not have or eat candies forever.

Now Hugo's mother would like to know, given a number N, how many subtractions Hugo can perform if she gives him that number to start his homework. In the previous example, in the second step Hugo would have N = 198 so that M = 189 and N - M = 198 - 189 = 9. Then in the third step N = 9, M = 9 and N - M = 0, so here the fun ends because in the fourth step he would have N = 0. Thus, starting with the number N = 321 Hugo will perform subtractions.

Input specification

One line containing an integer N, representing the number Hugo's mother will give him to start his homework (1 <= N <= 10^9).
Una línea conteniendo un entero N, que representa el número que su madre le da a Hugo para comenzar su tarea (1 <= N <= 10^9).
One line containing an integer N, representing the number Hugo's mother will give him to start his homework (1 <= N <= 10^9).

Output specification

Print one line containing one integer representing the number of subtractions Hugo will perform if he starts his homework with number N.
Imprimir en la salida una línea conteniendo un entero que representa la cantidad de restas que Hugo debe hacer si empieza su tarea con el número N.
One line containing an integer N, representing the number Hugo's mother will give him to start his homework (1 <= N <= 10^9).

Sample input

321

Sample output

3

Hint(s)

Sample input #2
20

Sample output #2
2

Sample input #3
960687301

Sample output #3
91
Sample input #2
20

Sample output #2
2

Sample input #3
960687301

Sample output #3
91
Sample input #2
20

Sample output #2
2

Sample input #3
960687301

Sample output #3
91

Recommendation

We have carefully selected several similar problems: 3376 | 2156 | 2441 | 2534 | 3479 | 1811