#include <iostream>
#include <string>
#include <random>
#include <unordered_map>
#include <functional>
using namespace std;
const double E = 1e-6;
 
void increaseCounters(unordered_map<int, int>& counters)
{
    for (auto& counter : counters)
        ++counter.second;
}
 
void resetCounters(unordered_map<int, int>& counters)
{
    for (auto& counter : counters)
        counter.second = 0;
}
 
double countInRS(double rate, unordered_map<int, int>& gacha)
{
    const int N = 1000000;
    int totalNum = 0;
    unordered_map<int, int> counters;
    for (auto& p : gacha)counters[p.first] = 0;
    std::random_device rd;
    std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
    std::uniform_real_distribution<> dis(0.0, 1.0);
    for (int i = 0; i < N; ++i)
    {
        bool hit = false;
        //check every counter to see if we hit one of them
        for (auto& p : counters)
        {
            if (!hit && p.second + 1 == p.first)
            {
                int r = rand() % 100;
                if (r < gacha[p.first])
                {
                    ++totalNum;
                    hit = true;
                    break;
                }
            }
        }
        if (hit)
        {
            resetCounters(counters);
            continue;
        }
        double r = dis(gen);
        if (rate - r > E)
        {
            ++totalNum;
            resetCounters(counters);
        }
        else
            increaseCounters(counters);
    }
    return static_cast<double>(totalNum) / static_cast<double>(N);
}
 
double getActualRate(double targetRate, unordered_map<int, int>& gacha)
{
    //actual rate
    double lo = 0, hi = targetRate;
    while (hi - lo > E)
    {
        double mid = (lo + hi) / 2;
        double actualRate = countInRS(mid, gacha);
        if (actualRate - targetRate > E)hi = mid;
        else lo = mid;
        cout << "\t" << to_string(mid) << endl;
    }
    return lo;
}
 
int main()
{
    int N = 10;
    double total = 0;
    //every pair <n, k> represent you have k/100 chance to get this card
    //when you have rolled n - 1 times without getting this card
    unordered_map<int, int> gacha = { {10, 10}, {100, 100} };
    //Run N times, calculate average
    for (int i = 0; i < N; ++i)
    {
        cout << "Iteration " << to_string(i) << " : " << endl;
        double acutalRate = getActualRate(0.015, gacha);
        total += acutalRate;
        cout << "Iteration " << to_string(i) << " end, " << "actual rate : " << to_string(acutalRate) << endl;
    }
    cout << "Average result: " + to_string(total / N) << endl;
    return 0;
}
 
 
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGRvdWJsZSBFID0gMWUtNjsKCnZvaWQgaW5jcmVhc2VDb3VudGVycyh1bm9yZGVyZWRfbWFwPGludCwgaW50PiYgY291bnRlcnMpCnsKICAgIGZvciAoYXV0byYgY291bnRlciA6IGNvdW50ZXJzKQogICAgICAgICsrY291bnRlci5zZWNvbmQ7Cn0KCnZvaWQgcmVzZXRDb3VudGVycyh1bm9yZGVyZWRfbWFwPGludCwgaW50PiYgY291bnRlcnMpCnsKICAgIGZvciAoYXV0byYgY291bnRlciA6IGNvdW50ZXJzKQogICAgICAgIGNvdW50ZXIuc2Vjb25kID0gMDsKfQoKZG91YmxlIGNvdW50SW5SUyhkb3VibGUgcmF0ZSwgdW5vcmRlcmVkX21hcDxpbnQsIGludD4mIGdhY2hhKQp7CiAgICBjb25zdCBpbnQgTiA9IDEwMDAwMDA7CiAgICBpbnQgdG90YWxOdW0gPSAwOwogICAgdW5vcmRlcmVkX21hcDxpbnQsIGludD4gY291bnRlcnM7CiAgICBmb3IgKGF1dG8mIHAgOiBnYWNoYSljb3VudGVyc1twLmZpcnN0XSA9IDA7CiAgICBzdGQ6OnJhbmRvbV9kZXZpY2UgcmQ7CiAgICBzdGQ6Om10MTk5MzcgZ2VuKHJkKCkpOyAvL1N0YW5kYXJkIG1lcnNlbm5lX3R3aXN0ZXJfZW5naW5lIHNlZWRlZCB3aXRoIHJkKCkKICAgIHN0ZDo6dW5pZm9ybV9yZWFsX2Rpc3RyaWJ1dGlvbjw+IGRpcygwLjAsIDEuMCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkKICAgIHsKICAgICAgICBib29sIGhpdCA9IGZhbHNlOwogICAgICAgIC8vY2hlY2sgZXZlcnkgY291bnRlciB0byBzZWUgaWYgd2UgaGl0IG9uZSBvZiB0aGVtCiAgICAgICAgZm9yIChhdXRvJiBwIDogY291bnRlcnMpCiAgICAgICAgewogICAgICAgICAgICBpZiAoIWhpdCAmJiBwLnNlY29uZCArIDEgPT0gcC5maXJzdCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IHIgPSByYW5kKCkgJSAxMDA7CiAgICAgICAgICAgICAgICBpZiAociA8IGdhY2hhW3AuZmlyc3RdKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICsrdG90YWxOdW07CiAgICAgICAgICAgICAgICAgICAgaGl0ID0gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZiAoaGl0KQogICAgICAgIHsKICAgICAgICAgICAgcmVzZXRDb3VudGVycyhjb3VudGVycyk7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICBkb3VibGUgciA9IGRpcyhnZW4pOwogICAgICAgIGlmIChyYXRlIC0gciA+IEUpCiAgICAgICAgewogICAgICAgICAgICArK3RvdGFsTnVtOwogICAgICAgICAgICByZXNldENvdW50ZXJzKGNvdW50ZXJzKTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgICAgICBpbmNyZWFzZUNvdW50ZXJzKGNvdW50ZXJzKTsKICAgIH0KICAgIHJldHVybiBzdGF0aWNfY2FzdDxkb3VibGU+KHRvdGFsTnVtKSAvIHN0YXRpY19jYXN0PGRvdWJsZT4oTik7Cn0KCmRvdWJsZSBnZXRBY3R1YWxSYXRlKGRvdWJsZSB0YXJnZXRSYXRlLCB1bm9yZGVyZWRfbWFwPGludCwgaW50PiYgZ2FjaGEpCnsKICAgIC8vYWN0dWFsIHJhdGUKICAgIGRvdWJsZSBsbyA9IDAsIGhpID0gdGFyZ2V0UmF0ZTsKICAgIHdoaWxlIChoaSAtIGxvID4gRSkKICAgIHsKICAgICAgICBkb3VibGUgbWlkID0gKGxvICsgaGkpIC8gMjsKICAgICAgICBkb3VibGUgYWN0dWFsUmF0ZSA9IGNvdW50SW5SUyhtaWQsIGdhY2hhKTsKICAgICAgICBpZiAoYWN0dWFsUmF0ZSAtIHRhcmdldFJhdGUgPiBFKWhpID0gbWlkOwogICAgICAgIGVsc2UgbG8gPSBtaWQ7CiAgICAgICAgY291dCA8PCAiXHQiIDw8IHRvX3N0cmluZyhtaWQpIDw8IGVuZGw7CiAgICB9CiAgICByZXR1cm4gbG87Cn0KCmludCBtYWluKCkKewogICAgaW50IE4gPSAxMDsKICAgIGRvdWJsZSB0b3RhbCA9IDA7CiAgICAvL2V2ZXJ5IHBhaXIgPG4sIGs+IHJlcHJlc2VudCB5b3UgaGF2ZSBrLzEwMCBjaGFuY2UgdG8gZ2V0IHRoaXMgY2FyZAogICAgLy93aGVuIHlvdSBoYXZlIHJvbGxlZCBuIC0gMSB0aW1lcyB3aXRob3V0IGdldHRpbmcgdGhpcyBjYXJkCiAgICB1bm9yZGVyZWRfbWFwPGludCwgaW50PiBnYWNoYSA9IHsgezEwLCAxMH0sIHsxMDAsIDEwMH0gfTsKICAgIC8vUnVuIE4gdGltZXMsIGNhbGN1bGF0ZSBhdmVyYWdlCiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkKICAgIHsKICAgICAgICBjb3V0IDw8ICJJdGVyYXRpb24gIiA8PCB0b19zdHJpbmcoaSkgPDwgIiA6ICIgPDwgZW5kbDsKICAgICAgICBkb3VibGUgYWN1dGFsUmF0ZSA9IGdldEFjdHVhbFJhdGUoMC4wMTUsIGdhY2hhKTsKICAgICAgICB0b3RhbCArPSBhY3V0YWxSYXRlOwogICAgICAgIGNvdXQgPDwgIkl0ZXJhdGlvbiAiIDw8IHRvX3N0cmluZyhpKSA8PCAiIGVuZCwgIiA8PCAiYWN0dWFsIHJhdGUgOiAiIDw8IHRvX3N0cmluZyhhY3V0YWxSYXRlKSA8PCBlbmRsOwogICAgfQogICAgY291dCA8PCAiQXZlcmFnZSByZXN1bHQ6ICIgKyB0b19zdHJpbmcodG90YWwgLyBOKSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0KCgo=