nested/NPAL_Yan.java

  1 import java.util.ArrayList;
  2 import java.util.Scanner;
  3 
  4 public class NPAL_Yan {
  5 
  6     private static boolean nestedPalindrome(int r, char[] chars) {
  7         if (r == 0) return true;
  8         if ((r + 1) % 2 == 0) return false;
  9 
 10         for (int i = 0, j = r; i <= j; i++, j--) {
 11             if (chars[i]==chars[j])continue;
 12             if (chars[i] != '?' && chars[j] != '?') return false;
 13             if (chars[i] == '?') chars[i]=chars[j];
 14             if (chars[j] == '?') chars[j]=chars[i];
 15         }
 16 
 17         return nestedPalindrome(r / 2 - 1, chars);
 18     }
 19 
 20     public static void main(String[] args) {
 21         Scanner scanner = new Scanner(System.in);
 22         //int t = scanner.nextInt();
 23 
 24         while (true) {
 25             long k = scanner.nextLong();
 26             if(k==0)break;
 27 
 28             k--;
 29 
 30             scanner.nextLine();
 31             String s = scanner.nextLine();
 32             char[] chars = s.toCharArray();
 33 
 34             if (!nestedPalindrome(s.length() - 1, chars)) {
 35                 System.out.println("-1");
 36                 continue;
 37             }
 38 
 39             if (chars[0] == '0') {
 40                 System.out.println("-1");
 41                 continue;
 42             }
 43 
 44             String gen = "" + chars[0];
 45             boolean bad = false;
 46             int free = 0;
 47             for (int i = 2; i <= s.length(); i *= 2) {
 48                 gen += chars[i - 1];
 49                 if (chars[0] != '?' && chars[0] == chars[i - 1]) bad = true;
 50                 if (chars[i - 1] == '?') free++;
 51             }
 52 
 53             if (bad) {
 54                 System.out.println("impossible");
 55                 continue;
 56             }
 57 
 58             long seg = k / (long) Math.pow(9.0, free);
 59             long off = k % (long) Math.pow(9.0, free);
 60 
 61             ArrayList<Character> characters = new ArrayList<Character>();
 62             if (chars[0] != '?') {
 63                 characters.add(chars[0]);
 64             } else {
 65                 for (int c = '1'; c <= '9'; c++) {
 66                     if (gen.indexOf(c) == -1) {
 67                         characters.add((char) c);
 68                     }
 69                 }
 70             }
 71 
 72             if (seg + 1 > characters.size()) {
 73                 System.out.println("-1");
 74                 continue;
 75             }
 76 
 77             String off_9 = Long.toString(off, 9);
 78             while (free > off_9.length()) off_9 = '0' + off_9;
 79             chars[0] = characters.get((int)seg);
 80             for (int i = 2, j = 0; i <= s.length(); i *= 2) {
 81                 if (chars[i - 1] == '?') {
 82                     chars[i - 1] = off_9.charAt(j);
 83                     if (chars[0] <= chars[i - 1]) {
 84                         chars[i - 1]++;
 85                     }
 86                     j++;
 87                 }
 88             }
 89 
 90             for (int i = 1; i <= s.length(); i *= 2) {
 91                 for (int j = i; j <= s.length(); j += 2 * i) {
 92                     chars[j - 1] = chars[i - 1];
 93                 }
 94             }
 95 
 96             System.out.println(String.valueOf(chars));
 97         }
 98 //        System.out.println( Hello World! );
 99     }
100 }