290 - Palindroms <---> smordnilaP

[yatsen]

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]

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]

Hmm..
Check this out:
Sample Example is wrong:
857 + 758 = 1726
1762 + 2671 = 7543

Why does 1726-->1762?

[pochmann]

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]

Check to see if the string is valid for each of the different bases.

[Sanghack]

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;
	// add reverse
	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;
	}
	// adjust
	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++;
				add_with_reverse(a,b,cur_scale);
				if(palindromes(b)){
					printf("%d ",cnt);
					break;
				}
				cnt++;
				add_with_reverse(b,a,cur_scale);
				if(palindromes(a)){
					printf("%d ",cnt);
					break;
				}
			}
		}
		while(cur_scale>1){
			printf("? ");
			cur_scale--;
		}
		printf("\n");
	}
}
//@END_OF_SOURCE_CODE

[/cpp]

[Rodrigo]

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.

How do I reach the site organizers to alert them about this?

[T.T.]

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]

ignore

[jingye]

error found. please ignore.

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

[21743NX]

Hi anyone can help me understand the base thingy

how did they get this??

Base 14 87 + 78 = 111

[DreamLinuxer]

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]

[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)
{
car = System.in.read();
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]

Please give me some advice. Thanks,

- Mike

[UFP2161]

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]

OMG I don