## 290 - Palindroms <---> smordnilaP

Moderator: Board moderators

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
OMG I don't understand why 87 + 78 in base 15 is 110! I've already lost a considerable time trying to understand this, but couldn't. I feel really embarassed about it!

UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You could convert all the numbers to base 10, then maybe it'll be easier to understand:

87 (base 15) = 8*15 + 7 = 127
78 (base 15) = 7*15 + 8 = 113
127 + 113 = 240 = 1*15^2 + 1*15 + 0 = 110 (base 15).

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:
When the input is 0, you print 15 0's, but there should be only 14 0's.

smajdalf.11
New poster
Posts: 1
Joined: Thu Mar 22, 2012 8:10 pm

### 290 - Palindroms <---> smordnilaP

Code: Select all

import java.io.*;
class Main {
static String[] result = new String[14];
static String[] print = new String[0];
static int step = 0;
static String base = "0123456789ABCDE";
static int bigCount = 0;
public static void main(String[] args){
try{
while (input != null  && input.length() != 0){
char[] number = new char[input.length()];
for(int i = 0; i<input.length(); i++){
number[i]=input.charAt(i);
}
if(isNumber(number)){
bigCount++;
for(int i = 2; i<=15; i++){
if(inBase(number, i)){
result[i-2]="?";
}
}
print=largePrint(print);
for(int i=result.length-1; i>0;i--){
print[bigCount-1]+=result[i]+" ";
}
print[bigCount-1]+=result[0];
}
}
for(int i = 0; i<print.length;i++){
System.out.println(print[i]);
}
br.close();
}catch(Exception e){
e.printStackTrace();
}
System.exit(0);
}

public static String[] largePrint(String[] small){
String[] big = new String[bigCount];
for(int i = 0; i<small.length; i++){
big[i]=small[i];
}
big[big.length-1]="";
return big;
}

public static boolean isNumber(char[] number){
for (int i = 0; i<number.length; i++){
if(!(number[i]>='0' && number[i]<='9')){
if(!(number[i]>='A' && number[i]<=base.charAt(base.length()-1))){
return false;
}
}
}
return true;
}

public static boolean inBase(char[] number, int length){
step=0;
if(length<=10){
for (int i = 0; i<number.length; i++){
if(!(number[i]>='0' && number[i]<=base.charAt(length-1))){
return true;
}
}
toNumber(number, length);
return false;
}
else{
for (int i = 0; i<number.length; i++){
if(!(number[i]>='0' && number[i]<='9')){
if(!(number[i]>='A' && number[i]<=base.charAt(length-1))){
return true;
}
}
}
toNumber(number, length);
return false;
}
}

public static void toNumber(char[] number, int length){
int[] numberD = new int[number.length];
for (int i = 0; i<number.length;i++){
if(number[i]<'9'){
numberD[i]=number[i]-48;
}
else if(number[i]>='A'){
numberD[i]=number[i]-55;
}
}
isPalindrom(numberD,length);
}

public static void isPalindrom(int[] number, int length){
if(step == 100){
result[length-2]="?";
}
else{
boolean podminka = true;
int count = number.length-1;
for(int i = 0; i<number.length; i++){
if(number[i]!=number[count]){
podminka = false;
}
count--;
}
if(podminka){
result[length-2]=""+step;
}
else{
step++;
dalsi(number, length);
}
}
}

public static void dalsi(int[] number, int length){
int[] opacne = new int[number.length];
int count = number.length-1;
for(int i = 0; i<number.length;i++){
opacne[i]=number[count];
count--;
}
int[] tmp = new int[number.length];
for(int i =0; i<tmp.length;i++){
tmp[i]=number[i]+opacne[i];
}
int[] end = new int[tmp.length+1];
int rest = 0;
for(int i = 0; i<tmp.length;i++){
end[i]=tmp[i]%length;
if(i!=tmp.length-1){
tmp[i+1]+=tmp[i]/length;
}
else{
rest=tmp[i]/length;
}
}
if(rest!=0){
end[tmp.length]=rest;
}
else{
end=decrease(end);
}
isPalindrom(end, length);
}

public static int[] decrease(int[] big){
int[] small = new int [big.length-1];
for(int i = 0; i<small.length;i++){
small[i]=big[i];
}
return small;
}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 290 Palindroms why WA

Input:
19

AC output:
1 1 1 1 1 2 ? ? ? ? ? ? ? ?
Check input and AC output for thousands of problems on uDebug!

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: 290 Palindroms why WA

WA...don't know y ?

Removed Code after AC.
Last edited by gr81 on Wed Oct 24, 2012 10:10 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 290 Palindroms why WA

You're printing an extra newline at the end of the output.
Check input and AC output for thousands of problems on uDebug!

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: 290 Palindroms why WA

thanks.

kier.guevara
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

### Re: 290 Palindroms why WA

Code: Select all

import java.util.*;
import java.math.*;

public class Main
{
public static BigInteger toDec(String a, int base)
{
BigInteger ans = new BigInteger("0");
BigInteger bMul = new BigInteger(Integer.toString(base));

for(int i = a.length()-1; i >= 0; i--)
{
int tempInt = (int) a.charAt(i);
String ch = "" + a.charAt(i);
bMul = new BigInteger(Integer.toString(base));
bMul = bMul.pow(a.length()-1-i);
//	System.out.println("" + bMul);
if(a.charAt(i) >= 'A')
{
tempInt = (tempInt - 'A') + 10;
String tempStr = Integer.toString(tempInt);
BigInteger toMul = new BigInteger(tempStr);
}
else
{
BigInteger toMul = new BigInteger(ch);
}
}
return ans;
}

public static String toBase(String ab, int base)
{
BigInteger a = new BigInteger(ab);
String ans = "";
BigInteger b = new BigInteger("" + base);

while(a.compareTo(new BigInteger("0")) != 0)
{
if(a.mod(b).compareTo(new BigInteger("10")) >= 0)
{
String aT = "" +  a.mod(b);
int temp = Integer.parseInt(aT);
char ch = (char)(temp + 'A' - 10);

ans += ch;
}
else
ans += "" + a.mod(b);
a = a.divide(b);
}
StringBuffer tm = new StringBuffer(ans);
tm.reverse();
return "" + tm;
}

public static int getMax(String a)
{
int maxAns = 0;
for(int i = 0; i < a.length(); i++)
{
int tempInt = (int) a.charAt(i);
tempInt = (tempInt - 'A') + 10;

if(tempInt >= 10)
maxAns = Math.max(tempInt,maxAns);
else
{
String b = "" + a.charAt(i);
maxAns = Math.max(maxAns,Integer.parseInt(b));
}

}
return maxAns;
}

public static String reverse(String a)
{
StringBuffer me = new StringBuffer(a);
me.reverse();

return "" + me;
}

public static boolean isPal(String a)
{
for(int i = 0; i < a.length()/2; i++)
if(a.charAt(i) != a.charAt(a.length()-1-i))
return false;
return true;
}

public static void main(String[] args)
{
String input;
Scanner cin = new Scanner(System.in);
int maxAns;
while(cin.hasNext())
{
input = cin.next();
maxAns = getMax(input);
//System.out.println(maxAns);
BigInteger a = new BigInteger("0");
BigInteger decA = new BigInteger("0");
BigInteger decB = new BigInteger("0");;
String aStr= "", bStr= "", ansStr= "";
BigInteger b = new BigInteger("0");
BigInteger ans = new BigInteger("0");
String checkPal = "";
for(int base = 15; base >= 2; base--)
{

if(base != 15)
System.out.printf(" ");
if(maxAns >= base)
{
System.out.printf("?");
continue;
}
int steps;
if(input.compareTo("0") == 0)
steps = 0;
else
steps = 1;

if(base != 10)
{
a = toDec(input,base);
b = toDec(reverse(input),base);

checkPal = "" + (toBase("" + ans,base));
aStr = "" + checkPal;
bStr = reverse("" + aStr);
decA = toDec(aStr,base);
decB = toDec(bStr,base);
}
else
{
a = new BigInteger(input);
b = new BigInteger(reverse(input));
checkPal = "" + ans;
}
//System.out.println(ans + " " + checkPal);

while(!isPal(checkPal))
{
steps++;
if(steps > 100)
{
steps = 0;
break;
}

if(base != 10)
{
a = decA;
b = decB;
checkPal = toBase("" + ans,base);
aStr = "" + checkPal;
bStr = "" + reverse("" + aStr);
decA = toDec(aStr,base);
decB = toDec(bStr,base);
}
else
{
a = ans;
b = new BigInteger(reverse("" + a));
checkPal = "" + ans;
}
//System.out.println(ans + " " + checkPal);
//checkPal = "" + ans;

}

System.out.printf("%s",steps);

}
System.out.println("");
}
}
}
I'm getting TLE. I don't know which input is making my code TLE. Can someone give a sample input/output?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 290 Palindroms why WA

Java, BigInteger, and Scanner are slow. Try rewriting your code in C++. If you use Java, try BufferedReader and BufferedWriter.
Check input and AC output for thousands of problems on uDebug!

kier.guevara
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

### Re: 290 Palindroms why WA

Thanks brianfry! I rewritten my code in C++ and I got AC now!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 290 Palindroms why WA

I am getting TLE. Can anyone help me to get rid of TLE. Thanks in advance.

Code: Select all

code removed after ac
Last edited by t.tahasin on Wed Jun 26, 2013 12:30 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 290 Palindroms why WA

Input 132, output should be 1 1 1 1 1 1 1 1 1 2 5 4 ? ?
Check input and AC output for thousands of problems on uDebug!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 290 Palindroms why WA

Thank you brianfry713. I changed the code, now I am getting WA.

Code: Select all

code removed after ac.
Last edited by t.tahasin on Wed Jun 26, 2013 12:29 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 290 Palindroms why WA

Input 0
correct output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0
Check input and AC output for thousands of problems on uDebug!