Submission #733113
Source Code Expand
import static java.lang.Math.*; import static java.util.Arrays.*; import java.util.*; import java.io.*; import java.math.BigInteger; import static java.math.BigInteger.*; public class Main { static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } void solve() { String[] s = sc.next().split("/"); long X = Long.parseLong(s[0]); long Y = Long.parseLong(s[1]); { long g = gcd(X, Y); X /= g; Y /= g; } long N1 = Math.max(2 * X / Y - 2, 0); long N2 = (2 * X + Y - 1) / Y + 1; boolean found = false; for (long N = N1; N <= N2; N++) { long M = check(N, X, Y); if (M != -1) { out.println(N + " " + M); found = true; } } if (!found) { out.println("Impossible"); } } long check(long N, long X, long Y) { BigInteger A = (valueOf(N+1).multiply(valueOf(Y)).subtract(valueOf(2*X))).multiply(valueOf(N)); if (A.remainder(valueOf(2 * Y)).equals(ZERO)) { long M = A.divide(valueOf(2 * Y)).longValue(); if (1 <= M && M <= N) return M; return -1; } else return -1; } static void tr(Object... os) { System.err.println(deepToString(os)); } static void tr(int[][] as) { for (int[] a : as) tr(a); } void print(int[] a) { out.print(a[0]); for (int i = 1; i < a.length; i++) out.print(" " + a[i]); out.println(); } public static void main(String[] args) throws Exception { new Main().run(); } MyScanner sc = null; PrintWriter out = null; public void run() throws Exception { sc = new MyScanner(System.in); out = new PrintWriter(System.out); for (;sc.hasNext();) { solve(); out.flush(); } out.close(); } class MyScanner { String line; BufferedReader reader; StringTokenizer tokenizer; public MyScanner(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public void eat() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { line = reader.readLine(); if (line == null) { tokenizer = null; return; } tokenizer = new StringTokenizer(line); } catch (IOException e) { throw new RuntimeException(e); } } } public String next() { eat(); return tokenizer.nextToken(); } public String nextLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public boolean hasNext() { eat(); return (tokenizer != null && tokenizer.hasMoreElements()); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } } }
Submission Info
Submission Time | |
---|---|
Task | C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi ) |
User | hs484 |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 2938 Byte |
Status | AC |
Exec Time | 472 ms |
Memory | 17844 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_killer.txt, 00_max.txt, 00_min.txt, 00_min2.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rnd2_00.txt, 02_rnd2_01.txt, 02_rnd2_02.txt, 02_rnd2_03.txt, 02_rnd2_04.txt, 02_rnd2_05.txt, 02_rnd2_06.txt, 02_rnd2_07.txt, 02_rnd2_08.txt, 02_rnd2_09.txt, 02_rnd2_10.txt, 02_rnd2_11.txt, 02_rnd2_12.txt, 02_rnd2_13.txt, 02_rnd2_14.txt, 02_rnd2_15.txt, 02_rnd2_16.txt, 02_rnd2_17.txt, 02_rnd2_18.txt, 02_rnd2_19.txt, 03_smallrnd_00.txt, 03_smallrnd_01.txt, 03_smallrnd_02.txt, 03_smallrnd_03.txt, 03_smallrnd_04.txt, 03_smallrnd_05.txt, 03_smallrnd_06.txt, 03_smallrnd_07.txt, 03_smallrnd_08.txt, 03_smallrnd_09.txt, 04_primes_01.txt, 04_primes_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_killer.txt | AC | 319 ms | 17844 KB |
00_max.txt | AC | 300 ms | 17640 KB |
00_min.txt | AC | 296 ms | 17688 KB |
00_min2.txt | AC | 292 ms | 17680 KB |
00_sample_01.txt | AC | 288 ms | 17704 KB |
00_sample_02.txt | AC | 290 ms | 17608 KB |
00_sample_03.txt | AC | 298 ms | 17692 KB |
00_sample_04.txt | AC | 306 ms | 17628 KB |
01_rnd_00.txt | AC | 312 ms | 17672 KB |
01_rnd_01.txt | AC | 319 ms | 17708 KB |
01_rnd_02.txt | AC | 302 ms | 17704 KB |
01_rnd_03.txt | AC | 312 ms | 17516 KB |
01_rnd_04.txt | AC | 364 ms | 17656 KB |
01_rnd_05.txt | AC | 330 ms | 17592 KB |
01_rnd_06.txt | AC | 298 ms | 17700 KB |
01_rnd_07.txt | AC | 306 ms | 17612 KB |
01_rnd_08.txt | AC | 303 ms | 17648 KB |
01_rnd_09.txt | AC | 301 ms | 17680 KB |
01_rnd_10.txt | AC | 302 ms | 17696 KB |
01_rnd_11.txt | AC | 296 ms | 17676 KB |
01_rnd_12.txt | AC | 306 ms | 17692 KB |
01_rnd_13.txt | AC | 290 ms | 17664 KB |
01_rnd_14.txt | AC | 289 ms | 17716 KB |
01_rnd_15.txt | AC | 303 ms | 17660 KB |
01_rnd_16.txt | AC | 302 ms | 17656 KB |
01_rnd_17.txt | AC | 306 ms | 17616 KB |
01_rnd_18.txt | AC | 302 ms | 17632 KB |
01_rnd_19.txt | AC | 315 ms | 17664 KB |
02_rnd2_00.txt | AC | 385 ms | 17628 KB |
02_rnd2_01.txt | AC | 472 ms | 17656 KB |
02_rnd2_02.txt | AC | 346 ms | 17696 KB |
02_rnd2_03.txt | AC | 340 ms | 17660 KB |
02_rnd2_04.txt | AC | 298 ms | 17708 KB |
02_rnd2_05.txt | AC | 322 ms | 17760 KB |
02_rnd2_06.txt | AC | 405 ms | 17644 KB |
02_rnd2_07.txt | AC | 415 ms | 17676 KB |
02_rnd2_08.txt | AC | 297 ms | 17728 KB |
02_rnd2_09.txt | AC | 404 ms | 17780 KB |
02_rnd2_10.txt | AC | 420 ms | 17648 KB |
02_rnd2_11.txt | AC | 388 ms | 17592 KB |
02_rnd2_12.txt | AC | 308 ms | 17716 KB |
02_rnd2_13.txt | AC | 313 ms | 17644 KB |
02_rnd2_14.txt | AC | 308 ms | 17628 KB |
02_rnd2_15.txt | AC | 300 ms | 17716 KB |
02_rnd2_16.txt | AC | 303 ms | 17636 KB |
02_rnd2_17.txt | AC | 302 ms | 17620 KB |
02_rnd2_18.txt | AC | 302 ms | 17636 KB |
02_rnd2_19.txt | AC | 309 ms | 17648 KB |
03_smallrnd_00.txt | AC | 302 ms | 17672 KB |
03_smallrnd_01.txt | AC | 301 ms | 17720 KB |
03_smallrnd_02.txt | AC | 306 ms | 17696 KB |
03_smallrnd_03.txt | AC | 306 ms | 17608 KB |
03_smallrnd_04.txt | AC | 315 ms | 17684 KB |
03_smallrnd_05.txt | AC | 306 ms | 17632 KB |
03_smallrnd_06.txt | AC | 317 ms | 17668 KB |
03_smallrnd_07.txt | AC | 314 ms | 17692 KB |
03_smallrnd_08.txt | AC | 313 ms | 17676 KB |
03_smallrnd_09.txt | AC | 299 ms | 17688 KB |
04_primes_01.txt | AC | 297 ms | 17656 KB |
04_primes_02.txt | AC | 297 ms | 17632 KB |