結果

問題 No.62 リベリオン(Extra)
ユーザー atn112323
提出日時 2016-02-11 20:28:21
言語 Java
(openjdk 23)
結果
AC  
実行時間 402 ms / 5,000 ms
コード長 13,496 bytes
コンパイル時間 2,939 ms
コンパイル使用メモリ 88,616 KB
実行使用メモリ 58,100 KB
最終ジャッジ日時 2024-09-22 00:53:19
合計ジャッジ時間 4,418 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    /**
     * This class represents a problem setting.
     */
    class Problem implements IProblem {
        int Q;
        int[][] WHDMXMYHXHYVXVY;
        
        @Override
        public void set(ProblemReader reader) throws IOException {
            Q = reader.nextInt();
            WHDMXMYHXHYVXVY = reader.nextIntArray2(Q);
        }
        
        @Override
        public String toString() {
            // TODO
            return null;
        }
    }
    
    /**
     * Solver for the problem.
     * It's the most important part of codes in this file.
     */
    class Solver implements IProblemSolver<Problem> {
        @Override
        public String solve(Problem problem) {
            int Q = problem.Q;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < Q; i++) {
                int W = problem.WHDMXMYHXHYVXVY[i][0], H = problem.WHDMXMYHXHYVXVY[i][1], D = problem.WHDMXMYHXHYVXVY[i][2];
                int MX = problem.WHDMXMYHXHYVXVY[i][3], MY = problem.WHDMXMYHXHYVXVY[i][4];
                int HX = problem.WHDMXMYHXHYVXVY[i][5], HY = problem.WHDMXMYHXHYVXVY[i][6];
                int VX = problem.WHDMXMYHXHYVXVY[i][7], VY = problem.WHDMXMYHXHYVXVY[i][8];
                if (solve(W, H, D, MX, MY, HX, HY, VX, VY)) {
                    sb.append("Hit\n");
                } else {
                    sb.append("Miss\n");
                }
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
        
        private boolean solve(long W, long H, long D, long MX, long MY, long HX, long HY, long VX, long VY) {
            if (VX < 0) {
                MX = W - MX;
                HX = W - HX;
                VX = -VX;
            }
            if (VY < 0) {
                MY = H - MY;
                HY = H - HY;
                VY = -VY;
            }
            long gcd = gcd(VX, VY);
            VX /= gcd;
            VY /= gcd;
            long[][] ps = new long[][]{
                {MX - HX, MY - HY},
                {MX - HX, 2 * H - MY - HY},
                {2 * W - MX - HX, MY - HY},
                {2 * W - MX - HX, 2 * H - MY - HY}
            };
            for (int i = 0; i < ps.length; i++) {
                long c1 = ps[i][0], c2 = ps[i][1];
                if (c1 < 0) {
                    c1 += 2 * W;
                }
                if (c2 < 0) {
                    c2 += 2 * H;
                }
                long t1 = minFactor(VX, 2 * W, c1);
                long t2 = minFactor(VY, 2 * H, c2);
                if (t1 == -1 || t2 == -1) {
                    continue;
                } else if (t1 == t2) {
                    if (t1 <= gcd * (long)D) {
                        return true;
                    }
                } else {
                    long d1 = 2 * W / gcd(2 * W, VX);
                    long d2 = 2 * H / gcd(2 * H, VY);
                    long t = minFactor(d1, d2, t2 - t1);
                    if (t >= 0 && t1 + d1 * t <= gcd * (long)D) {
                        return true;
                    }
                }
            }
            return false;
        }
        
        private long minFactor(long a, long b, long c) {
            long[] xy = new long[2];
            if (extgcd(a, b, c, xy)) {
                long d = b / gcd(a, b);
                if (xy[0] < 0) {
                    return xy[0] + ((-xy[0] - 1) / d + 1) * d;
                } else {
                    return xy[0] % d;
                }
            }
            return -1;
        }
        
        private long gcd(long a, long b) {
            if (a == 0) {
                return b;
            }
            return gcd(b % a, a);
        }
        
        private boolean extgcd(long a, long b, long c, long[] xy) {
            if (a == 0) {
                if (c % b == 0) {
                    xy[0] = 0;
                    xy[1] = c / b;
                    return true;
                } else {
                    xy[0] = -1;
                    xy[1] = -1;
                    return false;
                }
            } else {
                if (extgcd(b % a, a, c, xy)) {
                    long tmp = xy[0];
                    xy[0] = xy[1] - (b / a) * xy[0];
                    xy[1] = tmp;
                    return true;
                } else {
                    return false;
                }
            }
        }
    }
    
    /**
     * This class is a solver to confirm the main solver.
     * This solver often works only for a problem with a small number setting.
     */
    class Solver2 implements IProblemSolver<Problem> {
        @Override
        public String solve(Problem problem) {
            // TODO
            return null;
        }
    }
    
    class Factory implements IProblemFactory<Problem> {
        @Override
        public Problem newProblem() {
            // TODO
            return null;
        }
        @Override
        public Problem newProblem(ProblemReader reader) throws IOException {
            Problem problem = new Problem();
            problem.set(reader);
            return problem;
        }
    }
    
    ProblemProcessor<Problem> processor;
    
    Main() {
        Init();
    }
    
    void Init() {
        ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>();
        
        config.factory = new Factory();
        config.solver = new Solver();
        config.solver2 = new Solver2();
        
        processor = new ProblemProcessor<Problem>(config);
    }
    
    void process(String mode) throws IOException {
        processor.process(mode);
    }
    
    public static void main(String args[]) throws IOException {
        String mode = "solve";
        new Main().process(mode);
    }
    
/*
    Common library
*/
    
    interface IProblem {
        
        abstract void set(ProblemReader reader) throws IOException;
    }
    
    interface IProblemFactory<P extends IProblem> {
        
        abstract P newProblem();
        abstract P newProblem(ProblemReader reader) throws IOException;
    }
    
    interface IProblemSolver<P extends IProblem> {
        
        abstract String solve(P problem);
    }
    
    class ProblemReader {
        
        BufferedReader br = null;
        
        ProblemReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        int nextInt() throws IOException {
            return StringUtils.toInt(br.readLine());
        }
        
        long nextLong() throws IOException {
            return StringUtils.toLong(br.readLine());
        }
        
        double nextDouble() throws IOException {
            return StringUtils.toDouble(br.readLine());
        }
        
        String nextString() throws IOException {
            return br.readLine();
        }
        
        int[] nextIntArray() throws IOException {
            return StringUtils.toIntArray(br.readLine());
        }
        
        long[] nextLongArray() throws IOException {
            return StringUtils.toLongArray(br.readLine());
        }
        
        double[] nextDoubleArray() throws IOException {
            return StringUtils.toDoubleArray(br.readLine());
        }
        
        String[] nextStringArray() throws IOException {
            return StringUtils.toStringArray(br.readLine());
        }
        
        int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }
        
        long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }
        
        double[] nextDoubleArray(int n) throws IOException {
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextDouble();
            }
            return a;
        }
        
        String[] nextStringArray(int n) throws IOException {
            String[] strs = new String[n];
            for (int i = 0; i < n; i++) {
                strs[i] = nextString();
            }
            return strs;
        }
        
        int[][] nextIntArray2(int n) throws IOException {
            int[][] a = new int[n][];
            for (int i = 0; i < n; i++) {
                a[i] = nextIntArray();
            }
            return a;
        }
        
        long[][] nextLongArray2(int n) throws IOException {
            long[][] a = new long[n][];
            for (int i = 0; i < n; i++) {
                a[i] = nextLongArray();
            }
            return a;
        }
        
        double[][] nextDoubleArray2(int n) throws IOException {
            double[][] a = new double[n][];
            for (int i = 0; i < n; i++) {
                a[i] = nextDoubleArray();
            }
            return a;
        }
        
        String[][] nextStringArray2(int n) throws IOException {
            String[][] strs = new String[n][];
            for (int i = 0; i < n; i++) {
                strs[i] = nextStringArray();
            }
            return strs;
        }
        
        void close() throws IOException {
            if (br != null) {
                br.close();
            }
        }
    }
    
    class ProblemCreator<P extends IProblem> {
        
        IProblemFactory<P> factory;
        
        ProblemCreator(IProblemFactory<P> factory) {
            this.factory = factory;
        }
        
        void create() throws FileNotFoundException {
            P problem = factory.newProblem();
            System.out.println(problem.toString());
        }
    }
    
    class ProblemSolverComparator<P extends IProblem> {
        
        IProblemFactory<P> factory;
        IProblemSolver<P> solver1, solver2;
        
        ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2) {
            this.factory = factory;
            this.solver1 = solver1;
            this.solver2 = solver2;
        }
        
        void compare() throws IOException {
            ProblemReader reader = null;
            try {
                reader = new ProblemReader();
                P problem = factory.newProblem(reader);
                String res1 = solver1.solve(problem);
                String res2 = solver2.solve(problem);
                if (res1.equals(res2)) {
                    System.out.println(res1);
                } else {
                    System.err.println(res1 + " " + res2);
                }
            } finally {
                if (reader != null) {
                    reader.close();
                }
            }
        }
    }
    
    class ProblemAnswerer<P extends IProblem> {
        
        IProblemFactory<P> factory;
        IProblemSolver<P> solver;
        
        ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) {
            this.factory = factory;
            this.solver = solver;
        }
        
        void answer() throws IOException {
            ProblemReader reader = null;
            try {
                reader = new ProblemReader();
                P problem = factory.newProblem(reader);
                String res = solver.solve(problem);
                System.out.println(res);
            } finally {
                if (reader != null) {
                    reader.close();
                }
            }
        }
    }
    
    class ProblemProcessorConfig<P extends IProblem> {
        
        IProblemFactory<P> factory;
        
        IProblemSolver<P> solver, solver2;
    }
    
    class ProblemProcessor<P extends IProblem> {
        
        ProblemProcessorConfig<P> config;
        
        ProblemCreator<P> creator;
        ProblemSolverComparator<P> comparator;
        ProblemAnswerer<P> answerer;
        
        ProblemProcessor(ProblemProcessorConfig<P> config) {
            this.config = config;
            creator = new ProblemCreator<P>(config.factory);
            comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2);
            answerer = new ProblemAnswerer<P>(config.factory, config.solver);
        }
        
        void process(String mode) throws IOException {
            switch (mode) {
            case "create":
                creator.create();
                break;
            case "debug":
                comparator.compare();
                break;
            case "solve":
                answerer.answer();
                break;
            }
        }
    }
    
    static class StringUtils {
        
        static String toString(int a) {
            return String.valueOf(a);
        }
        
        static String toString(long a) {
            return String.valueOf(a);
        }
        
        static String toString(double a) {
            return String.valueOf(a);
        }
        
        static String toString(String str) {
            return str;
        }
        
        static String toString(int[] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                if (i < a.length - 1) {
                    sb.append(a[i] + " ");
                } else {
                    sb.append(a[i]);
                }
            }
            return sb.toString();
        }
        
        static String toString(long[] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                if (i < a.length - 1) {
                    sb.append(a[i] + " ");
                } else {
                    sb.append(a[i]);
                }
            }
            return sb.toString();
        }
        
        static String toString(double[] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                if (i < a.length - 1) {
                    sb.append(a[i] + " ");
                } else {
                    sb.append(a[i]);
                }
            }
            return sb.toString();
        }
        
        static String toString(String[] strs) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < strs.length; i++) {
                if (i < strs.length - 1) {
                    sb.append(strs[i] + " ");
                } else {
                    sb.append(strs[i]);
                }
            }
            return sb.toString();
        }
        
        static String toString(int[][] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    if (j < a[i].length - 1) {
                        sb.append(a[i][j] + " ");
                    } else {
                        sb.append(a[i][j]);
                    }
                }
                sb.append("\n");
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
        
        static String toString(long[][] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    if (j < a[i].length - 1) {
                        sb.append(a[i][j] + " ");
                    } else {
                        sb.append(a[i][j]);
                    }
                }
                sb.append("\n");
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
        
        static String toString(double[][] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    if (j < a[i].length - 1) {
                        sb.append(a[i][j] + " ");
                    } else {
                        sb.append(a[i][j]);
                    }
                }
                sb.append("\n");
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
        
        static String toString(String[][] a) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    if (j < a[i].length - 1) {
                        sb.append(a[i][j] + " ");
                    } else {
                        sb.append(a[i][j]);
                    }
                }
                sb.append("\n");
            }
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
        
        static int toInt(String s) throws IOException {
            return Integer.parseInt(s);
        }
        
        static long toLong(String s) throws IOException {
            return Long.parseLong(s);
        }
        
        static double toDouble(String s) throws IOException {
            return Double.parseDouble(s);
        }
        
        static int[] toIntArray(String s) throws IOException {
            String[] tokens = s.split(" ");
            int[] a = new int[tokens.length];
            for (int i = 0; i < tokens.length; i++) {
                a[i] = Integer.parseInt(tokens[i]);
            }
            return a;
        }
        
        static long[] toLongArray(String s) throws IOException {
            String[] tokens = s.split(" ");
            long[] a = new long[tokens.length];
            for (int i = 0; i < tokens.length; i++) {
                a[i] = Long.parseLong(tokens[i]);
            }
            return a;
        }
        
        static double[] toDoubleArray(String s) throws IOException {
            String[] tokens = s.split(" ");
            double[] a = new double[tokens.length];
            for (int i = 0; i < tokens.length; i++) {
                a[i] = Double.parseDouble(tokens[i]);
            }
            return a;
        }
        
        static String[] toStringArray(String s) throws IOException {
            return s.split(" ");
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1