10110 - Light, more light

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

10110 - Light, more light

Post by C8H10N4O2 » Wed Apr 17, 2002 4:52 pm

Works for all test cases. Don't know why it WAs. Some help from them JAVA people would be nice.
[java]import java.io.*;
import java.lang.*;

class Main
{
public static void main(String args[])
{
StringBuffer B;
String S;
int N,Length,i;
char c;
while(true)
{
try
{
B=new StringBuffer();
while((c=(char)System.in.read())!='\n'&&c!=-1)
B.append(c);
}
catch(IOException e)
{
break;
}
S=B.toString();
N = Integer.parseInt(S.substring(0,S.length()-1));
if(N==0||c==-1)
break;
if(Math.pow(Math.floor(Math.sqrt(N)),2)==N)
System.out.println("yes");
else
System.out.println("no");
}
}
};[/java]

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Wed Apr 17, 2002 5:25 pm

there's a statement in the problem "Which is less then or equals 2^32-1"
i code my solution in C++, but i guess in Java, int would be the same that it cannot hold more than 2^31-1. so maybe try another data type

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Apr 17, 2002 9:25 pm

Good point. Should have used JAVA long or unsigned int. Thanks.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Apr 18, 2002 2:37 am

As far as I remember, Java doesn't have unsigned types. This is also exactly the one single reason one of my friends always mentions to explain why Java is crap ;-)

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Apr 18, 2002 10:43 am

That program ONLY took me 7 hours in JAVA:O I am starting to see why without the good classes, JAVA is horribly complicated and slow. Although the error checking compiler is quite nice. It is much more strict than C++ and won't let you access out of bounds and such. The other thing I noticed is that the compiler on the 24 hour judge doesn't support all the features of even simple classes; there are wierd little discrepancies. However, I think it would be useful to know from things like TopCoder where you need to analyze other people's code as well as use the nice BigInt. It is silly how some people think StringTokenizer is better than strtok; they haven't mastered strtok. Strings and general input/output is SOOO much easier in C++ (e.g. SSCANF).

ante
New poster
Posts: 8
Joined: Wed Mar 20, 2002 2:00 am

10110 More Light's Please

Post by ante » Tue Apr 23, 2002 6:58 pm

Why I receive WA ??? What's the problem ???

[cpp]
#include<stdio.h>
#include<math>
void main()
{
int n;
while (1)
{
scanf("%d",&n);
if (n == 0) break;
if (((int)sqrt(n))==sqrt(n))
printf("yes\n");
else
printf("no\n");
}
}
[/cpp]

Thanx in advance 8)

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Tue Apr 23, 2002 8:21 pm

Maybe you have a roundng problem?

(int)sqrt could give you a wrong answer. For example 4.999999... would be just 4, not 5. As far as I know at least.

Ivor

ante
New poster
Posts: 8
Joined: Wed Mar 20, 2002 2:00 am

More Pascal Light also

Post by ante » Wed Apr 24, 2002 4:17 pm

I tried this in Pascal but it didn't work also, i need to check if N has integer square root .
Please help !

[pascal]
program p10110;
var
n: integer;
begin
while not eof(input) do
begin
readln(n);
if (n = 0) then break;
if frac(sqrt(n))<0.000001 then writeln('yes') else
writeln('no');
end;
end.
[/pascal]

P.S: also tried
[pascal]

if abs(trunc(sqrt(n))-sqrt(n))<0.000001 then writeln('yes') else writeln('no');

if trunc(sqrt(n))*trunc(sqrt(n))=n then writeln('yes') else writeln('no');
[/pascal]

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Wed Apr 24, 2002 5:56 pm

Why don't you try generating all squares and then search the array for n.

You'll have 65535 squares at max. So, using binary search you could determine, whteher sqrt(n) is an integer or not. The array won't be that big, but it could be not the fastest way.

Ivor
P.S I haven't solved the problem myself, so I'm just giving some ideas that popped up my mind.

ante
New poster
Posts: 8
Joined: Wed Mar 20, 2002 2:00 am

UNSIGNED PROBLEM

Post by ante » Wed Apr 24, 2002 6:25 pm

I didn't read problem carefully enough :( , 2^32 - 1 is 4,294,967,295 and this must be UNSIGNED int .

Thanx anyway !
Last edited by ante on Wed Apr 24, 2002 11:42 pm, edited 1 time in total.

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Wed Apr 24, 2002 7:03 pm

Want to know a secret?

2^31 - 1 = 2147483647.

Ivor 8)

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Apr 26, 2002 4:15 am

Isn't ints in pascal 2 bytes? I don't know; I am C++ coder. Have you tried longs? You need unsigned longs in C++ or int64. This problem requires a unsigned 4 byte integer.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

use type cardinal in pascal

Post by xenon » Fri May 24, 2002 11:39 am

type integer is signed 32 bits.
type cardinal is unsigned 32 bits (could be more, I don't know).
this code works:
[pascal]var
n,r:cardinal;
begin
repeat
readln(n);
if (n=0) then break;
r:=trunc(sqrt(n));
if (r*r=n) then writeln('yes') else writeln('no');
until false;
end.
[/pascal]
so there's no rounding problem

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

10110 - Lights, more lights (slow and fat)

Post by Cubist » Mon Jun 10, 2002 3:58 am

How do you reduce either the running time or the memory usage for
this problem? I was astonished to see my tiny Pascal program using
0.670 seconds and something like 468K! This code doesn't use
anything that other programs I'm submitted, which all ran in 0.000
and 64K.

Any ideas?
--
Chris Long, Mathematics Department, Rutgers University

Mozart needs food. Beethoven now has extra fight power. Bach is about to die.

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

Post by Betovsky » Mon Jun 10, 2002 4:12 am

read the rulz, there is already a topic about this prob plz post ur questions in there ...

and we dont know nothing about ur code do u want us to guess out ???

Post Reply

Return to “Volume 101 (10100-10199)”