[Google Kickstart] GBus count 暴力求解法

最近听说某个不存在的网站有个Kickstart的测评。通过Kickstart测试有机会可以获得这家不存在的公司的面试机会,好奇害死猫,吓得我赶紧去看看。

参赛指南参考这里:传送门

经过重重注册,我终于进到了系统,发现没有比赛,查了一下,哦原来有题库,赶紧看看题库,有个2月份的热身赛(Kickstart Practice Round 2018),撸起袖子加油干,开始写:


Problem A. GBus count

Problem

There exists a straight line along which cities are built.

Each city is given a number starting from 1. So if there are 10 cities, city 1 has a number 1, city 2 has a number 2,... city 10 has a number 10.

Different buses (named GBus) operate within different cities, covering all the cities along the way. The cities covered by a GBus are represented as 'first_city_number last_city_number' So, if a GBus covers cities 1 to 10 inclusive, the cities covered by it are represented as '1 10'

We are given the cities covered by all the GBuses. We need to find out how many GBuses go through a particular city.

Input

The first line contains the number of test cases (T), after which T cases follow each separated from the next with a blank line.
For each test case,
The first line contains the number of GBuses.(N)
Second line contains the cities covered by them in the form
a1 b1 a2 b2 a3 b3...an bn
where GBus1 covers cities numbered from a1 to b1, GBus2 covers cities numbered from a2 to b2, GBus3 covers cities numbered from a3 to b3, upto N GBuses.
Next line contains the number of cities for which GBus count needs to be determined (P).
The below P lines contain different city numbers.
Output
For each test case, output one line containing "Case #Ti:" followed by P numbers corresponding to the number of cities each of those P GBuses goes through.

Limits

1 <= T <= 10
ai and bi will always be integers.

Small dataset

1 <= N <= 50 
1 <= ai <= 500, 1 <= bi <= 500 
1 <= P <= 50

Large dataset

1 <= N <= 500 
1 <= ai <= 5000, 1 <= bi <= 5000 
1 <= P <= 500

Sample

Input

 

2
4
15 25 30 35 45 50 10 20
2
15
25

10
10 15 5 12 40 55 1 10 25 35 45 50 20 28 27 35 15 40 4 5
3
5
10
27

Output

Case #1: 2 1
Case #2: 3 3 4

Explanation for case 1:

2 GBuses go through city 15 (GBus1 [15 25] and GBus4 [10 20])
1 GBus goes through city 25 (GBus1 [15 25])

Code (Java)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.Reader;
import java.util.Arrays;
import java.util.Scanner;

public class GBusCount {
    
    private static String path = "/Users/ousheobin/Downloads/";

    public static void main(String[] args) throws FileNotFoundException {
        FileInputStream fis = new FileInputStream(path+"A-large-practice.in");
        PrintStream out = new PrintStream(new FileOutputStream(path+"A-large-practice.out"));
        System.setIn(fis);
        System.setOut(out);
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int total = in.nextInt();
        int testCase = 1;
        while( total >= testCase ) {
            int n = in.nextInt();
            int curr = 0;
            int[][] pair = new int[1005][2];
            while(curr<n) {
                pair[curr][0] = in.nextInt();
                pair[curr][1] = in.nextInt();
                curr ++;
            }
            int p = in.nextInt();
            System.out.print("Case #"+testCase+":");
            for(int i = 0 ; i < p ; i ++ ) {
                int city = in.nextInt();
                int count = 0;
                for(int j = 0 ; j < n ; j ++ ) {
                    if( city >= pair[j][0] && city <= pair[j][1] ) {
                        count ++;
                    }
                }
                System.out.print(" "+count);
            }
            System.out.println();
            testCase ++;
        }
        
    }

}

标签: none
返回文章列表 文章二维码
本页链接的二维码
打赏二维码