ARC-011-A 鉛筆リサイクルの新技術

■■■問題■■■

世界的大手鉛筆会社のファイバーカステラ社が、
小さくなって使えなくなってしまった鉛筆を再利用する画期的な新技術を発明した。
この技術は小さくなった鉛筆m本から新しい鉛筆をn本 (m>n) 作り出すものである。

ファイバーカステラ社がN本の鉛筆を製造・販売し、その全てが使用されて回収され、
回収された使えなくなった鉛筆から新しい鉛筆を作る。

これらを販売し、やはり全てが使用後回収されて新たな鉛筆の原料となる。
これを繰り返した結果として、
ファイバーカステラ社が総計何本の鉛筆を販売できるか計算するプログラムを作成せよ。

再利用する際に、回収されたにもかかわらず新しい鉛筆の原料とされなかった鉛筆を保持しておき、
任意のタイミングで回収した鉛筆に加えても良い。

販売できる本数には、はじめのN本も忘れずに加えること。
また、 N>m とし、mとnが互いに素であるとする。

■■■入力■■■

m n N

1行目には整数m、n、Nが与えられる。
●mは小さくなって使えなくなってしまった鉛筆の数である。
●nはファイバーカステラ社が作り出す新しい鉛筆の本数である。
●Nはファイバーカステラ社が最初に販売する鉛筆の本数である。
●(1 <= n < m < N <= 1000) であり、mとnが互いに素であることは保証されている。

■■■出力■■■

ファイバーカステラ社が販売する鉛筆の総数を標準出力に1行で出力すること。
この数には使い終わった後に再度製造された鉛筆も含まれる。
また、出力の最後には改行をいれること。 

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("2 1 8");
            //1.初めに、鉛筆を8本販売する。
            //2.販売した8本を回収する。
            //  2本から1本鉛筆を作るので新たに4本作成し、販売する。
            //3.販売した4本を回収する。
            //  2本から1本鉛筆を作るので新たに2本作成し、販売する。
            //4.販売した2本を回収する。
            //  2本から1本鉛筆を作るので新たに1本作成し、販売する。
            //5.販売した1本を回収する。
            //  2本から1本鉛筆を作るが、1本しか回収できなかったので、
            //  新たに作成することができない。
            //販売した鉛筆の合計は 8+4+2+1=15本である。
            //15
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 4 30");
            //1.初めに、鉛筆を30本販売する。
            //2.販売した30本を回収する。鉛筆を新たに16本作成し、販売する。
            //  このとき、 2本だけ再利用されない。
            //3.販売した16本を回収する。鉛筆を新たに8本作成し、販売する。
            //  このときも、2本再利用されない鉛筆があり、計4本再利用されていない。
            //4.販売した 8本を回収する。鉛筆を新たに4本作成し、販売する。
            //  このとき、1本再利用されない鉛筆があり、計5本再利用されていない。
            //5.販売した 4本を回収する。鉛筆7本から新たに4本鉛筆を作りたいが、
            //  販売した 4本しか回収できなかったので、
            //  これだけでは新たに作成することができない。
            //  このとき、回収した4本の鉛筆に
            //  新しい鉛筆の原料とされなかった5本の鉛筆を追加し、
            //  計9本の再利用されていない鉛筆がある。
            //6.再利用されていない鉛筆が9本あるので、
            //  そのうち7本から新たに4本鉛筆を作成し、販売する。
            //  このとき、2本再利用されない鉛筆がある。
            //7.販売した4本を回収する。7本から4本鉛筆を作るが、
            //  回収した4本と余った2本の鉛筆を足しても6本なので、
            //  新たに鉛筆を作成することができない。
            //販売した鉛筆の合計は 30+16+8+4+4=62本である。
            //62
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100 99 1000");
            //90199
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        int m = wkArr[0];
        int n = wkArr[1];
        int M = wkArr[2];

        int RestCnt = M;
        int SellCnt = M;
        while (RestCnt >= m) {
            int MakeCnt = RestCnt / m * n;
            RestCnt %= m;
            SellCnt += MakeCnt;
            RestCnt += MakeCnt;
        }
        Console.WriteLine(SellCnt);
    }
}

解説

制約が緩いので、
ナイーブにシュミレーションしてます。