nested/Palindrome_Calvin.java

  1 import java.util.ArrayList;
  2 import java.util.Arrays;
  3 import java.util.Scanner;
  4 
  5 public class Palindrome_Calvin {
  6 	
  7 	private static void fold(int l, char[] chars) {
  8 		if (l == 0) {
  9 			return;
 10 		}
 11 		int half = (l - 1)/2;
 12 		for (int i = 0; i < half; ++i) {
 13 			if (chars[i] == '?') {
 14 				chars[i] = chars[i + half + 1];
 15 			}
 16 		}
 17 		fold(half, chars);
 18 	}
 19 	
 20     public static void main(String[] args) {
 21         Scanner in = new Scanner(System.in);
 22         sol:
 23         while (true) {
 24             long k = Long.parseLong(in.nextLine());
 25             if (k == 0) {
 26             	break;
 27             }
 28             --k; //really, first index is not 0?
 29             String t = in.nextLine();
 30             char[] chars = t.toCharArray();
 31             fold(chars.length, chars);
 32             char[] _result = new char[13];
 33             int p = 0;
 34             int c = 0;
 35             while (p < chars.length) {
 36             	_result[c] = chars[p];
 37             	p = p*2 + 1;
 38             	++c;
 39             }
 40             char[] result = new char[c];
 41             long q = 0;
 42             for (int i = 0; i < c; ++i) {
 43             	result[i] = _result[i];
 44             	if (i != 0 && _result[i] == '?') {
 45             		++q;
 46             	}
 47             }
 48             long first = k / power(9, q);
 49             long offset = k % power(9, q);
 50             String s_result = new String(result);
 51         	ArrayList<Character> possibles = new ArrayList<Character>();
 52             if (result[0] == '?') {
 53             	for (int i = 1; i <= 9; i++) {
 54             		if(s_result.indexOf((char) ('0'+i)) == -1) {
 55                 		possibles.add((char) ('0'+i));            			
 56             		}
 57             	}
 58             }
 59             else {
 60             	possibles.add(result[0]);
 61             }
 62             if (first >= possibles.size()) {
 63             	System.out.println(-1);
 64             	continue;
 65             }
 66             
 67             result[0] = possibles.get((int)first);
 68             
 69             String base9 = Long.toString(offset, 9);
 70             while (q > base9.length()) {
 71             	base9 = '0' + base9;
 72             }
 73             int j = 0;
 74             for (int i = 1; i < result.length; ++i) {
 75             	if (result[i] == '?') {
 76             		result[i] = base9.charAt(j);
 77                 	if (result[0] <= result[i]) {
 78                 		++result[i];
 79                 	}
 80                 	++j;
 81             	}
 82             }            
 83             System.out.println(new String(generateSolution(result)));
 84         }
 85         in.close();
 86     }
 87     
 88     static long power(long a, long b) {
 89     	long result = 1;
 90     	for (int i = 0; i < b; ++i) {
 91     		result *= a;
 92     	}
 93     	return result;
 94     }
 95 	
 96 	static char[] generateSolution(char[] a) {
 97 		char[] b = new char[(int) (power(2, a.length) - 1)];
 98 		int pointer = 0;
 99 		for (int i = 0; i < a.length; ++i) {
100 			b[pointer] = a[i];
101 			for (int j = 0; j < pointer; ++j) {
102 				b[pointer + 1 + j] = b[j]; 
103 			}
104 			pointer *= 2;
105 			++pointer;
106 		}
107 		return b;
108 	}
109 
110 }