10872  Triangles
Moderator: Board moderators
10872  Triangles
I could not understand promlem.
How for sample input 5 sample output will be 1.
Please describe me.
This problem was set by shahriarmonzoor.
How for sample input 5 sample output will be 1.
Please describe me.
This problem was set by shahriarmonzoor.
Mr. Arithmetic logic Unit
2 TISARKER:
You may want to read this http://www.themathcircle.org/integertriangles.pdf
2 All:
I think it should work fine, but always get WA? Why?
You may want to read this http://www.themathcircle.org/integertriangles.pdf
2 All:
I think it should work fine, but always get WA? Why?
Code: Select all
program kpC;
label finish;
var
res: int64;
procedure init;
begin
end;
procedure solve;
var
k: integer;
rese: extended;
n: int64;
begin
k:= 0;
while true do begin
readln(n);
if n=0 then exit;
inc(k);
if odd(n) then begin
res:= n+3;
res:= res*res;
rese:= res/48;
if abs(resetrunc(rese)0.5)<0.0000000001 then
if odd(trunc(rese)) then res:= trunc(rese)+1
else res:= trunc(rese)
else res:= round(rese);
end else begin
res:= n;
res:= res*res;
rese:= res/48;
if abs(resetrunc(rese)0.5)<0.0000000001 then
if odd(trunc(rese)) then res:= trunc(rese)+1
else res:= trunc(rese)
else res:= round(rese);
end;
writeln('Case ',k,': ',res);
end;
end;
procedure print;
begin
end;
begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
{$ENDIF}
init;
solve;
print;
finish:
{$IFNDEF ONLINE_JUDGE}
close(input); close(output);
{$ENDIF}
end.
I would like to know the method you guys used to solve this problem?
.. in the real time contest, I generated the first few results using brute force and then found a pattern..
It becomes summation of two arithmatic series; something like
1 + 4 + 7 + 10 + ....
+
2 + 5 + 8 + 11 + ....
where the number of terms is ( n/2  n/3 ) or something similar to that.
Is this what you have used?
.. in the real time contest, I generated the first few results using brute force and then found a pattern..
It becomes summation of two arithmatic series; something like
1 + 4 + 7 + 10 + ....
+
2 + 5 + 8 + 11 + ....
where the number of terms is ( n/2  n/3 ) or something similar to that.
Is this what you have used?
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
kp:
The function round() can handle only numbers within the range of integers (2^31<= number < 2^31). Outside this range the function will produce a runtime error, which the Judge reports as WA.
Better not rely on floating point numbers and round(), but do the rounding yourself:
The function round() can handle only numbers within the range of integers (2^31<= number < 2^31). Outside this range the function will produce a runtime error, which the Judge reports as WA.
Better not rely on floating point numbers and round(), but do the rounding yourself:
Code: Select all
res:= n+3;
res:= res*res;
res:= (res+24) div 48;

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Yes, that is also what I got, but I derived it from a linear time solution.sohel wrote:It becomes summation of two arithmatic series
The idea for the linear time solution is quite obvious, you do a brute force over possible longest sides, and then sum up the number of ways to build the remaining length as sum of two integers <= maximum side length.
The number of ways to build remaining length v with maximum side mside can be calculated like this:
Code: Select all
int getPart(int v, int mside) {
return mside(v+1)/2+1;
}
sum_{i=k to l} i and the other like sum_{i=n to m} i/2.
The first sum is easy to calculate, but the second one is more tricky.
You would like to have the /2 before the sum, but if you do that, you are ignoring the fact that for all odd numbers in the range from n to m, the division is rounded down. So before dividing the sum by 2, you should subtract the number of odd numbers in the range.
I got another idea. Let A be the number of all possible triangle tuple (i, j, k) without taking care of the duplicates. i.e. (i, j, k) and (j, k, i) are considered different.
Then it would be easier to count A. The possible values of the first side length i would in in the range [1, r] where r=floor((n1)/2). For fixed i, by considering the triangle inequality, the number of possible jk combination would be 2rn+i+1. i.e. A=r(5r2n+3)/2.
Now we need to remove the duplicates. Let B be the number of triangle with all three side length being distinct, C be the number of isosceles triangle, D be the number of equilateral triangle. Then A=6B+3(CD)+D. Fortunately, both C and D are pretty easy to get.
After solving all unknowns, B+C will be the final solution.
[EDIT:] It seems there is something wrong with my idea. I got WA even my code can pass the sample.
[EDIT:] OK. It turns out to be some integer over flow problem
Then it would be easier to count A. The possible values of the first side length i would in in the range [1, r] where r=floor((n1)/2). For fixed i, by considering the triangle inequality, the number of possible jk combination would be 2rn+i+1. i.e. A=r(5r2n+3)/2.
Now we need to remove the duplicates. Let B be the number of triangle with all three side length being distinct, C be the number of isosceles triangle, D be the number of equilateral triangle. Then A=6B+3(CD)+D. Fortunately, both C and D are pretty easy to get.
After solving all unknowns, B+C will be the final solution.
[EDIT:] It seems there is something wrong with my idea. I got WA even my code can pass the sample.
[EDIT:] OK. It turns out to be some integer over flow problem
Last edited by Cho on Mon Jun 27, 2005 2:41 pm, edited 1 time in total.
Thanks a lot!little joey wrote:kp:
The function round() can handle only numbers within the range of integers (2^31<= number < 2^31). Outside this range the function will produce a runtime error, which the Judge reports as WA.
Better not rely on floating point numbers and round(), but do the rounding yourself:Code: Select all
res:= n+3; res:= res*res; res:= (res+24) div 48;
But:
1. Round() works fine on my Delphi, at least I think so
2. If round(x) raise RTE when X>2^31, why I got WA??? Why
not RTE???
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
1. The judge uses fpc (Free Pascal Compiler) and not Delphi. In the version of fpc the judge uses all functions that return integers, return 32 bits integers (I think fpc also has a 64 bits version, but the judge doesn't use that).
2. The judge software can't handle fpc runtime errors. The output from your program, including error messages, is dumped into a text file and compared to the judges output. If the output file contains an error message it is obviously not equal to the judge's output and gets the verdict WA. It's a real pain in the neck and the main reason why I switched from Pascal to C.
2. The judge software can't handle fpc runtime errors. The output from your program, including error messages, is dumped into a text file and compared to the judges output. If the output file contains an error message it is obviously not equal to the judge's output and gets the verdict WA. It's a real pain in the neck and the main reason why I switched from Pascal to C.
Problem
Hi,
I'm also using those close form, but since contest time all of my submission leads WA. I used long long for taking input and then after dividing by a constant value then i use (floor(tmp+.5)). Is it ok ? In others problem i did this things for rounding upto nearest integer. But i dont know why i gets WA for this problem.
I'm also using those close form, but since contest time all of my submission leads WA. I used long long for taking input and then after dividing by a constant value then i use (floor(tmp+.5)). Is it ok ? In others problem i did this things for rounding upto nearest integer. But i dont know why i gets WA for this problem.
Re: Problem
Post the relevant part of your code so that we can see the types of all intermediate variables. E.g.Chok wrote:Hi,
I'm also using those close form, but since contest time all of my submission leads WA. I used long long for taking input and then after dividing by a constant value then i use (floor(tmp+.5)). Is it ok ? In others problem i did this things for rounding upto nearest integer. But i dont know why i gets WA for this problem.
Code: Select all
long long x=7;
double y=x/2;
Yeah, I know that Judge uses fpc, but I read that fpc compatible with Delphi, so now I know that it's not fully compatible!little joey wrote:1. The judge uses fpc (Free Pascal Compiler) and not Delphi. In the version of fpc the judge uses all functions that return integers, return 32 bits integers (I think fpc also has a 64 bits version, but the judge doesn't use that).
I will not "give up" that easylittle joey wrote:2. ... It's a real pain in the neck and the main reason why I switched from Pascal to C.

 Experienced poster
 Posts: 131
 Joined: Sat Jul 17, 2004 4:09 am
 Location: Lima, Per
10872(How Many Triangles?)WA
It gives wrong answer.Why?.
Please give me some random sample input and output.
Please give me some random sample input and output.
Mr. Arithmetic logic Unit