290 - Palindroms <---> smordnilaP

[Jemerson]

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!

Can anyone explain me, please?

Thanx in advance.

[mf]

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]

When the input is 0, you print 15 0's, but there should be only 14 0's.

[smajdalf.11]

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{
		    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		    String input = br.readLine();
		    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];
				}
				input = br.readLine();
		    }
		    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]

Input:
19

AC output:
1 1 1 1 1 2 ? ? ? ? ? ? ? ?

[gr81]

WA...don't know y ?

Removed Code after AC.

[brianfry713]

You're printing an extra newline at the end of the output.

[gr81]

thanks.

[kier.guevara]

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);
				ans = ans.add(toMul.multiply(bMul));
			}
			else
			{
				BigInteger toMul = new BigInteger(ch);
				ans = ans.add(toMul.multiply(bMul));
			}
		}
		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);
					ans = a.add(b);
					
				  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));
					ans = a.add(b);
					checkPal = "" + ans;
				}
//System.out.println(ans + " " + checkPal);
				
				while(!isPal(checkPal))
				{
					steps++;
					if(steps > 100)
					{
						steps = 0;
						break;
					}
					
					
					if(base != 10)
					{
						a = decA;
						b = decB;
						ans = a.add(b);
						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));
						ans = a.add(b);
						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]

Java, BigInteger, and Scanner are slow. Try rewriting your code in C++. If you use Java, try BufferedReader and BufferedWriter.

[kier.guevara]

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

[t.tahasin]

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

Code: Select all

code removed after ac

[brianfry713]

Input 132, output should be 1 1 1 1 1 1 1 1 1 2 5 4 ? ?

[t.tahasin]

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

Code: Select all

code removed after ac.

[brianfry713]

Input 0
correct output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0