Discussion @ 1539. Intelligence Data @ Timus Online Judge

KIRILL(ArcSTU) What are the answers for this tests? [14] // Problem 1539. Intelligence Data 4 Mar 2007 03:10

5 5
0.00000
0.03138
0.86105
0.20258
0.27292

5 50
0.67165
0.31869
0.16180
0.37224
0.42567
0.08201
0.47479
0.07057
0.84085
0.05972
0.29330
0.91728
0.36791
0.77466
0.32793
0.69767
0.84417
0.71798
0.30664
0.16263
0.32950
0.46602
0.24665
0.82568
0.27903
0.48177
0.14918
0.87434
0.28729
0.77275
0.97646
0.49253
0.88794
0.82728
0.02030
0.14106
0.14350
0.50081
0.02168
0.59293
0.00965
0.77448
0.65066
0.77049
0.70811
0.55751
0.20603
0.68109
0.59285
0.95546

TheBeet Re: What are the answers for this tests? [10] // Problem 1539. Intelligence Data 4 Mar 2007 08:57

5 5
0.00000
0.03138
0.86105
0.20258
0.27292
The answer is 12652.

5 50
0.67165
0.31869
0.16180
0.37224
0.42567
0.08201
0.47479
0.07057
0.84085
0.05972
0.29330
0.91728
0.36791
0.77466
0.32793
0.69767
0.84417
0.71798
0.30664
0.16263
0.32950
0.46602
0.24665
0.82568
0.27903
0.48177
0.14918
0.87434
0.28729
0.77275
0.97646
0.49253
0.88794
0.82728
0.02030
0.14106
0.14350
0.50081
0.02168
0.59293
0.00965
0.77448
0.65066
0.77049
0.70811
0.55751
0.20603
0.68109
0.59285
0.95546

The answer is 84779.

KIRILL(ArcSTU) Re: What are the answers for this tests? [9] // Problem 1539. Intelligence Data 4 Mar 2007 14:43

Thank you!
I was trying write my solution with long arithmetics
But I see the answers is small:)

KIRILL(ArcSTU) Re: What are the answers for this tests? [4] // Problem 1539. Intelligence Data 5 Mar 2007 01:21

I have WA5
I don't understand why

my prog returns

1 1
0.0
-----
0

1 1
1000.1
-----
7

5 1
1.54321
----
81

5 1
1000.00001
-----
66667

2 5
1000.11111
1000.99999
-----
66673

5 10
1000.00000
1000.11111
1000.22222
1000.33333
1000.44444
1000.55555
1000.66666
1000.77777
1000.88888
1000.99999
-----
66673

Falin.Lov Re: What are the answers for this tests? [3] // Problem 1539. Intelligence Data 5 Mar 2007 07:53

5 2
1000.11111
1000.99999
-----
66673

I think it should be 66670
Do you think so???

KIRILL(ArcSTU) Re: What are the answers for this tests? [2] // Problem 1539. Intelligence Data 5 Mar 2007 14:15

Yes you are right
My prog returns 66670

But I think I have problems with accuracy
I don't know how to avoid it

I use this way
(from sample)

if round(round(52.29*7)/7*100) = round(52.29*100) then ..

How I should calc

Please help me

svr Re: What are the answers for this tests? [1] // Problem 1539. Intelligence Data 5 Mar 2007 17:17

To solve should use math, _int64 and don't use double
and rounding.
Let K=10^(d+1);S[i]- double ratios;i=1..N
__int64 N[i]=S(i)*K;
j-is good groop number if and only if
ceil((N[i]-5)*j)/K)<=floor(([N[i]+5)*j)/K))
if [(N[i]+5)*j]%K>0
and
ceil((N[i]-5)*j)/K)<=floor(([N[i]+5)*j)/K))-1 othewise

Edited by author 05.03.2007 17:17

KIRILL(ArcSTU) Re: What are the answers for this tests? // Problem 1539. Intelligence Data 5 Mar 2007 18:40

to svr : Thank you very much!:)

Vedernikoff Sergey Re: What are the answers for this tests? [3] // Problem 1539. Intelligence Data 7 Mar 2007 13:16

KIRILL(ArcSTU) wrote 4 March 2007 14:43

I was trying write my solution with long arithmetics
But I see the answers is small:)

Obviously, answer is not bigger than 100000, because we can always get necessary precision by picking 100000*avg things...

Falin.Lov Re: What are the answers for this tests? [2] // Problem 1539. Intelligence Data 11 Mar 2007 06:45

Use following
"k:=trunc(a[j]*i+0.5);
if trunc(k/i*t+0.5)<>trunc(a[j]*t+0.05) then"
don't use round

Edited by author 11.03.2007 06:47

Alexander Kouprin Re: What are the answers for this tests? [1] // Problem 1539. Intelligence Data 12 Mar 2007 11:33

But I used round and got AC(0.984)!

This is my method:

// find number c
x:=1;
for i:=1 to c do
x:=x*10;
c:=x;

procedure test;
var i:integer;
e,q,f:real;
begin
for i:=1 to 100000 do begin
q:=e*i; // e is a[n]
f:=round(q);
if round(f/i*c+0.00000001)=z then...

So, it's work! :)

Falin.Lov Re: What are the answers for this tests? // Problem 1539. Intelligence Data 13 Mar 2007 16:59

Yeah
I just meant using round is easy to get WA.
But It seems that you are careful enough to use round :)

Sergey A. Weiss WA 5 [2] // Problem 1539. Intelligence Data 12 Jun 2007 00:27

My program has passed all the tests offered here, but it's WA#5 still. I don't understand why. Can anyone offer harder tests?

Denis Koshman Re: WA 5 [1] // Problem 1539. Intelligence Data 19 Aug 2008 06:04

It is possible to solve using 'int' data type and track quotients/remainders with each increment. Just +- and comparisons inside main loop. Also, no 64 bit stuff is necessary.

Denis Koshman Re: WA 5 // Problem 1539. Intelligence Data 19 Aug 2008 06:53

5 5
0.00000
0.03138
0.86105
0.20258
0.27292

This test is invalid because all input numbers are positive (I also checked Russian version, it's more clear from that one)

But if this test would be valid, correct answer is 200001 because 1/12652 becomes 0.00001 after rounding :)

Edited by author 19.08.2008 07:09

Discussion of Problem 1539. Intelligence Data