Loading...
ucko0o avatar 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

2 2 2

3 2 2

stop

4

2

4

Row 2 full

0
Java Advanced
AleksandarRadev avatar 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;
    }
}

0
AlexNestorov42 avatar AlexNestorov42 7 Точки

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

 

https://pastebin.com/jcM0WVp3

0
Nataliya_Zlateva avatar Nataliya_Zlateva 0 Точки

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.