10872 - How Many Triangles?

[TISARKER]

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

[Cho]

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

[kp]

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]

Thx cho
Thx kp

[sohel]

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]

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]

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]

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

[kp]

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]

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]

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]

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]

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!

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]

Hi guys

Could someone give me any I/O?

I got several WA but I don

[TISARKER]

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