PROBLEM LINK:
Author Rishab Jain
Tester Sandeep Singh
Editorialist Rishab Jain
DIFFICULTY :
SIMPLE
PREREQUISITES:
MATH
PROBLEM:
There are N boxes of tiles . The number of tiles present in i^{th} box is i (i varies from 1 to N) . The Chef has two houses with N rooms each, whose floors is a square with area (i∗i) ,i varies from (1....N). You have to choose boxes such that you can distribute equal number of tiles to any two rooms ,one room for each house. After distributing equal tiles there should be no tiles left in the box and both rooms of different house should be tiled completely.
EXPLANATION
You have to find such boxes where number of tiles present is the sum of two equal perfect square.Like (2,8,18,32......)
Suppose n is the number of room that are completely tiled for single building. N is the total boxes.
2*n^2 <=N
n<=sqrt(N/2)
Therefore the total number of completely tiled room is 2*sqrt(N/2) .
SOLUTION
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
long long int N;
cin>>N;
long long int x=2*floor(sqrt(N/2));
cout<<x<<"\n";
}
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;
inline int get_sqrt(long long x)
{
int r = sqrt(x);
while(r * (long long) r > x) r--;
while((r + 1) * (long long)(r + 1) <= x) r++;
return r;
}
void solve(){
ll n;
cin >> n;
ll ans = get_sqrt(n / 2);
cout << 2 * ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
cin >> t;
while(t--)
solve();
}