846 - Steps

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:
Darko wrote: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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada
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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
Thanks...... I got Ac now

I change 0.01 to 0.00001

Thanks your help

soulseek
New poster
Posts: 1
Joined: Wed Feb 07, 2007 4:48 am

846

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
New poster
Posts: 1
Joined: Sun Mar 18, 2007 3:03 am

Test cases

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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
In fact, if the input number is n, the maximum step cannot exceed floor(sqrt(n)).
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 846 - Steps

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

Code: Select all

``````Removed after AC
``````
pls help
Last edited by abid_iut on Sun Jan 04, 2009 5:56 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA

Re: 846 - Steps

Just try 5 5

And remove your code after AC
Remove your code after AC

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 846 - Steps

Thanks A lot
it was lack of concentration
anyway thanks a lot once again
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 846 - Steps

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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 846 - Steps

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
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

nm_varun
New poster
Posts: 5
Joined: Tue Dec 25, 2012 7:27 am

Re: 846 - Steps

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 846 - Steps

Try using scanf and printf instead of cin and cout.
Check input and AC output for thousands of problems on uDebug!

nm_varun
New poster
Posts: 5
Joined: Tue Dec 25, 2012 7:27 am

Re: 846 - Steps

brianfry713 wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 846 - Steps

If ab<=2 you need to decrement n.
Check input and AC output for thousands of problems on uDebug!