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

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

12321 - Gas Station

Post by Amoeba » Wed Oct 26, 2011 11:54 am

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

Post by JavyLeon » Mon Dec 02, 2013 4:53 am

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

Post by brianfry713 » Wed Dec 04, 2013 12:50 am

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: 75
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 12321 - Gas Stations

Post by dibery » Thu Feb 23, 2017 10:57 am

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.

Post Reply

Return to “Volume 123 (12300-12399)”

Who is online

Users browsing this forum: No registered users and 1 guest