コーディングテスト練習記録

2022.02.2.12 49日目
白駿1052号(水瓶)
質問する
志敏は水瓶をN個持っている.各水瓶は無限に水を注ぐことができる.最初はすべての水瓶に水が1リットル入っていました.志敏はこの水瓶を別の場所に移す.志敏は一度にK個の水瓶を運ぶことができる.しかし、ジミンは水を無駄にしたくないし、一度の移動よりも多くしたくない.そこで、志敏は水瓶の水を適当に再分配し、K個を超えない空き水瓶を作ろうとする.
水は次のように再分配される.
まず等量の水が入った水瓶を2つ選びます.そして、ある水瓶に別の水瓶のすべての水を入れます.必要なだけ使う.
このような制限のため、K個を超えない空き水瓶をN個で製造することは不可能である可能性がある.幸いなことに、新しい水瓶が買えます.店で買った水瓶に水が1リットル入っている.
例えば、n=3、k=1の場合、3つの水瓶で1つを作ることは不可能である.1本は別の瓶に注ぎ、2リットル入りの水瓶と1リットル入りの水瓶が残っている.店で水瓶を1つ買うと、2リットル入りの水瓶を2つ、最後の4リットル入りの水瓶を2つ作ることができます.
私の答え

水瓶N、一回移動可能な水瓶K、条件:購入した水瓶が最低限

に近い

N 2を2で割った場合、残数が発生するとカウントが増加し、0まで

を繰り返す.

カウントダウンK値と比較すると、カウントダウンが大きいほど、水瓶

を購入する.

カウントダウンがもっと大きい時に水瓶を購入し、N 1を増加し、

を繰り返す.

計数が購入した水瓶の数以下である出力

.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int answer = 0;
        while (true) {
            int count = 0;
            int N2 = N;
            while (N2 != 0) {
                if (N2 % 2 == 1) {
                    count += 1;
                }
                N2 /= 2;
            }
            if (count <= K)
                break;
            N += 1;
            answer += 1;
        }

        System.out.println(answer);
    }
}

考える

バイナリ、ペットボトル1本
Integer.bitCount