TripProblem code: TRIP |
All submissions for this problem are available.
You are starting out on a long (really long) trip. On the way, there are N gas stations, the locations of which are given as a_1,a_2,...,a_N. Initially you are located at the gas station at a_1, and your destination is at location a_N. Your car can only store enough fuel to travel atmost M units without refilling. You can stop at any station and refill the car by any amount. Now you wish to plan your trip such that the number of intermediate stops needed to reach the destination is minimum, and also how many ways are there to plan your trip accordingly.
Input :
The first line two space seperated integers N and M. N lines follow, and the ith line has the value a_i (0 <= a_i <= 1000000000). The input will be such that a solution will always exist.Output :
Output two space seperated integers : The least number of stops, and the number of ways to plan the trip which uses the least number of stops. Output this value modulo 1000000007.Sample Input :
6 3 0 1 3 4 7 10
Sample Output :
3 2
Constraints :
2 <= N <= 1000000 1 <= M <= 1000 a_1 < a_2 < .. < a_N
| Author: | syco |
| Date Added: | 20-03-2010 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
The test cases are not good
The test cases are not good enough. I submitted a wrong program and it got ac.
I have taken N upto 1000000
I have taken N upto 1000000 and M as 999[Max value taken]
I am getting result without any exception.
Why i am getting runtime exception from your end.
Is that i have to put some memory constraints before running my script.
can you please provide
can you please provide another test case which has the number of ways more than 2
What d o you mean by number of wyas
i understand that it is
2 for all problems
one is from start
one from ending
am i wrong?
can anyone please suggest me
5 6 0 4 5 6 10 You cannot go
5 60
4
5
6
10
You cannot go directly from the start to the end, because they are too far apart. You can however get there with 1 intermediate stop, and there are three ways of doing so: 0-4-10, 0-5-10, 0-6-10.
The correct output is 1 3.
what is wrong in my solution
what is wrong in my solution ???
pls anyone help me....
#include<stdio.h>
main()
{
long no_state , in_value;
long lower,upper,count=0,least=-1,state;
scanf("%ld %ld",&no_state,&in_value);
count=no_state;
if((no_state>1)&&(in_value>0))
{
while(no_state>0)
{
scanf("%ld",&state);
if(count==no_state)
lower=state;
if(state<=in_value)
least++;
if(no_state==1)
upper=state;
no_state--;
}
if((upper-lower)<=in_value)
printf("%ld %ldn",0,1);
else
printf("%ld %ldn",((upper-lower)/in_value),least);
}
return 0;
}
Admin here is my
Dear Admin I was just
Dear Admin
I was just wondering the way different languages are tested. If I look at my code, I don't find any complexity difference with the solution of a guy who consumed 0M and 0sec to find the solution. Difference is I solved it in Java and his solution is in C++.
I wonder why there isn't a single accepted solution in Java.
Regards,
wonder why there is no Java
wonder why there is no Java solution to this problem
@admin the judge gives 0M to
@admin
the judge gives 0M to my programme which is not true also it gives TLE whereas for input of size of order 10^6 it works fast on my pc
pls respond
my soln takes same time as
my soln takes same time as that of anant
any hint to improve the soln
pls respond
where i can find editorials