結果

問題 No.5015 Escape from Labyrinth
ユーザー Yu_212Yu_212
提出日時 2023-04-16 16:36:38
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 24,893 bytes
コンパイル時間 5,139 ms
コンパイル使用メモリ 87,492 KB
実行使用メモリ 71,800 KB
スコア 161,710
最終ジャッジ日時 2023-04-16 16:41:38
合計ジャッジ時間 297,505 ms
ジャッジサーバーID
(参考情報)
judge16 / judge15
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,865 ms
70,264 KB
testcase_01 AC 2,848 ms
69,956 KB
testcase_02 AC 2,845 ms
71,708 KB
testcase_03 AC 2,821 ms
70,328 KB
testcase_04 AC 2,809 ms
69,680 KB
testcase_05 AC 2,860 ms
70,172 KB
testcase_06 AC 2,840 ms
69,728 KB
testcase_07 AC 2,830 ms
70,032 KB
testcase_08 AC 2,826 ms
69,964 KB
testcase_09 AC 2,813 ms
70,476 KB
testcase_10 AC 2,864 ms
69,844 KB
testcase_11 AC 2,842 ms
70,588 KB
testcase_12 AC 2,862 ms
69,664 KB
testcase_13 AC 2,836 ms
69,528 KB
testcase_14 AC 2,807 ms
69,348 KB
testcase_15 AC 2,836 ms
70,716 KB
testcase_16 AC 2,878 ms
69,800 KB
testcase_17 AC 2,897 ms
70,176 KB
testcase_18 AC 2,831 ms
69,924 KB
testcase_19 AC 2,817 ms
69,912 KB
testcase_20 AC 2,841 ms
69,656 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 2,845 ms
69,956 KB
testcase_24 AC 2,816 ms
69,944 KB
testcase_25 AC 2,846 ms
69,996 KB
testcase_26 AC 2,854 ms
70,496 KB
testcase_27 AC 2,900 ms
69,988 KB
testcase_28 AC 2,822 ms
69,968 KB
testcase_29 AC 2,830 ms
69,528 KB
testcase_30 AC 2,837 ms
69,868 KB
testcase_31 AC 2,871 ms
69,768 KB
testcase_32 AC 2,877 ms
69,808 KB
testcase_33 AC 2,861 ms
69,636 KB
testcase_34 AC 2,818 ms
69,876 KB
testcase_35 AC 2,889 ms
69,700 KB
testcase_36 AC 2,835 ms
70,036 KB
testcase_37 WA -
testcase_38 AC 2,864 ms
70,000 KB
testcase_39 AC 2,820 ms
70,116 KB
testcase_40 AC 2,846 ms
69,992 KB
testcase_41 AC 2,848 ms
70,548 KB
testcase_42 AC 2,852 ms
69,852 KB
testcase_43 AC 2,822 ms
69,628 KB
testcase_44 AC 2,823 ms
69,524 KB
testcase_45 AC 2,851 ms
70,536 KB
testcase_46 AC 2,858 ms
69,768 KB
testcase_47 AC 2,858 ms
69,860 KB
testcase_48 AC 2,822 ms
69,680 KB
testcase_49 AC 2,833 ms
70,492 KB
testcase_50 AC 2,850 ms
69,820 KB
testcase_51 AC 2,841 ms
69,880 KB
testcase_52 AC 2,823 ms
69,956 KB
testcase_53 AC 2,862 ms
69,500 KB
testcase_54 WA -
testcase_55 AC 2,860 ms
70,188 KB
testcase_56 AC 2,916 ms
70,248 KB
testcase_57 AC 2,839 ms
70,440 KB
testcase_58 WA -
testcase_59 AC 2,836 ms
69,604 KB
testcase_60 AC 2,842 ms
70,124 KB
testcase_61 AC 2,833 ms
69,472 KB
testcase_62 AC 2,836 ms
70,020 KB
testcase_63 WA -
testcase_64 AC 2,855 ms
69,916 KB
testcase_65 AC 2,887 ms
69,716 KB
testcase_66 AC 2,849 ms
70,464 KB
testcase_67 AC 2,828 ms
70,192 KB
testcase_68 AC 2,828 ms
70,128 KB
testcase_69 AC 2,858 ms
70,036 KB
testcase_70 AC 2,887 ms
69,960 KB
testcase_71 AC 2,869 ms
69,980 KB
testcase_72 WA -
testcase_73 AC 2,831 ms
70,220 KB
testcase_74 AC 2,812 ms
69,796 KB
testcase_75 AC 2,853 ms
69,972 KB
testcase_76 AC 2,874 ms
70,200 KB
testcase_77 AC 2,851 ms
70,312 KB
testcase_78 AC 2,846 ms
69,476 KB
testcase_79 AC 2,842 ms
69,480 KB
testcase_80 AC 2,839 ms
70,308 KB
testcase_81 AC 2,839 ms
69,924 KB
testcase_82 AC 2,851 ms
70,388 KB
testcase_83 WA -
testcase_84 AC 2,853 ms
69,680 KB
testcase_85 AC 2,929 ms
68,352 KB
testcase_86 AC 2,861 ms
70,144 KB
testcase_87 AC 2,859 ms
69,756 KB
testcase_88 AC 2,837 ms
69,976 KB
testcase_89 AC 2,828 ms
69,560 KB
testcase_90 AC 2,858 ms
69,644 KB
testcase_91 AC 2,843 ms
70,340 KB
testcase_92 WA -
testcase_93 AC 2,848 ms
71,800 KB
testcase_94 AC 2,832 ms
70,308 KB
testcase_95 AC 2,893 ms
70,060 KB
testcase_96 AC 2,866 ms
70,056 KB
testcase_97 AC 2,837 ms
70,432 KB
testcase_98 AC 2,883 ms
70,156 KB
testcase_99 AC 2,826 ms
70,260 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;

public class Main {
    static boolean isLocal;
    Random rand = new Random();
    In in = new In(System.in);
    PrintStream out = System.out;
    long inf = 0x1fffffffffffffffL;
    int iinf = 0x3fffffff;
    long startTime;

    public static final int N = 60;
    public int D;
    public static final int H = 1500;
    public int M;
    public int J;
    public char[] grid;
    public Pos[] ps;
    public int[] ds;
    public Pos[] jps;
    int[][] distances;
    boolean[][] beam = new boolean[60][N * N];
    int[] avgWait = new int[N * N];
    int[] jid = new int[N * N];
    public static final String[] ss = {"M L", "M U", "M R", "M D", "S"};
    long solve(int seed) {
        startTime = System.currentTimeMillis();
        in();
        distances = new int[J+3][J+3];
        for (int i = 0; i < J + 3; i++) {
            Arrays.fill(distances[i], iinf);
        }
        for (int i = 0; i < M; i++) {
            for (int d = 0; d < 4; d++) {
                Pos cur = ps[i];
                while (true) {
                    cur = cur.moved((d+2)%4);
                    if (cur == null || grid[cur.z] == '#') {
                        break;
                    }
                    for (int j = 0; j < 60; j += ds[i]) {
                        beam[j][cur.z] = true;
                    }
                }
            }
        }
        for (int i = 0; i < N * N; i++) {
            int c = 1;
            for (int j = 0; j < 60; j++) {
                if (beam[j][i]) {
                    c++;
                } else {
                    c = 1;
                }
                avgWait[i] += c;
            }
        }
        for (int i = 0; i < J + 3; i++) {
            calcDist(i);
        }
//        BitSet visited = new BitSet(J + 3);
//        visited.set(J);
//        visited.set(J + 1);
//        visited.set(J + 2);
//        List<Integer> routes = new ArrayList<>();
//        routes.add(J);
//        routes.add(J + 1);
//        routes.add(J + 2);
//        int dsum = distances[J][J+1] + distances[J+1][J+2];
//        int c = 0;
//        while (elapsed() < 2000) {
//            int p;
//            do {
//                p = rand.next(0, J);
//            } while (visited.get(p));
//            int bi = -1;
//            int bd = iinf;
//            for (int i = 1; i < routes.size(); i++) {
//                int f = routes.get(i - 1);
//                int t = routes.get(i);
//                int diff = distances[f][p] + distances[p][t] - distances[f][t];
//                if (bd > diff) {
//                    bd = diff;
//                    bi = i;
//                }
//            }
//            if (bi == -1) {
//                continue;
//            }
////            debug(p, bi, bd, dsum);
//            if (routes.size() >= 200) {
//                break;
//            }
////            if (dsum + bd * MUL[D] >= 60 * 500) {
//////                c++;
//////                if (c >= 100) {
//////                    break;
//////                } else {
//////                    continue;
//////                }
////                continue;
////            }
//            visited.set(p);
//            dsum += bd;
//            routes.add(bi, p);
//        }

        debug("?", elapsed());
        State result = annealing(new State(), 180*10, 180, 2500);
        List<Integer> routes = result.routes;
        debug("?", elapsed());

        Pos p = jps[J];
        int tt = 0;
        int ds1 = 0;
        int ds2 = 0;
        for (int i = 1; i < routes.size(); i++) {
            Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt);
//            debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60);
            ds1 += distances[routes.get(i - 1)][routes.get(i)];
            ds2 += res.damage;
//            debug(p, res.from, res.to);
            res.out(p, tt);
            tt = (tt + res.time) % 60;
            p = res.to;
        }
        debug(D, result.dsum, ds1, result.dsum/60, ds1/60, ds2, ds2*60./result.dsum);
        if (ds2 > 1400) {
            debug("!");
            throw new RuntimeException();
        }
        debug(ds2, totalCost, routes.size() * 10);
        return routes.size() * 10L;
//        List<Result> routes = new ArrayList<>();
//        routes.add(route(jps[J], jps[J + 1], 0));
//        routes.add(route(jps[J + 1], jps[J + 2], routes.get(0).time));
//        int dsum = routes.get(0).damage + routes.get(1).damage;
//        while (true) {
//            int p;
//            do {
//                p = rand.next(0, J);
//            } while (visited.get(p));
//            int tt = 0;
//            int bi = 0;
//            int bd = iinf;
//            Result br1 = null, br2 = null;
//            for (int i = 0; i < routes.size(); i++) {
//                Result r = routes.get(i);
//                Result r1 = route(r.from, jps[p], tt);
//                Result r2 = route(jps[p], r.to, (tt + r.time) % 60);
//                int diff = r1.damage + r2.damage - r.damage;
//                if (bd > diff) {
//                    bd = diff;
//                    bi = i;
//                    br1 = r1;
//                    br2 = r2;
//                }
//                tt = (tt + r.time) % 60;
//            }
//            debug(p, bi, bd, dsum);
//            if (dsum + bd >= 700) {
//                break;
//            }
//            visited.set(p);
//            dsum += bd;
//            routes.set(bi, br1);
//            routes.add(bi + 1, br2);
//        }
//        Pos p = jps[J];
//        int tt = 0;
//        for (Result res : routes) {
//            debug(p, res.from, res.to);
//            res.out(p, tt);
//            tt = (tt + res.time) % 60;
//            p = res.to;
//        }
//        visited.set(J + 2);
//        visited.set(J);
//        tt = moveTo(J, J+1, tt, visited);
//        visited.clear(J + 2);
//        tt = moveTo(J+1, J+2, tt, visited);
    }

    int totalCost = 0;
//    int moveTo(int s, int g, int tt, BitSet visited) {
//        int cur = s;
//        int ds = 0;
//        while (cur != g) {
//            int md = iinf;
//            int mi = -1;
//            for (int i = 0; i < J + 3; i++) {
//                if (visited.get(i)) {
//                    continue;
//                }
////                debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]);
//                int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50;
//                if (md > d) {
//                    md = d;
//                    mi = i;
//                }
//            }
//            ds += distances[cur * (J + 3) + mi];
//            visited.set(mi);
//            tt = moveStraight(cur, mi, tt);
//            cur = mi;
//        }
//        debug(ds, totalCost);
//        return tt;
//    }


    public static final double[] MUL = {0, 0, 0, 1.25, 1.33, 1.4, 1.6, 1.8};
    class State {
        BitSet visited = new BitSet(J + 3);
        List<Integer> routes = new ArrayList<>();
        int dsum;
        double score;
        boolean hasScore;
        State prevCopy;

        State() {
            visited.set(J);
            visited.set(J + 1);
            visited.set(J + 2);
            routes.add(J);
            routes.add(J + 1);
            routes.add(J + 2);
            dsum = distances[J][J+1] + distances[J+1][J+2];
        }

        State(State prev) {
            this.visited = (BitSet)prev.visited.clone();
            this.routes = new ArrayList<>(prev.routes);
            this.dsum = prev.dsum;
            this.score = prev.score;
            this.hasScore = true;
        }

        State rollback() {
            return prevCopy;
        }

        int neighbor0(double stage) {
            while (true) {
                int p;
                do {
                    p = rand.next(0, J);
                } while (visited.get(p));
                int bi = -1;
                int bd = iinf;
                for (int i = 1; i < routes.size(); i++) {
                    int f = routes.get(i - 1);
                    int t = routes.get(i);
                    int diff = distances[f][p] + distances[p][t] - distances[f][t];
                    if (bd > diff) {
                        bd = diff;
                        bi = i;
                    }
                }
                if (bi == -1) {
                    continue;
                }
                visited.set(p);
                dsum += bd;
                routes.add(bi, p);
                score = calcScore(0);
                break;
            }
            return 0;
        }

        int neighbor1(double stage) {
            int bd = -iinf;
            int bp = 0;
            for (int p = 1; p + 1 < routes.size(); p++) {
                int f = routes.get(p - 1);
                int t = routes.get(p + 1);
                int r = routes.get(p);
                if (r >= J) {
                    continue;
                }
                int diff = distances[f][r] + distances[r][t] - distances[f][t];
                if (bd < diff) {
                    bd = diff;
                    bp = p;
                }
            }
            visited.clear(routes.get(bp));
            dsum -= bd;
            routes.remove(bp);
            score = calcScore(0);
            return 1;
        }

        int neighbor(double stage) {
            hasScore = false;
            prevCopy = copy();
            if (routes.size() >= 60 && rand.next(3) == 0 || dsum * MUL[D] >= 60 * 1100) {
//                debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 1);
                return neighbor1(stage);
            } else {
//                debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 0);
                return neighbor0(stage);
            }
        }

        State copy() {
            return new State(this);
        }

        double getScore(double stage) {
            if (!hasScore) {
                score = calcScore(stage);
                hasScore = true;
            }
            return score;
        }

        double calcScore(double stage) {
            double score = (routes.size() - 3) * 1800 - dsum * MUL[D];
            return score;
        }

        long realScore() {
            int score = 0;
            return score;
        }
    }

    State annealing(State state, double startTemp, double endTemp, long timeLimit) {
        State bestState = state.copy();
        double bestScore = state.getScore(0);
        int itr = 0;
        int rb = 0;
        int c0 = 0;
        while (true) {
            long nowTime = System.currentTimeMillis() - startTime;
            if (nowTime >= timeLimit) {
                break;
            }
            itr++;
            double stage = (double)nowTime / timeLimit;
            double prevScore = state.getScore(stage);
            double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit;
            double thres = prevScore + rand.nextLog() * temp;
            int nid = state.neighbor(stage);
            if (nid == -1) {
                continue;
            }
            if (nid == 0) {
                c0++;
            }
            if (bestScore < state.getScore(stage)) {
                bestScore = state.getScore(stage);
                bestState = state.copy();
            }
            if (state.getScore(stage) <= thres) {
                state = state.rollback();
                rb++;
            }
        }
        debug(itr, rb, c0);
        return bestState;
    }
    
    class Result {
        List<Integer> route;
        int damage;
        int time;
        Pos from;
        Pos to;

        public Result(List<Integer> route, int damage, Pos from, Pos to) {
            this.route = route;
            this.damage = damage;
            this.time = route.size() % 60;
            this.from = from;
            this.to = to;
        }

        public void out(Pos p, int tt) {
            for (int v : route) {
                if (v < 4) p = p.moved(v);
                tt = (tt + 1) % 60;
                if (beam[tt][p.z]) {
                    totalCost += D;
                }
                totalCost++;
                out.println(ss[v]);
            }
        }
    }
    Result route(Pos s, Pos g, int tt) {
        class S {
            private final Pos p;
            private final int t;
            private final int d;

            public S(Pos p, int t, int d) {
                this.p = p;
                this.t = t;
                this.d = d;
            }
        }
        PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
        queue.add(new S(s, tt, 0));
        int[][] dist = new int[60][N * N];
        int[][] prev = new int[60][N * N];
        for (int i = 0; i < 60; i++) {
            Arrays.fill(dist[i], iinf);
            Arrays.fill(prev[i], -1);
        }
        dist[tt][s.z] = 0;
        while (!queue.isEmpty()) {
            S v = queue.remove();
            if (dist[v.t][v.p.z] < v.d) {
                continue;
            }
            if (v.p.z == g.z) {
                List<Integer> route = new ArrayList<>();
                Pos cur = v.p;
                int ct = v.t;
                int damage = dist[ct][cur.z];
                while (prev[ct][cur.z] != -1) {
                    route.add(prev[ct][cur.z]);
                    if (prev[ct][cur.z] < 4) {
                        cur = cur.moved((prev[ct][cur.z] + 2) % 4);
                    }
                    ct = (ct + 59) % 60;
                }
                Collections.reverse(route);
                return new Result(route, damage, s, g);
            }
            int nt = (v.t + 1) % 60;
            for (int d = 0; d < 4; d++) {
                Pos q = v.p.moved(d);
                if (q == null || grid[q.z] == '#') {
                    continue;
                }
                int cost = dist[v.t][v.p.z] + 1 + (beam[nt][q.z] ? D : 0);
                if (dist[nt][q.z] > cost) {
                    dist[nt][q.z] = cost;
                    prev[nt][q.z] = d;
                    queue.add(new S(q, nt, cost));
                }
            }
            int cost = dist[v.t][v.p.z] + 1 + (beam[nt][v.p.z] ? D : 0);
            if (dist[nt][v.p.z] > cost) {
                dist[nt][v.p.z] = cost;
                prev[nt][v.p.z] = 4;
                queue.add(new S(v.p, nt, cost));
            }
        }
        throw new RuntimeException();
    }

    void calcDist(int s) {
        class S {
            private final Pos p;
            private final int d;

            public S(Pos p, int d) {
                this.p = p;
                this.d = d;
            }
        }
        PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
        queue.add(new S(jps[s], 0));
        int[] dist = new int[N * N];
        Arrays.fill(dist, iinf);
        dist[jps[s].z] = 0;
        while (!queue.isEmpty()) {
            S v = queue.remove();
            if (dist[v.p.z] < v.d) {
                continue;
            }
            if (jid[v.p.z] != -1) {
                distances[s][jid[v.p.z]] = v.d;
            }
            for (int d = 0; d < 4; d++) {
                Pos q = v.p.moved(d);
                if (q == null || grid[q.z] == '#') {
                    continue;
                }
                int cost = dist[v.p.z] + avgWait[q.z];
                if (dist[q.z] > cost) {
                    dist[q.z] = cost;
                    queue.add(new S(q, cost));
                }
            }
        }
    }

    void in() {
        in.nextInt();
        D = in.nextInt();
        in.nextInt();
        grid = new char[N * N];
        int jc = 0;
        for (int i = 0; i < N; i++) {
            char[] s = in.nextCharArray();
            for (int j = 0; j < N; j++) {
                grid[i * N + j] = s[j];
                if (grid[i * N + j] == 'J') {
                    jc++;
                }
            }
        }
        M = in.nextInt();
        J = jc;
        jps = new Pos[J + 3];
        ps = new Pos[M];
        ds = new int[M];
        for (int i = 0; i < M; i++) {
            int y = in.nextInt();
            int x = in.nextInt();
            int d = in.nextInt();
            ps[i] = pos(x, y);
            ds[i] = d;
        }
        jc = 0;
        Arrays.fill(jid, -1);
        for (int i = 0; i < N * N; i++) {
            if (grid[i] == 'S') {
                jps[J] = pos(i);
                jid[i] = J;
                grid[i] = '.';
            } else if (grid[i] == 'K') {
                jps[J + 1] = pos(i);
                jid[i] = J + 1;
                grid[i] = '.';
            } else if (grid[i] == 'G') {
                jps[J + 2] = pos(i);
                jid[i] = J + 2;
                grid[i] = '.';
            } else if (grid[i] == 'J') {
                jid[i] = jc;
                jps[jc++] = pos(i);
            } else if (grid[i] == 'E') {
                grid[i] = '#';
            }
        }
    }

    static Pos pos(int x, int y) {
        return Pos.instances[y * N + x];
    }

    static Pos pos(int z) {
        return Pos.instances[z];
    }

    static class Timing {
        Pos p;
        int t, z;

        public Timing(Pos p, int t) {
            this.p = p;
            this.t = t;
            this.z = p.z * 60 + t;
        }
    }

    static class Pos implements Comparable<Pos> {
        static Pos[] instances;
        static Pos[] moved;
        static {
            instances = new Pos[N * N];
            moved = new Pos[4 * N * N];
            for (int i = 0; i < N * N; i++) {
                instances[i] = new Pos(i % N, i / N, i);
            }
            for (int i = 0; i < N * N; i++) {
                for (int d = 0; d < 4; d++) { // LURD
                    int nx = i % N + (d - 1) % 2;
                    int ny = i / N + (d - 2) % 2;
                    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                        moved[i * 4 + d] = instances[ny * N + nx];
                    }
                }
            }
        }

        final int x, y, z;

        private Pos(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        Pos moved(int d) {
            return moved[z * 4 + d];
        }

        int dist(Pos o) {
            return Math.abs(x - o.x) + Math.abs(y - o.y);
        }

        Pos[] neighbors() {
            Pos[] p = new Pos[4];
            int i = 0;
            if ((p[i] = moved(0)) != null) i++;
            if ((p[i] = moved(1)) != null) i++;
            if ((p[i] = moved(2)) != null) i++;
            if ((p[i] = moved(3)) != null) i++;
            return i == 4 ? p : Arrays.copyOf(p, i);
        }

        @Override
        public int compareTo(Pos o) {
            return Integer.compare(z, o.z);
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Pos && z == ((Pos)o).z;
        }

        @Override
        public int hashCode() {
            return z;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    static void debug(Object... args) {
        if (!isLocal) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        System.err.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return clazz == byte[].class ? Arrays.toString((byte[])obj) :
                   clazz == short[].class ? Arrays.toString((short[])obj) :
                   clazz == int[].class ? Arrays.toString((int[])obj) :
                   clazz == long[].class ? Arrays.toString((long[])obj) :
                   clazz == char[].class ? Arrays.toString((char[])obj) :
                   clazz == float[].class ? Arrays.toString((float[])obj) :
                   clazz == double[].class ? Arrays.toString((double[])obj) :
                   clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
                   obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
                   String.valueOf(obj);
        }).collect(Collectors.joining(" ")));
    }

    long elapsed() {
        return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));
    }

    boolean elapsed(long timeLimit) {
        return elapsed() >= timeLimit;
    }

    public static void main(String[] args) {
        new Main().solve(0);
    }

    static class Random {
        private long a, b, c, d;

        Random() {
            this(ThreadLocalRandom.current().nextLong());
        }

        Random(long seed) {
            this.a = seed;
            for (int i = 0; i < 20; i++) {
                rand();
            }
        }

        private int rand() {
            long t = a ^ (a << 11);
            a = b;
            b = c;
            c = d;
            d = d ^ (d >>> 19) ^ t ^ (t >>> 8);
            return (int)(a & 0x7fffffff);
        }

        long next() {
            return (long)rand() << 31 | rand();
        }

        int next(int n) {
            return rand() % n;
        }

        int next(int l, int r) {
            return rand() % (r - l) + l;
        }

        double nextDouble() {
            return rand() / 2147483648.0;
        }

        double nextLog() {
            return Math.log(rand() + 1) - 21.487562597358306;
        }
    }

    static class In {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        In(InputStream input) {
            this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);
        }

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char[] nextCharArray() {
            return next().toCharArray();
        }

        String[] nextStringArray(int n) {
            String[] s = new String[n];
            for (int i = 0; i < n; i++) {
                s[i] = next();
            }
            return s;
        }

        char[][] nextCharGrid(int n, int m) {
            char[][] a = new char[n][m];
            for (int i = 0; i < n; i++) {
                a[i] = next().toCharArray();
            }
            return a;
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        int[] nextIntArray(int n, IntUnaryOperator op) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsInt(nextInt());
            }
            return a;
        }

        int[][] nextIntMatrix(int h, int w) {
            int[][] a = new int[h][w];
            for (int i = 0; i < h; i++) {
                a[i] = nextIntArray(w);
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }

        long[] nextLongArray(int n, LongUnaryOperator op) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsLong(nextLong());
            }
            return a;
        }

        long[][] nextLongMatrix(int h, int w) {
            long[][] a = new long[h][w];
            for (int i = 0; i < h; i++) {
                a[i] = nextLongArray(w);
            }
            return a;
        }

        List<List<Integer>> nextEdges(int n, int m, boolean directed) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                res.add(new ArrayList<>());
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                res.get(u).add(v);
                if (!directed) {
                    res.get(v).add(u);
                }
            }
            return res;
        }
    }
}
0