SRM 155 DIV2 Level One - キープ

C++ TopCoder

こういう問題好きだな。


インカ帝国では文字を持ってなくて、数を表すのに「縄の結び目の形で数で表す」という手法(キープ)を使っていたらしい。

へぇぇ。


で、問題。Xで結び目、-が結び目と結び目の間を表して、

  • -XX-XXXX-XXX-で、1の位が3。10の位が4。100の位が2で243
  • -XX--XXXX---XXX-何も結び目が無い場合は0、-XX-_-XXXX-_-_-XXX-と分けて、204003

として、キープを表現する。


後ろから読んでいく方針。

  • 最初の一個が邪魔なので取ってやる。
    • -XX-XXXX-XXX
  • -が来るまで読んで、expt(10,桁数) * 結び目数。で畳み込む。
  • 繰り返す。

以上！！

#include <string>
using namespace std;

class Quipu
{
    public:
        static int readKnots(string knots)
        {
            int sum = 0;

            for (int i = knots.length() - 2, k = 1; i >= 0; i--, k *= 10) {
                int n;

                for (n = 0; knots[i] == 'X'; i--, n++)
                    ;

                sum += k * n;
            }

            return sum;
        }
};


順次足していく方針を取れば、もうちょっと短くなる。

class Quipu
{
    public:
        static int readKnots(string knots)
        {
            int sum = 0;

            for (int i = knots.length() - 2, k = 1; i >= 0; i--, k *= 10)
                for (; knots[i] == 'X'; i--, sum += k)
                    ;

            return sum;
        }
};

イイネ。