1187 - Roboti 1

Cerința

O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M. Terenul este împărțit în parcele de dimensiune 1x1. Pe unele dintre cele N×M parcele sunt plantați copaci. Firma dorește construirea unui grandios complex comercial și este necesară defrișarea întregului teren. În acest scop sunt utilizați roboți, fiecare robot având baza un pătrat de latură L. Suprafața defrișată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L. Fiecare robot pătrunde prin colțul stânga sus de coordonate (1, 1), se poate deplasa doar în dreapta și în jos și poate părăsi suprafața numai prin colțul dreapta jos, de coordonate (N, M). Cunoscând dimensiunile N, M ale terenului și coordonatele parcelelor în care sunt plantați copaci se cere:

1. Numărul minim de roboți necesari defrișării întregului teren. 2. Să se răspundă la Q interogări de forma k, unde k este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrișare cel mult k roboți.

Date de intrare

Fişierul de intrare roboti1.in conţine:

• Pe prima linie un număr natural p reprezentând varianta cerinței de rezolvare. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
• Pe a doua linie se află 3 numere naturale N, M, T separate prin câte un spațiu reprezentând numărul liniilor, numărul coloanelor terenului dreptunghiular, respectiv numărul copacilor plantați.
• Următoarele T linii conțin fiecare câte două numere naturale x y separate prin câte un spațiu, reprezentând linia, respectiv coloana parcelei în care este plantat un copac.
• În cazul cerinței 1, ultima linie conține un singur număr natural L, reprezentând latura unui robot.
• În cazul cerinței 2, penultima linie va conține un număr natural Q, iar ultima linie Q numere naturale k[1], k[2], …, k[Q] separate prin câte un spațiu, reprezentând numărul maxim de roboți ce pot fi utilizați în fiecare dintre cele Q interogări.

Date de ieșire

• Dacă valoarea lui p este 1, se va rezolva numai cerința 1. În acest caz, în fişierul de ieşire roboti1.out se va scrie un singur număr natural n1, reprezentând numărul minim de roboți utilizați.
• Dacă valoarea lui p este 2, se va rezolva numai cerința 2. În acest caz, în fişierul de ieşire roboti1.out se vor scrie Q linii. Fiecare linie i va conţine câte un număr natural ni, reprezentând latura minimă a unui robot astfel încât pentru defrișare să fie utilizați cel mult ki roboți.

Restricții și precizări

• 2 ≤ N, M, L ≤ 150
• 1 ≤ Q ≤ 150
• 1 ≤ k[i] ≤ 150, 1 ≤ i ≤ Q
• 1 ≤ T ≤ 1000
• Latura robotului nu poate fi mai mare decât dimensiunile terenului
• Pe tot parcursul deplasării, fiecare robot se va afla în interiorul suprafeţei terenului.
• În orice moment în interiorul suprafeţei terenului se va afla cel mult un robot.

Exemplu 1

Intrare

1
6 8 8
4 1
5 3
3 5
2 6
5 5
4 7
3 8
6 8
4

Iesire

1

Rezolvare

from collections import deque


def citire_date_intrare(fisier_intrare):
    with open(fisier_intrare, "r") as f:
        p = int(f.readline().strip())
        n, m, l = map(int, f.readline().strip().split())
        copaci = []
        for _ in range(l):
            x, y = map(int, f.readline().strip().split())
            copaci.append((x - 1, y - 1))  # Corectăm indexarea la 0
        if p == 2:
            Q = int(f.readline().strip())
            k = list(map(int, f.readline().strip().split()))
        else:
            Q = 0
            k = []
    return p, n, m, l, copaci, Q, k


def bfs(n, m, copaci, latura):
    def in_bounds(x, y):
        return 0 <= x < n and 0 <= y < m

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    vizitat = [[False] * m for _ in range(n)]
    for x, y in copaci:
        vizitat[x][y] = True

    num_roboți = 0
    for i in range(n):
        for j in range(m):
            if not vizitat[i][j]:
                num_roboți += 1
                q = deque([(i, j)])
                vizitat[i][j] = True
                while q:
                    x, y = q.popleft()
                    for d in range(4):
                        for k in range(1, latura + 1):
                            nx, ny = x + dx[d] * k, y + dy[d] * k
                            if in_bounds(nx, ny) and not vizitat[nx][ny]:
                                vizitat[nx][ny] = True
                                q.append((nx, ny))
    return num_roboți


def defrisare_minima(n, m, copaci, max_roboți):
    def numar_roboți(latura):
        return bfs(n, m, copaci, latura)

    stanga, dreapta = 1, min(n, m)
    while stanga < dreapta:
        mijloc = (stanga + dreapta) // 2
        if numar_roboți(mijloc) <= max_roboți:
            dreapta = mijloc
        else:
            stanga = mijloc + 1
    return stanga


def latura_minima_robot(n, m, copaci, Q, k):
    rezultate = []
    for fiecare_k in k:
        rezultate.append(defrisare_minima(n, m, copaci, fiecare_k))
    return rezultate


def scrie_rezultate(fisier_iesire, rezultate):
    with open(fisier_iesire, "w") as f:
        for rezultat in rezultate:
            f.write(f"{rezultat}\n")


def main():
    fisier_intrare = "roboti.in"
    fisier_iesire = "roboti.out"

    p, n, m, l, copaci, Q, k = citire_date_intrare(fisier_intrare)

    # Restricții și precizări
    assert 2 <= n <= 150, "n trebuie să fie între 2 și 150"
    assert 2 <= m <= 150, "m trebuie să fie între 2 și 150"
    assert 1 <= l <= 150, "l trebuie să fie între 1 și 150"
    for x, y in copaci:
        assert 0 <= x < n, "Coordonata x trebuie să fie între 1 și n"
        assert 0 <= y < m, "Coordonata y trebuie să fie între 1 și m"
    if p == 2:
        assert 1 <= Q <= 1000, "Q trebuie să fie între 1 și 1000"
        for fiecare_k in k:
            assert 1 <= fiecare_k <= 150, "k[i] trebuie să fie între 1 și 150"

    if p == 1:
        num_roboți = defrisare_minima(n, m, copaci, l)
        rezultate = [num_roboți]
    elif p == 2:
        laturi_minime = latura_minima_robot(n, m, copaci, Q, k)
        rezultate = laturi_minime

    scrie_rezultate(fisier_iesire, rezultate)


if __name__ == "__main__":
    main()