2013/01/20

[競技プログラミング][PHP][AtCoder]鉛筆リサイクルの新技術

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

時間制限 : 2sec / スタック制限 : 64MB / メモリ制限 : 256MB

問題文

世界的大手鉛筆会社のファイバーカステラ社が、
小さくなって使えなくなってしまった鉛筆を再利用する画期的な新技術を発明した。
この技術は小さくなった鉛筆 m 本から新しい鉛筆を n 本 (m > n) 作り出すものである。
ファイバーカステラ社が N 本の鉛筆を製造・販売し、その全てが使用されて回収され、
回収された使えなくなった鉛筆から新しい鉛筆を作る。
これらを販売し、やはり全てが使用後回収されて新たな鉛筆の原料となる。
これを繰り返した結果として、
ファイバーカステラ社が総計何本の鉛筆を販売できるか計算するプログラムを作成せよ。
再利用する際に、回収されたにもかかわらず新しい鉛筆の原料とされなかった鉛筆を保持しておき、
任意のタイミングで回収した鉛筆に加えても良い。
販売できる本数には、はじめの N 本も忘れずに加えること。
また、 N > m とし、m と n が互いに素であるとする。

入力

入力は以下の形式で標準入力から与えられる。 自然数 m 、 n 、 N がこの順に半角空白区切りで入力される。
m n N
1 行目には整数 m 、 n 、N が与えられる。
m は小さくなって使えなくなってしまった鉛筆の数である。
n はファイバーカステラ社が作り出す新しい鉛筆の本数である。
N はファイバーカステラ社が最初に販売する鉛筆の本数である。
(1 ≦ n < m < N ≦ 1,000) であり、m と n が互いに素であることは保証されている。

出力

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

出典

A: 鉛筆リサイクルの新技術 - AtCoder Regular Contest #011 | AtCoder

回答

AtCoder/arc011_1.php at master · wada811/AtCoder · GitHub
<?php
fscanf(STDIN, "%d %d %d", $consume, $create, $number);
$total = $number;
$rest = 0;
while($number >= $consume){
    $rest = $number % $consume;
    $number = (int)($number/ $consume) * $create;
    $total += $number;
    $number += $rest;
}
println($total);
function println($var, $line = null){
    if(is_null($line)){
        echo $var . PHP_EOL;
    }else{
        echo $line . ':' . $var . PHP_EOL;
    }
}
?>
A問題くらい飲みながらでも解けるだろーとか思ってたら
いつものA問題よりちょっと難しくてヤベってなった。
シャキッとして出力例2の解説を読みつつ組んだ。
途中で競技プログラミング用に結果出力とデバッグ出力を兼ねた関数を作り始めて、
SublimeText2 のスニペット登録してたら時間終わってた。

タグ(RSS)