ABC-046-C AtCoDeerくんと選挙速報

■■■問題■■■

シカのAtCoDeerくんは選挙速報を見ています。
選挙には二人の候補高橋くんと青木くんが出ています。

速報では、現在の二人の得票数の比が表示されていますが、
得票数そのものは表示されていません。

AtCoDeerくんはN回画面を見て、
i(1 <= i <= N)回目に見たときに表示されている比は Ti:Ai でした。
ここで、AtCoDeerくんが選挙速報の画面を1回目に見た段階で
既にどちらの候補にも少なくとも一票は入っていたことがわかっています。

N回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち
最小となるものを求めてください。
ただし、得票数が途中で減ることはありません。

■■■入力■■■

N
T1 A1
T2 A2
・
・
・
TN AN

●1 <= N <= 1000
●1 <= Ti,Ai <= 1000(1 <= i <= N)
●TiとAiは互いに素 (1 <= i <= N)
●答えが10の18乗以下になることは保証されている

■■■出力■■■

N回目に画面を見たときの投票数として考えられる最小値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("2 3");
            WillReturn.Add("1 1");
            WillReturn.Add("3 2");
            //10
            //二人の得票数が 2,3 -> 3,3 -> 6,4 と動くと
            //投票数は10になって、これが最小値です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            WillReturn.Add("1 5");
            WillReturn.Add("1 100");
            //101
            //一度画面を見てからもう一度画面を見るまでに
            //一票も入ってないことがありえます。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("3 10");
            WillReturn.Add("48 17");
            WillReturn.Add("31 199");
            WillReturn.Add("231 23");
            WillReturn.Add("3 2");
            //6930
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => long.Parse(X)).ToArray();

        long TotalT = 1;
        long TotalA = 1;

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long CurrT = wkArr[0];
            long CurrA = wkArr[1];

            //TotalT以上で最小のCurrTの倍数を求める
            long MinBaisuuT = DeriveMinBaisuu(TotalT, CurrT);

            //TotalA以上で最小のCurrAの倍数を求める
            long MinBaisuuA = DeriveMinBaisuu(TotalA, CurrA);

            //倍率を求める
            long BairituT = MinBaisuuT / CurrT;
            long BairituA = MinBaisuuA / CurrA;

            //大きいほうの倍率となる
            long Bairitu = Math.Max(BairituT, BairituA);

            TotalT = CurrT * Bairitu;
            TotalA = CurrA * Bairitu;
        }
        Console.WriteLine(TotalT + TotalA);
    }

    //A,Bを引数として、A以上で最小のBの倍数を求める
    static long DeriveMinBaisuu(long pA, long pB)
    {
        long Syou = pA / pB;
        long Amari = pA % pB;

        return pB * (Syou + Math.Sign(Amari));
    }
}

解説

X:Y = 3:7 ⇔ (X,Y) = ( 3, 7)
      または (X,Y) = ( 6,14)
      または (X,Y) = ( 9,21)
      または (X,Y) = (12,28)
      または 以下省略

という同値な関係があることをふまえて、
各速報ごとに、高橋君と青木君の最小の得票数を更新してます。