#include "dzilib.h" #include <map> #include <vector> #include <set> #include <cassert> #include <iostream> unsigned long long najmniejszyDzielnikWiekszyNiz(unsigned long long wartosc, unsigned long long szukanyDzielnik) { for (int i = szukanyDzielnik + 1; i <= wartosc; ++i) { if ((wartosc % i) == 0) return i; } return -1; } class Zgadywacz { unsigned long long INITIAL_BIAS = 1023; int liczbaPytan = 0; std::map<unsigned long long, unsigned long long> liczbyDzielnikow; unsigned long long zapytajOLiczbeDzielnikow(unsigned long long y) { if (liczbyDzielnikow.count(y+INITIAL_BIAS) == 0) { liczbaPytan++; liczbyDzielnikow[y + INITIAL_BIAS] = Ask(y + INITIAL_BIAS); } return liczbyDzielnikow[y + INITIAL_BIAS]; } public: void zgadnijLiczbe(unsigned long long maxC) { std::vector<bool> candidates(8, false); int numberCandidates = 0; for (unsigned long long i = 0; i < 8; ++i) { if (zapytajOLiczbeDzielnikow(i) % 3 == 0) { numberCandidates++; candidates[i] = true; } } unsigned long long bias = 8; while (numberCandidates > 1) { for (unsigned long long i = 0; i < candidates.size(); ++i) { if (candidates[i] == false) continue; if (zapytajOLiczbeDzielnikow(i + bias) % 3 != 0) { candidates[i] = false; numberCandidates--; } } bias += 8; } unsigned long long c = -1; for (int i = 0; i < candidates.size(); ++i) { if (candidates[i]) c = i; } assert(c != -1); c = c+4; unsigned long long potegaDwojki = 3; while (true) { int liczbaReszta16Przez32 = 0; int ktoryPodzielny = -1; for (int i = 0; i < 32; i=i+8) { auto liczbaDzielnikow = zapytajOLiczbeDzielnikow(c+i); if (liczbaDzielnikow % 5 == 0) { liczbaReszta16Przez32++; ktoryPodzielny = c+i; } } assert(liczbaReszta16Przez32 > 0); if (liczbaReszta16Przez32 == 1) { c = ktoryPodzielny + 16; potegaDwojki = 5; break; } c = c+8; } while (true) { auto liczbaDzielnikow = zapytajOLiczbeDzielnikow(c); potegaDwojki = najmniejszyDzielnikWiekszyNiz(liczbaDzielnikow, potegaDwojki) - 1; if (liczbaDzielnikow == potegaDwojki + 1) { unsigned long long value = (1ll << potegaDwojki) - c - INITIAL_BIAS; //std::cout << "liczba=" << value << "\n"; //std::cout << "liczba zapytan=" << liczbaPytan << "\n"; Answer(value); return; } //std::cout << ", potegaDwojki=" << potegaDwojki << "\n"; c = c + (1ll << potegaDwojki); } } }; int main() { int t = GetT(); int q = GetQ(); long long c = GetC(); long long n = GetN(); while (t--) { Zgadywacz zgadywacz; zgadywacz.zgadnijLiczbe(c); /*if (Ask(1) == 8) Answer(1000); else Answer(1);*/ } //std::cout << "AAAAAAA\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include "dzilib.h" #include <map> #include <vector> #include <set> #include <cassert> #include <iostream> unsigned long long najmniejszyDzielnikWiekszyNiz(unsigned long long wartosc, unsigned long long szukanyDzielnik) { for (int i = szukanyDzielnik + 1; i <= wartosc; ++i) { if ((wartosc % i) == 0) return i; } return -1; } class Zgadywacz { unsigned long long INITIAL_BIAS = 1023; int liczbaPytan = 0; std::map<unsigned long long, unsigned long long> liczbyDzielnikow; unsigned long long zapytajOLiczbeDzielnikow(unsigned long long y) { if (liczbyDzielnikow.count(y+INITIAL_BIAS) == 0) { liczbaPytan++; liczbyDzielnikow[y + INITIAL_BIAS] = Ask(y + INITIAL_BIAS); } return liczbyDzielnikow[y + INITIAL_BIAS]; } public: void zgadnijLiczbe(unsigned long long maxC) { std::vector<bool> candidates(8, false); int numberCandidates = 0; for (unsigned long long i = 0; i < 8; ++i) { if (zapytajOLiczbeDzielnikow(i) % 3 == 0) { numberCandidates++; candidates[i] = true; } } unsigned long long bias = 8; while (numberCandidates > 1) { for (unsigned long long i = 0; i < candidates.size(); ++i) { if (candidates[i] == false) continue; if (zapytajOLiczbeDzielnikow(i + bias) % 3 != 0) { candidates[i] = false; numberCandidates--; } } bias += 8; } unsigned long long c = -1; for (int i = 0; i < candidates.size(); ++i) { if (candidates[i]) c = i; } assert(c != -1); c = c+4; unsigned long long potegaDwojki = 3; while (true) { int liczbaReszta16Przez32 = 0; int ktoryPodzielny = -1; for (int i = 0; i < 32; i=i+8) { auto liczbaDzielnikow = zapytajOLiczbeDzielnikow(c+i); if (liczbaDzielnikow % 5 == 0) { liczbaReszta16Przez32++; ktoryPodzielny = c+i; } } assert(liczbaReszta16Przez32 > 0); if (liczbaReszta16Przez32 == 1) { c = ktoryPodzielny + 16; potegaDwojki = 5; break; } c = c+8; } while (true) { auto liczbaDzielnikow = zapytajOLiczbeDzielnikow(c); potegaDwojki = najmniejszyDzielnikWiekszyNiz(liczbaDzielnikow, potegaDwojki) - 1; if (liczbaDzielnikow == potegaDwojki + 1) { unsigned long long value = (1ll << potegaDwojki) - c - INITIAL_BIAS; //std::cout << "liczba=" << value << "\n"; //std::cout << "liczba zapytan=" << liczbaPytan << "\n"; Answer(value); return; } //std::cout << ", potegaDwojki=" << potegaDwojki << "\n"; c = c + (1ll << potegaDwojki); } } }; int main() { int t = GetT(); int q = GetQ(); long long c = GetC(); long long n = GetN(); while (t--) { Zgadywacz zgadywacz; zgadywacz.zgadnijLiczbe(c); /*if (Ask(1) == 8) Answer(1000); else Answer(1);*/ } //std::cout << "AAAAAAA\n"; return 0; } |