// C++11
//
// 最終方針:
// notePlayで一定回数回して期待値を出す
// 回数は maxTime / noteTime に比例させた
// 各スロットで出てきた3文字の文字列は重複をカウントして保存
// あり得る最も短い文字列であると仮定する
// 前後で2つ重複できるものをペアにする
// 上記以外で1つ重複できるものをペアにする
// ペアの作り方は複数あるが、重複部分の文字列は一意になるので、重複を排除してカウントした文字の出現数も一意になる
// 最も短い文字列の文字数が3つのスロットで一致したら、確定とする
// 文字数が足りない分は出現していないと思われるので、適当に埋める
// 基本は元の出現確率 {2, 4, 5, 6, 6, 7, 8} / 38.0
// 1文字だけ足りない場合は、1つ重複させた部分が重なっていないか、重複させれてない部分の間に何かがあると見なす
// 各台の 期待値 * 閾値 < 最も高い台の期待値 なら切り捨て
// 最低限の回数を回せない場合は適当にquickPlay
// 期待値が最も高い台でquickPlayを最後までやる
// 期待値が閾値以下の場合は何もせずに終了
//
// やったこと:
// テスターがなかったので、埋め込んだ
// デバッガも埋め込めたので、今後はたぶん毎回やる
// デバッガは3種類
// DEBUG 1万回のプレイをしてスコアを出す
// 数秒で終わる
// DEBUG2 1回のプレイで詳細を出力
// DEBUG3 パラメータをグリッドサーチしてどれがいいか探す
// 至る所に埋め込まれてる変な定数はこれをやった結果
// パラメータ調整していないしていないのと比べると3%以上は違う感じ
// 実装の追加とパラメータ調整を交互にやってたので、単純な比較はできてないけど
// スコア計算
// 事前に[何もしない, どれかにquickPlayを最大回数やる]の最大値を保存しておく
// Σ min(結果のコイン / 最大値, 1.0)
//
// 感想など:
// 暫定結果は 857466.02 で5位だけど、下がることはありそう
// ローカルでのスコアは8727とかになっているので、最高でもこの値
// デバッガを埋め込んだのが便利で、こういうのをちゃんとやるのがMMの戦いには必須なのだと認識した
// 処理時間がかかってないおらず、pythonチャンスなので書き換えようかとも思ったけど、面倒になったのでやめた
//
#define DEBUG
#define _DEBUG2
#define _DEBUG3
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cmath>
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <bitset>
#ifdef DEBUG3
double t1;
int t2;
#endif
using namespace std;
inline long long GetTSC() {
long long lo, hi;
asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
return lo + (hi << 32);
}
inline double GetSeconds() {
return GetTSC() / 2.8e9;
}
class XRand
{
public:
unsigned int x, y, z, w;
XRand() { init(); }
void init() { x = 314159261; y = 358979323; z = 846264338; w = 327950288; }
unsigned int next() { unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; }
int nextInt(int m) { return (int)(next() % m); }
};
const double TO = 29.0;
const string PT = "AABBBBCCCCCDDDDDDEEEEEEFFFFFFFGGGGGGGG";
const int SCORES[] = {1000, 200, 100, 50, 20, 10, 5};
const int PT_SIZE = 38;
const int MIN_COINS = 100;
const int MAX_COINS = 10000;
const int MIN_MAX_TIME = 100;
const int MAX_MAX_TIME = 10000;
const int MIN_NOTE_TIME = 2;
const int MAX_NOTE_TIME = 10;
const int MIN_MACHINES = 3;
const int MAX_MACHINES = 10;
const int MIN_WHEEL_SIZE = 10;
const int MAX_WHEEL_SIZE = 30;
double starttime, gt;
XRand rnd = XRand();
#ifdef DEBUG
struct XorShift {
uint64_t x = 88172645463325252ULL;
XorShift() {}
void setSeed(uint64_t seed) {
x = seed;
}
uint64_t next() {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
int nextInt(int n) {
uint64_t upper = 0xFFFFFFFFFFFFFFFFULL / n * n;
uint64_t v = next();
while (v >= upper) {
v = next();
}
return v % n;
}
double nextDouble() {
uint64_t v = next() >> 11; // 53bit
return (double)v / (1ULL << 53);
}
};
XorShift xs;
int p_seed, p_coins, s_coins, p_maxTime, p_noteTime, p_numMachines;
int wheels[MAX_MACHINES][3][MAX_WHEEL_SIZE];
int wheel_sizes[MAX_MACHINES];
int pt = 0;
class PlaySlots {
public:
static void init(int i){
p_seed = i;
xs.setSeed(p_seed);
s_coins = p_coins = xs.next() % (MAX_COINS - MIN_COINS + 1) + MIN_COINS;
p_maxTime = xs.next() % (MAX_MAX_TIME - MIN_MAX_TIME + 1) + MIN_MAX_TIME;
p_noteTime = xs.next() % (MAX_NOTE_TIME - MIN_NOTE_TIME + 1) + MIN_NOTE_TIME;
p_numMachines = xs.next() % (MAX_MACHINES - MIN_MACHINES + 1) + MIN_MACHINES;
for(int i=0; i<p_numMachines; i++){
int size = xs.next() % (MAX_WHEEL_SIZE - MIN_WHEEL_SIZE + 1) + MIN_WHEEL_SIZE;
wheel_sizes[i] = size;
for(int j=0; j<3; j++){
auto wheel = wheels[i][j];
for(int k=0; k<size; k++){
wheel[k] = PT[xs.next() % PT_SIZE] - 'A';
}
}
}
}
static void score_print(){
cout << p_seed << " " << p_coins << endl;
}
static void print(){
#ifdef DEBUG2
cerr << "seed: " << p_seed << endl;
cerr << "coins: " << p_coins << endl;
cerr << "maxTime: " << p_maxTime << endl;
cerr << "noteTime: " << p_noteTime << endl;
cerr << "numMachines: " << p_numMachines << endl;
for(int i=0; i<p_numMachines; i++){
cerr << endl;
for(int j=0; j<3; j++){
auto wheel = wheels[i][j];
for(int k=0; k<wheel_sizes[i]; k++){
cerr << char(wheel[k] + 'A');
}
cerr << " " << wheel_sizes[i];
cerr << endl;
}
cerr << setprecision(10) << rate(i) << endl;
}
cerr << endl;
#endif
}
static double rate(int n){
auto size = wheel_sizes[n];
double r = 0.0;
for(int i=0; i<7; i++){
double tr = SCORES[i];
for(int j=0; j<3; j++){
auto wheel = wheels[n][j];
int cc = 0;
for(int k=0; k<size; k++){
if(wheel[k] == i) cc++;
}
tr *= 1.0 * cc / size;
}
r += tr;
}
return r;
}
static int max_rate_id(){
int mi = -1;
double mr = 0;
for(int i=0; i<p_numMachines; i++){
double tr = rate(i);
if(tr > mr){
mr = tr;
mi = i;
}
}
return mi;
}
static int quickPlay(int mi, int n){
pt++;
int r = 0;
auto wheel = wheels[mi];
for(int i=0; i<n; i++){
int c = wheel[0][xs.next() % wheel_sizes[mi]];
int d = wheel[1][xs.next() % wheel_sizes[mi]];
int e = wheel[2][xs.next() % wheel_sizes[mi]];
if(c==d && d==e){
r += SCORES[c];
}
}
p_coins += r - n;
return r;
}
static vector<string> notePlay(int mi, int n){
pt++;
int r = 0;
auto wheel = wheels[mi];
auto size = wheel_sizes[mi];
vector<string> res;
char cs[10] = {};
for(int i=0; i<n; i++){
auto c = xs.next();
auto d = xs.next();
auto e = xs.next();
for(int j=0; j<3; j++){
cs[j*3] = wheel[0][(c+j) % size] + 'A';
cs[j*3+1] = wheel[1][(d+j) % size] + 'A';
cs[j*3+2] = wheel[2][(e+j) % size] + 'A';
}
res.emplace_back(cs);
if(cs[3]==cs[4] && cs[4]==cs[5]){
r += SCORES[cs[3] - 'A'];
}
}
p_coins += r - n;
auto it = res.begin();
res.insert(it, to_string(r));
return res;
}
};
#endif
class BrokenSlotMachines {
public:
int playSlots(int coins, int maxTime, int noteTime, int numMachines) {
starttime = GetSeconds();
double RS[11] = {};
int RT[11][3] = {};
int RTM[11] = {};
int RC[11][3][8] = {};
char RSS[11][3][31][4] = {};
char RSI[11][3] = {};
bool RE[11] = {};
double CR[7] = {2, 4, 5, 6, 6, 7, 8};
for(int i=0; i<7; i++){
CR[i] /= 38.0;
}
int min_n = 4 + maxTime / noteTime / 199;
int max_n = 13 + maxTime / noteTime / 53;
int tt = 0;
int mi = -1;
int start_coins = coins;
if(maxTime < noteTime * min_n * numMachines){
for(; tt<maxTime; ){
if(coins < 1) break;
int res = PlaySlots::quickPlay((mi<0 ? tt%numMachines : mi), 1);
tt += 1;
coins += res - 1;
if(res>9){
mi = tt%numMachines;
}
}
return mi;
}
vector<int> cur;
for(int i=0; i<numMachines; i++){
cur.emplace_back(i);
}
int ct = 0;
for(; (tt+cur.size())*noteTime<=maxTime && ct < max_n; ){
ct++;
if(cur.size() == 1){
mi = cur[0];
break;
}else if(cur.size() == 0){
mi = -1;
break;
}
if(coins < cur.size()) break;
for(const auto &ti: cur){
if(RE[ti]) continue;
auto rc = RC[ti];
auto rsi = RSI[ti];
auto resv = PlaySlots::notePlay(ti, 1);
int res = stoi(resv[0]);
int rr = 0;
for(int i=0; i<3; i++){
auto rss = RSS[ti][i];
bool rf = 0;
for(int j=0; j<rsi[i]; j++){
bool rjf = 1;
for(int k=0; k<3; k++){
if(resv[1][k*3+i] != rss[j][k]){
rjf = 0;
break;
}
}
if(rjf){
rf = 1;
rss[j][3]++;
break;
}
}
if(rf) continue;
for(int j=0; j<3; j++){
rss[rsi[i]][j] = resv[1][j*3+i];
}
rss[rsi[i]][3] = 1;
rsi[i]++;
for(int j=0; j<3; j++){
char c = resv[1][i*3+j];
rc[i][c-'A']++;
}
RT[ti][i] += 1;
}
tt++;
coins += res - 1;
}
if(ct >= min_n){
double tm = 0;
for(const auto &ti: cur){
double tmp = 0;
auto rc = RC[ti];
bool RELS[3][31][4] = {};
int KN[3][8] = {};
int KC[3] = {};
for(int i=0; i<3; i++){
auto rss = RSS[ti][i];
auto rsi = RSI[ti][i];
auto rel = RELS[i];
int mm = -1;
int tm = 0;
for(int j=0; j<rsi; j++){
for(int ki=1; ki<rsi; ki++){
int k = (j+ki) % rsi;
if(rel[j][0] || rel[k][1]) continue;
if(rss[j][1] == rss[k][0] && rss[j][2] == rss[k][1]){
rel[j][0] = 1;
rel[k][1] = 1;
tm++;
}
}
}
for(int j=0; j<rsi; j++){
for(int ki=1; ki<rsi; ki++){
int k = (j+ki) % rsi;
if(rel[j][0] || rel[k][1] || rel[j][2] || rel[k][3]) continue;
if(rss[j][2] == rss[k][0]){
rel[j][2] = 1;
rel[k][3] = 1;
}
}
}
for(int j=0; j<8; j++){
rc[i][j] = 0;
}
RT[ti][i] = 0;
for(int j=0; j<rsi; j++){
rc[i][rss[j][0] - 'A']++;
RT[ti][i]++;
if(rel[j][0]) continue;
rc[i][rss[j][1] - 'A']++;
RT[ti][i]++;
if(rel[j][2]) continue;
rc[i][rss[j][2] - 'A']++;
RT[ti][i]++;
}
}
if(RT[ti][0] > 9 && RT[ti][0] == RT[ti][1] && RT[ti][0] == RT[ti][2]){
RE[ti] = 1;
RTM[ti] = RT[ti][0];
}else{
RTM[ti] = max(RT[ti][0], max(RT[ti][1], RT[ti][2]));
}
for(int i=0; i<3; i++){
if(RT[ti][i] != RTM[ti] - 1) continue;
auto rss = RSS[ti][i];
auto rsi = RSI[ti][i];
auto rel = RELS[i];
auto kn = KN[i];
bool kf[7] = {};
for(int j=0; j<rsi; j++){
if(rel[j][2]) kf[rss[j][2] - 'A'] = 1;
if(rel[j][3]) kf[rss[j][0] - 'A'] = 1;
}
for(int j=0; j<rsi; j++){
if(!rel[j][0] && kf[rss[j][2] - 'A']){
kn[rss[j][2] - 'A'] += 1;
for(int k=0; k<rsi; k++){
if(rss[k][0] == rss[j][1] && rss[k][1] == rss[j][2] && rss[k][2] == rss[j][2]){
kn[rss[j][2] - 'A'] += int(rss[k][3]);
}
}
}
if(!rel[j][1] && kf[rss[j][0] - 'A']){
kn[rss[j][0] - 'A'] += 1;
for(int k=0; k<rsi; k++){
if(rss[k][0] == rss[j][0] && rss[k][1] == rss[j][0] && rss[k][2] == rss[j][1]){
kn[rss[j][0] - 'A'] += int(rss[k][3]);
}
}
}
}
for(int j=0; j<7; j++){
kn[j] *= 122;
}
for(int j=0; j<rsi; j++){
if(rel[j][0] || rel[j][2]) continue;
for(int k=0; k<rsi; k++){
if(rel[k][1] || rel[k][3]) continue;
for(int l=0; l<7; l++){
kn[l] += 1;
}
for(int l=0; l<rsi; l++){
if(rss[l][0] == rss[j][2] && rss[l][2] == rss[k][0]){
kn[rss[l][1] - 'A'] += int(rss[l][3]) * 23;
}
}
}
}
}
for(int j=0; j<3; j++){
KC[j] = 0;
for(int k=0; k<7; k++){
KC[j] += KN[j][k];
}
for(int k=0; k<7; k++){
if(1.0 * KN[j][k] / KC[j] > 0.981){
for(int l=0; l<7; l++){
KN[j][k] = l==k;
}
KC[j] = 1;
rc[j][k] += 1;
RT[ti][j] += 1;
break;
}
}
}
for(int i=0; i<7; i++){
double tc = SCORES[i] + 1;
for(int j=0; j<3; j++){
double rts = RTM[ti] - RT[ti][j];
if(KC[j]>0){
tc *= 1.0 * (rc[j][i] + rts * KN[j][i] / KC[j] / 2.34) / (RTM[ti] - rts / 2.34);
}else{
tc *= 1.0 * (rc[j][i] + rts * CR[i] / 1.82) / (RTM[ti] - rts / 1.82);
}
}
tmp += tc;
}
if(tmp > tm){
tm = tmp;
mi = ti;
}
RS[ti] = tmp;
}
if(ct >= min_n){
vector<int> next;
for(const auto &ti: cur){
if(RS[ti] * (RE[mi] ? 1.38 : 2.18) < RS[mi]) continue;
next.emplace_back(ti);
}
cur = next;
}
}
}
tt *= noteTime;
int htt = tt;
#ifdef DEBUG2
cerr << "htt: " << htt << " coins: " << coins << endl;
#endif
if(mi >= 0 && RS[mi] > 1.13){
for(; tt<maxTime; ){
if(coins < 1) break;
int res = PlaySlots::quickPlay(mi, 1);
tt += 1;
coins += res - 1;
}
}
#ifdef DEBUG2
cerr << coins << " mi: " << mi << " htt: " << htt << " tt: " << tt << " time: " << (GetSeconds()-starttime) << endl;
for(int i=0; i<numMachines; i++){
cerr << i << ": " << RS[i] << ", (" << RT[i][0] << ", " << RT[i][1] << ", " << RT[i][2] << ")" << endl;
}
#endif
return mi;
}
};
#ifdef DEBUG
#ifdef DEBUG2
const int TEST_MAX = 1;
#else
const int TEST_MAX = 10000;
#endif
int main() {
srand((unsigned) time(NULL));
rand();
auto bsm = BrokenSlotMachines();
int max_scores[TEST_MAX+1] = {};
ifstream ifs("./max_score.txt");
int seed, score;
for(int i=1; i<=TEST_MAX; i++){
ifs >> seed >> score;
max_scores[seed] = score;
}
double m_rate = 0;
#ifdef DEBUG3
for(t1=1.15; t1<=1.16; t1+=0.01) for(t2=0; t2<=0; t2+=1){
#endif
int hit = 0;
int m1 = 0;
int m2 = 0;
int over = 0;
double os = 0;
double rate_score = 0;
for(int i=1; i<=TEST_MAX; i++){
#ifdef DEBUG2
PlaySlots::init(rand());
#else
PlaySlots::init(i);
#endif
PlaySlots::print();
int mp_coins = p_coins;
int mi = bsm.playSlots(p_coins, p_maxTime, p_noteTime, p_numMachines);
if(mi < 0) m1++;
if(mi == PlaySlots::max_rate_id()) hit++;
#ifdef DEBUG2
PlaySlots::score_print();
}
#else
double score = 1.0 * p_coins / max_scores[i];
rate_score += score;
if(score > 1){
over++;
os += score - 1;
}
if(score < 0.1){
m2++;
}
#ifdef DEBUG3
}
if(m_rate < rate_score - os){
m_rate = rate_score - os;
cerr << t1 << ", " << t2 << ": " << rate_score - os << " os: " << os << " MAX!!" << endl;
}else{
cerr << t1 << ", " << t2 << ": " << rate_score - os << " os: " << os << endl;
}
}
#else
if(i%1000==1){
cerr << i << " " << (rate_score-os) << " hit: " << hit << " m1: " << m1 << " m2: " << m2 << " over: " << over << " os: " << os << endl;
}
}
cerr << "rate_score: " << (rate_score-os) << " hit: " << hit << " m1: " << m1 << " m2: " << m2 << " over: " << over << " os: " << os << endl;
#endif
#endif
return 0;
}
#endif