9. *Parking System

ucko0o 3 Точки

9. *Parking System

Здравейте, колеги.

Доста се затрудних с въпросната задача, от Java Advanced (Multidimensional Arrays).

Пробвах всичко, за което се сетих, но така и не можах да изкарам повече от 50 точки.

Съответно 5 и 9 тест са ми Time Limit, а 4, 8 и 10 грешни отговори.

Смених двумерния масив и с двумерен списък, но резултатът не се подобри.

Ще съм благодарен ако някой помогне.

РЕЩЕНИЕ: https://pastebin.com/P61Jxsz7

УСЛОВИЕ:

1.*Parking System

The parking lot in front of SoftUni is one of the busiest in the country, and it’s a common cause for conflicts between the doorkeeper Bai Tzetzo and the students. The SoftUni team wants to proactively resolve all conflicts, so an automated parking system should be implemented. They are organizing a competition – Parkoniada – and the author of the best parking system will win a romantic dinner with RoYaL. That’s exactly what you’ve been dreaming of, so you decide to join in.

The parking lot is a rectangular matrix where the first column is always free and all other cells are parking spots. A car can enter from any cell of the first column and then decides to go to a specific spot. If that spot is not free, the car searches for the closest free spot on the same row. If all the cells on that specific row are used, the car cannot park and leaves. If two free cells are located at the same distance from the initial parking spot, the cell which is closer to the entrance is preferred. A car can pass through a used parking spot.

Your task is to calculate the distance travelled by each car to its parking spot.

Example: A car enters the parking at row 1. It wants to go to cell 2, 2 so it moves through exactly four cells to reach its parking spot.

Input

On the first line of input, you are given the integers R and C, defining the dimensions of the parking lot
On the next several lines, you are given the integers Z, X, Y where Z is the entry row and X, Y are the coordinates of the desired parking spot
The input stops with the command ‘stop’. All integers are separated by a single space

Output

For each car, print the distance travelled to the desired spot or the first free spot
If a car cannot park on its desired row, print the message ‘Row {row number} full’

Constraints

2 ≤ R,C ≤ 10000
Z, X, Y are inside the dimensions of the matrix. Y is never on the first column
There are no more than 1000 input lines
Allowed time/space: 0.1s (C#) /16MB

Examples

Input

Output

4 4

1 2 2

2 2 2

3 2 2

stop

Row 2 full

Тагове:

24/01/2020 12:25:37 Java Advanced

AleksandarRadev 2 Точки

Ето един код който написах, обаче time limit си остава. Не виждам никакво complexity в кода.. Ако някой може да помогне, много ще съм благодарен :D. Направих масив където да записвам кои от редовете са пълни, за да не въртя през тях да проверявам всяко число, обаче пак дава time limit. 



import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
//        long s = System.nanoTime();
        Scanner scanner = new Scanner(System.in);

        String[] dimensions = scanner.nextLine().split(" ");

        int rows = Integer.parseInt(dimensions[0]);
        int cols = Integer.parseInt(dimensions[1]);

        int[][] parking = new int[rows][cols];

        while (true) {
            String input = scanner.nextLine();
            if (input.equals("stop")) break;
            String[] command = input.split(" ");

            int z = Integer.parseInt(command[0]);
            int x = Integer.parseInt(command[1]);
            int y = Integer.parseInt(command[2]);

            int moves = 0;
            boolean found = false;

            if (parking[x][y] == 0) {
                moves = findMoves(z, x, y);
                parking[x][y] = 1;
                found = true;
            } else {
                int range = 1;
                while (!found) {
                    if (y - range >= 1 && parking[x][y - range] == 0) {
                        moves = findMoves(z, x, y - range);
                        found = true;
                        parking[x][y - range] = 1;
                    } else if (y + range < parking[x].length && parking[x][y + range] == 0) {
                        moves = findMoves(z, x, y + range);
                        found = true;
                        parking[x][y + range] = 1;
                    }
                    if (y - range < 1 && y + range >= parking[x].length) {
                        System.out.printf("Row %d full%n", x);
                        break;
                    }
                    range++;
                }
            }
            if (found) System.out.println(moves);
        }
//        long end = System.nanoTime();
//        System.out.printf("%.6f", (double) (end - s) / 1000000);
    }

    private static int findMoves(int z, int x, int y) {
        return Math.abs(z - x) + y + 1;
    }
}

07/09/2020 19:15:53

AlexNestorov42 7 Точки

Заповядайте едно примерно решение :

https://pastebin.com/jcM0WVp3

08/09/2020 10:26:26

Nataliya_Zlateva 0 Точки

@ AlexNestorov42: Много ти благодаря! Смених от int[][] на boolean[][], както е в твоето решение, и взех последните 20 точки за време :))

22/09/2020 19:18:28