28a Olimpíada Brasileira de Informática
Remove Dígitos
Beatriz continua se divertindo inventando jogos sobre dígitos. Sua mais nova invenção é o jogo Remove Dígitos. Durante o jogo, Beatriz possui um número inteiro positivo N. A cada rodada, ela pode subtrair de N o valor de um dos dígitos presentes nele, reduzindo o valor de N. Por exemplo, se N=437, Beatriz pode escolher uma das seguintes operaçōes:- subtrair 4, obtendo 433;
- subtrair 3, obtendo 434;
- subtrair 7, obtendo 430.
Entrada
A entrada é composta por uma única linha contendo um único inteiro, o número N com o qual Beatriz inicia o jogo.Saída
Seu programa deverá imprimir uma única linha contendo um único inteiro, o número mínimo de rodadas de Remove Dígitos necessárias para transformar o número N em 0.Restrições
- 1 ≤ N ≤ 100 000
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima.- Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
- Subtarefa 2 (18 pontos): N ≤ 20.
- Subtarefa 3 (36 pontos): N ≤ 100.
- Subtarefa 4 (46 pontos): Sem restrições adicionais.
Exemplos
Entrada
23 |
Saída
5 |
Entrada
14 |
Saída
3 |
Entrada
437 |
Saída
75 |