846 - Steps

[Sajid]

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...

[miras]

Hi did u tried with
input

1 2
1 3
1 4
1 5
1 1212321425345345
??????????

[Sajid]

but the problem says...

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

isn't it??????

[Red Scorpion]

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)

[Sajid]

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 ?

[Per]

No, it is not OK.

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

[Solutor]

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]

[little joey]

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.

[Solutor]

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

[little joey]

Yes, your calculation is wrong.
Try

Code: Select all

4
1 10
251 476
23 38
99 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

[Solutor]

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
Could anybody please help me to make it (much more) faster?
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

[little joey]

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){

[soyoja]

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 )...

[Wei-Ming Chen]

I don't know why I got WA....
Please help me

#include <stdio.h>
#include <math.h>
int main()
{

[Darko]

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

Darko