846 - Steps
Moderator: Board moderators
-
- Learning poster
- Posts: 94
- Joined: Sat Oct 05, 2002 5:34 pm
- Location: CS - AIUB, Dhaka, Bangladesh.
- Contact:
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...
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
-
- Learning poster
- Posts: 94
- Joined: Sat Oct 05, 2002 5:34 pm
- Location: CS - AIUB, Dhaka, Bangladesh.
- Contact:
but the problem says...
isn't it??????
For each test case, a line follows with two integers: 0 <= x <= y < 2^31
isn't it??????
Sajid Online: www.sajidonline.com
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
-
- Learning poster
- Posts: 94
- Joined: Sat Oct 05, 2002 5:34 pm
- Location: CS - AIUB, Dhaka, Bangladesh.
- Contact:
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 ?
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
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]
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]
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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)
And you can handle any number of inputs.
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;
}
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
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
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Yes, your calculation is wrong.
Try
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
Try
Code: Select all
4
1 10
251 476
23 38
99 163
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
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
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
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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){
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){
-
- Experienced poster
- Posts: 106
- Joined: Sun Feb 17, 2002 2:00 am
- Location: Seoul, South Korea
- Contact:
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 )...
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!!!
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
846.... WA
I don't know why I got WA....
Please help me
#include <stdio.h>
#include <math.h>
int main()
{
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.