ENCJMAY7-Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest Link
Author: Shloka Mahesheka
Tester: Sandeep Singh
Editorialist: Shloka Mahesheka

DIFFICULTY:

EASY

PREREQUISITES:

Math, Geometry

PROBLEM:

Given an area N, we need to figure out if it is possible to make a square of area N in a grid of infinite dots and each dot is equidistant from the dot above it, below it, left to it and right to it (uniformly spaced, the distance being one unit). The sides of the squares can only be drawn by joining any 4 dots as long as the connected figure is a square.

QUICK EXPLANATION:

Area of N is possible only if the area is the sum of two squared integers.
N = a^2 + b^2 , where a and b are whole numbers.

EXPLANATION :

The Pythagoras theorem states that:

“The square on the hypotenuse of a right triangle is equal to the sum of the squares on the two legs”.
Let there be two squares A ( side a) and B (side b) on the legs of the right triangle and the square C (side c) is on the hypotenuse.

Area of Square A,B,C : a^2,b^2,c^2 respectively.

So, according to Pythagoras theorem:

c^2 = a^2 + b^2
c^2 is the required area of the square.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
bool sumSquare(int n)
{
    for (long i = 1; i * i <= n; i++)
	    for (long j = 1; j * j <= n; j++)
		    if (i * i + j * j == n) {
			    return true;
		    }
    return false;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    int n;
    cin>>n;
    if (sumSquare(n))
	    cout << "Yes "<<"\n";
    else
    {
        double sr=sqrt(n);
        if(((sr - floor(sr)))==0)
        cout<<"Yes\n";
        else
        cout<<"No\n";
    }

    }

}
Tester's Solution 
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////

void solve(){
    int n,i,j;
    cin>>n;

    string ans = "No";

    if(pow(int(sqrt(n)), 2) == n)
        ans = "Yes";

    for(i = 1; i < 400; ++i){
        for(j = 1; j < 400; ++j){
            if(((i * i) + (j * j)) == n){
                ans = "Yes";
          
            }
        }
    }
    cout << ans <<endl;


}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif
    int t;
    cin>>t;
    while(t--)
        solve();
}
2 Likes