// Compile: g++ -std=c++20 -O2 -Wall -I$HOME/ctf/tools/ac-library -DLOCAL -o sol sol.cpp // Or: make sol (uses Makefile in this dir) // Run: ./sol < in.txt #include #include using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using vi = vector; using vll = vector; using vvi = vector; using vvll = vector; using pii = pair; using pll = pair; #define rep(i,n) for(ll i=0;i<(ll)(n);++i) #define rep2(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define sz(x) ((ll)(x).size()) template bool chmin(T&a,const T&b){if(b bool chmax(T&a,const T&b){if(a> p; prd[i - 1] = p; } if(n==2) { if(prd[0] == 1) cout << "! 11" << endl; else if(prd[0] == 25) cout << "! 25" << endl; else if(prd[0] == 36) cout << "! 66" << endl; else if(prd[0] == 49) cout << "! 77" << endl; else if(prd[0] == 64) cout << "! 88" << endl; else if(prd[0] == 81) cout << "! 99" << endl; else cout << "! -1" << endl; return 0; } int count_not_zero = 0; int last_prd = 0; vector last(2); for (int i = 0; i < n - 1; i++) { if(prd[i] != 0) { last[count_not_zero] = n - 2 - i; last_prd = prd[i]; count_not_zero++; if (count_not_zero >= 2) break; } } if (count_not_zero >= 2){ cout << "? " << last[1] << " " << last[0] << endl; int p; cin >> p; for (int first_digit = 1; first_digit <= 9; first_digit++){ bool is_ok = true; rep(j, sz(prd)) { if (prd[j] % first_digit != 0) is_ok = false; } if(is_ok) { int a_digit = prd[n-2-last[1]] / first_digit; int b_digit = prd[n-2-last[0]] / first_digit; if( p == a_digit*b_digit) { cout << first_digit; rep(d, n-1) { cout << prd[d] / first_digit; } cout << endl; return 0; } } } }else{ if (count_not_zero==0){ cout << "! -1" << endl; return 0; }else{ // 101,505,606,707,808,909は解けるはず・・・・ if(last_prd==1 ||last_prd==25 ||last_prd==36 ||last_prd==49 ||last_prd==64 ||last_prd==81){ int first_digit = (int)sqrt(last_prd); cout << first_digit; rep(d, n-1) { if(d == n-2-last[0]) cout << first_digit; else cout << "0"; } cout << endl; return 0; }else{ cout << "! -1" << endl; return 0; } } } return 0; }