## 12321 - Gas Stations

All about problems in Volume 123. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Amoeba
New poster
Posts: 6
Joined: Tue Sep 20, 2011 4:01 pm

### 12321 - Gas Station

i don't know reason for why i got a WA.

my outputs are correct. i think

anyone give me advice to solve this problem.

here my code.

Code: Select all

``````#include "stdio.h"
#include "stdlib.h"

#define SIZE 10050

typedef struct Gas
{
int start;
int end;
bool isRemoved;
}Gas;

int cmp(const void* a, const void* b)
{
if(((Gas*)a)->start == ((Gas*)b)->start)
return ((Gas*)a)->end - ((Gas*)b)->end;
return ((Gas*)a)->start - ((Gas*)b)->start;
}

int MIN(int a, int b)
{
return (a<=b)?a:b;
}

int MAX(int a, int b)
{
return (a>=b)?a:b;
}

int main()
{
Gas gas[SIZE];
int length, number, location, range, max, cnt;
int sRange, eRange;
bool exit;

while(1)
{
scanf("%d %d", &length, &number);

if(length == 0 && number == 0)
break;

max = -1000000;
cnt = 0;
exit = false;

for(int i=0; i<number; i++)
{
scanf("%d %d", &location, &range);
gas[i].start = location - range;
gas[i].end = location + range;
gas[i].isRemoved = false;
}

qsort(gas, number, sizeof(Gas), cmp);

if(gas[0].start > 0)
{
puts("-1");
continue;
}

max = gas[0].end;

if(max >= length)
{
printf("%d\n", number-1);
continue;
}

for(int i=1; i<number; i++)
{
if(max >= gas[i].start)
{
max = MAX(max, gas[i].end);

if(max >= length)
break;
}
}

if(max < length)
{
puts("-1");
continue;
}

for(int i=0; i<number-1; i++)
{
if(exit)
break;

if(!gas[i].isRemoved && gas[i].start <= 0 && gas[i].end >= length)
{
cnt = number-1;
exit = true;
break;
}

for(int j=i+1; j<number; j++)
{
if(!gas[i].isRemoved && gas[i].end >= gas[j].start)
{
sRange = MIN(gas[i].start, gas[j].start);
eRange = MAX(gas[i].end, gas[j].end);

if(sRange <= 0 && eRange >= length)
{
cnt = number-2;
exit = true;
break;
}

for(int k=i+1; k<j; k++)
{
if(!gas[k].isRemoved && sRange <= gas[k].start && gas[k].end <= eRange)
{
if(gas[k].start == 0 && gas[k].end >= gas[i].end)
break;
cnt++;
gas[k].isRemoved = true;
}
}

if(sRange <= 0)
{
for(int z=0; z<i; z++)
{
if(gas[z].end < eRange)
{
cnt++;
gas[z].isRemoved = true;
}
}
}
if(eRange >= length)
{
cnt += number - j -1;
exit = true;
break;
}
}
}
}
printf("%d\n", cnt);
}
return 0;
}

``````
thx for ur time

JavyLeon
New poster
Posts: 1
Joined: Tue Nov 19, 2013 5:42 pm

### 12321 - Gas Stations

I know it's very difficult can see one error in a complete code but i don't know what to do, I only get wa therefore the test case works perfectly and the in/out it's correct, I let my code, I hope you can help me, thank you so much

Code: Select all

``````import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
/**
* Gas Stations Final
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Throwable {
// TODO Auto-generated method stub
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
for (StringTokenizer st; (st = new StringTokenizer(in.readLine())) != null;) {
int longi,numGas;
int puntoactual=0, resul=0;
longi=parseInt(st.nextToken());
numGas = parseInt(st.nextToken());
//System.out.println("longitud:"+longi);
//System.out.println("gasolineras:"+numGas);
if(longi!=0 && numGas!=0){
ArrayList<ArrayList<Integer>>array=new ArrayList<ArrayList<Integer>>();
int radio, posicion;
for(int i=0;i<numGas;i++){
st=new StringTokenizer(in.readLine());
posicion=parseInt(st.nextToken());
radio=parseInt(st.nextToken());
array.add(new ArrayList<Integer>());
array.get(i).add(posicion);
array.get(i).add(radio);
}
while(!array.isEmpty()){
posicion=array.get(0).get(0);
radio=array.get(0).get(1);
if(puntoactual<posicion-radio){
resul=-1;
break;

}else if(puntoactual>posicion+radio){
resul++;
//System.out.println("resul aumentado:"+resul);
}else if(array.size()>1&&puntoactual>=(array.get(1).get(0)-array.get(1).get(1))){
resul++;
//System.out.println("resul aumentado:"+resul);
}else if(puntoactual>=longi){
resul++;
//System.out.println("resul aumentado:"+resul);
}else if(array.size()==1 && posicion+radio<longi){
resul=-1;
break;
}else{
puntoactual=posicion+radio;
}
//System.out.println("punto actual:"+puntoactual);
array.remove(0);
}
System.out.printf("%d%n", resul);

}else{
break;
}

}
}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12321 - Gas stations

Input:

Code: Select all

``````71055 2
3141 60596
52214 59153
26972 10
14979 14244
2197 7397
25385 6632
23279 6822
15509 22965
17447 23775
23163 25546
24113 21278
21565 17446
669 8057
83079 8
31404 40459
61295 46409
36114 3905
30309 45582
15527 79623
54453 47993
74151 43294
63753 39840
37064 2
29375 20216
4400 29262
59539 8
52204 48417
47873 30104
21314 10052
57691 17202
49271 5459
24276 53419
41373 3725
17760 13085
49081 1
1098 10345
90822 7
21810 17381
15970 45024
86861 80972
40375 48841
90559 23949
5092 87772
71726 7563
52358 4
19035 34045
44285 29343
11306 52339
11948 26668
74065 10
54642 60576
54782 50705
43016 14868
21859 6444
47803 71611
52157 15778
36098 61594
41079 56399
73639 33669
47262 9518
76225 6
17153 70938
21430 75751
34746 35967
71611 20602
16595 29461
40874 47431
0 0
``````
AC output:

Code: Select all

``````1
9
7
0
7
-1
6
3
9
5
``````
Check input and AC output for thousands of problems on uDebug!

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 12321 - Gas Stations

This problem is very similar to 10020.
If you get accepted on that problem, the same code can be used here with little modification.
Life shouldn't be null.