## 290 - Palindroms <---> smordnilaP

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
I am confused for the base in 290.
In the Example:
Base 8 87+78=207
But how can digit 8 appear in the number based 8. I think 8 is illegal here.

Could anyone tell me what's wrong?

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i'm not sure which one you're referring to. the version on the web site states 'illegal' already

but, i can't get AC either.
can anyone tell me what tricks it has?

1. need to trim leading zeros first?
2. is there 0 steps?
3. what other tricks it has?
4. if input 0, then all zeros?

gilbert
New poster
Posts: 4
Joined: Wed Dec 12, 2001 2:00 am
Hmm..
Check this out:
Sample Example is wrong:
857 + 758 = 1726
1762 + 2671 = 7543

Why does 1726-->1762?

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
1. need to trim leading zeros first?
No (I don't).

2. is there 0 steps?
Yes.

3. what other tricks it has?
None. Maybe the input is badly formatted? I read it with scanf("%s").

4. if input 0, then all zeros?
Yes.

"1726-->1762" is obviously a mistake. Ignore it.

Good luck,
Stefan

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Check to see if the string is valid for each of the different bases.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

### 290 Palindromes... Are there any special cases? Nope~

I don't know why I still got WA.
I programmed it twice..

Do I have to use longer array more than 300?
Nope. cause max integer is 2^31 and... step will never be bigger than 100 so.. even step is reach to 100.. (even every time carry happen)
no more 131

... Then...

Should I have to deal with 'lower case'?
I don't think so..

What's wrong with me~
(so sorry about my poor english)

[cpp]

Code: Select all

``````//@JUDGE_ID:21160AX 290 C++ "simple"
//@BEGIN_OF_SOURCE_CODE
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_ARR_SIZE 300
void add_with_reverse(char* input,char* dest,int scale){
char temp[MAX_ARR_SIZE];
char* input_ptr=input;
char* temp_ptr=temp;
int carry;
int len,len2;
// copy
while(*input_ptr){
*temp_ptr=(*input_ptr<='9')? *input_ptr-'0':*input_ptr-'A'+10;
input_ptr++;
temp_ptr++;
}
input_ptr=input;
*temp_ptr=NULL;
len2=len=temp_ptr-temp;
temp_ptr--;
while(true){
*temp_ptr+=(*input_ptr<='9')? *input_ptr-'0':*input_ptr-'A'+10;
input_ptr++;
if(*input_ptr) temp_ptr--;
else break;
}
temp_ptr=temp_ptr+len-1;
carry=0;
while(len--){
*temp_ptr+=carry;
if(*temp_ptr>=scale){
carry=1;
*temp_ptr-=scale;
}
else{
carry=0;
}
if(len) temp_ptr--;
}
// to ascii.
if(carry){
*dest='1';
dest++;
}
while(len2--){
*dest=(*temp_ptr<=9)? *temp_ptr+'0':*temp_ptr+'A'-10;
dest++;
temp_ptr++;
}
*dest=NULL;
}
int palindromes(char* str){
char* begin=str;
int len=strlen(str);
char* end=str+len-1;
len>>=1;
while(len--){
if(*begin!=*end) return 0;
begin++;
end--;
}
return 1;
}
char max_char(char* str){
char result=str[0];
str++;
while(*str){
if(result<*str) result=*str;
str++;
}
return result;
}
void main(){
char *input,*a,*b;
int cnt,cur_scale,min_scale;
a=new char[MAX_ARR_SIZE];
b=new char[MAX_ARR_SIZE];
input=new char[MAX_ARR_SIZE];
//freopen("290.txt","rt",stdin);
while(scanf("%s\n",input)!=-1){
// for every input
min_scale=max_char(input);
min_scale=(min_scale>='A')? min_scale-'A'+10:min_scale-'0';
// for every possible scale.
for(cur_scale=15;cur_scale>min_scale && cur_scale>1;cur_scale--){
strcpy(a,input);
cnt=0;
while(true){
cnt++;
if(palindromes(b)){
printf("%d ",cnt);
break;
}
cnt++;
if(palindromes(a)){
printf("%d ",cnt);
break;
}
}
}
while(cur_scale>1){
printf("? ");
cur_scale--;
}
printf("\n");
}
}
//@END_OF_SOURCE_CODE``````
[/cpp]

Rodrigo
New poster
Posts: 14
Joined: Sun Jul 07, 2002 12:03 am
Location: Brazil
Contact:
The example is totally messed up!

Base 15 87 + 78 = 110
110 + 011 = 121 2 steps
Base 14 87 + 78 = 111 1 step <-- it should be "121 1 step"
Base 13 87 + 78 = 132
132 + 231 = 363 2 steps
Base 12 87 + 78 = 143
143 + 341 = 484 2 steps
Base 11 87 + 78 = 154
154 + 451 = 5A5 2 steps
Base 10 87 + 78 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884 4 steps
Base 9 87 + 78 = 176
176 + 671 = 857
857 + 758 = 1726
1762 + 2671 = 7543 <-- it should be "1726 + 6271 = 8107"
7543 + 3457 = 12111 <-- it should be "8107 + 7018 = 16126"
12111 + 11121 = 23232 6 steps <-- it should be "16126 + 62161 = 78287 6 steps"
Base 8 87 + 78 = 207 <-- in base 8 digits go from 0 to 7, 87 is illegal!
207 + 702 = 1111 2 steps <-- therefore, this line shouldn't be here
Base 7 illegal ? steps
Base 6 illegal ? steps
Base 5 illegal ? steps
Base 4 illegal ? steps
Base 3 illegal ? steps
Base 2 illegal ? steps

Which means, the correct output for 87 is not:

2 1 2 2 2 4 6 2 ? ? ? ? ? ?

like shown in the sample output; it is:

2 1 2 2 2 4 6 ? ? ? ? ? ? ?

Which is almost the same, but the intermediate results are completely wrong.

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

### WA

try the input
1
A

my output is
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 ? ? ? ? ? ? ? ? ?

but your output is
1 1 1 1 1 1 1 1 1 1 1 1 1 2
2 2 2 2 2 ? ? ? ? ? ? ? ? ?

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

### 290 Palindroms

ignore
Last edited by jingye on Fri Nov 15, 2002 7:35 pm, edited 1 time in total.

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

error found. please ignore.

be careful if the number is 0.
my code printed out 15 0's.

21743NX
New poster
Posts: 9
Joined: Tue Aug 27, 2002 8:39 am

### Harlow

Hi anyone can help me understand the base thingy

how did they get this??

Base 14 87 + 78 = 111

DreamLinuxer
New poster
Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

### 290 WA

Is there any special input?
I've tried many times but still got WA

[c]#include<stdio.h>
#include<string.h>
#define turn(a) ((a>='0'&&a<='9')?(a-'0'):((a>='A'&&a<='Z')?(10+a-'A'):(10+a-'a')))
#define max(a,b) (a<b?b:a)
char num[1024];
int tmp[1024],test[1024];
int pal(int l)
{
int i,j;
for(i=0,j=l-1;i<j;i++,j--)if(test!=test[j])return 0;
return 1;
}
int count(int base)
{
int t,i,j,l,k;
l=strlen(num);
for(i=l-1,j=0;i>=0;i--,j++)test[j]=num;
for(t=0;t<=100;t++)
{
if(pal(l))break;
for(i=0;i<1024;i++)tmp=0;
for(i=0;i<l;i++)tmp=test;
for(i=0;i<1024;i++)test=0;
for(k=i=0,j=l-1;k<l;k++,i++,j--)test[k]=tmp+tmp[j];
for(i=0;i<l;i++)if(test>=base)
{
if(i==l-1)l++;
test[i+1]+=test/base;
test%=base;
}
}
return t;
}
int main()
{
int i,f,m,l;
while(scanf("%s",&num)==1)
{
l=strlen(num);
for(i=m=0;i<l;i++)
{
num[i]=turn(num[i]);
m=max(m,num[i]);
}
for(i=15,f=0;i>m;i--)
{
if(f)putchar(' ');
printf("%d",count(i));
f=1;
}
for(;i>1;i--)
{
if(f)putchar(' ');
putchar('?');
f=1;
}
putchar('\n');
}
return 0;
}
[/c]

mdb47
New poster
Posts: 1
Joined: Mon Jun 16, 2003 12:14 am

### 290 Can't figure out why it rejects my solution :(

[java]import java.util.*;
import java.io.*;

class Main {

private boolean isPalindrome(String str) {

str = str.toUpperCase();

int midPoint = str.length() / 2;
for(int i = 0, j = str.length() - 1; i < midPoint; i++, j--)
if (str.charAt(i) != str.charAt(j))
return false;
return true;
}

private String reverse(String str) {
StringBuffer sb = new StringBuffer(str);
sb.reverse();
return sb.toString();
}

private int computeSteps(String str, int base) {

//System.out.println("BASE " + base);

try {
str = Long.toString(Long.parseLong(str, base), base);

for(int i = 0; i < 10000; i++) {
if (isPalindrome(str))
return i;

String rev = reverse(str);

long sum = Long.parseLong(str, base) + Long.parseLong(rev, base);

//System.out.println(str + " + " + rev + " = " + Long.toString(sum, base));

str = Long.toString(sum, base);
}
} catch(Throwable t) {
return -1;
}

return -1;
}

public Main() {
String input = null;
while((input = ReadLn(255)) != null) {
input = input.trim();
if (input.length() == 0)
continue;
StringBuffer sb = new StringBuffer();
for(int b = 15; b >= 2; b--) {
int steps = computeSteps(input, b);
if (b != 15)
sb.append(' ');
if (steps < 0)
sb.append('?');
else
sb.append(steps);
}
sb.append('\n');
System.out.print(sb.toString());
}
}

public static void main(String[] args) {
new Main();
}

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

}[/java]

- Mike

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Hopefully you figured it out by now, but to any others who come across this problem, the corrected example is below:
Base 15 87 + 78 = 110
110 + 011 = 121 2 steps
Base 14 87 + 78 = 121 1 step (was: 111 1 step)
Base 13 87 + 78 = 132
132 + 231 = 363 2 steps
Base 12 87 + 78 = 143
143 + 341 = 484 2 steps
Base 11 87 + 78 = 154
154 + 451 = 5A5 2 steps
Base 10 87 + 78 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884 4 steps
Base 9 87 + 78 = 176
176 + 671 = 857
857 + 758 = 1726
1726 + 6271 = 8107 (was: 1762 + 2671 = 7543)
8107 + 7018 = 16126 (was: 7543 + 3457 = 12111)
16126 + 62161 = 78287 6 steps (was: 12111 + 11121 = 23232 6 steps)
Base 8 illegal ? steps
Base 7 illegal ? steps
Base 6 illegal ? steps
Base 5 illegal ? steps
Base 4 illegal ? steps
Base 3 illegal ? steps
Base 2 illegal ? steps

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
OMG I don
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!