#33248 (C#(csc)) No.229 線分上を往復する3つの動点の一致

提出ソース

結果

問題	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	672 ms 18,048 KB
testcase_01	AC	428 ms 18,048 KB
testcase_02	AC	433 ms 17,920 KB
testcase_03	AC	460 ms 17,920 KB
testcase_04	AC	420 ms 17,792 KB
testcase_05	AC	468 ms 18,048 KB
testcase_06	AC	449 ms 17,920 KB
testcase_07	AC	683 ms 17,792 KB
testcase_08	AC	665 ms 18,048 KB
testcase_09	AC	677 ms 18,048 KB
testcase_10	AC	634 ms 18,048 KB
testcase_11	AC	731 ms 17,920 KB
testcase_12	AC	680 ms 17,920 KB
testcase_13	AC	505 ms 17,920 KB
testcase_14	AC	697 ms 17,920 KB
testcase_15	AC	698 ms 17,920 KB
testcase_16	AC	694 ms 18,048 KB
testcase_17	AC	727 ms 18,048 KB
testcase_18	AC	700 ms 17,920 KB
testcase_19	AC	710 ms 18,048 KB
testcase_20	AC	704 ms 17,920 KB
testcase_21	AC	706 ms 18,048 KB
testcase_22	AC	721 ms 17,792 KB
testcase_23	AC	746 ms 18,048 KB
testcase_24	AC	720 ms 18,048 KB
testcase_25	AC	696 ms 18,048 KB
testcase_26	AC	710 ms 17,920 KB
testcase_27	AC	739 ms 18,048 KB
testcase_28	AC	714 ms 17,920 KB
testcase_29	AC	726 ms 17,920 KB
testcase_30	AC	699 ms 18,048 KB
testcase_31	AC	730 ms 18,048 KB
testcase_32	AC	604 ms 17,920 KB
testcase_33	AC	725 ms 18,048 KB
testcase_34	AC	712 ms 17,920 KB
testcase_35	AC	684 ms 17,792 KB
testcase_36	AC	690 ms 18,048 KB
testcase_37	AC	699 ms 18,048 KB
testcase_38	AC	703 ms 17,920 KB
testcase_39	AC	730 ms 18,048 KB
testcase_40	AC	719 ms 17,920 KB
testcase_41	AC	713 ms 18,048 KB
testcase_42	AC	565 ms 17,920 KB
testcase_43	AC	631 ms 17,920 KB
testcase_44	AC	696 ms 18,048 KB
testcase_45	AC	685 ms 18,048 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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;
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード