EvbCFfp1XB

problem and my answer.


formula               number
1 1
2! 2
2^2 4
3! 6
2^3 8
10^1 10
2^4 16
4! 24
2^5 32
2^6 64
10^2 100
5! 120
2^7 128
2^8 256
2^9 512
6! 720
10^3 1000
2^10 1024
2^11 2048
2^12 4096
7! 5040
2^13 8192
10^4 10000
2^14 16384
2^15 32768
8! 40320
2^16 65536
10^5 100000
2^17 131072
2^18 262144
9! 362880
2^19 524288
10^6 1000000
2^20 1048576
2^21 2097152
10! 3628800
2^22 4194304
2^23 8388608
10^7 10000000
2^24 16777216
2^25 33554432
11! 39916800
2^26 67108864
10^8 100000000
2^27 134217728
2^28 268435456
12! 479001600
2^29 536870912
10^9 1000000000
2^30 1073741824
2^31 2147483648
2^32 4294967296
13! 6227020800
2^33 8589934592
10^10 10000000000
2^34 17179869184
2^35 34359738368
2^36 68719476736
14! 87178291200
10^11 100000000000
2^37 137438953472
2^38 274877906944
2^39 549755813888
10^12 1000000000000
2^40 1099511627776
15! 1307674368000
2^41 2199023255552
2^42 4398046511104
2^43 8796093022208
10^13 10000000000000
2^44 17592186044416
16! 20922789888000
2^45 35184372088832
2^46 70368744177664
10^14 100000000000000
2^47 140737488355328
2^48 281474976710656
17! 355687428096000
2^49 562949953421312
10^15 1000000000000000
2^50 1125899906842624
2^51 2251799813685248
2^52 4503599627370496
18! 6402373705728000
2^53 9007199254740992
10^16 10000000000000000
2^54 18014398509481984
2^55 36028797018963968
2^56 72057594037927936
10^17 100000000000000000
19! 121645100408832000
2^57 144115188075855872
2^58 288230376151711744
2^59 576460752303423488
10^18 1000000000000000000
2^60 1152921504606846976
2^61 2305843009213693952
20! 2432902008176640000
2^62 4611686018427387904
2^63 9223372036854775808
10^19 10000000000000000000
2^64 18446744073709551616


source code

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class PrintNumbers {
public static void main(String[] args) {
Map<BigInteger, String> map = new HashMap<BigInteger, String>();

BigInteger[] dp = new BigInteger[65];

BigInteger TWO = new BigInteger("2");
dp[0] = BigInteger.ONE;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1].multiply(TWO);
map.put(dp[i], "2^" + i);
}

BigInteger LIMIT = dp[64];

dp[0] = BigInteger.ONE;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1].multiply(BigInteger.TEN);
if (dp[i].compareTo(LIMIT) > 0) {
break;
}
map.put(dp[i], "10^" + i);
}

dp[0] = BigInteger.ONE;
for (int i = 1; i < dp.length; i++) {
dp[i] = dp[i - 1].multiply(new BigInteger("" + i));
if (dp[i].compareTo(LIMIT) > 0) {
break;
}
map.put(dp[i], i + "!");
}

map.put(BigInteger.ONE, "1");

System.out.format("%7s %20s\n", "formula", "number");
for (BigInteger bi : new TreeSet<BigInteger>(map.keySet())) {
System.out.format("%7s %20s\n", map.get(bi), bi);
}
}
}



32768KB = (2^15) * (2^10) B = 2^25 B です。
int(4B) の配列なら、 2^25 / 4 = 2^25 * 2^(-2) = 2^23 = 8388608 まで使えます。
ということでしょうか?

問題 Dice Puzzle

問題の
1つのサイコ ロに同じ文字が複数回描かれていることは無いものとします(同じアルファベットの大文字と小文字は その限りではありません)。
と Sample Input の
zabznq
は矛盾しています。

解き方 深さ優先探索+枝刈りです。


Code

import java.util.Scanner;

public class DicePuzzle {
    public static void main(String[] args) {
        boolean test = true;
        if (test) {
            long start = System.nanoTime();
            {
                String s = solve(new String[] { "zabznq", "BCxmAi", "ZcbBCj",
                        "aizXCm", "QgmABC", "JHzMop", "ImoXGz", "MZTOhp", });
                System.out.print("YES".equals(s) ? "(A)" : "(" + s + ")");
            }
            {
                String s = solve(new String[] { "zabznQ", "BCxmAi", "ZcbBCj",
                        "aizXCm", "QgmABC", "JHzMop", "ImoXGz", "MZTOhp", });
                System.out.print("NO".equals(s) ? "(B)" : "(" + s + ")");
            }
            {
                String s = solve(new String[] { "abcdef", "ABDCFE", "FBDCAE",
                        "abcdef", "BEACDF", "bfcaed", "fabcde", "DEABCF", });
                System.out.print("YES".equals(s) ? "(C)" : "(" + s + ")");
            }
            {
                String s = solve(new String[] { "UnivOf", "AizuaH", "zTXZYW",
                        "piglIt", "GRULNP", "higGth", "uAzIXZ", "FizmKZ", });
                System.out.print("YES".equals(s) ? "(D)" : "(" + s + ")");
            }
            {
                String s = solve(new String[] { "UnivOf", "AizuaH", "piglIt",
                        "higGth", "GRULNP", "uAzIXZ", "FizmKZ", "ZTXZYW", });
                System.out.print("NO".equals(s) ? "(E)" : "(" + s + ")");
            }
            long end = System.nanoTime();
            System.out.print("[" + (end - start) / 1000000000d + "]");
        } else {
            Scanner sc = new Scanner(System.in);
            for (; sc.hasNext();) {
                String line = sc.nextLine();
                if (line.equals("0")) {
                    break;
                }
                String[] dice = new String[8];
                dice[0] = line;
                for (int i = 1; i < dice.length; i++) {
                    dice[i] = sc.nextLine();
                }
                System.out.print(solve(dice) + "\n");
            }
        }
    }

    private static String solve(String[] s) {
        return depthFirstSearch(toChar(s), 0) ? "YES" : "NO";
    }

    /**
     * index<br>
     * upper<br>
     * back {6, 7},<br>
     * front {4, 5},<br>
     * lower<br>
     * back {2, 3},<br>
     * front {0, 1}<br>
     * */
    private static boolean depthFirstSearch(char[][] dice, int index) {
        if (index == 0) {
            for (int face = 0; face <= 5; face++) {
                for (int i = 0; i < 4; i++) {
                    if (depthFirstSearch(dice, index + 1)) {
                        return true;
                    }
                    counterclockwise(dice[index]);
                }
                if (face % 2 == 0) {
                    front(dice[index]);
                } else {
                    left(dice[index]);
                }
            }
        } else if (index == 1 || index == 2 || index == 4) {
            int d0 = 0;
            int f0;
            if (index == 1) {
                f0 = 2;
            } else if (index == 2) {
                f0 = 4;
            } else {
                f0 = 5;
            }
            char c = lowerToUpperOrUpperToLower(dice[d0][f0]);
            for (int i = index; i < dice.length; i++) {
                int face = faceOfChar(dice[i], c);
                if (face != -1) {
                    swap(dice, index, i);
                    rotate(dice[index], face, 5 - f0);
                    for (int j = 0; j < 4; j++) {
                        if (depthFirstSearch(dice, index + 1)) {
                            return true;
                        }
                        if (index == 1) {
                            front(dice[index]);
                        } else if (index == 2) {
                            right(dice[index]);
                        } else {
                            clockwise(dice[index]);
                        }
                    }
                }
            }
        } else if (index == 3 || index == 5 || index == 6) {
            int d0;
            int f0;
            int d1;
            int f1;
            if (index == 3) {
                d0 = 1;
                f0 = 4;
                d1 = 2;
                f1 = 2;
            } else if (index == 5) {
                d0 = 1;
                f0 = 5;
                d1 = 4;
                f1 = 2;
            } else {
                d0 = 2;
                f0 = 5;
                d1 = 4;
                f1 = 4;
            }
            char c0 = lowerToUpperOrUpperToLower(dice[d0][f0]);
            char c1 = lowerToUpperOrUpperToLower(dice[d1][f1]);
            for (int i = index; i < dice.length; i++) {
                int face0 = faceOfChar(dice[i], c0);
                int face1 = faceOfChar(dice[i], c1);
                if (face0 != -1 && face1 != -1) {
                    swap(dice, index, i);
                    rotate(dice[index], face0, 5 - f0);
                    for (int j = 0; j < 4; j++) {
                        if (dice[index][5 - f1] == c1) {
                            if (depthFirstSearch(dice, index + 1)) {
                                return true;
                            }
                        }
                        if (index == 3) {
                            right(dice[index]);
                        } else if (index == 5) {
                            clockwise(dice[index]);
                        } else {
                            clockwise(dice[index]);
                        }
                    }
                }
            }
        } else if (index == 7) {
            char c0 = lowerToUpperOrUpperToLower(dice[3][5]);
            char c1 = lowerToUpperOrUpperToLower(dice[5][4]);
            char c2 = lowerToUpperOrUpperToLower(dice[6][2]);
            {
                int face0 = faceOfChar(dice[index], c0);
                int face1 = faceOfChar(dice[index], c1);
                int face2 = faceOfChar(dice[index], c2);
                if (face0 != -1 && face1 != -1 && face2 != -1) {
                    rotate(dice[index], face0, 5 - 5);
                    for (int j = 0; j < 4; j++) {
                        if (dice[index][5 - 4] == c1
                                && dice[index][5 - 2] == c2) {
                            return true;
                        }
                        clockwise(dice[index]);
                    }
                }
            }
        }
        return false;
    }

    private static void swap(char[][] dice, int i0, int i1) {
        char[] swap = dice[i0];
        dice[i0] = dice[i1];
        dice[i1] = swap;
    }

    private static char lowerToUpperOrUpperToLower(char ch) {
        return Character.isLowerCase(ch) ? Character.toUpperCase(ch)
                : Character.toLowerCase(ch);
    }

    private static int faceOfChar(char[] dice, char c) {
        for (int i = 0; i < dice.length; i++) {
            if (dice[i] == c) {
                return i;
            }
        }
        return -1;
    }

    private static void rotate(char[] dice, int face0, int face1) {
        if (face0 == 0) {
        } else if (face0 == 1) {
            front(dice);
        } else if (face0 == 2) {
            right(dice);
        } else if (face0 == 3) {
            left(dice);
        } else if (face0 == 4) {
            back(dice);
        } else if (face0 == 5) {
            front(dice);
            front(dice);
        }
        if (face1 == 0) {
        } else if (face1 == 1) {
            back(dice);
        } else if (face1 == 2) {
            left(dice);
        } else if (face1 == 3) {
            right(dice);
        } else if (face1 == 4) {
            front(dice);
        } else if (face1 == 5) {
            front(dice);
            front(dice);
        }
    }

    private static void rotate(char[] dice, int[] i) {
        char swap = dice[i[0]];
        dice[i[0]] = dice[i[1]];
        dice[i[1]] = dice[i[2]];
        dice[i[2]] = dice[i[3]];
        dice[i[3]] = swap;
    }

    /** ground plan */
    private static void right(char[] dice) {
        rotate(dice, new int[] { 0, 2, 5, 3 });
    }

    /** ground plan */
    private static void left(char[] dice) {
        rotate(dice, new int[] { 3, 5, 2, 0 });
    }

    /** ground plan */
    private static void front(char[] dice) {
        rotate(dice, new int[] { 1, 5, 4, 0 });
    }

    /** ground plan */
    private static void back(char[] dice) {
        rotate(dice, new int[] { 0, 4, 5, 1 });
    }

    /** ground plan */
    private static void clockwise(char[] dice) {
        rotate(dice, new int[] { 2, 4, 3, 1 });
    }

    /** ground plan */
    private static void counterclockwise(char[] dice) {
        rotate(dice, new int[] { 1, 3, 4, 2 });
    }

    private static char[][] toChar(String[] s) {
        char[][] a = new char[s.length][];
        for (int i = 0; i < a.length; i++) {
            a[i] = s[i].toCharArray();
        }
        return a;
    }
}

このページのトップヘ