PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Akash Bhalotia
Tester: Rahul Dugar
Editorialist: Nandini Kapoor
DIFFICULTY:
Simple
PREREQUISITES:
Math
PROBLEM:
Chef has a secret number. The only information you have is that it has an odd number of factors, and that it lies between 1 and 10^6, both inclusive. He challenges you to guess the number in at most 2000 tries. Can you guess it?
QUICK EXPLANATION:
Only perfect squares have an odd number of factors, thus the possible secret numbers Chef can have would all be perfect squares and can be guessed correctly by querying all perfect squares in the given range [1, 10^6].
EXPLANATION:
The simple way of guessing the right number within the given number of tries is to query all perfect squares between 1 to 10^6. As 10^6 (the maximum possible secret number) is the square of 10^3, we would have to query numbers from 1^2 to (10^3)^2 so as to cover all the perfect squares lying between 1 and 10^6. This constitutes 1000 tries which is less than the limit given as 2000.
We deduced that the only possible secret numbers are perfect squares because the number of factors are given to be odd. We know that the factors of a number always exist in pairs because if x is a factor of a number N, then \large \frac {N}{x} will also be a factor. The only possible case in which the factors will not be in a pair is when x=\large \frac {N}{x} for one of the factors x of N, which is the true in case of perfect squares. Therefore perfect squares have odd number of factors and we only need to query them to reach the correct guess.
TIME COMPLEXITY:
O(1) per test case, as it takes maximum 1000 interactions to guess the number which is a constant.
SOLUTIONS:
Setter
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static void print(int N)
{
System.out.println(N);
System.out.flush();
}
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
while (T-->0)
{
for(i=1;i<=1000;i++)
{
print(i*i);
int verd=Integer.parseInt(br.readLine().trim());
if(verd==1) break;
else if(verd==-1) System.exit(0);
}
}
}
}
Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
//#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define double long double
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void solve() {
fr(i,1,1000) {
cout<<i*i<<endl;
int pp;
cin>>pp;
if(pp==1)
return;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
int t=readIntLn(1,100);
// int t=1;
// cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long int
#define endl "\n"
#define mod 1000000007
#define pb_ push_back
#define mp_ make_pair
//______________________________z_____________________________
vector<int> perfs;
void solve()
{
for(auto it: perfs) {
cout<<it<<endl;
fflush(stdout);
int status;
cin>>status;
if(status==1) return;
else if(status==-1) exit(0);
}
}
int32_t main()
{
//_z;
int t=1;
cin>>t;
for(int i=1; i<=1000; i++) perfs.pb_(i*i);
while(t--)
{
solve();
}
}