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

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

846 - Steps

Post by Sajid » Fri Aug 08, 2003 10:49 pm

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

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

Post by miras » Tue Aug 26, 2003 1:33 pm

Hi did u tried with
input

1 2
1 3
1 4
1 5
1 1212321425345345
?????????? :D

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

Post by Sajid » Tue Aug 26, 2003 2:24 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

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Fri Aug 29, 2003 8:59 am

Hi, sajid!! :lol:

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) :lol: :lol:

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

Sorry

Post by Sajid » Sun Sep 07, 2003 11:37 am

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Sep 07, 2003 6:50 pm

No, it is not OK.

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

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

846 - Why SIGSEGV???

Post by Solutor » Thu May 13, 2004 6:52 pm

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 :roll:
[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]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 13, 2004 9:08 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.

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

Post by Solutor » Fri May 14, 2004 8:38 am

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 :D 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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri May 14, 2004 10:24 am

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
New poster
Posts: 3
Joined: Wed May 05, 2004 2:02 pm

Post by Solutor » Mon May 17, 2004 10:43 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 :cry:
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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 17, 2004 11:39 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){

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

Post by soyoja » Tue Jun 08, 2004 4:43 am

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!!! :) :) :)

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

846.... WA

Post by Wei-Ming Chen » Tue Dec 20, 2005 7:15 am

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

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Dec 20, 2005 9:28 am

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

Darko

Post Reply

Return to “Volume 8 (800-899)”