第1回 CodeIQプロコン 2問目 雉

■■■問題■■■

てんびんが1つあります。
1グラムからnグラムまで、1グラム刻みの重さn通りすべてを、
それぞれてんびんを1回使うことで量ることができるようにします。

使用するおもりの個数をできるだけ少なくなるようにすると、
おもりは最低いくつ必要になるかを計算するプログラムを書いてください。

例えば4グラムまですべて量るには、1グラムのおもり(A)と3グラムのおもり(B)を用意すると、
次のように1〜4グラムすべて量ることができます。

1グラム・・・(A)をてんびんの片側に置く
2グラム・・・(A)をてんびんの片側に、(B)をその反対側に置く（3-1=2グラムを量ることができる）
3グラム・・・(B)をてんびんの片側に置く
4グラム・・・(A)と(B)の両方をてんびんの片側に置く（3+1=4グラムを量ることができる）

■■■入力■■■

標準入力から、整数n（1 <= n <= 300）が与えられます。

■■■出力■■■

標準出力に、入力nに対するおもりの個数の最小値のみを出力してください。
行末の改行コードは有無を問いません。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        int SumVal = 0;
        int Base = 1;
        for (int I = 1; ; I++) {
            SumVal += Base;
            Base *= 3;
            if (SumVal >= N) {
                Console.WriteLine(I);
                break;
            }
        }
    }
}

解説

重りがABCDなら、計測可能な重さは
A*(-1か0か1) + B*(-1か0か1) + C*(-1か0か1) + D*(-1か0か1)
となるので、平衡3進数とした際の、最大値まで計測可能です。

Kを1以上の整数とし、
3の(K-1)乗をAとすると
3のK乗-3の(K-1)乗 = 3A-A = 2A
よって、任意桁の2は、
上位桁の1、当該桁の-1
で表現可能です。

あとは、1の位をインクリメントしていくと考えれば、
1から最大値までの、連続した整数が作成できると分かります。
(2になると上位桁が1足されて、当該桁が-1になるイメージ)

『第1回CodeIQ プログラミングコンテスト』問題解説 --- CodeIQ MAGAZINE