28a Olimpíada Brasileira de Informática
Submeta sua solução

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.
Observe que, após cada rodada, o número de Beatriz diminui. O objetivo do jogo é transformar o número em 0 o mais rápido possível. O exemplo abaixo ilustra uma das maneiras de ganhar o jogo começando com N=23, para o qual o mínimo de rodadas necessárias é 5. Observe que existe mais de uma sequência de operações que transforma 23 em 0 com cinco rodadas, mas é impossível transformar 23 em 0 com quatro ou menos rodadas. 23 →(-2) 21 →(-2) 19 →(-9) 10 →(-1) 9 →(-9) 0 Beatriz pediu sua ajuda para verificar os resultados do jogo: dado o número inicial N, determine o número mínimo necessário de rodadas de Remove Dígitos para transformar N em 0.

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.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por qualquer uma das suas submissões.

Exemplos

Entrada
23
Saída
5
	

 

Entrada
14
Saída
3
	

 

Entrada
437
Saída
75
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação