USACO - Palindromic Squares

[polska]

Boas pessoal, estou com uma duvida no seguinte problema:

Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.

Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.

Print both the number and its square in base B.

PROGRAM NAME: palsquare

INPUT FORMAT

A single line with B, the base (specified in base 10).

SAMPLE INPUT (file palsquare.in)

10

OUTPUT FORMAT

Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself.

SAMPLE OUTPUT (file palsquare.out)

1 1

2 4

3 9

11 121

22 484

26 676

101 10201

111 12321

121 14641

202 40804

212 44944

264 69696

Eu não estou a perceber o que é que o output tem mesmo haver com o input...

e.g. no teste:

input: 10

1 1

2 4

3 9

11 121

22 484

26 676

101 10201

111 12321

121 14641

202 40804

212 44944

264 69696

O que é que o 10 tem haver com o resultado? A lógica que vejo ali é multiplicar o número por ele mesmo e ver se é palindrome, tipo 101*101 = 10201 (palindrome) , não percebo o porquê do 10, e se mudar para 15? Quais seriam os resultados?

Edited June 30, 2012 at 10:40 PM by polska

[pmg]

O 10 é a base em que os resultados sáo escritos. Se fosse 2 (numeração binária) o output seria qualquer coisa como (números completamente inventados, sem relação uns com os outros)

10101 10101010101

10101010 1111010111101011101

0101010000001 0101010101011111010100101

[polska]

O 10 é a base em que os resultados sáo escritos. Se fosse 2 (numeração binária) o output seria qualquer coisa como (números completamente inventados, sem relação uns com os outros)

10101 10101010101

10101010 1111010111101011101

0101010000001 0101010101011111010100101

então vou ter 4 tipos de output certo?

binario, octal, decimal e hexa certo? se for outro numero é decimal na mesma ?

[pmg]

Se o input for

3

o ouput seria qualquer coisa como (mais uma vez, números completamente inventados, sem relação uns com os outros)

0120122 22200001002010
01110101221 0012121212121212121200

[polska]

Se o input for

3

o ouput seria qualquer coisa como (mais uma vez, números completamente inventados, sem relação uns com os outros)

0120122 22200001002010
01110101221 0012121212121212121200

Não estou a perceber.. se for 2 binários, 8 octais, 10 decimais, 16 hexa, outro numero qualquer são numeros inventados?

[pmg]

Não são números inventados. São números em base 2, 3, 4, 5, ..., ou 20.

A sequencia de caracteres "450054" (um palindromo):

em base 6 representa o número 4*6^5 + 5*6^4 + 4*6^1 + 5*6^0 (ou 37613)

em base 10 representa o número 4*10^5 + 5*10^4 + 4*10^1 + 5*10^0 (ou 450054)

em base 17 representa o número 4*17^5 + 5*17^4 + 4*17^1 + 5*17^0 (ou 6097106)

...

[HappyHippyHippo]

não ... o que pmg quer dizer é que um palindroma numa base não significa que o seja noutro

apesar de que é normal uma pessoa conhecer as bases 2, 8, 10 e 16, nada impossibilita o uso de outras

[pmg]

o que pmg quer dizer é que um palindroma numa base não significa que o seja noutro

Não exactamente. Um palindroma é propriedade da representação do número, não é propriedade dum número.

Um número por si só, nem é, nem deixa de ser, um palindroma; assim como um número não é, nem deixa de ser amarelo.

O que é (ou não) um palindroma, é a representação textual dum número.

E, sendo a representação textual dum número um palindroma, é sempre um palindroma qualquer que seja a base (válida) para essa representação.

A sequência de caracteres "1110000111" representa um palindroma em qualquer representação com base maior ou igual a 2.

[polska]

Penso que já percebi, vou tentar resolver.

Obrigado pelas respostas 😄

[HappyHippyHippo]

Não exactamente. Um palindroma é propriedade da representação do número, não é propriedade dum número.

Um número por si só, nem é, nem deixa de ser, um palindroma; assim como um número não é, nem deixa de ser amarelo.

O que é (ou não) um palindroma, é a representação textual dum número.

E, sendo a representação textual dum número um palindroma, é sempre um palindroma qualquer que seja a base (válida) para essa representação.

A sequência de caracteres "1110000111" representa um palindroma em qualquer representação com base maior ou igual a 2.

ok, aceito que a minha frase seja demasiado aberta.

o que eu queria dizer foi : que um número na sua representação em base X não o seja em base Y

PS : faltava um "não" lá pelo meio 😄

Edited July 1, 2012 at 11:01 AM by HappyHippyHippo

[polska]

O meu prog funcionou para base 10, mas não para os outros casos..

ex: 121 em base 2 , 1*2^2 + 2*2^1 + 2*1^0 certo?

int toBase( int num, int base )
{
 float B = base;
 int i = 0;
 int numero = 0;
 do
 {
   numero = numero + (num%10)*pow(B,i);
   num /= 10;
   if( num == 0 )
    break;
   i++;
 } while( true );
 return numero;
}

[pmg]

ex: 121 em base 2 , 1*2^2 + 2*2^1 + 2*1^0 certo?

Não. Os digitos em base 2 só podem ser 0 e 1; em geral, os digitos na base N só podem ser de 0 a N-1 (de 0 a 9 em base 10; de 0 a 15 (F) em base 16).

121 não pode nunca represntar um número em binário; o 2 é inválido

[mogers]

Vê por exemplo a parte de conversão de bases em http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

No problema da usaco tens de usar os digitos 0..9 e letras A..J (representam digitos 11..19 em bases > 10).

Edited July 1, 2012 at 03:38 PM by mogers

[polska]

Vê por exemplo a parte de conversão de bases em http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

No problema da usaco tens de usar os digitos 0..9 e letras A..J (representam digitos 11..19 em bases > 10).

Deu-me bastante jeito esse post, já entendi direitinho o que tenho de fazer, e já fiz, mas estou com um pequeno problema em bases menores ou iguais a 10, por exemplo, em base binária.. Tenho o i = 40, e passo para a função o num = 40*40 (1600) e passo a base = 2 .. O problema e que ao converter o 1600 para binário, o número onde guardo o resultado vai ficando muito grande, e toma dimensões que um inteiro não consegue suportar, e o resultado fica-me com um número completamente estranho, que depois faz retornar true na função de verificar palindrome... Isto é chato xD !

Devo fazer a conversão para um vector ou haverá uma maneira de contornar isto ?

conversão:

int toBase( int num, int base )
{
int result = 0;
int multiplicacao = 1;

while( num > 0 )
{
 result += num%base*multiplicacao;
 multiplicacao *= 10;
 num /= base;
}

return result;
}

palindrome? :

bool palindrome ( int num )
{
string result = "";

while( num > 0 )
{
 result += num%10 ;
 num /= 10;
}

for( int i=0; i<result.length(); i++ )
{
 if( result[i] != result[result.length()-i-1] )
  return false;
}

return true;
}

Ao acontecer isto, não passo no teste da base 2.. apenas por causa dos números estranhos, que também são imprimidos..

1 1
3 1001
40 -1883901888
41 -1874891887
42 -1873801788
43 -1784790887
44 -1774891888
45 -1773800887
51 -2079114103
52 -2069205104
53 -2068104103
54 -1978115004
55 -1968205103
56 -1668149696
57 -1659039695
58 -1569049596
59 -1559138695
60 -669139696
61 -659148695
62 -569149596
63 -559149695
64 -727379968
65 -717379967
66 -627379868
67 -617378967
88 -1395529664
89 -1385419663
90 -1286429564
94 -1968832284
95 -1877832383
96 -1568766976
97 -1557766975
98 -1458766876
99 -567765975
100 -468756976
101 -457755975
102 -1752980092
103 -1661970191
104 -762080192
105 -663070191
106 -651980092
107 -342903783
108 -243004784
118 -1295046844
119 -1195136943
122 -1490360060
123 -1390449159
124 -1080384752
125 -980393751
126 -80394652
134 -1608354556
135 -1508344655
138 -1801667772
139 -1701656871
140 -1382692464
141 -1282601463
142 -381702364
143 -281602463
144 -350932736
154 -2109982332
155 -2009071431
156 -1020072432
159 -1691385151
160 -1292319744
161 -1191319743
162 -282319644
163 -181318743
164 -1386622960
165 -485621959
166 -376532860
167 -65457551
173 -2008598711
174 -1018699612
175 -909599711
176 -2114012928
177 -1212912927
178 -1103012828
179 -703846519
182 -1429394876
183 -519484975
184 -119429568
185 -10319567
187 -304731783
194 -1157874844
195 -837808535
198 -942022652
199 -32012751
203 -203249063
207 -1998161951
210 -1882509660
211 -1772408759
212 -773499760
213 -841629031
221 -1599888727
222 -1244047644
223 -253047743
230 -1913097340
231 -1980317711
232 -980427712
233 -571352303
234 -460262204
236 -655665520
243 -1812713719
245 -2016016935
246 -1605962428
247 -606052527
248 -664292800
255 -1334442495
257 -1420047871
258 -1009982364
259 -9981463
260 -1204285680
261 -204284679
265 -2146417839
266 -1736262332
267 -736251431
268 -1921665648
269 -921574647
270 -510610140
272 -1003912960
273 -3812959
279 -1831282927
280 -830292928
281 -420117519
283 -604529735
287 -2032600639
288 -733535232
290 -917848348
295 -1759870607
296 -459915200
297 -1645218415
298 -644128316
299 -145052007

Edited July 2, 2012 at 02:12 PM by polska

[pikax]

eu resolvi esse criando um array com o os caracteres possiveis de 0....J, depois tinha outro array que era o resultado, de cada operacao:

while( num > 0 )

{

result[i++] += num%base*multiplicacao;

multiplicacao *= 10;

num /= base;

}

depois criavas um array com o numero, isso fazes ao percorreres o array de resultado inversamente

[polska]

eu resolvi esse criando um array com o os caracteres possiveis de 0....J, depois tinha outro array que era o resultado, de cada operacao:

while( num > 0 )

{

result[i++] += num%base*multiplicacao;

multiplicacao *= 10;

num /= base;

}

depois criavas um array com o numero, isso fazes ao percorreres o array de resultado inversamente

void toBase ( int num, int base, int resultado[30], int numero[30] )
{

int multiplicacao = 1;
int i = 0;
int p = 0;

while ( num > 0 )
{
   resultado[i++] += num%base*multiplicacao;
   multiplicacao *= 10;
   num /= base;
}

for( int j=i; j>=0; j-- )
{
   numero[p] = resultado[j];
   p++;
}

}

Fiz assim, mas o array numero que guarda o numero no final fica mal, na posição 0 tem 0, na 1 já tem um numero grande tipo 12347213, na 2 ja tem 1 .. etc etc

Edited July 2, 2012 at 04:32 PM by polska

[pikax]

primeiro tens que decrementar o i uma vez.

porque que estas a multiplicar?? :S

[polska]

primeiro tens que decrementar o i uma vez.

porque que estas a multiplicar?? :S

eu antes tinha o i a começar em -1 .. xD

Realmente, basta-me guardar o resto da divisão... Tens razão ;D

Edited July 2, 2012 at 04:59 PM by polska

[polska]

GRRRRR!

Conssegui fazer o dual palindromes, mas o palindromic square não passa!

Como é que é suposto o meu output estar errado?

----- our output ---------

1_1

11_1001

---- your output ---------

1_1

3_1001

--------------------------

se 3*3 = 9 e 9 = 1001 em binário, como é que tenho mal isto ?

nem 11 nem 11*11 representa 1001 em binário..!

xD

EDIT: TIpo já sei, o 3 = 11 em binário, <facepalm> !!!

é cada uma

Edited July 2, 2012 at 06:51 PM by polska

[Warrior]

Acho que deves ter percebido mal o problema.

Apesar de não ter o input, eu diria que a base é binário; assim sendo:

11 = 3

1001 = 9

Tens que indicar tanto N como N^2 na base pedida.