846 - Steps

[mamun]

What if d == c*(c+1) ? Are you sure it's 2*c ?

Should be.

Wei-Ming Chen's problem is in precision.

Code: Select all

c=(int)(sqrt(d)-0.01);

is too risky. Handle it in a more clear-cut way.
Output of

Code: Select all

0 2147395601

is

Code: Select all

92680

Remember, you need long in this problem.

[Darko]

Heh, I didn't even look at the problem, I looked at my code and saw that I have three different answers (2*c-1 if c*(c+1)==d), so I thought that was the problem.

That is so wrong (say 45 51, answer is 4, not 3). But it's AC anyway, go figure :)

Darko

[Wei-Ming Chen]

Thanks...... I got Ac now

I change 0.01 to 0.00001

Thanks your help

[soulseek]

I need a lot of correct test cases
I think my code had solved the problem perfectly, but got WA
plz help me

[Cristiano Garcia]

These are the a few test cases. My code was accepted and these are the answers it provides for the input below. Hope it helps:
Number of test cases 91.
Format:
x y
steps
---------------------------------
91
0 0
0
1 4
3
0 1
1
2 3
1
2 8
4
0 3
3
4 5
1
3 15
6
0 6
4
7 11
3
7 30
9
0 12
6
14 21
5
15 60
13
0 24
9
29 42
7
30 119
18
0 48
13
58 84
10
60 238
26
1 97
19
116 168
14
120 475
37
3 194
27
232 335
20
240 950
53
7 389
39
465 671
28
480 1900
75
15 778
55
930 1341
40
959 3800
106
30 1555
78
1860 2683
57
1919 7600
150
60 3110
110
3719 5365
81
3839 15200
213
121 6221
156
7438 10730
114
7678 30400
301
242 12442
220
14877 21460
162
15356 60800
426
484 24884
312
29754 42920
229
30712 121600
602
968 49768
441
59508 85840
324
61424 243200
852
1936 99536
624
119016 171680
458
122848 486400
1205
3872 199072
883
238032 343360
649
245696 972800
1705
7744 398144
1249
476064 686720
917
491392 1945600
2411
15488 796288
1767
952128 1373440
1298
982784 3891200
3410
30976 1592576
2499
1904256 2746880
1835
1965568 7782400
4823
61952 3185152
3534
3808512 5493760
2596
3931136 15564800
6821
123904 6370304
4998
7617024 10987520
3671
7862272 31129600
9647
247808 12740608
7069
15234048 21975040
5192
15724544 62259200
13643
495616 25481216
9997
30468096 43950080
7343
31449088 124518400
19294
991232 50962432
14138
60936192 87900160
10385
62898176 249036800
27286
1982464 101924864
19994
121872384 175800320
14687
125796352 498073600
38588
3964928 203849728
28276
243744768 351600640
20770
251592704 996147200
54573
7929856 407699456
39988
487489536 703201280
29374
503185408 1992294400
77177
15859712 815398912
56552
974979072 1406402560
41541
--------------------------
You'll probably use this as an input file. So here are only the inputs:
0 0
1 4
0 1
2 3
2 8
0 3
4 5
3 15
0 6
7 11
7 30
0 12
14 21
15 60
0 24
29 42
30 119
0 48
58 84
60 238
1 97
116 168
120 475
3 194
232 335
240 950
7 389
465 671
480 1900
15 778
930 1341
959 3800
30 1555
1860 2683
1919 7600
60 3110
3719 5365
3839 15200
121 6221
7438 10730
7678 30400
242 12442
14877 21460
15356 60800
484 24884
29754 42920
30712 121600
968 49768
59508 85840
61424 243200
1936 99536
119016 171680
122848 486400
3872 199072
238032 343360
245696 972800
7744 398144
476064 686720
491392 1945600
15488 796288
952128 1373440
982784 3891200
30976 1592576
1904256 2746880
1965568 7782400
61952 3185152
3808512 5493760
3931136 15564800
123904 6370304
7617024 10987520
7862272 31129600
247808 12740608
15234048 21975040
15724544 62259200
495616 25481216
30468096 43950080
31449088 124518400
991232 50962432
60936192 87900160
62898176 249036800
1982464 101924864
121872384 175800320
125796352 498073600
3964928 203849728
243744768 351600640
251592704 996147200
7929856 407699456
487489536 703201280
503185408 1992294400
15859712 815398912
974979072 1406402560

[andmej]

In fact, if the input number is n, the maximum step cannot exceed floor(sqrt(n)).

[abid_iut]

why I am getting WA
pls someone check
here is the code:

Code: Select all

Removed after AC


pls help

[ExUCI]

Just try 5 5

And remove your code after AC

[abid_iut]

Thanks A lot
it was lack of concentration
anyway thanks a lot once again

[Shafaet_du]

In 'n' steps you can advance to maximum (i/2)*( (i/2) +1) numbers if n is odd and (i/2)*( (i/2) +1) + ceil(i/2) numbers if n is even,where i=n/2. Save this and do a binary search(linear search may also do)

[plamplam]

There is a simpler solution regardless of n being odd/even. First notice that the result only depends on the value of |x - y| regardless of the values of x and y. Now try a few cases with pen and paper and you will soon find out why a formula can be derived using sqrt(|x - y|).
Hint: (n * n) = ((n - 1) * (n - 1) + n + n) - 1

[nm_varun]

Can anyone help me out here (Time Limit exceeded)? Is there any way to improve the efficiency that I'm missing?

Code: Select all

#include<iostream>
#include<math.h>

using namespace std;

int main()
{
    long long ab;
    long x,y,a,b,root;
    int n;
   
    cin>>n;
    while(n!=0)
    {
        cin>>x>>y;
        ab=y-x;
        if(ab<=2)
        {
            cout<<ab<<endl;
            continue;
        }
        root=ceil((sqrt(4*ab+1)-1)/2);
        a=root*(root+1);
        b=root*(root-1);
        if((ab-b)<=(a-b)/2)
            cout<<root*2-1<<endl;
        else
            cout<<root*2<<endl;
        n--;
    }
   
    return 0;
}


[brianfry713]

Try using scanf and printf instead of cin and cout.

[nm_varun]

Try using scanf and printf instead of cin and cout.

still goes beyond TL. i'm going to try saving the outputs and running a binomial search.

thanks anyway

[brianfry713]

If ab<=2 you need to decrement n.