あなたは世界中で人気のオープンワールドRPG「原神」をプレイしている。
このゲームでは、キャラクターに装備させることができる「聖遺物」と呼ばれるアイテムが存在する。
聖遺物は、1つにつき3つまたは4つのステータスを持っている。ステータスはそれぞれ、「種類」と「値」を持っている。ステータスの種類には以下の10種類が存在し、同じ聖遺物の中でステータスの種類の重複は存在しない。
聖遺物は、レベルを上げることでステータスを強化させることができる。初期のレベルは0であり、最大5まで上げることができる。聖遺物のレベルを上げるのには経験値が必要であり、現在のレベルによって必要な経験値の量は異なる。それぞれのレベルに必要な経験値の量は以下の通りである。
| レベル | 必要経験値 |
|---|---|
| 0 → 1 | 16300 |
| 1 → 2 | 28425 |
| 2 → 3 | 42425 |
| 3 → 4 | 66150 |
| 4 → 5 | 117175 |
聖遺物のレベルを上げると、ステータスが確率的に上昇する。ステータスの上昇アルゴリズムについては、後の「ステータスの選択・上昇アルゴリズム」に記載する。
さて、あなたは現在所持している聖遺物のレベルを上げ、最強の聖遺物を作り上げたいと考えている。しかし、聖遺物のレベルを上げるための経験値は入手量が限られている。そこで、あなたは聖遺物のレベルを上げるための最適な戦略を考えることにした。
聖遺物の強さは、非公式ながら以下のように定義されるスコアによって表されることが多い。
聖遺物のスコア = 攻撃力 + 会心ダメージ + 会心率 * 2
あなたは現在、N個の聖遺物を所持している。これらの聖遺物は、1からNまでのIDが付けられている。これらの聖遺物をレベルアップさせることで、持っている聖遺物のスコアの最大値をなるべく大きくしたい。
限られた経験値の中でレベルアップを行うための最適な戦略を考え、実装せよ。
F N M E Ei
I_1 L_1 E_1 C_1 s_1_0 s_1_1 s_1_2 ... s_1_9
I_2 L_2 E_2 C_2 s_2_0 s_2_1 s_2_2 ... s_2_9
...
I_M L_M E_M C_M s_M_0 s_M_1 s_M_2 ... s_M_9
I T
0を出力せよ。0 0を出力したものとみなされる。聖遺物の初期ステータスは、以下のアルゴリズムによって決定される。
聖遺物をレベルアップさせると、以下のアルゴリズムによってステータスが確率的に上昇する。
| ステータス | ステータスID | 重率 |
|---|---|---|
| 攻撃力 | 0 | 10 |
| 会心率 | 1 | 7.5 |
| 会心ダメージ | 2 | 7.5 |
| 固定攻撃力 | 3 | 15 |
| 防御力 | 4 | 10 |
| 固定防御力 | 5 | 15 |
| HP | 6 | 10 |
| 固定HP | 7 | 15 |
| 元素チャージ効率 | 8 | 10 |
| 元素熟知 | 9 | 10 |
※足しても100になりません。
| ステータス | 上昇量 |
|---|---|
| 攻撃力 | 4.1, 4.7, 5.3, 5.8 |
| 会心率 | 2.7, 3.1, 3.5, 3.9 |
| 会心ダメージ | 5.4, 6.2, 7.0, 7.8 |
| その他 | 1, 1, 1, 1 |
プログラムが0を出力した時点で、ゲームは終了する。ゲーム終了時に、最も高い聖遺物のスコアがそのままあなたのスコアとなる。
実行ごとに、以下の制約に基づきテストケースが生成される。
以下のプログラムは、この問題に対して不正でない出力を行うプログラムである。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Artifact {
int id;
int level;
int count;
double s0;
double s1;
double s2;
double s3;
double s4;
double s5;
double s6;
double s7;
double s8;
double s9;
};
int main() {
int F, N, M, E, Ei;
while (1) {
cin >> F >> N >> M >> E >> Ei;
if (F == 3) {
fprintf(stdout, "%d %d\n", 0, 0);
fflush(stdout);
break;
}
if (cin.eof()) {
break;
}
vector <struct Artifact> artifacts;
for (size_t i = 0; i < M; i++) {
struct Artifact artifact;
int temp;
cin >> artifact.id >> artifact.level >> temp >> artifact.count >> artifact.s0 >>
artifact.s1 >> artifact.s2 >> artifact.s3 >> artifact.s4 >>
artifact.s5 >> artifact.s6 >> artifact.s7 >> artifact.s8 >>
artifact.s9;
artifacts.push_back(artifact);
}
fprintf(stdout, "%d %d\n", F + 1, 0);
fflush(stdout);
}
return 0;
}