## 10872 - Triangles

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

Moderator: Board moderators

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 10872 - Triangles

I could not understand promlem.
How for sample input 5 sample output will be 1.
This problem was set by shahriarmonzoor.
Mr. Arithmetic logic Unit

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Because there is only one possible triangle (1, 2, 2).

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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?

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
if n=0 then exit;
inc(k);
if odd(n) then begin
res:= n+3;
res:= res*res;
rese:= res/48;
if abs(rese-trunc(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(rese-trunc(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.
``````

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:
Thx cho
Thx kp
Mr. Arithmetic logic Unit

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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?

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:

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
sohel wrote:It becomes summation of two arithmatic series
Yes, that is also what I got, but I derived it from a linear time solution.

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;
}
``````
Then you can derive two arithmetic series, one looks like
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.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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((n-1)/2). For fixed i, by considering the triangle inequality, the number of possible j-k combination would be 2r-n+i+1. i.e. A=r(5r-2n+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(C-D)+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.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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;
``````
Thanks a lot!

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.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

### 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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

### Re: Problem

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.
Post the relevant part of your code so that we can see the types of all intermediate variables. E.g.

Code: Select all

``````long long x=7;
double y=x/2;
``````
ends with y==3, so there may be many subtle issues involved. Also, keep in mind that "real" numbers are imprecise and rounding errors may occur.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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).
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:2. ... It's a real pain in the neck and the main reason why I switched from Pascal to C.
I will not "give up" that easy Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Hi guys

Could someone give me any I/O?

I got several WA but I don

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm