結果

問題 No.229 線分上を往復する3つの動点の一致
コンテスト
ユーザー EmKjp
提出日時 2015-06-19 22:56:55
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 746 ms / 5,000 ms
コード長 6,759 bytes
コンパイル時間 1,122 ms
コンパイル使用メモリ 109,184 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2024-07-07 04:11:36
合計ジャッジ時間 33,235 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

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