Problema - Trinta e Três

[Ricardo Pereira]

Eu tou a concorrer a umas olimpiadas de informatica e tem lá uns programas de anos anteriores para praticarmos e eu gostava de ter o vosso aconselhamento sobre o seguinte

Problema - Trinta e Três

http://mooshak.dcc.fc.up.pt/~oni-treino/cgi-bin/execute/8527973903588938?image+A+probA.jpgCertamente te recordas da Ana e do Aniceto, os dois amigos que gostam de matemática. Eles estão agora ocupados com o jogo do 33. O desafio consiste em ir escrevendo números (sem repetir) que tenham exactamente duas ocorrências do algarismo 3 (nem mais nem menos):

133 653783 76338 433 3763 993734

A Ana e o Aniceto repararam que os números não estavam a aparecer por nenhuma ordem específica. Decidiram então fazer um jogo onde cada um tinha de dizer o número que vinha a seguir na sequência ordenada de forma crescente de todos os números com duas ocorrências do algarismo 3.

Ordem na sequência: 1 2 3 4 5 6 7

Números com 2 ocorrências do algarismo 3: 33 133 233 303 313 323 330 (...)

As mentes matemáticas dos dois amigos queriam ainda um desafio maior. E em vez de dizerem simplesmente o próximo número, o desafio passou a ser descobrir qual o N-ésimo número da sequência de números com exactamente duas ocorrências do algarismo 3, ou seja, qual o número cuja ordem nessa sequência é N. Por exemplo, se a pergunta fosse qual o 7º número, isto é, o número de ordem 7, a resposta seria 330. Já se a pergunta fosse qual o 5º número, a resposta seria 313.

Com todas estas ideias ainda na cabeça eles pensaram então em generalizar o problema. Dados dois inteiros A e C, eles querem pensar na sequência de números com exactamente Cocorrências do algarismo A. E naturalmente, querem saber, dado um número N, qual o N-ésimo número dessa sequência. Por exemplo, se a sequência for a dos números com uma ocorrência do algarismo 5 temos:

Ordem na sequência: 1 2 3 4 5 6 7 8 9

Números com 1 ocorrência do algarismo 5: 5 15 25 35 45 50 51 52 53 (...)

Tens de ajudá-los criando um programa para jogar este jogo!

O Problema

Dados um algarismo A, um número inteiro C e uma sequência de Q números inteiros N_i, a tua tarefa é calcular uma sequência de números S_i tal que N_i é o seu número de ordem na sequência ordenada de números com exactamente C ocorrências do algarismo A.

Input

Na primeira linha do input vêm um algarismo A e um número inteiro C, separados por um espaço, indicando que queremos números com exactamente C ocorrências do algarismo A.

Segue-se uma linha com um único número inteiro Q, indicando a quantidade de casos a considerar.

Seguem-se exactamente Q linhas, cada uma contendo um único número inteiro N_i, indicando que deves calcular o número cuja ordem na sequência de números com C ocorrências do algarismo A é N_i.

Output

O output deve ser constituído exactamente por Q linhas, cada uma delas no formato "N_i: S_i", onde S_i é o N-ésimo número da sequência que estamos a considerar. Estas linhas devem vir pela mesma ordem em que aparecem no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa: 1 ≤ A ≤ 9 Algarismo a considerar 1 ≤ C ≤ 9 Número de ocorrências do algarismo 1 ≤ N_i ≤ 1 000 000 000 Números de ordem 1 ≤ S_i ≤ 2 000 000 000 Números da sequência 1 ≤ Q ≤ 1 000 Quantidade de casos a considerar

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N_i≤100, Q≤100 e S_i≤100 000. Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que N_i≤500 000 e S_i≤1 000 000.

Exemplo de Input 1

3 2

7

1

2

3

7

6

5

4

Exemplo de Output 1

1: 33

2: 133

3: 233

7: 330

6: 323

5: 313

4: 303

Exemplo de Input 2

5 1

4

1

3

20

10

Exemplo de Output 2

1: 5

3: 25

20: 115

10: 54

E eu tenho a seguinte solução

program ex_a_finais;
uses
crt,sysutils;
var
n_vezes,n_max,cont,n_chars,total,num_seq,i,x,alg:integer;
num_str,algarismo,alg_prov:string[10];
max_seq,j:longint;
begin
clrscr();
max_seq:=1000000000;
readln(alg, n_vezes);
str(alg,algarismo);
readln(n_max);
for i:=1 to n_max do
begin
 readln(num_seq);
 total:=0;
 alg_prov:='';
 for j:=1 to n_vezes do //Numero de vezes que pede o n¦ da sequencia
 begin
	 alg_prov:=alg_prov+algarismo; //Reduzir o numero de itera‡äes, saltando logo para a primeira possivel
 end;
 x:=StrToInt(alg_prov);
 for j:=x to max_seq do //Repete para achar o numero
 begin
	 cont:=0;
	 str(j,num_str);
	 n_chars:=length(num_str);

	 for x:=1 to n_chars do //Correr os algarismos com o numero ja dividido
	 begin
	 if num_str[x] = algarismo then
		 cont:=cont+1;
	 end;
	 if cont=n_vezes then
	 total:=total+1;
	 if num_seq=total then
	 break;
 end;
 writeln(num_seq,': ',j);
end;
end.

O programa é submetido e rodado remotamente num servidor passando por determinados testes e é dado uma pontuação. Eu mesmo fazendo o que sabia apenas consegui 20 pontos em 100 e gostaria que me pudessem ajudar, indicando outro tipo de algoritmo para resolver o mesmo problema.

Aguardando Resposta

Edited May 1, 2013 at 08:26 AM by Ricardo Pereira
GeSHi