10519 - !! Really Strange !!

[Red Scorpion]

for :
n= 1 we get -> 2
n = 2 we get -> 4
n = 3 we get -> 8
n = 4 we get -> 14
... this pattern repeated

Code: Select all

2
      2
4          2
      4         0
8          2
      6
14

see this sequences have 2 extrapolation, so the formula is :
f(n) = a*n^2 + b*n + c
n = 1 -> a + b + c = 2 ...1)
n = 2 -> 4a + 2b + c = 4 ...2)
n = 3 -> 9a + 3b + c = 8 ...3)

solve it you will get a = 1, b = -1, and c = 2;
so the equation is:
f(n) = n^2 - n + 2.

I hope it helps.

[Almost Human]

I've generated the same formula ... May be I can explain a little to you. Hope it's useful.

But by the way ... I got WA for this .... Is this problem big number or what ?

Firstly, I didn't add 1 to the result... so I got the sequence :

1 , 3 , 7 , 13 , 21 ...

we get the extrapolation :
2 2 2
2 4 6 8
1 3 7 13 21

I'm using a recursive approach :

f(n) = f(n-1) + range, where range is defined as 2 * ( n - 1 )
so :
f(n) = f(n-1) + 2 * (n-1)
f(n) = f(n-2) + 2 * (n-2) + 2*(n-1)..
f(n) = f(1) + 2 * ( 1 ) + ... + 2 * ( n-1 ) where f(1) = 1

f(n) = f(1) + total of the sequence above, that is
2*(1) + 2*(2) + ... + 2*(n-1)

Sum = (n-1)/2 * ( 2 + 2*(n-1) )

so ...
f(n) = f(1) + (n-1)/2*(2+2*(n-1))
f(n) = f(1) + (n-1)*(1+(n-1))
f(n) = f(1) + (n-1)*n ;
f(n) = 1 + n(n-1) ;

then .. we add 1 to this formula ....
f(n) = 2 + n(n-1)

[titid_gede]

yes, the input can be up to 1000 digits (not 1000 numbers!), and be careful of n = 0. hope it can help.

[Almost Human]

Allright ....

I've changed my code and used my bignum class and got ACC..

thanks ...

[Faizur]

I get Wa after rejudge of the problem 10519.What is changed after the rejudgement............

[Jalal]

SAME 2 ME
HAVE 2 CHEAK CRITICAL INPUTS

[shamim]

I am getting WA, I realize that I have to use BigNumber. Here are some output from my program.

INPUT

• 0
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  99
  100
  9999
  10000

OUTPUT

• 0
  2
  4
  8
  14
  22
  32
  44
  58
  74
  92
  9704
  9902
  99970004
  99990002

Please verify whether they are correct.

[Larry]

Why do you think if there is zero circles, there's zero regions?

[shamim]

What about the others, are they correct.

[UFP2161]

Yes, the others are correct.

[helloneo]

Code: Select all

code removed

i got WA..
did i miss anything..?
when there is no circle.. ouput should be 1.. right..?

[Martin Macko]

Any comment about algorithm you have used? Why just posting the code without any comment? It would be much easier to help you if you would describe your algorithm instead of posting just the code.

Have you read all topics on this problem? You can find a lot of usefull info in them: http://online-judge.uva.es/board/viewtopic.php?t=4402, http://online-judge.uva.es/board/viewtopic.php?t=3520, or http://online-judge.uva.es/board/viewtopic.php?t=3408.

BTW, cited from the board main page: "If there is a thread about your problem, please use it."

[sclo]

Here's a way to derive the formula without using any sequences, just uses some elementary graph theory.

The case n=0 and n=1 are special cases, but it turns out that for n=1 the formula is correct.

For the cases n>1,
Let v be the number of intersection points, we know there are n(n-1) of them since there are n(n-1)/2 pairs of circles and each pair has exactly 2 intersection points. These are the vertices of our graph. Now v=n(n-1).

We can now think of the arcs of the circles bounding the regions as edges between the vertices. It is easy to see that the degree of each vertex is 4 (since exactly 2 circles intersect at each intersection point), so by the handshaking lemma, the total number of edges, e = 4v/2 = 2v = 2n(n-1).

We are asked to compute the number of regions f, so by Euler's formula,
f = e - v + 2 = n (n - 1) + 2.

This is the same formula as above.

[dust_cover]

can anybuddy tell me what should be the output for inout 0 & 1.....I am getting WA.
I used BigInt library
Also used the standard formula for the problem!

Thanx in advance

[dust_cover]

can anybuddy tell me what should be the output for inout 0 & 1.....I am getting WA.
I used BigInt library
Also used the standard formula for the problem!

Thanx in advance