ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1073. Square Country

easy search
Posted by Artem Ladik 8 Jul 2009 01:22
var i,j,k,n:longint;
begin

for i:=1 to 250 do
if sqr(i)=n then begin write(1); exit; end;

for i:=1 to 250 do
for j:=1 to 250 do
if sqr(i)+sqr(j)=n then begin write(2); exit; end;

for i:=1 to 250 do
for j:=1 to 250 do
for k:=1 to 250 do
if sqr(i)+sqr(j)+sqr(k)=n then begin write(3); exit; end;

write(4);
end.
Re: easy search
Posted by evjava 23 Oct 2009 20:20
If N was bigger, you would have time limit.
Re: easy search
Posted by nguyenductam 4 Apr 2010 18:14
I don't think so. My code got AC.
#include<stdio.h>

int i,j,k;
long int n;

int main()
{
scanf("%d",&n);

for(i=1;(i*i)<=n;i++)
if((i*i)==n)
{
printf("%d",1);
return 0;
}
for(i=1;i*i<=n;i++)
for(j=1;j*j<=n;j++) if((i*i+j*j)==n)
{
printf("%d",2);
return 0;
}

for(i=1;i*i<=n;i++)
for(j=1;j*j<=n;j++)
for(k=1;k*k<=n;k++) if((i*i+j*j+k*k)==n)
{
printf("%d",3);

return 0;
}

printf("%d",4);
return 0;

}
Re: easy search
Posted by Connector 10 Jul 2010 18:30
I think it's DP in this problem O(n*sqrt(n));
Re: easy search
Posted by Mahmood 4 Oct 2011 21:02
this is the most epic answer I've read....hhhh :) u are awesome
thanks dud and good luck
I don't think so. My code got AC
Posted by Daniyar 8 Feb 2013 11:25
for(i=1;(i*i)<=n;i++)
if((i*i)==n)
{
printf("%d",1);
return 0;
}
you can just write if (sqrt(n) * sqrt(n) == n)