Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

JOAOMG - João e o Pé de Feijão

João foi ao mercado vender uma vaca, a pedido de sua mãe. Chegando lá, um estranho lhe propôs trocar a vaca por cinco feijões mágicos e João aceita a oferta. A mãe dele, porém, fica furiosa com isso e joga os feijões pela janela e o coloca de castigo.

Durante a noite, os feijões germinam e se transformam em gigantescos pés de feijão. Quando João acorda, ele escala os pés de feijão e chega numa terra mágica acima das nuvens, habitada por um gigante que se alimenta de seres humanos. Felizmente, para João, o gigante não estava com fome e, em vez de degustá-lo logo de cara, o gigante o prendeu em uma cela até o jantar.

A cela é mantida trancada por um complicado mecanismo. Para destravá-lo, é preciso entrar com uma senha numérica, um processo extremamente tedioso e lento. A esposa do gigante simpatizou com João e lhe forneceu todas as informações que sabe sobre a tranca: a senha que a destrava é um número inteiro menor ou igual a 41001 e esse número é um número de Kaprekar.

Um número de Kaprekar é um inteiro positivo cujo quadrado, em sua representação decimal, pode ser dividido em duas partes que individualmente são inteiros positivos e que quando somadas são iguais ao número original. Por exemplo:

  • 297 é um número de Kaprekar porque 2972 = 88209 e 88+209=297;
  • 999 é um número de Kaprekar porque 9992 = 998001 e 998+001=999;
  • 100 não é um número de Kaprekar. 1002=10000 pode ser escrito como 100+00=100, mas 00=0 não é um inteiro positivo.

Por definição, 1 é um número de Kaprekar, ainda que ele não atenda ao critério acima. Mais formalmente, um inteiro n é um número de Kaprekar se:

n = q+r

n^2 = q·10m+r

Para algum m ≥ 1, q ≥ 0 e 0 ≤ r < 10m inteiros, com n ≠ 10a para todo a>=1 inteiro.

Entrar com uma senha errada no mecanismo faz com que ele fique inacessível por 5 minutos. Assim, se João tentar todos os números possíveis, ele muito provavelmente não conseguirá escapar antes da hora do jantar. João desconfia, porém, que apenas poucos valores sejam números de Kaprekar, de forma que seja possível testar todos esses antes do gigante retornar.

Sua tarefa é ajudar João: dado um inteiro, determine se ele é ou não um número de Kaprekar.

Entrada

A entrada possui vários casos de teste. Cada caso de teste é dado numa linha que contém um inteiro n (0 < n ≤ 41001). A entrada termina com n=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha na saída no formato N: A, onde N é o número analisado no caso de teste e A é S se n é um número de Kaprekar ou N se ele não for.

Exemplos

Entrada:
1
2
3
4
9
45
50
38962
0

Saída:
1: S
2: N
3: N
4: N
9: S
45: S
50: N
38962: S

Adicionado por:Wanderley Guimarăes
Data:2012-03-14
Tempo limite:3.890s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva UFMG 2011

hide comments
2017-07-10 14:33:10
Faltava um else if para excluir os valores 10, 100, 1000 e 10000.
para resolver o pr0blema.

#include <iostream>

// João e o Pé de Feijão
using namespace std;

int main( )
{
int k, q, P, n2, r;
char Resp;
do{
q=0; P=10; n2=0; r=0;
cin >> k;
if ((k==0) || (k > 41001) ){
break;
}
n2 = k*k;
while(P<n2){
q = n2/P;
r = n2%P;
P *= 10;
if (k == (q + r)){break;}
}
// aqui faltava um else if para excluir os valores 10, 100, 1000 e 10000.
// resolveu o prblema.
else if ((k == (q + r)) || (k==1))
{ Resp = 'S';}
else if (k != (q + r))
{ Resp = 'N';}

cout << k << ": " << Resp << endl;

}while(1);

return 0;
}
2016-04-25 01:11:09
faltava só um "\n" pra acertar a questão, pqp

Last edit: 2016-04-26 16:19:48
2012-11-03 17:14:52 Thalyson Nepomuceno [UECE]
LOL, vi agora o "com n ≠ 10a", agora fica ai a escolha de if's xD
2012-11-03 17:13:41 Thalyson Nepomuceno [UECE]
o enunciado da questăo está errado, vc tem q considerar que os valores de q,r > 0, se considerar >= 0, valores do tipo n == 10^k văo ser números de Kaprekar, o que na verdade năo săo, fica a dica aew, coloquem q e r > 0... sendo q só precisa o q > 0
2012-08-27 18:05:29 Carvalho
Eu năo compreendo, o meu agoritmo funciona perfeitamente em minha máquina. Porém quando o submeto aparece 'tempo limite excedido'. Entretanto em minha máquina funciona normalmente.

Já resolvi outros problemas antes e nunca tive esse problema
2012-04-29 19:54:57 Matheus Henrique


Last edit: 2012-04-29 19:56:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.