ECAUG203 - EDITORIAL

PROBLEM LINK:

Practice
Contest

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();
} 
5 Likes

Has it not been added to practice yet?
prac

Now it is added you can check it.

2 Likes

okay thanks

1 Like