結果
問題 | No.229 線分上を往復する3つの動点の一致 |
ユーザー | ぴろず |
提出日時 | 2015-06-19 23:18:37 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 178 ms / 5,000 ms |
コード長 | 3,594 bytes |
コンパイル時間 | 3,898 ms |
コンパイル使用メモリ | 82,744 KB |
実行使用メモリ | 57,404 KB |
最終ジャッジ日時 | 2023-09-21 10:11:28 |
合計ジャッジ時間 | 14,396 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 166 ms
57,232 KB |
testcase_01 | AC | 168 ms
57,060 KB |
testcase_02 | AC | 178 ms
57,036 KB |
testcase_03 | AC | 167 ms
57,200 KB |
testcase_04 | AC | 168 ms
57,120 KB |
testcase_05 | AC | 165 ms
57,248 KB |
testcase_06 | AC | 170 ms
57,068 KB |
testcase_07 | AC | 166 ms
57,012 KB |
testcase_08 | AC | 167 ms
57,040 KB |
testcase_09 | AC | 171 ms
57,008 KB |
testcase_10 | AC | 167 ms
57,040 KB |
testcase_11 | AC | 170 ms
56,844 KB |
testcase_12 | AC | 168 ms
57,052 KB |
testcase_13 | AC | 168 ms
57,224 KB |
testcase_14 | AC | 168 ms
55,140 KB |
testcase_15 | AC | 170 ms
57,352 KB |
testcase_16 | AC | 173 ms
57,052 KB |
testcase_17 | AC | 171 ms
57,120 KB |
testcase_18 | AC | 174 ms
56,904 KB |
testcase_19 | AC | 172 ms
57,232 KB |
testcase_20 | AC | 171 ms
57,012 KB |
testcase_21 | AC | 170 ms
57,232 KB |
testcase_22 | AC | 173 ms
57,052 KB |
testcase_23 | AC | 171 ms
57,100 KB |
testcase_24 | AC | 171 ms
57,008 KB |
testcase_25 | AC | 171 ms
57,328 KB |
testcase_26 | AC | 171 ms
57,404 KB |
testcase_27 | AC | 167 ms
57,284 KB |
testcase_28 | AC | 169 ms
57,032 KB |
testcase_29 | AC | 165 ms
57,008 KB |
testcase_30 | AC | 166 ms
57,008 KB |
testcase_31 | AC | 167 ms
57,060 KB |
testcase_32 | AC | 166 ms
57,164 KB |
testcase_33 | AC | 165 ms
57,052 KB |
testcase_34 | AC | 168 ms
57,036 KB |
testcase_35 | AC | 167 ms
57,016 KB |
testcase_36 | AC | 165 ms
57,052 KB |
testcase_37 | AC | 170 ms
56,832 KB |
testcase_38 | AC | 167 ms
57,364 KB |
testcase_39 | AC | 168 ms
57,044 KB |
testcase_40 | AC | 164 ms
57,340 KB |
testcase_41 | AC | 165 ms
57,324 KB |
testcase_42 | AC | 165 ms
57,000 KB |
testcase_43 | AC | 165 ms
57,252 KB |
testcase_44 | AC | 168 ms
57,036 KB |
testcase_45 | AC | 167 ms
57,056 KB |
ソースコード
package no229; import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Frac[] t = new Frac[3]; for(int i=0;i<3;i++) { t[i] = new Frac(2, sc.nextInt()); } Frac ans = new Frac(Long.MAX_VALUE); for(int i=0;i<8;i++) { Frac[] s = new Frac[3]; for(int j=0;j<3;j++) { s[j] = ((i >> j & 1 ) == 0) ? t[j] : t[j].multiply(new Frac(-1)); } Frac x = s[0].subtract(s[1]).abs().inverse().lcm(s[1].subtract(s[2]).abs().inverse()).multiply(new Frac(2)); ans = ans.min(x); } System.out.println(ans); } } class Frac { public static Frac ZERO = new Frac(0,1); BigInteger a,b; public Frac(long a) { this.a = BigInteger.valueOf(a); this.b = BigInteger.ONE; } public Frac(long a,long b) { this(BigInteger.valueOf(a),BigInteger.valueOf(b)); } public Frac(BigInteger a,BigInteger b) { int sign = a.signum() * b.signum(); a = a.abs(); b = b.abs(); BigInteger gcd = a.gcd(b); this.a = a.divide(gcd); this.b = b.divide(gcd); if (sign < 0) { this.a = this.a.negate(); } } public Frac add(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.b).add(x.b.multiply(y.a)), x.b.multiply(y.b)); } public Frac subtract(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.b).subtract(x.b.multiply(y.a)), x.b.multiply(y.b)); } public Frac multiply(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.a),x.b.multiply(y.b)); } public Frac divide(Frac y) { Frac x = this; return new Frac(x.a.multiply(y.b),x.b.multiply(y.a)); } public long longValueExact() { if (!b.equals(BigInteger.ONE)) { throw new ArithmeticException(); } return a.longValueExact(); } public boolean equals(Object o) { if (o instanceof Frac) { Frac f = (Frac) o; return this.a.equals(f.a) && this.b.equals(f.b); } return super.equals(o); } public int hashCode() { return a.hashCode() ^ b.hashCode(); } public String toString() { return a + "/" + b; } public Frac lcm(Frac y) { return new Frac(lcm(a.multiply(y.b),b.multiply(y.a)),b.multiply(y.b)); } private static BigInteger lcm(BigInteger a,BigInteger b) { return a.divide(a.gcd(b)).multiply(b); } public Frac abs() { return new Frac(a.abs(), b); } public Frac inverse() { return new Frac(b,a); } public Frac min(Frac y) { if (a.multiply(y.b).compareTo(y.a.multiply(b)) < 0) { return this; }else{ return y; } } } class Mod { public static long n(long x,long mod) { x %= mod; if (x < 0) { x += mod; } return x; } public static long pow(long a,long n,long mod) { long res = 1; while(n > 0) { if ((n & 1) > 0) { res = (res * a) % mod; } a = (a * a) % mod; n/=2; } return res; } public static long inverse(long a,long mod) { long b = mod, u = 1, v = 0; while(b > 0) { long temp; long t = a / b; a -= t * b; temp = a; a = b; b = temp; u -= t * v; temp = u; u = v; v = temp; } return (u % mod + mod) % mod; } /** * @return [a,m] where x = a (mod m) */ public static long[] linearCongruence(long[] A,long[] B,long[] M) { long x = 0; long m = 1; for(int i=0;i<A.length;i++) { long a = A[i] * m; long b = B[i] - A[i] * x; long d = gcd(M[i],a); if (b % d != 0) { return null; } long t = b / d * inverse(a / d, M[i] / d) % (M[i] / d); x = x + m * t; m *= M[i] / d; } long[] ret = {x%m, m}; return ret; } public static long gcd(long a,long b) { while(b!=0) { long r = a%b; a = b; b = r; } return a; } }