#include #include using namespace std; const int kMaxN = 1005, kMaxK = 11; int dp[kMaxK][kMaxN]; int from[kMaxK][kMaxN]; void makeDP(int n, int k) { for (int i = 2; i <= n; ++i) { dp[1][i] = i - 1; // pt un singur ou raspunsul e tot timpul n - 1. In cel mai rau caz punem n - 1 intrabari // si daca oul nu s-a spart inseamna ca raspunsul e n from[1][i] = 1; } for (int i = 2; i <= k; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = n; // infinity } dp[i][1] = 0; } for (int K = 2; K <= k; ++K) { for (int poz = 2; poz <= n; ++poz) { // pt un etaj raspunsul e 0 tot timpul -> clar se sparge de la acel etaj for (int queryPoz = 1; queryPoz <= poz; ++queryPoz) { // cerr << poz << '\t' << queryPoz << '\t' << dp[K][poz] << '\t' << dp[K - 1][queryPoz] << '\t' << dp[K][poz - queryPoz] << '\n'; int v = max(dp[K - 1][queryPoz], dp[K][poz - queryPoz]) + 1; // daca avem un sir de lungime poz si K oua accesibile daca intrebam la pozitia queryPoz avem 2 variante de raspuns. // presupunem ca amandoua sunt in aceeasi masura probabile, deoarece noi vrem sa minimizam worst case-ul // astfel daca cumva oul se sparge atunci putem restrange intervalul in care se afla etajul la [1, queryPoz] cu K - 1 oua // ->> oul curent s-a spart. Stim ca in cel mai rau caz putem afla unde se afla etajul cu dp[queryPoz - 1][K - 1] mutari // daca cumva oul nu se sparge inseamna ca etajul se afla in intervalul [queryPoz + 1, poz] cu K oua. // rationamentul e similar, iar noi cum trebuie sa minimizam cazul cel mai prost luam maximul dintre cele 2 dinamici if (v < dp[K][poz]) { dp[K][poz] = v; from[K][poz] = queryPoz; } } } } } int main() { int n, k; cin >> n >> k; string response; cout << "answer " << 1 << '\n'; cin >> response; return 0; cout << "query " << n << '\n'; cout.flush(); // cin >> response; // assert(response == "broke"); // --k; makeDP(1000, 10); // completarea dinamicii nu are legatura cu valorile N si K initiale. Dinamica se face individual pentru orice portiune int left = 0; while (response != "exit") { if (n != 1) { cout << "query " << left + from[k][n] << '\n'; cout.flush(); cin >> response; if (response == "broke") { n = from[k][n]; --k; } else { left += from[k][n]; n -= from[k][n]; } } else { // n = 1 -> aici e raspunsul cout << "answer " << n + left << '\n'; cout.flush(); cin >> response; } } return 0; }