結果
| 問題 |
No.5003 物理好きクリッカー
|
| コンテスト | |
| ユーザー |
 siman
|
| 提出日時 | 2018-12-07 04:34:36 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 758 ms / 10,000 ms |
| コード長 | 20,839 bytes |
| コンパイル時間 | 860 ms |
| 実行使用メモリ | 21,900 KB |
| スコア | 249,110,278,498 |
| 平均クエリ数 | 10000.00 |
| 最終ジャッジ日時 | 2021-07-19 09:02:24 |
| 合計ジャッジ時間 | 27,032 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 |
ソースコード
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
#include <string.h>
typedef long long ll;
using namespace std;
const int N = 10000;
const int NOTHING = -1;
const int CLICK = 0;
const int BUY = 1;
const int SELL = 2;
const int REINFORCE = 3;
const int ENHCLICK = 4;
const int BUY_HAND = 5;
const int BUY_LILY = 6;
const int BUY_FACTORY = 7;
const int BUY_CASINO = 8;
const int BUY_GRIMOIRE = 9;
const int BUY_NEXT = 10;
const int BUY_SAME = 11;
const int UPDATE_HAND = 12;
const int UPDATE_LILY = 13;
const int UPDATE_FACTORY = 14;
const int UPDATE_CASINO = 15;
const int UPDATE_GRIMOIRE = 16;
const int UPGRADE_FACTORY = 17;
const int HAND = 1;
const int LILY = 2;
const int FACTORY = 3;
const int CASINO = 4;
const int GRIMOIRE = 5;
const int BUY_OPERATIONS[7] = {
NOTHING,
BUY_HAND,
BUY_LILY,
BUY_FACTORY,
BUY_CASINO,
BUY_GRIMOIRE,
NOTHING
};
const int UPDATE_OPERATIONS[7] = {
NOTHING,
UPDATE_HAND,
UPDATE_LILY,
UPDATE_FACTORY,
UPDATE_CASINO,
UPDATE_GRIMOIRE,
NOTHING
};
const int BONUS = 1;
const int FEVER = 2;
const int SALE = 3;
const int PRODUCTIVITY[6] = {
1,
1,
10,
120,
2000,
25000
};
const ll UPDATE_COST[6][6] = {
{
15,
150,
1500,
15000,
150000,
1500000
},
{
150,
1500,
15000,
150000,
1500000,
15000000
},
{
2000,
20000,
200000,
2000000,
20000000,
200000000,
},
{
15,
150,
1500,
15000,
150000,
1500000
},
{
15,
150,
1500,
15000,
150000,
1500000
},
{
15,
150,
1500,
15000,
150000,
1500000
},
};
unsigned long long xor128() {
static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
unsigned long long rt = (rx ^ (rx << 11));
rx = ry;
ry = rz;
rz = rw;
return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}
ll factory_price[7][50];
ll update_cost[7][50];
int operations[N];
int bonus[N + 21];
int OPERATION_LENGTH = 150;
class CookieClicker {
public:
void init(string events) {
memset(operations, CLICK, sizeof(operations));
memset(bonus, NOTHING, sizeof(bonus));
for (int i = 0; i < N; i++) {
switch (events[i]) {
case 'B':
bonus[i] = BONUS;
break;
case 'F':
for (int j = i + 1; j <= i + 20; j++) {
bonus[j] = FEVER;
}
break;
case 'S':
bonus[i + 1] = SALE;
break;
}
}
int prices[6] = {
0,
150,
2000,
30000,
600000,
10000000
};
for (int i = 1; i <= 5; i++) {
ll price = prices[i];
ll cost = 10 * prices[i];
for (int j = 0; j < 19; j++) {
update_cost[i][j] = cost;
cost *= 10;
}
for (int j = 0; j < 50; j++) {
factory_price[i][j] = price;
price = ceil((6 * price) / 5) + 1;
}
}
}
vector<int> firstAnswer() {
vector<int> actions;
actions.push_back(ENHCLICK);
actions.push_back(ENHCLICK);
actions.push_back(BUY_NEXT);
for (int i = 0; i < 10; i++) {
actions.push_back(BUY_SAME);
actions.push_back(NOTHING);
}
actions.push_back(BUY_NEXT);
for (int i = 0; i < 10; i++) {
actions.push_back(BUY_SAME);
actions.push_back(NOTHING);
}
actions.push_back(UPGRADE_FACTORY);
actions.push_back(BUY_NEXT);
for (int i = 0; i < 10; i++) {
actions.push_back(BUY_SAME);
actions.push_back(NOTHING);
}
actions.push_back(UPGRADE_FACTORY);
actions.push_back(BUY_NEXT);
for (int i = 0; i < 10; i++) {
actions.push_back(BUY_SAME);
actions.push_back(NOTHING);
}
actions.push_back(UPGRADE_FACTORY);
actions.push_back(BUY_NEXT);
for (int i = 0; i < 10; i++) {
actions.push_back(BUY_SAME);
actions.push_back(NOTHING);
}
actions.push_back(UPGRADE_FACTORY);
actions.push_back(UPGRADE_FACTORY);
actions.push_back(UPGRADE_FACTORY);
while (actions.size() < OPERATION_LENGTH) {
actions.push_back(NOTHING);
}
assert(actions.size() == OPERATION_LENGTH);
return actions;
}
vector <string> run(string events) {
init(events);
vector<int> bestActions = firstAnswer();
vector<int> actions = bestActions;
ll bestScore = updateAnswer(bestActions);
int opes[2] = {BUY_SAME, UPGRADE_FACTORY};
for (int i = 0; i < 10000; i++) {
int j = xor128() % OPERATION_LENGTH;
int act = actions[j];
if (actions[j] == NOTHING) {
actions[j] = opes[xor128() % 2];
} else if (actions[j] == BUY_SAME) {
actions[j] = (xor128() % 2 == 0) ? NOTHING : UPGRADE_FACTORY;
} else if (actions[j] == UPGRADE_FACTORY) {
actions[j] = (xor128() % 2 == 0) ? NOTHING : BUY_SAME;
} else {
continue;
}
ll score = updateAnswer(actions);
if (bestScore < score) {
cerr << bestScore << endl;
bestScore = score;
bestActions = actions;
} else {
actions[j] = act;
}
}
updateAnswer(bestActions);
vector <string> answer = createAnswer();
return answer;
}
vector <string> createAnswer() {
vector <string> answer;
for (int i = 0; i < N; i++) {
switch (operations[i]) {
case NOTHING:
answer.push_back("nothing");
break;
case CLICK:
answer.push_back("click");
break;
case BUY:
answer.push_back("buy");
break;
case SELL:
break;
case REINFORCE:
break;
case ENHCLICK:
answer.push_back("enhclick");
break;
case BUY_HAND:
answer.push_back("buy hand");
break;
case BUY_LILY:
answer.push_back("buy lily");
break;
case BUY_FACTORY:
answer.push_back("buy factory");
break;
case BUY_CASINO:
answer.push_back("buy casino");
break;
case BUY_GRIMOIRE:
answer.push_back("buy grimoire");
break;
case UPDATE_HAND:
answer.push_back("reinforce hand");
break;
case UPDATE_LILY:
answer.push_back("reinforce lily");
break;
case UPDATE_FACTORY:
answer.push_back("reinforce factory");
break;
case UPDATE_CASINO:
answer.push_back("reinforce casino");
break;
case UPDATE_GRIMOIRE:
answer.push_back("reinforce grimoire");
break;
default:
cerr << operations[i] << endl;
assert(false);
}
}
return answer;
}
ll updateAnswer(vector<int> actions) {
memset(operations, CLICK, sizeof(operations));
int index = 0;
int clickLevel = 0;
int factoryGrade = 0;
ll cookie = 0;
ll productivity = 0;
int clickPower = 1;
ll updateCost;
int clickPoint;
ll price;
int factoryCount[7] = {0, 0, 0, 0, 0, 0, 0};
int factoryLevels[7] = {0, 0, 0, 0, 0, 0, 0};
int nextFactory;
for (int i = 0; i < N; i++) {
if (actions.size() <= index) break;
clickPoint = clickPower;
switch (actions[index]) {
case ENHCLICK:
updateCost = UPDATE_COST[CLICK][clickLevel];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
if (cookie >= updateCost) {
cookie -= updateCost;
clickLevel++;
clickPower *= 2;
operations[i] = ENHCLICK;
index++;
clickPoint = 0;
}
break;
case BUY_LILY:
price = factory_price[LILY][factoryCount[LILY]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
if (cookie >= price) {
cookie -= price;
factoryCount[LILY]++;
productivity += PRODUCTIVITY[LILY];
operations[i] = BUY_LILY;
factoryGrade = max(factoryGrade, LILY);
index++;
clickPoint = 0;
}
break;
case BUY_NEXT:
nextFactory = factoryGrade + 1;
if (nextFactory <= GRIMOIRE) {
price = factory_price[nextFactory][factoryCount[nextFactory]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
if (cookie >= price) {
cookie -= price;
factoryCount[nextFactory]++;
productivity += PRODUCTIVITY[nextFactory];
operations[i] = BUY_OPERATIONS[nextFactory];
factoryGrade = max(factoryGrade, nextFactory);
index++;
clickPoint = 0;
}
} else {
index++;
}
break;
case BUY_SAME:
price = factory_price[factoryGrade][factoryCount[factoryGrade]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
if (cookie >= price) {
cookie -= price;
factoryCount[factoryGrade]++;
productivity += PRODUCTIVITY[factoryGrade] * pow(2, factoryLevels[factoryGrade]);
operations[i] = BUY_OPERATIONS[factoryGrade];
index++;
clickPoint = 0;
}
break;
case UPGRADE_FACTORY:
updateCost = update_cost[factoryGrade][factoryLevels[factoryGrade]];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
assert(factoryCount[factoryGrade] > 0);
if (cookie >= updateCost) {
cookie -= updateCost;
productivity += factoryCount[factoryGrade] * PRODUCTIVITY[factoryGrade] *
pow(2, factoryLevels[factoryGrade]);
operations[i] = UPDATE_OPERATIONS[factoryGrade];
index++;
factoryLevels[factoryGrade]++;
clickPoint = 0;
}
break;
case NOTHING:
index++;
break;
default:
assert(false);
break;
}
switch (bonus[i]) {
case FEVER:
cookie += 7 * (productivity + clickPoint);
break;
case BONUS:
cookie += productivity + clickPoint;
cookie += ceil(cookie * 0.01) - 1;
break;
default:
cookie += productivity + clickPoint;
break;
}
}
return cookie;
}
ll calcScore() {
ll cookie = 0;
int clickPower = 1;
int clickLevel = 0;
int updateCost;
int price;
int factoryCount[6] = {0, 0, 0, 0, 0, 0};
int factoryLevels[6] = {0, 0, 0, 0, 0, 0};
int factoryLevel = 0;
int productivity = 0;
for (int i = 0; i < N; i++) {
switch (operations[i]) {
case NOTHING:
break;
case CLICK:
if (bonus[i] == FEVER) {
cookie += 7 * clickPower;
} else {
cookie += clickPower;
}
break;
case ENHCLICK:
updateCost = UPDATE_COST[CLICK][clickLevel];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
assert(cookie >= updateCost);
cookie -= updateCost;
clickPower *= 2;
clickLevel++;
break;
case BUY_HAND:
price = factory_price[HAND][factoryCount[HAND]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
assert(cookie >= price);
cookie -= price;
factoryLevel = max(factoryLevel, HAND);
factoryCount[HAND]++;
productivity += PRODUCTIVITY[HAND] * pow(2, factoryLevels[HAND]);
break;
case BUY_LILY:
price = factory_price[LILY][factoryCount[LILY]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
assert(cookie >= price);
cookie -= price;
factoryLevel = max(factoryLevel, LILY);
factoryCount[LILY]++;
productivity += PRODUCTIVITY[LILY] * pow(2, factoryLevels[LILY]);
break;
case BUY_FACTORY:
price = factory_price[FACTORY][factoryCount[FACTORY]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
assert(cookie >= price);
cookie -= price;
factoryCount[FACTORY]++;
productivity += PRODUCTIVITY[FACTORY] * pow(2, factoryLevels[FACTORY]);
break;
case BUY_CASINO:
price = factory_price[CASINO][factoryCount[CASINO]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
assert(cookie >= price);
cookie -= price;
factoryCount[CASINO]++;
productivity += PRODUCTIVITY[CASINO] * pow(2, factoryLevels[CASINO]);
break;
case BUY_GRIMOIRE:
price = factory_price[GRIMOIRE][factoryCount[GRIMOIRE]];
if (bonus[i] == SALE) {
price = ceil(price * 0.9) + 1;
}
assert(cookie >= price);
cookie -= price;
factoryCount[GRIMOIRE]++;
productivity += PRODUCTIVITY[GRIMOIRE] * pow(2, factoryLevels[GRIMOIRE]);
break;
case UPDATE_HAND:
updateCost = update_cost[HAND][factoryLevels[HAND]];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
if (cookie >= updateCost) {
cookie -= updateCost;
productivity += factoryCount[HAND] * PRODUCTIVITY[HAND] * pow(2, factoryLevels[HAND]);
factoryLevels[HAND]++;
}
break;
case UPDATE_LILY:
updateCost = update_cost[LILY][factoryLevels[LILY]];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
if (cookie >= updateCost) {
cookie -= updateCost;
productivity += factoryCount[LILY] * PRODUCTIVITY[LILY] * pow(2, factoryLevels[LILY]);
factoryLevels[LILY]++;
}
break;
case UPDATE_FACTORY:
updateCost = update_cost[FACTORY][factoryLevels[FACTORY]];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
if (cookie >= updateCost) {
cookie -= updateCost;
productivity += factoryCount[FACTORY] * PRODUCTIVITY[FACTORY] * pow(2, factoryLevels[FACTORY]);
factoryLevels[FACTORY]++;
}
break;
case UPDATE_CASINO:
updateCost = update_cost[CASINO][factoryLevels[CASINO]];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
if (cookie >= updateCost) {
cookie -= updateCost;
productivity += factoryCount[CASINO] * PRODUCTIVITY[CASINO] * pow(2, factoryLevels[CASINO]);
factoryLevels[CASINO]++;
}
break;
case UPDATE_GRIMOIRE:
updateCost = update_cost[GRIMOIRE][factoryLevels[GRIMOIRE]];
if (bonus[i] == SALE) {
updateCost = ceil(updateCost * 0.9) + 1;
}
if (cookie >= updateCost) {
cookie -= updateCost;
productivity +=
factoryCount[GRIMOIRE] * PRODUCTIVITY[GRIMOIRE] * pow(2, factoryLevels[GRIMOIRE]);
factoryLevels[GRIMOIRE]++;
}
break;
default:
assert(false);
break;
}
switch (bonus[i]) {
case FEVER:
cookie += 7 * productivity;
break;
case BONUS:
cookie += productivity;
cookie += ceil(cookie * 0.01);
break;
default:
cookie += productivity;
break;
}
// fprintf(stderr, "%d: cookie = %d\n", i, cookie);
}
fprintf(stderr, "clickLevel = %d\n", clickLevel);
return cookie;
}
};
int main() {
int n;
string s, res;
CookieClicker cc;
cin >> n;
cin >> s;
vector <string> answer = cc.run(s);
for (int i = 0; i < N; i++) {
cout << answer[i] << endl;
cin >> res;
assert(res[0] == 'o');
}
ll score = cc.calcScore();
fprintf(stderr, "Score = %lld\n", score);
return 0;
}