SRM 163 DIV2 Level One - シャクトリムシのお食事

英語で泣きそうになるな。

シャクトリムシは結構面白い動きをして、シャクトリムシ - Wikipediaこんなん。

日本語で尺取虫、英語でinchwormと言う位なので、長さを計る虫。という意味は変わらないらしい。

枝に等間隔に葉っぱが付いてる。シャクトリムシも等間隔でしか移動できない。

~   ~   ~   ~   ~   ~　← シャクトリムシ
+----+----+----+----+--
葉   葉   葉   葉   葉

さて、シャクトリムシは何枚の葉っぱを食べられるでしょうか。という問題。

と、ここまで理解するまでが死にそう。

回答は簡単で、必ず0で一回食べられるので、一回足しといて、lcm取ればいい。入力は1以上なのでゼロ除算は見る必要なし。

int gcd(int a,int b) { return (b == 0) ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a * b / gcd(a, b); }

class Inchworm
{
public:
    static int lunchtime(int branch, int rest, int leaf)
    {
        return 1 + branch / lcm(rest, leaf);
    }
};

英語修行じゃ。

英語メモ

• inchworm
  • シャクトリムシ
• inch (動)
  • 少しづつ動く、徐々に進む
• habit
  • 習慣、習性
• make a meal of
  • 〜を食べる。