## 846 - Steps

Moderator: Board moderators

### 846 - Steps

What is the question asking in this problem??? i have used the following technic, but got WA...

1. x==y, step=0;
2. x+1==y step=1;
3. else {
diff=y-x
if(divisible(diff,2)) then step=diff/2+2;
else step=diff/2+3;
}

plz, help me...
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

Hi did u tried with
input

1 2
1 3
1 4
1 5
1 1212321425345345
??????????
miras
Learning poster

Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

but the problem says...
For each test case, a line follows with two integers: 0 <= x <= y < 2^31

isn't it??????
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

Hi, sajid!!

There are no input like that's.

Regards to your algo, what's the output for this:
1 7
diff = 7-1 = 6.
step = 6/2 + 2 = 5

The right answer is 4 step.
-> (1 - 2), (2 - 4), (4 - 6), (6 - 7)
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### Sorry

Sorry, i submited my wrong algo... the correction is.. below...

1. x==y, step=0;
2. x+1==y step=1;
3. else {
diff=(y-1)-(x+1)
if(divisible(diff,2)) then step=diff/2+2;
else step=diff/2+3;
}

Is it OK ?
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

No, it is not OK.

For instance, for input "45 54", the correct answer is "5", whereas you would answer "6".
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### 846 - Why SIGSEGV???

The following (quite simple) source works just fine for me under Win32 compiled with Dev-Cpp.
But when I want to submit it, the result is always SIGSEGV!
Could anyone help me why is that? I tried to read the lines in a simple array, a stringarray etc, but the result is always SIGSEGV...
Thanks before
[c]
#include <stdio.h>
#include <stdlib.h>

struct valuepair{
int value1;
int value2;
}VALUEARRAY[200];

int calculate_steps(int num1, int num2){
int diff, steps = 0, paratlan = 0;
if(num1 == num2)
return 0;
if((num1+1) == num2)
return 1;
diff = (num2 - 1) - (num1 + 1);
if(diff%2)
paratlan = 1;
steps = (diff/2)+2+paratlan;
return steps;
}

int main(void){
int i, j, numofrows, inputted = 0, outputted;
for(scanf("%d", &numofrows);inputted<numofrows;++inputted){
scanf("%d %d", &i, &j);
VALUEARRAY[inputted].value1 = i;
VALUEARRAY[inputted].value2 = j;
}
for(outputted=0;outputted<numofrows;++outputted)
printf("%d\n", calculate_steps(VALUEARRAY[outputted].value1, VALUEARRAY[outputted].value2));
return 0;
}
[/c]
Solutor
New poster

Posts: 3
Joined: Wed May 05, 2004 2:02 pm

SIGSEGV means a segmentation fault, which is (almost always) caused by accessing memory that doesn't belong to your program.

You reserve an array of 200 elements to store the input, but what happens if the input is bigger? Your program tries to access array elements beyond the last element of the array, and you get a segmentation fault.

In this case you don't know the number of inputs (there can be thousands), so it's better to read, calculate and report them one at the time,without storing them into an array:
(pseudo)
Code: Select all
`read numofrows;for al rows{   read valuepair;   calculate result;   print result;   }`

And you can handle any number of inputs.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Thanks a lot for your reply, little joey! You're right, cause I didn't realised that I don't have to store the input values in this problem, it's enough to store the results. So I've just send my prog with the new input handler and i didn't got SIGSEGV I've got WA instead I bet the fault is in the calculate_steps function now...
Any idea why i get WA?

Ps: I've tried to process the input lines into a full dinamic, reallocated array (which method got accepted in a previous problem) before my first post but it's got SIGSEGV too :O

greets
Solutor
New poster

Posts: 3
Joined: Wed May 05, 2004 2:02 pm

Try
Code: Select all
`41 10251 47623 3899 163`

Your program: 6, 114, 9, 33
Correct answer: 5, 29, 7, 15

For the first example it's easy to see that the answer must be 5:
1 + (1+2+3+2+1) = 10
the third:
23 + (1+2+3+3+3+2+1) = 38

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Finally I wrote a program that is able to calculate the right result(s) but it seems too slow for the problem and got TLE
I figured out that there is a system in the results, for example:

input:
5
0 15
0 1515
0 151515
0 15151515
0 1515151515 (this one takes a way too much time to calculate )

output:

7
77
778
7784
77849

as you can see, each result is equal to it's previous result + one digit more. But how can I calculate the last digit?

Thanks a lot
Solutor
New poster

Posts: 3
Joined: Wed May 05, 2004 2:02 pm

What is the maximal difference you can reach with 9 steps? (1+2+3+4+5+4+3+2+1=25). What is the maximal difference you can reach with 10 steps? (1+2+3+4+5+5+4+3+2+1=30). So what is the number of steps for all 25 < difference <= 30 ?
Can you derive a direct formula to calculate the maximal difference you can reach with n steps? Can you "reverse" this formula to directly compute steps(difference) with a "simple" formula?

BTW, you still use an array to store the results. Simpler is to write[c]
for(scanf("%d", &numofrows);(k<numofrows) && (scanf("%ld %ld", &i, &j));++k){

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

The most important idea is "Growing numbers are increase regularary".
For example,

1 answer = 1, maximum step = 1
1.2.1 answer = 4, maximum step = 3
1.2.3.2.1 answer = 9, maximum step = 5
1.2.3.4.3.2.1 answer = 16, maximum step = 7
and so on..

if the input number is 3, then maximum step couldn't exceed 3 ( Because it is smaller than 4, its maximum step is 3 )...
I love Problem Solving!!!
soyoja
Experienced poster

Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea

### 846.... WA

I don't know why I got WA....

#include <stdio.h>
#include <math.h>
int main()
{
Last edited by Wei-Ming Chen on Wed Dec 21, 2005 6:57 am, edited 1 time in total.
Wei-Ming Chen
Experienced poster

Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

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

Darko
Darko
Guru

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am