## 10872 - How Many Triangles?

Moderator: Board moderators

### 10872 - How Many 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
TISARKER
Learning poster

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

Because there is only one possible triangle (1, 2, 2).

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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;beginend;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(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.`
kp
Learning poster

Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Thx cho
Thx kp
Mr. Arithmetic logic Unit
TISARKER
Learning poster

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

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?

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

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;`

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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.

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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???
kp
Learning poster

Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

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.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 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.
Chok
New poster

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

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

misof
A great helper

Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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
kp
Learning poster

Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Hi guys

Could someone give me any I/O?

I got several WA but I don
Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 10872(How Many Triangles?)WA

Please give me some random sample input and output.
Mr. Arithmetic logic Unit
TISARKER
Learning poster

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