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
Location: Bangladesh
Contact:

10872 - Triangles

Post by TISARKER » Sat Jun 25, 2005 9:30 pm

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Jun 25, 2005 9:37 pm

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

Post by kp » Sat Jun 25, 2005 10:11 pm

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

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

Post by TISARKER » Sun Jun 26, 2005 7:15 am

Thx cho
Thx kp
Mr. Arithmetic logic Unit

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 26, 2005 12:53 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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Jun 26, 2005 2:14 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;

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

Post by Adrian Kuegel » Sun Jun 26, 2005 3:45 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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Jun 26, 2005 5:05 pm

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

Post by kp » Mon Jun 27, 2005 2:17 pm

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???

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Jun 27, 2005 3:20 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

Post by Chok » Mon Jun 27, 2005 4:29 pm

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

Post by misof » Mon Jun 27, 2005 11:41 pm

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

Post by kp » Tue Jun 28, 2005 1:38 am

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

Post by Antonio Ocampo » Tue Jun 28, 2005 3:32 am

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
Location: Bangladesh
Contact:

10872(How Many Triangles?)WA

Post by TISARKER » Tue Jun 28, 2005 8:16 am

It gives wrong answer.Why?.
Please give me some random sample input and output.
Mr. Arithmetic logic Unit

Post Reply

Return to “Volume 108 (10800-10899)”