結果

問題 No.229 線分上を往復する3つの動点の一致
ユーザー EmKjpEmKjp
提出日時 2015-06-19 22:56:55
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 841 ms / 5,000 ms
コード長 6,759 bytes
コンパイル時間 2,230 ms
コンパイル使用メモリ 110,932 KB
実行使用メモリ 22,972 KB
最終ジャッジ日時 2023-09-21 10:05:04
合計ジャッジ時間 38,853 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 749 ms
20,836 KB
testcase_01 AC 488 ms
20,844 KB
testcase_02 AC 498 ms
18,724 KB
testcase_03 AC 513 ms
20,948 KB
testcase_04 AC 468 ms
20,772 KB
testcase_05 AC 520 ms
20,896 KB
testcase_06 AC 505 ms
20,832 KB
testcase_07 AC 770 ms
22,960 KB
testcase_08 AC 753 ms
20,904 KB
testcase_09 AC 742 ms
22,856 KB
testcase_10 AC 707 ms
20,812 KB
testcase_11 AC 841 ms
20,884 KB
testcase_12 AC 753 ms
20,916 KB
testcase_13 AC 566 ms
20,908 KB
testcase_14 AC 780 ms
20,840 KB
testcase_15 AC 777 ms
22,880 KB
testcase_16 AC 765 ms
20,940 KB
testcase_17 AC 794 ms
20,888 KB
testcase_18 AC 778 ms
20,864 KB
testcase_19 AC 804 ms
18,944 KB
testcase_20 AC 770 ms
20,824 KB
testcase_21 AC 779 ms
20,872 KB
testcase_22 AC 785 ms
22,972 KB
testcase_23 AC 811 ms
20,796 KB
testcase_24 AC 787 ms
20,964 KB
testcase_25 AC 774 ms
20,936 KB
testcase_26 AC 786 ms
22,896 KB
testcase_27 AC 805 ms
22,956 KB
testcase_28 AC 784 ms
20,832 KB
testcase_29 AC 806 ms
20,876 KB
testcase_30 AC 771 ms
22,888 KB
testcase_31 AC 805 ms
18,892 KB
testcase_32 AC 672 ms
20,872 KB
testcase_33 AC 794 ms
20,860 KB
testcase_34 AC 796 ms
20,908 KB
testcase_35 AC 762 ms
20,788 KB
testcase_36 AC 768 ms
20,880 KB
testcase_37 AC 777 ms
22,848 KB
testcase_38 AC 780 ms
20,820 KB
testcase_39 AC 799 ms
20,776 KB
testcase_40 AC 783 ms
22,812 KB
testcase_41 AC 792 ms
22,908 KB
testcase_42 AC 642 ms
20,920 KB
testcase_43 AC 702 ms
20,872 KB
testcase_44 AC 772 ms
22,956 KB
testcase_45 AC 755 ms
20,888 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #

using System;
using System.IO;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;


public struct Fraction : IComparable<Fraction> {
    public long Numerator { get; private set; }
    public long Denominator { get; private set; }

    static long Gcd(long s, long t) {
        return t != 0 ? Gcd(t, s % t) : Math.Abs(s);
    }

    static long Lcm(long s, long t) {
        return s / Gcd(s, t) * t;
    }

    void Reduce() {
        if (Denominator < 0) {
            Numerator = -Numerator;
            Denominator = -Denominator;
        }

        if (Numerator == 0) Denominator = 1;
        else {
            long g = Gcd(Numerator, Denominator);
            Numerator /= g;
            Denominator /= g;
        }
    }

    public Fraction(long a, long b = 1)
        : this() {
        this.Numerator = a;
        this.Denominator = b;
        Reduce();
    }

    public static implicit operator double(Fraction r) {
        return r.Numerator * 1.0 / r.Denominator;
    }

    public static Fraction operator +(Fraction f1, Fraction f2) {
        long lcm = Lcm(f1.Denominator, f2.Denominator);
        return new Fraction(f1.Numerator * (lcm / f1.Denominator) + f2.Numerator * (lcm / f2.Denominator), lcm);
    }

    public static Fraction operator -(Fraction f1, Fraction f2) {
        long lcm = Lcm(f1.Denominator, f2.Denominator);
        return new Fraction(f1.Numerator * (lcm / f1.Denominator) - f2.Numerator * (lcm / f2.Denominator), lcm);
    }

    public static Fraction operator *(Fraction f1, Fraction f2) {
        return new Fraction(f1.Numerator * f2.Numerator, f1.Denominator * f2.Denominator);
    }

    public static Fraction operator /(Fraction f1, Fraction f2) {
        return new Fraction(f1.Numerator * f2.Denominator, f1.Denominator * f2.Numerator);
    }

    public static Fraction operator -(Fraction f) {
        return new Fraction(-f.Numerator, f.Denominator);
    }

    public int CompareTo(Fraction f) {
        return (this.Numerator * f.Denominator).CompareTo(f.Numerator * this.Denominator);
    }

    public static bool operator <(Fraction f1, Fraction f2) {
        return f1.CompareTo(f2) < 0;
    }
    public static bool operator <=(Fraction f1, Fraction f2) {
        return f1.CompareTo(f2) <= 0;
    }
    public static bool operator ==(Fraction f1, Fraction f2) {
        return f1.CompareTo(f2) == 0;
    }
    public static bool operator >(Fraction f1, Fraction f2) {
        return f1.CompareTo(f2) > 0;
    }
    public static bool operator >=(Fraction f1, Fraction f2) {
        return f1.CompareTo(f2) >= 0;
    }
    public static bool operator !=(Fraction f1, Fraction f2) {
        return f1.CompareTo(f2) != 0;
    }

    public override string ToString() {
        return String.Format("{0}/{1}", Numerator, Denominator);
    }

    public override bool Equals(object obj) {
        if (obj == null) return false;
        var instance = (Fraction)obj;
        return this == instance;
    }

    public override int GetHashCode() {
        return Numerator.GetHashCode() ^ Denominator.GetHashCode();
    }
}

partial class Solver {
    static public long Gcd(long s, long t) {
        return t != 0 ? Gcd(t, s % t) : s;
    }

    static public long Lcm(long s, long t) {
        return s / Gcd(s, t) * t;
    }

    Fraction Position(long T, long a, long b) {
        T *= b;
        a %= T;
        if (a * 2 <= T) { // a <= T / 2
            return new Fraction(a) / new Fraction(T, 2);
        } else {
            a = T - a;
            return new Fraction(a) / new Fraction(T, 2);
        }
    }

    public void Run() {
        var t1 = ni();
        var t2 = ni();
        var t3 = ni();

        var lcm = Lcm(Lcm(t1, t2), t3);
        Fraction ans = new Fraction(1000000000000000000L);
        for (int i = 1; i < 1000000; i++) {
            var p1 = Position(t1, lcm, i);
            var p2 = Position(t2, lcm, i);
            if (p1 != p2) continue;
            var p3 = Position(t3, lcm, i);
            if (p1 == p2 && p2 == p3) {
                ans = new Fraction(lcm, i);
            }
        }
        cout.WriteLine("{0}/{1}", ans.Numerator, ans.Denominator);
    }
}

// PREWRITEN CODE BEGINS FROM HERE
partial class Solver : Scanner {
    public static void Main(string[] args) {
        new Solver(Console.In, Console.Out).Run();
    }

    TextReader cin;
    TextWriter cout;

    public Solver(TextReader reader, TextWriter writer)
        : base(reader) {
        this.cin = reader;
        this.cout = writer;
    }
    public Solver(string input, TextWriter writer)
        : this(new StringReader(input), writer) {
    }

    public int ni() { return NextInt(); }
    public int[] ni(int n) { return NextIntArray(n); }
    public long nl() { return NextLong(); }
    public long[] nl(int n) { return NextLongArray(n); }
    public double nd() { return NextDouble(); }
    public string ns() { return Next(); }
    public string[] ns(int n) { return NextArray(n); }
}

public class Scanner {
    private TextReader Reader;
    private Queue<String> TokenQueue = new Queue<string>();
    private CultureInfo ci = CultureInfo.InvariantCulture;

    public Scanner()
        : this(Console.In) {
    }

    public Scanner(TextReader reader) {
        this.Reader = reader;
    }

    public int NextInt() { return Int32.Parse(Next(), ci); }
    public long NextLong() { return Int64.Parse(Next(), ci); }
    public double NextDouble() { return double.Parse(Next(), ci); }
    public string[] NextArray(int size) {
        var array = new string[size];
        for (int i = 0; i < size; i++) array[i] = Next();
        return array;
    }
    public int[] NextIntArray(int size) {
        var array = new int[size];
        for (int i = 0; i < size; i++) array[i] = NextInt();
        return array;
    }

    public long[] NextLongArray(int size) {
        var array = new long[size];
        for (int i = 0; i < size; i++) array[i] = NextLong();
        return array;
    }

    public String Next() {
        if (TokenQueue.Count == 0) {
            if (!StockTokens()) throw new InvalidOperationException();
        }
        return TokenQueue.Dequeue();
    }

    public bool HasNext() {
        if (TokenQueue.Count > 0)
            return true;
        return StockTokens();
    }

    private bool StockTokens() {
        while (true) {
            var line = Reader.ReadLine();
            if (line == null) return false;
            var tokens = line.Trim().Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            if (tokens.Length == 0) continue;
            foreach (var token in tokens)
                TokenQueue.Enqueue(token);
            return true;
        }
    }
}
0