質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.49%

  • C++

    3576questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    420questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

yukicoder.No47 : ビスケットが2の指数で増える問題

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 772

huyuhumi_fg

score 55

[質問文]
こんにちは,今回はyukicoderというサイトの問題で質問させていただきに来ました.
こちらにNo.47の問題,
http://yukicoder.me/problems/89
があります.前提として,自分はこの問題を人づてに聞いておりまして,
最初2進数であらわす問題だと思って以下に示すコードを作りました.
ですが,実際に問題サイトへいってみると,ビスケット1000枚 --> 10回 が答えになっており
,疑問に思い,他の方のコードを拝見させていただくと,どうも 2^k ≧ Nとなるkを求めているようでした.

そこで質問なのですが,
1. この問題は,「N = ビスケット数,となるように2の指数で増えるポケットをだけをつかってビスケットを増やす.そのためにポケットにいれるビスケットの数を調整する」という問題なのでしょうか?
つまり,2^k ≧ Nとなるkをもとめる問題では無いという解釈でいいのでしょうか?
2. 自分の問題解釈があっているなら,1000 --> 10にできるような組み合わせが存在するということでしょうか?
3. 解釈が間違っているのなら,いかに示すコードは,自分の解釈通りなら正解のコードといえるでしょうか?

[ソースコード]

#include <iostream>
#include <string>

int sumTataku( int n )
{
    int ans = 0;
    
    int on_bit_num = 0, dist = 0;
    int temp = n, dist_calc = 0;
    do{
        if( temp % 2 ){
            ++on_bit_num;
            dist += dist_calc;
        }
        ++dist_calc;
    } while( ( temp = temp >> 1 ) > 0 );

    std::cout << "on_bit_num = " << on_bit_num << "\n";
    std::cout << "dist = " << dist << "\n";

    ans += dist;
    
    temp = on_bit_num;
    if( temp % 2 && temp > 1){
        ++ans;
    }
    on_bit_num = 0;
    dist = 0; dist_calc = 0;
    do{
        if( temp % 2 ){
            ++on_bit_num;
            dist += dist_calc;
        }
        ++dist_calc;
    } while( ( temp = temp >> 1 ) > 0 );

    std::cout << "on_bit_num2 = " << on_bit_num << "\n";
    std::cout << "dist2 = " << dist << "\n";

    ans += dist;

    return ans;
}

void mysource()
{
    while( true ){
        try{
            std::cout << "number : ";
            std::string strn;
            std::cin >> strn;
            int n = std::stoi( strn );
            std::cout << "  ans = " << sumTataku( n ) << "\n\n";
        }
        catch( ... ){
            break;
        }
    }
}

int main()
{
    
    mysource();

    return 0;
}

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+2

問題のサンプルにあるとおりに1000枚のビスケットを目指すとすると、

1回目 1枚をポケットに入れ 叩く → 2枚
2回目 2枚をポケットに入れ 叩く → 4枚
3回目 4枚をポケットに入れ 叩く → 8枚
4回目 8枚をポケットに入れ 叩く → 16枚
5回目 16枚をポケットに入れ 叩く → 32枚
6回目 32枚をポケットに入れ 叩く → 64枚
7回目 64枚をポケットに入れ 叩く → 128枚
8回目 128枚をポケットに入れ 叩く → 256枚
9回目 256枚をポケットに入れ 叩く → 512枚
10回目 488枚をポケットに入れ 叩く → 1000枚

もし目指す枚数が500枚だとしたら、
1回目 1枚をポケットに入れ 叩く → 2枚
2回目 2枚をポケットに入れ 叩く → 4枚
3回目 4枚をポケットに入れ 叩く → 8枚
4回目 8枚をポケットに入れ 叩く → 16枚
5回目 16枚をポケットに入れ 叩く → 32枚
6回目 32枚をポケットに入れ 叩く → 64枚
7回目 64枚をポケットに入れ 叩く → 128枚
8回目 128枚をポケットに入れ 叩く → 256枚
9回目 244枚をポケットに入れ 叩く → 500枚

途中までは持っているビスケットの全てをポケットに入れて増やす、
最後の1回だけ、ポケットに入れるビスケットの枚数を減らして、
数値の調整をすればいいのです。

つまり、
2枚 1回
3~4枚 2回
5~8枚 3回
9~16枚 4回
17~32枚 5回
33~64枚 6回
65~128枚 7回
129~256枚 8回
257~512枚 9回
513~1024枚 10回

よって、2^k ≧ Nとなるkを求めれば良いということになります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/07/13 14:55

    なるほど,任意にポケットから取り出せるということを失念していました.
    つまり,この問題のキモは,2^k ≧ N となるkをもとめればよい,というのを,
    証明することだったわけですね(コード上には載りませんが).

    キャンセル

+1

2倍になるて書いてあるので、
N = 2 * x ですね。
最初にポケットに入る数は1固定ぽいので、
1回目のタッチで2枚
2回目のタッチで4枚
3回目のタッチで8枚と増えるようですね。
でN枚得るには何回タッチするかて問題ですね。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/07/13 14:38

    キモは,Nちょうどなのか,N≧なのかということです.
    Nちょうどならこれは2進数への変換問題と考えられる,と考えた次第です.

    キャンセル

  • 2015/07/13 14:40

    あ,Nちょうどっておっしゃられてますね.失礼しました.
    であれば,1000 --> 10となるようなタッチが存在するということでしょうか?

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3576questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    420questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。