Final 2007 - Números Divertidos

[SirDave]

Estou com umas dúvidas em relação a este problema.

Basicamente, não sei até que K devo testar. O enunciado não define limites e assim não sei bem o que fazer.

Eu assim que li o enunciado pensei em programação dinâmica (Bottom up ou memoization, mas bottom up era melhor, se soubesse os limites).

#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cmath>

using namespace std;

bool is_fun(int n, int k) {
 stringstream temp_n;
 temp_n << n;
 string str_n = temp_n.str();

 int exponential_sum = 0;
 char current_char;
 for (int i = 0; i < (int) str_n.length(); i++) {
current_char = str_n[i];
exponential_sum += pow(atoi(&current_char), k);
 }

 if (exponential_sum == n) return true;
 return false;
}

int main() {
 int c;
 cin >> c;


 int a, b;
 int counter;
 for (int i = 0; i < c; i++) {
cin >> a >> b;

counter = 0;
for (int u = a; u <= b; u++) {
  for (int k = 1; k < 10; k++) {
	if (is_fun(u, k)) counter++;
  }
}

cout << counter << endl;
 }

 return 0;
}

Fiz a resolução brute force, é mesmo muito lenta, tive 35 pontos, com Time Limit Exceeded, como já esperava, porque nem se quer estou a fazer DP.

Eu agora quero implementar DP (é fácil 😛 ), mas não sei até que K devo testar.

Obrigado!

EDIT:

Já agora, o novo software do fórum tira as linhas vazias do código, que o tornam um bocado mais feio -.-

EDIT 2:

E também tira a indentação, estava tudo com 2 espaços, mas aqui no fórum fica uma mistura, quero o SMF de volta (software antigo do fórum)!

Edited May 19, 2012 at 08:37 PM by Warrior

[Warrior]

EDIT:

Já agora, o novo software do fórum tira as linhas vazias do código, que o tornam um bocado mais feio -.-

EDIT 2:

E também tira a indentação, estava tudo com 2 espaços, mas aqui no fórum fica uma mistura, quero o SMF de volta (software antigo do fórum)!

Podes colocar essas sugestões num tópico desta secção: http://www.portugal-a-programar.pt/forum/25-sugestoes-criticas-ou-duvidas-relativas-ao-pp/

Em relação à tua pergunta, acho que podes colocar facilmente um limite superior para o k:

O limite superior do intervalo é 2^31. De todos os números maiores que 1, aquele cuja exponencial cresce mais lentamente é o 2. Facilmente podes ver que não necessitas de testar para k > 31, dado que quando tal acontece ou o número sai fora do intervalo, ou então é 1 cuja exponencial é constante.

Mas acredito que consigas arranjar um limite superior ainda menor.

[xtrm0]

Acho que a solução não funciona como estas a fazer, eu acho que passaria por gerar todos os numeros engraçados (acho que a maioria dos numeros não são engraçados XD) e guardá-los num vector. E depois ver quantos há entre os limites para cada caso.

Spoiler 1:

Para gerares os numeros, podias começar por outra forma: para cada k [1,31], e para 10 inteiros [0,9], vias quais as somas que geravam numeros formados pelos inteiros que usaste. Claro que terias de chegar a outras conclusões para chegares aos 100 pontos...

Spoiler 2:

Nota que para este problema a ordem dos numeros [0,9] nao importa.

Edit 1:

EDIT:

Já agora, o novo software do fórum tira as linhas vazias do código, que o tornam um bocado mais feio -.-

EDIT 2:

E também tira a indentação, estava tudo com 2 espaços, mas aqui no fórum fica uma mistura, quero o SMF de volta (software antigo do fórum)!

Concordo para algumas coisas, mas tens de ver que a versão antiga do forum ja estava a ser modificada pela comunidade do p@p há 5(?) anos eque por isso a maioria dos bugs tinha sido corrigida pela comunidade. Esta versão do forum vai provavelmente também ver esses bugs corrigidos, mas terás de esperar algum tempo.

Edited May 19, 2012 at 09:00 PM by xtrm0

[mogers]

Estou com umas dúvidas em relação a este problema.

Basicamente, não sei até que K devo testar. O enunciado não define limites e assim não sei bem o que fazer.

Só gostaria de reforçar que o enunciado define correctamente os limites.

Os problemas das olimpiadas definem sempre os limites dos dados de entrada (input). O "K" que referes está relacionado com a resposta do problema (output), logo, o enunciado não precisa de dizer qual é o "K" máximo.

Penso que parte do desafio era precisamente pensar qual é o limite para o "K" (vê o post do warrior).