#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print_array(const char* name, const vector<int>& a) {
    cout << name << "=";
    for (int i = 0; i < int(a.size()); ++i) {
        if (i > 0) cout << ",";
        cout << a[i];
    }
    cout << "\n";
}

int main() {
    const bool swap_move = true;
    const int item = 1;
    const int other = 4;
    const int destination = 2;
    const bool exact_two = true;
    vector<int> current = {0, 0, 1, 1, 2, 2};
    vector<int> candidate = current;
    if (swap_move) swap(candidate[item], candidate[other]);
    else candidate[item] = destination;
    vector<int> counts(3, 0);
    for (int person : candidate) ++counts[person];
    bool allowed = true;
    if (exact_two) {
        for (int count : counts) if (count != 2) allowed = false;
    }
    print_array("before", current);
    print_array("candidate", candidate);
    print_array("counts", counts);
    cout << "allowed=" << allowed << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print_array(const char* name, const vector<int>& a) {
    cout << name << "=";
    for (int i = 0; i < int(a.size()); ++i) {
        if (i > 0) cout << ",";
        cout << a[i];
    }
    cout << "\n";
}

const vector<int> weight = {8, 7, 6, 5, 4, 3};

vector<int> get_load(const vector<int>& assign) {
    vector<int> load(3, 0);
    for (int job = 0; job < int(weight.size()); ++job) {
        load[assign[job]] += weight[job];
    }
    return load;
}

int score(const vector<int>& assign) {
    vector<int> load = get_load(assign);
    int value = 0;
    for (int total : load) value += total * total;
    return value;
}

int main() {
    const int trials = 60;
    const bool with_swap = false;
    const bool exact_two = false;
    vector<int> current = {0, 0, 1, 1, 2, 2};
    int current_value = score(current);
    // {種類, 仕事番号, 移動先または交換相手}。0は移動、1は交換。
    vector<vector<int>> moves;
    for (int job = 0; job < 6; ++job) {
        for (int person = 0; person < 3; ++person) moves.push_back({0, job, person});
    }
    if (with_swap) {
        for (int a = 0; a < 6; ++a) {
            for (int b = a + 1; b < 6; ++b) moves.push_back({1, a, b});
        }
    }
    for (int step = 0; step < trials; ++step) {
        vector<int> move = moves[step % moves.size()];
        vector<int> candidate = current; // コピー側だけを変更する。
        if (move[0] == 0) candidate[move[1]] = move[2];
        else swap(candidate[move[1]], candidate[move[2]]);
        vector<int> counts(3, 0);
        for (int person : candidate) ++counts[person];
        bool allowed = true;
        if (exact_two) {
            for (int count : counts) if (count != 2) allowed = false;
        }
        // -1はルール違反で計算しない目印。答えの値として比べない。
        int value = allowed ? score(candidate) : -1;
        int before = current_value;
        bool accepted = allowed && value < current_value;
        if (accepted) {
            current = candidate;
            current_value = value;
        }
        cout << "step=" << step + 1 << "," << before << "," << value << ","
             << allowed << "," << accepted << "," << current_value << "\n";
    }
    print_array("assign", current);
    cout << "score=" << current_value << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print_array(const char* name, const vector<int>& a) {
    cout << name << "=";
    for (int i = 0; i < int(a.size()); ++i) {
        if (i > 0) cout << ",";
        cout << a[i];
    }
    cout << "\n";
}

const vector<int> weight = {8, 7, 6, 5, 4, 3};

vector<int> get_load(const vector<int>& assign) {
    vector<int> load(3, 0);
    for (int job = 0; job < int(weight.size()); ++job) {
        load[assign[job]] += weight[job];
    }
    return load;
}

int score(const vector<int>& assign) {
    vector<int> load = get_load(assign);
    int value = 0;
    for (int total : load) value += total * total;
    return value;
}

struct State {
    vector<int> assign;
    vector<int> load;
};

struct Undo {
    int item, from, to;
    int old_from_load, old_to_load;
};

Undo apply(State& state, int item, int to) {
    // この教材の設定ではitemとtoは範囲内。記録は書き換え前に作る。
    const int from = state.assign[item];
    Undo log{item, from, to, state.load[from], state.load[to]};
    state.assign[item] = to;
    state.load[from] -= weight[item];
    state.load[to] += weight[item];
    return log;
}

void undo(State& state, const Undo& log, bool restore_load) {
    state.assign[log.item] = log.from;
    // falseは更新漏れを観察するための、意図した不具合。
    if (restore_load) {
        state.load[log.from] = log.old_from_load;
        state.load[log.to] = log.old_to_load;
    }
}

int main() {
    const int item = 1;
    const int destination = 2;
    const bool restore_load = true;
    vector<int> initial = {0, 0, 1, 1, 2, 2};
    State state{initial, get_load(initial)};
    const State before = state; // 検証用。探索で毎回コピーする必要はない。
    print_array("before_assign", state.assign);
    print_array("before_load", state.load);
    Undo log = apply(state, item, destination);
    print_array("trial_assign", state.assign);
    print_array("trial_load", state.load);
    undo(state, log, restore_load);
    print_array("after_assign", state.assign);
    print_array("after_load", state.load);
    cout << "consistent=" << (state.load == get_load(state.assign)) << "\n";
    cout << "restored=" << (state.assign == before.assign && state.load == before.load) << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print_array(const char* name, const vector<int>& a) {
    cout << name << "=";
    for (int i = 0; i < int(a.size()); ++i) {
        if (i > 0) cout << ",";
        cout << a[i];
    }
    cout << "\n";
}

const vector<int> weight = {8, 7, 6, 5, 4, 3};

vector<int> get_load(const vector<int>& assign) {
    vector<int> load(3, 0);
    for (int job = 0; job < int(weight.size()); ++job) {
        load[assign[job]] += weight[job];
    }
    return load;
}

int score(const vector<int>& assign) {
    vector<int> load = get_load(assign);
    int value = 0;
    for (int total : load) value += total * total;
    return value;
}

long long square(long long x) { return x * x; }

long long delta_move(const vector<int>& load, int from, int to,
                     int w, bool include_destination) {
    // 同じ担当者への移動では負荷は変わらない。
    if (from == to) return 0;
    long long delta = square(load[from] - w) - square(load[from]);
    // falseは移動先の寄与を落とす、意図した不具合。
    if (include_destination) {
        delta += square(load[to] + w) - square(load[to]);
    }
    return delta;
}

int main() {
    const int item = 1;
    const int destination = 2;
    const bool include_destination = true;
    vector<int> assign = {0, 0, 1, 1, 2, 2};
    const vector<int> load = get_load(assign);
    const long long before = score(assign);
    const long long delta = delta_move(load, assign[item], destination,
                                      weight[item], include_destination);
    vector<int> candidate = assign;
    candidate[item] = destination;
    const long long full_after = score(candidate); // 差分とは独立に全計算。
    print_array("before_load", load);
    print_array("after_load", get_load(candidate));
    cout << "before=" << before << "\n";
    cout << "delta=" << delta << "\n";
    cout << "predicted_after=" << before + delta << "\n";
    cout << "full_after=" << full_after << "\n";
    cout << "delta_ok=" << (before + delta == full_after) << "\n";
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include <cstdint>
#include <cmath>
#include <iomanip>

void print_array(const char* name, const vector<int>& a) {
    cout << name << "=";
    for (int i = 0; i < int(a.size()); ++i) {
        if (i > 0) cout << ",";
        cout << a[i];
    }
    cout << "\n";
}

const vector<int> weight = {8, 7, 6, 5, 4, 3};

vector<int> get_load(const vector<int>& assign) {
    vector<int> load(3, 0);
    for (int job = 0; job < int(weight.size()); ++job) {
        load[assign[job]] += weight[job];
    }
    return load;
}

int score(const vector<int>& assign) {
    vector<int> load = get_load(assign);
    int value = 0;
    for (int total : load) value += total * total;
    return value;
}

struct Random {
    uint32_t x;
    uint32_t next() {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        return x;
    }
};

struct State {
    vector<int> assign;
    vector<int> load;
};
struct Undo {
    int item, from, to, old_from_load, old_to_load;
};
int delta_move(const State& s, int item, int to) {
    const int from = s.assign[item], w = weight[item];
    if (from == to) return 0;
    const int a = s.load[from], b = s.load[to];
    return (a-w)*(a-w) + (b+w)*(b+w) - a*a - b*b;
}
Undo apply(State& s, int item, int to) {
    const int from = s.assign[item];
    Undo log{item, from, to, s.load[from], s.load[to]};
    s.assign[item] = to;
    s.load[from] -= weight[item];
    s.load[to] += weight[item];
    return log;
}
void undo(State& s, const Undo& log) {
    s.assign[log.item] = log.from;
    s.load[log.from] = log.old_from_load;
    s.load[log.to] = log.old_to_load;
}

int main() {
    const int trials = 120;
    const uint32_t seed = 42;
    const double start_temp = 20, end_temp = 1;
    const bool allow_worse = true;
    vector<int> initial = {0, 1, 2, 1, 2, 0}; // 負荷11,12,10。評価値365。
    State current{initial, get_load(initial)};
    vector<int> best = initial;
    int current_value = score(initial), best_value = current_value;
    int accepted_worse = 0;
    bool consistent = true;
    Random rng{seed};
    cout << fixed << setprecision(6);
    // stepの列: 手数,仕事ID,移動先,差分,温度,採用確率,乱数,採用,current,best
    for (int i = 0; i < trials; ++i) {
        // 比較しやすくするため、改善手でも毎回3回の乱数を消費する。
        const int item = rng.next() % 6;
        const int to = rng.next() % 3;
        const double u = rng.next() / 4294967296.0;
        const double progress = trials == 1 ? 0.0 : double(i) / (trials - 1);
        const double temperature = start_temp + (end_temp - start_temp) * progress;
        const int delta = delta_move(current, item, to);
        const double probability = delta <= 0 ? 1.0 :
            (allow_worse ? exp(-double(delta) / temperature) : 0.0);
        const Undo log = apply(current, item, to);
        const bool take = u < probability;
        if (take) {
            current_value += delta;
            if (delta > 0) ++accepted_worse;
            if (current_value < best_value) {
                best = current.assign;
                best_value = current_value;
            }
        } else {
            undo(current, log);
        }
        // 教材用の照合。高速化の効果を測る版では頻度を減らす。
        consistent = consistent && current.load == get_load(current.assign)
            && current_value == score(current.assign) && best_value == score(best);
        cout << "step=" << i+1 << "," << item << "," << to << "," << delta
             << "," << temperature << "," << probability << "," << u
             << "," << take << "," << current_value << "," << best_value << "\n";
    }
    print_array("current_assign", current.assign);
    print_array("best_assign", best);
    cout << "current_value=" << current_value << "\n";
    cout << "best_value=" << best_value << "\n";
    cout << "accepted_worse=" << accepted_worse << "\n";
    cout << "consistent=" << consistent << "\n";
    return 0;
}

#include <chrono>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    const int n=120, trials=200;
    const bool cached=true, copy_state=true;
    vector<int> weight(n), assign(n);
    vector<long long> load(3,0);
    for(int i=0;i<n;i++){weight[i]=8-i%6;assign[i]=(i/2)%3;load[assign[i]]+=weight[i];}
    long long value=0; for(auto x:load)value+=x*x;
    long long visits=0, copied=0, checksum=0;
    auto start=chrono::steady_clock::now();
    // 探索の採否は入れず、同じ変更列を全て適用して評価計算だけを比べる。
    for(int t=0;t<trials;t++){
        const int item=t%n, to=(t+1)%3, from=assign[item], w=weight[item];
        if(copy_state){vector<int> candidate=assign;copied+=n;candidate[item]=to;assign.swap(candidate);}
        if(cached){
            if(from!=to){
                visits+=2;
                value-=load[from]*load[from]+load[to]*load[to];
                load[from]-=w;load[to]+=w;
                value+=load[from]*load[from]+load[to]*load[to];
            }
            assign[item]=to;
        }else{
            assign[item]=to;load.assign(3,0);
            for(int i=0;i<n;i++){load[assign[i]]+=weight[i];visits++;}
            value=0;for(auto x:load)value+=x*x;
        }
        checksum+=value;
    }
    auto elapsed=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now()-start).count();
    vector<long long> reference(3,0);
    for(int i=0;i<n;i++)reference[assign[i]]+=weight[i];
    long long full=0;for(auto x:reference)full+=x*x;
    cout<<"score="<<value<<"\nchecksum="<<checksum<<"\nvisits="<<visits<<"\ncopied="<<copied
        <<"\nconsistent="<<(reference==load && full==value)<<"\n";
    // 実測時間は環境で変わるため、ページとの照合対象に混ぜない。
    cerr<<"elapsed_us="<<elapsed<<"\n";
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include <cstdlib>

int final_cost(int sum, int target) {
    return abs(sum - target);
}
int evaluate(int sum, int target, int remaining, int mode) {
    if (mode == 0) return final_cost(sum, target);
    if (mode == 1) {
        // 区間[sum, sum+remaining]までの距離。区間内の全値が作れるとは限らない。
        return max({sum - target, 0, target - (sum + remaining)});
    }
    // この小問題では残りが一個なので、二通りを正確に比較できる。
    return min(final_cost(sum, target), final_cost(sum + remaining, target));
}

int main() {
    const int target = 11;
    const int remaining = 5;
    const int mode = 0; // 0:現在の差、1:区間の下界、2:最後の二通りを比較
    const vector<int> partial = {8, 6}; // A:8だけを選択、B:6だけを選択した途中状態。
    vector<int> evaluation, completed_sum, completed_cost;
    for (int sum : partial) {
        const int value = evaluate(sum, target, remaining, mode);
        const bool take = final_cost(sum + remaining, target) < final_cost(sum, target);
        const int finished = sum + (take ? remaining : 0);
        evaluation.push_back(value);
        completed_sum.push_back(finished);
        completed_cost.push_back(final_cost(finished, target));
        cout << "candidate=" << sum << "," << value << "," << finished
             << "," << completed_cost.back() << "\n";
    }
    // 評価が同点ならAを残す。最終誤差を見て選び直さない。
    const int chosen = evaluation[1] < evaluation[0] ? 1 : 0;
    const int reference = min(completed_cost[0], completed_cost[1]);
    cout << "chosen=" << (chosen == 0 ? "A" : "B") << "\n";
    cout << "evaluation=" << evaluation[chosen] << "\n";
    cout << "final_sum=" << completed_sum[chosen] << "\n";
    cout << "final_error=" << completed_cost[chosen] << "\n";
    cout << "reference_error=" << reference << "\n";
    cout << "kept_best=" << (completed_cost[chosen] == reference) << "\n";
    return 0;
}

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

// 各数を「選ぶ / 選ばない」で、合計を TARGET に近づけます。
// この小例は、途中評価による枝の選択を学ぶためのものです。
const std::vector<int> VALUES = { 8, 6, 5 };
constexpr int TARGET = 11;
constexpr int WIDTH = 3;

struct State {
    int sum;
    std::string path; // この段階では履歴をコピー。0=選ばない、1=選ぶ。
};

bool better(const State& a, const State& b) {
    const int ca = std::abs(TARGET - a.sum), cb = std::abs(TARGET - b.sum);
    if (ca != cb) return ca < cb;
    return a.path < b.path; // 同点の扱いも固定して再現します。
}

int main() {
    if (VALUES.empty() || VALUES.size() > 8 || TARGET < 0 || TARGET > 80 ||
        WIDTH < 1 || WIDTH > 6) {
        std::cerr << "Invalid experiment settings\n";
        return 1;
    }
    for (int value : VALUES) if (value < 1 || value > 20) {
        std::cerr << "Use values from 1 to 20\n";
        return 1;
    }
    std::vector<State> beam = {{0, ""}};
    int step = 0;
    for (int value : VALUES) {
        std::vector<State> next;
        for (const State& state : beam) {
            next.push_back({state.sum, state.path + "0"});
            next.push_back({state.sum + value, state.path + "1"});
        }
        std::sort(next.begin(), next.end(), better);
        if (int(next.size()) > WIDTH) next.resize(WIDTH);
        beam = next;
        ++step;
        std::cout << "step=" << step << " sums=";
        for (int i = 0; i < int(beam.size()); ++i) {
            if (i) std::cout << ',';
            std::cout << beam[i].sum;
        }
        std::cout << '\n';
    }
    std::cout << "best_sum=" << beam.front().sum << '\n';
    std::cout << "error=" << std::abs(TARGET - beam.front().sum) << '\n';
    std::cout << "path=" << beam.front().path << '\n';
}

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
struct Node{int sum,parent,bit;};
int main(){
    const int width=3, buckets=1, target=11;
    const bool exact=true;
    const vector<int> values={8,6,5,5};
    vector<Node> pool={{0,-1,-1}}; vector<int> beam={0};
    int duplicates=0, collisions=0;
    for(int step=0;step<int(values.size());step++){
        vector<int> next;map<int,vector<int>> seen;
        for(int parent:beam)for(int bit=0;bit<2;bit++){
            Node node{pool[parent].sum+bit*values[step],parent,bit};
            int id=pool.size();pool.push_back(node);
            auto& bucket=seen[node.sum%buckets];bool duplicate=false;
            for(int other:bucket){
                if(pool[other].sum==node.sum){duplicate=true;break;}
                collisions++;
                if(!exact){duplicate=true;break;} // 意図した誤り：ハッシュ一致だけで消す。
            }
            if(duplicate){duplicates++;continue;}
            bucket.push_back(id);next.push_back(id);
        }
        sort(next.begin(),next.end(),[&](int a,int b){
            int x=abs(pool[a].sum-target), y=abs(pool[b].sum-target);
            return x!=y?x<y:a<b;
        });
        if(int(next.size())>width)next.resize(width);
        beam=next;
        cout<<"layer="<<step+1<<","<<pool.size()<<","<<beam.size()<<"\n";
    }
    int best=beam.front();string path;
    for(int id=best;pool[id].parent!=-1;id=pool[id].parent)path+=char('0'+pool[id].bit);
    reverse(path.begin(),path.end());int replay=0;
    for(int i=0;i<int(values.size());i++)replay+=(path[i]-'0')*values[i];
    cout<<"path="<<path<<"\nsum="<<pool[best].sum<<"\nerror="<<abs(pool[best].sum-target)
        <<"\nduplicates="<<duplicates<<"\ncollisions="<<collisions
        <<"\nreplay_ok="<<(replay==pool[best].sum)<<"\n";
}

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
struct Node{int parent,group,score,finished;};
int main(){
    const int width=3, cap=1, scenario=0;
    // ID0が根、1〜3が共通の親、4〜9が比較する候補。
    vector<Node> pool={{-1,-1,0,0},{0,0,0,0},{0,1,0,0},{0,2,0,0},
        {1,0,10,30},{1,0,11,scenario?5:31},{1,0,12,32},
        {2,1,13,8},{2,1,14,9},{3,2,15,7}};
    vector<int> kept,counts(3,0);
    for(int id=4;id<10;id++){
        int g=pool[id].group;if(cap>0 && counts[g]>=cap)continue;
        kept.push_back(id);counts[g]++;if(int(kept.size())==width)break;
    }
    set<int> alive;int best=1000;
    for(int id:kept){best=min(best,pool[id].finished);for(int p=id;p!=-1;p=pool[p].parent)alive.insert(p);}
    cout<<"kept=";for(int i=0;i<int(kept.size());i++){if(i)cout<<",";cout<<kept[i];}
    cout<<"\ngroups="<<counts[0]<<","<<counts[1]<<","<<counts[2]
        <<"\nallocated_nodes="<<pool.size()<<"\nlive_nodes="<<alive.size()<<"\ncopied_history_nodes="<<3*kept.size()
        <<"\nfinished_best="<<best<<"\n";
}

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
enum Color { RED=0, BLUE=1 };
const char* color_name(int c){return c==RED?"RED":c==BLUE?"BLUE":"NONE";}
struct Judge {
    virtual int ask()=0;
    virtual void finish(int answer)=0;
    virtual ~Judge()=default;
};
class MockJudge:public Judge {
    int truth,flip,available,turn=0; // 箱の中の色と未来の返事はソルバから見えない。
public:
    MockJudge(int truth,int flip,int available):truth(truth),flip(flip),available(available){}
    int ask() override {
        cout<<"send=?\n";
        if(turn>=available){cout<<"recv=EOF\n";return -1;}
        int reply=(turn++==flip)?1-truth:truth;
        cout<<"recv="<<color_name(reply)<<"\n";return reply;
    }
    void finish(int answer) override {cout<<"send=!"<<color_name(answer)<<"\n";}
};
// この教材の ? / ! 形式の通信アダプタ。本番では問題の形式へ合わせる。
struct StreamJudge:Judge {
    int ask() override {
        cout<<"?\n"<<flush;string y;if(!(cin>>y))return -1;
        if(y=="RED")return RED;if(y=="BLUE")return BLUE;return -1;
    }
    void finish(int answer) override {cout<<"! "<<color_name(answer)<<"\n"<<flush;}
};
struct Result{int answer,queries;bool aborted;};
Result solve(Judge& judge,int budget){
    int reds=0,blues=0,queries=0;
    while(queries<budget){
        queries++;int y=judge.ask();
        if(y!=RED && y!=BLUE)return {-1,queries,true};
        if(y==RED)reds++;else blues++;
    }
    int answer=reds>=blues?RED:BLUE; // 同数・観測なしは固定の基準回答RED。
    judge.finish(answer);return {answer,queries,false};
}
int main(){
    const int truth=1, budget=3, flip=1, available=5;
    MockJudge judge(truth,flip,available);
    Result r=solve(judge,budget);
    cout<<"queries="<<r.queries<<"\nanswer="<<color_name(r.answer)<<"\naborted="<<r.aborted<<"\n";
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include <cmath>
#include <iomanip>
#include <limits>

enum Color { RED=0, BLUE=1 };
const char* color_name(int c) { return c==RED ? "RED" : "BLUE"; }
int main() {
    const double prior_red = 50 / 100.0;
    const double accuracy = 75 / 100.0;
    const int sequence = 3;
    // 観測済みの返事だけを入力にする。隠れた真値は使わない。
    const vector<vector<int>> examples = {
        {RED}, {RED,RED}, {RED,BLUE}, {RED,RED,BLUE}, {BLUE,BLUE,RED},
        {RED,RED,RED,RED,RED,RED,RED,RED,BLUE,BLUE,BLUE,BLUE,BLUE,BLUE,BLUE,BLUE}
    };
    vector<double> log_probability = {log(prior_red), log(1.0-prior_red)};
    vector<double> posterior = {prior_red, 1.0-prior_red}; // 赤、青の順
    const double negative_infinity = -numeric_limits<double>::infinity();
    int mismatch_at = 0, used = 0;
    cout << fixed << setprecision(6);
    for (int reply : examples[sequence]) {
        ++used;
        const double likelihood_red = reply == RED ? accuracy : 1.0-accuracy;
        const double likelihood_blue = reply == BLUE ? accuracy : 1.0-accuracy;
        const double a = log_probability[0] +
            (likelihood_red > 0 ? log(likelihood_red) : negative_infinity);
        const double b = log_probability[1] +
            (likelihood_blue > 0 ? log(likelihood_blue) : negative_infinity);
        const double top = max(a, b);
        if (!isfinite(top)) {
            mismatch_at = used; // 全仮説で確率0。正規化せず、モデルの矛盾を報告。
            break;
        }
        const double log_normalizer = top + log(exp(a-top) + exp(b-top));
        log_probability = {a-log_normalizer, b-log_normalizer};
        posterior = {exp(log_probability[0]), exp(log_probability[1])};
        cout << "step=" << used << "," << color_name(reply) << "," << exp(log_normalizer)
             << "," << posterior[0] << "," << posterior[1] << "\n";
    }
    cout << "mismatch_at=" << mismatch_at << "\n";
    if (mismatch_at) {
        cout << "posterior=NOT_DEFINED\n";
    } else {
        cout << "posterior=" << posterior[0] << "," << posterior[1] << "\n";
        // 数値的な同率は同率として扱い、微小な丸め誤差で断定しない。
        cout << "favours_red=" << (posterior[0] > posterior[1] + 1e-12) << "\n";
    }
    return 0;
}

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
enum Color { RED=0, BLUE=1 };
const char* color_name(int c){return c==RED?"RED":"BLUE";}
double entropy(double p){return (p>0?-p*log2(p):0)+(p<1?-(1-p)*log2(1-p):0);}
int main(){
    const double p=50/100.0, loss=10; // p = カードが赤である事前確率
    const vector<double> accuracies={.75,.9},costs={ 1, 2 };
    vector<double> risk={loss*min(p,1-p)};
    cout<<fixed<<setprecision(6)<<"stop_risk="<<risk[0]<<"\n";
    for(int i=0;i<2;i++){
        double future_loss=0,expected_entropy=0,q=accuracies[i];
        for(int reply=0;reply<2;reply++){
            double a=p*(reply==RED?q:1-q),b=(1-p)*(reply==BLUE?q:1-q),z=a+b;
            double posterior=a/z;
            future_loss+=loss*min(a,b);
            expected_entropy+=z*entropy(posterior);
            cout<<"branch="<<i<<","<<color_name(reply)<<","<<z<<","<<posterior<<"\n";
        }
        risk.push_back(costs[i]+future_loss);
        cout<<"query="<<i<<","<<risk.back()<<","<<entropy(p)-expected_entropy<<"\n";
    }
    int chosen=0;for(int i=1;i<3;i++)if(risk[i]<risk[chosen]-1e-12)chosen=i;
    cout<<"chosen="<<chosen<<"\nexpected_loss="<<risk[chosen]<<"\n";
}

#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
struct Random{uint32_t x;uint32_t next(){x^=x<<13;x^=x>>17;x^=x<<5;return x;}};
int main(){
    const int budget=40, seed=42;const double c=100/100.0;
    const bool use_ucb=true;
    Random rng{uint32_t(seed)};vector<int> counts(2,0);vector<double> totals(2,0);
    cout<<fixed<<setprecision(6);
    for(int t=0;t<budget;t++){
        int arm;
        if(counts[0]==0)arm=0;else if(counts[1]==0)arm=1;
        else if(!use_ucb)arm=t%2;
        else{
            double a=totals[0]/(8*counts[0])+c*sqrt(log(double(t))/counts[0]);
            double b=totals[1]/(8*counts[1])+c*sqrt(log(double(t))/counts[1]);
            arm=b>a?1:0;
        }
        // 容量3で今の容量2・報酬3を受けるか、次の容量2・報酬8/0を待つか。
        int reward=arm==0?3:(rng.next()/4294967296.0<.5?8:0);
        counts[arm]++;totals[arm]+=reward;
        cout<<"step="<<t+1<<","<<arm<<","<<reward<<","<<counts[0]<<","<<counts[1]<<"\n";
    }
    double a=counts[0]?totals[0]/counts[0]:0,b=counts[1]?totals[1]/counts[1]:0;
    int chosen=counts[1] && b>a?1:0;
    cout<<"counts="<<counts[0]<<","<<counts[1]<<"\nmeans="<<a<<","<<b<<"\nchosen="<<chosen<<"\n";
}