結果
問題 | No.3162 Five Two Three |
ユーザー |
|
提出日時 | 2025-05-04 04:12:21 |
言語 | Java (openjdk 23) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 20,544 bytes |
コンパイル時間 | 3,874 ms |
コンパイル使用メモリ | 97,312 KB |
実行使用メモリ | 41,600 KB |
最終ジャッジ日時 | 2025-05-05 01:35:54 |
合計ジャッジ時間 | 22,409 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 171 WA * 16 |
ソースコード
package FiveTwoThree; import java.util.ArrayList; public class Main { public static final int MOD998 = 998244353; public static final int MOD100 = 1000000007; public static void main(String[] args) throws Exception { ContestScanner sc = new ContestScanner(); ContestPrinter cp = new ContestPrinter(); long X = sc.nextLong(); long Y = sc.nextLong(); long Z = sc.nextLong(); long[] fib = new long[47]; fib[1] = 1; for (int i = 2; i < 47; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } if (X == 0) { if (Y == 0) { if (Z == 0) { cp.println(3); cp.println("0 0 0"); } else { cp.println(4); cp.println("0 " + Z + " " + Z + " 0"); } } else { if (Z == 0) { cp.println(5); cp.println("0 " + Y + " " + Y + " 0 " + Y); } else { boolean found = false; for (int i = 2; i < 46; i++) { for (int j = 1; j < i; j++) { if (Y % fib[i] == 0 && Z % fib[j] == 0 && Y / fib[i] == Z / fib[j]) { cp.println(i + 1); cp.print("0"); for (int n = 1; n <= i; n++) { cp.print(" " + (fib[n] * (Y / fib[i]))); } cp.println(); found = true; break; } } if (found) { break; } } if (!found) { cp.println(-1); } } } } else { if (Y == 0) { if (Z == 0) { cp.println(5); cp.println(X + " 0 " + X + " " + X + " 0"); } else { boolean found = false; for (int i = 2; i < 46; i++) { for (int j = 1; j < i; j++) { if (X % fib[i] == 0 && Z % fib[j] == 0 && X / fib[i] == Z / fib[j]) { cp.println(i + 1); for (int n = i; n >= 1; n--) { cp.print((fib[n] * (X / fib[i])) + " "); } cp.print("0"); cp.println(); found = true; break; } } if (found) { break; } } if (!found) { cp.println(-1); } } } else { if (Z == 0) { boolean found = false; for (int i = 1; i < 46; i++) { for (int j = 1; j < 46; j++) { if (X % fib[i] == 0 && Y % fib[j] == 0 && X / fib[i] == Y / fib[j]) { cp.println(i + j + 1); for (int n = i; n >= 1; n--) { cp.print((fib[n] * (X / fib[i])) + " "); } cp.print("0"); for (int n = 1; n <= j; n++) { cp.print(" " + (fib[n] * (X / fib[i]))); } cp.println(); found = true; break; } } if (found) { break; } } if (!found) { cp.println(-1); } } else { int min = 1000; ArrayList<Long> ans = new ArrayList<>(); // rr for (int i = 1; i < 46; i++) { for (int j = 0; j < i; j++) { // xa A + xb B = X // ya A + yb B = Y long xa = fib[j]; long xb = fib[j + 1]; long ya = fib[i]; long yb = fib[i + 1]; if ((X * yb - Y * xb) % (xa * yb - ya * xb) != 0 || (X * ya - Y * xa) % (xb * ya - yb * xa) != 0) { continue; } long a = (X * yb - Y * xb) / (xa * yb - ya * xb); long b = (X * ya - Y * xa) / (xb * ya - yb * xa); if (a < 0 || b < 0) { continue; } ArrayList<Long> res = new ArrayList<>(); for (int k = j + 1; k < i; k++) { res.add(fib[k] * a + fib[k + 1] * b); } if (res.size() < min && res.contains(Z)) { min = res.size(); ans = res; } } } // ll for (int i = 1; i < 46; i++) { for (int j = 0; j < i; j++) { // xa A + xb B = X // ya A + yb B = Y long xa = fib[i]; long xb = fib[i + 1]; long ya = fib[j]; long yb = fib[j + 1]; if ((X * yb - Y * xb) % (xa * yb - ya * xb) != 0 || (X * ya - Y * xa) % (xb * ya - yb * xa) != 0) { continue; } long a = (X * yb - Y * xb) / (xa * yb - ya * xb); long b = (X * ya - Y * xa) / (xb * ya - yb * xa); if (a < 0 || b < 0) { continue; } ArrayList<Long> res = new ArrayList<>(); for (int k = i - 1; k > j; k--) { res.add(fib[k] * a + fib[k + 1] * b); } if (res.size() < min && res.contains(Z)) { min = res.size(); ans = res; } } } // lr for (int i = 0; i < 46; i++) { for (int j = 0; j < 46; j++) { // xa A + xb B = X // ya A + yb B = Y long xa = fib[i + 1]; long xb = fib[i]; long ya = fib[j]; long yb = fib[j + 1]; if (xa * yb - ya * xb == 0) { if (X == Y && Z <= X) { min = 2; ans = new ArrayList<>(); ans.add(Z); ans.add(X - Z); } } else { if ((X * yb - Y * xb) % (xa * yb - ya * xb) != 0 || (X * ya - Y * xa) % (xb * ya - yb * xa) != 0) { continue; } long a = (X * yb - Y * xb) / (xa * yb - ya * xb); long b = (X * ya - Y * xa) / (xb * ya - yb * xa); if (a < 0 || b < 0) { continue; } ArrayList<Long> res = new ArrayList<>(); for (int k = i - 1; k >= 0; k--) { res.add(fib[k + 1] * a + fib[k] * b); } for (int k = 0; k < j; k++) { res.add(fib[k] * a + fib[k + 1] * b); } if (res.size() < min && res.contains(Z)) { min = res.size(); ans = res; } } } } // prt if (min == 1000) { cp.println(-1); } else { cp.println(min + 2); cp.print(X + " "); for (long l : ans) { cp.print(l + " "); } cp.print(Y); cp.println(); } } } } cp.close(); } static class ContestScanner { private final java.io.InputStream in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private static final long LONG_MAX_TENTHS = 922337203685477580L; private static final int LONG_MAX_LAST_DIGIT = 7; private static final int LONG_MIN_LAST_DIGIT = 8; public ContestScanner(java.io.InputStream in) { this.in = in; } public ContestScanner() { this(System.in); } private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (java.io.IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } public boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } public String next() { if (!hasNext()) throw new java.util.NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new java.util.NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { int digit = b - '0'; if (n >= LONG_MAX_TENTHS) { if (n == LONG_MAX_TENTHS) { if (minus) { if (digit <= LONG_MIN_LAST_DIGIT) { n = -n * 10 - digit; b = readByte(); if (!isPrintableChar(b)) { return n; } else if (b < '0' || '9' < b) { throw new NumberFormatException( String.format("%d%s... is not number", n, Character.toString(b))); } } } else { if (digit <= LONG_MAX_LAST_DIGIT) { n = n * 10 + digit; b = readByte(); if (!isPrintableChar(b)) { return n; } else if (b < '0' || '9' < b) { throw new NumberFormatException( String.format("%d%s... is not number", n, Character.toString(b))); } } } } throw new ArithmeticException( String.format("%s%d%d... overflows long.", minus ? "-" : "", n, digit)); } n = n * 10 + digit; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next()); } public long[] nextLongArray(int length) { long[] array = new long[length]; for (int i = 0; i < length; i++) array[i] = this.nextLong(); return array; } public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map) { long[] array = new long[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsLong(this.nextLong()); return array; } public int[] nextIntArray(int length) { int[] array = new int[length]; for (int i = 0; i < length; i++) array[i] = this.nextInt(); return array; } public int[][] nextIntArrayMulti(int length, int width) { int[][] arrays = new int[width][length]; for (int i = 0; i < length; i++) { for (int j = 0; j < width; j++) arrays[j][i] = this.nextInt(); } return arrays; } public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map) { int[] array = new int[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsInt(this.nextInt()); return array; } public double[] nextDoubleArray(int length) { double[] array = new double[length]; for (int i = 0; i < length; i++) array[i] = this.nextDouble(); return array; } public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map) { double[] array = new double[length]; for (int i = 0; i < length; i++) array[i] = map.applyAsDouble(this.nextDouble()); return array; } public long[][] nextLongMatrix(int height, int width) { long[][] mat = new long[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) { mat[h][w] = this.nextLong(); } return mat; } public int[][] nextIntMatrix(int height, int width) { int[][] mat = new int[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) { mat[h][w] = this.nextInt(); } return mat; } public double[][] nextDoubleMatrix(int height, int width) { double[][] mat = new double[height][width]; for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) { mat[h][w] = this.nextDouble(); } return mat; } public char[][] nextCharMatrix(int height, int width) { char[][] mat = new char[height][width]; for (int h = 0; h < height; h++) { String s = this.next(); for (int w = 0; w < width; w++) { mat[h][w] = s.charAt(w); } } return mat; } } static class ContestPrinter extends java.io.PrintWriter { public ContestPrinter(java.io.PrintStream stream) { super(stream); } public ContestPrinter() { super(System.out); } private static String dtos(double x, int n) { StringBuilder sb = new StringBuilder(); if (x < 0) { sb.append('-'); x = -x; } x += Math.pow(10, -n) / 2; sb.append((long) x); sb.append("."); x -= (long) x; for (int i = 0; i < n; i++) { x *= 10; sb.append((int) x); x -= (int) x; } return sb.toString(); } @Override public void print(float f) { super.print(dtos(f, 20)); } @Override public void println(float f) { super.println(dtos(f, 20)); } @Override public void print(double d) { super.print(dtos(d, 20)); } @Override public void println(double d) { super.println(dtos(d, 20)); } public void printArray(int[] array, String separator) { int n = array.length; for (int i = 0; i < n - 1; i++) { super.print(array[i]); super.print(separator); } super.println(array[n - 1]); } public void printArray(int[] array) { this.printArray(array, " "); } public void printArray(int[] array, String separator, java.util.function.IntUnaryOperator map) { int n = array.length; for (int i = 0; i < n - 1; i++) { super.print(map.applyAsInt(array[i])); super.print(separator); } super.println(map.applyAsInt(array[n - 1])); } public void printArray(int[] array, java.util.function.IntUnaryOperator map) { this.printArray(array, " ", map); } public void printArray(long[] array, String separator) { int n = array.length; for (int i = 0; i < n - 1; i++) { super.print(array[i]); super.print(separator); } super.println(array[n - 1]); } public void printArray(long[] array) { this.printArray(array, " "); } public void printArray(long[] array, String separator, java.util.function.LongUnaryOperator map) { int n = array.length; for (int i = 0; i < n - 1; i++) { super.print(map.applyAsLong(array[i])); super.print(separator); } super.println(map.applyAsLong(array[n - 1])); } public void printArray(long[] array, java.util.function.LongUnaryOperator map) { this.printArray(array, " ", map); } } }