Jump to content
Ricardo Pereira

Problema

Recommended Posts

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 Ni, a tua tarefa é calcular uma sequência de números Si tal que Ni é 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 Ni, indicando que deves calcular o número cuja ordem na sequência de números com C ocorrências do algarismo A é Ni.

Output

O output deve ser constituído exactamente por Q linhas, cada uma delas no formato "Ni: Si", onde Si é 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 ≤ Ni ≤ 1 000 000 000 Números de ordem 1 ≤ Si ≤ 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 Ni≤100, Q≤100 e Si≤100 000. Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que Ni≤500 000 e Si≤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 by Ricardo Pereira
GeSHi

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.