Zoznam úloh

5. Jednoduché plavidlá

Zadanie

Účastníci si na LTT vyrábali rôzne plavidlá. Plavidlo vyzerá ako drevený kváder vyplnený sudmi / bandaskami / inými nádobami so vzduchom, aby plavidlo plávalo. Na stavanie potrebujeme najprv vyrobiť rám z dreva. Vedúci na to už dopredu nakúpili kopu materiálu.

Úloha

Máme dostupných $2n$ drevených dosiek a $4n$ drevených hranolov. Každá doska je v tvare obdĺžnika s rozmermi $x$ a $y$. Z týchto vieme postaviť najviac $n$ plavidiel, na každé použijeme dve dosky spojené štyrmi hranolmi do kvádra. Na to aby plavidlo fungovalo musí mať objem aspoň $a$, ale nechceme, aby bolo príliš veľké, teda objem plavidla nesmie byť väčší ako $b$. Dostaneme rozmery dosiek a dĺžky hranolov. Zisti, koľko najviac plavidiel z nich vieme postaviť. Z každej dosky máme dva kusy, a z každého hranolu máme štyri kusy.

Formát vstupu

V prvom riadku vstupu sú tri čísla $n$, $a$ a $b$ ($1 \leq n \leq 10^6$, $1 \leq a \leq b \leq 10^9$) udávajúce počet rôznych dosiek, minimálny objem a maximálny objem plavidla.

V druhom riadku je $n$ čísel $h_i$ ($1 \leq h_i \leq 10^9$) udávajúce dĺžky hranolov.

Nasleduje $n$ riadkov s rozmermi dosiek. V každom riadku sú dve čísla $x$ a $y$ ($1 \leq x, y \leq 10^9$) udávajúce rozmery dosky.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
$1 \leq n \leq$ $100$ $1000$ $2 \cdot 10^5$ $2 \cdot 10^5$

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo udávajúce maximálny počet plavidiel, ktoré vieme postaviť z materiálov na vstupe.

Príklady

Vstup

5 29 35
1 4 3 6 3
10 3
1 8
7 1
6 1
2 5

Výstup

3

Plavidlá môžu byť napríklad rozmerov $10 \cdot 3 \cdot 1$, $1 \cdot 8 \cdot 4$ a $2 \cdot 5 \cdot 3$. Iné plavidlá s požadovaným objemom vytvoriť nevieme.

Vstup

3 1 5
1 4 5
10 3
6 1
2 3

Výstup

0

Najmenšie plavidlá, čo vieme postaviť, májú rozmery $6 \cdot 1 \cdot 1 = 2 \cdot 3 \cdot 1 = 6$, čo už je príliš veľké.

Objem jedného plavidla je $xyh$. Toto číslo musí byť v intervale $[a, b]$. Takže pre každú dosku si vieme vypočítať možný interval dĺžky hranolov. Pre každé plavidlo teda platí $\lceil \frac{a}{xy} \rceil \leq h \leq \lfloor \frac{b}{xy} \rfloor$. Takže naša úloha sa transformuje na to, že máme na vstupe $n$ čísel a $n$ intervalov. Chceme medzi nimi vytvoriť čo najviac párov pre ktoré platí, že dané číslo je v intervale. Nech intervaly sú $[L_i, R_i]$ a čísla $h_i$.

Bruteforce

Ku každému číslu $h_i$ chceme nájsť interval $[L_j, R_j]$. Čísla si utriedime a budeme ich párovať v poradí od najmenšieho. Pre každé číslo si potrebujeme nájsť interval do ktorého pasuje. Pre dané čislo chceme nájsť ten najlepší interval, teda taký do ktorého pasuje a zároveň hodnota $R_j$ je čo najmenšia. Potom sa nám nestane, že sme nejaký už spárovali a potom nám niečo nebude sedieť. Inými slovami ak existuje nejaké optimálne riešenie, tak existuje rovnako dobré, ktoré páruje vždy tie najbližšie intervaly. Naopak to platiť nemusí. Pre každé číslo si nájdeme takýto najbližší nevyužitý interval a spárujeme ich spolu ak sa našiel. Inak ideme ďalej.

Časová zložitosť tohoto bude $O(n^2)$, lebo pre každé číslo budeme hľadať najbližší nepoužitý interval, teda všetkými intervalmi prechádzať pri každom čísle. Pamäť bude $O(n)$, lebo si pamätáme iba vstup.

import sys

input = sys.stdin.buffer.readline

n, a, b = map(int, input().split())

boards = list(map(int, input().split()))

intervals = []

for _ in range(n):
    x, y = map(int, input().split())
    s = x * y

    L = (a + s - 1) // s
    R = b // s

    if L <= R:
        intervals.append([L, R, False])

boards.sort()

ans = 0

for h in boards:
    best = -1

    for i in range(len(intervals)):
        if intervals[i][2]:
            continue

        L, R, used = intervals[i]

        if L <= h <= R:
            if best == -1 or R < intervals[best][1]:
                best = i

    if best != -1:
        intervals[best][2] = True
        ans += 1

print(ans)
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Interval {
    int64 L, R;
    bool used = false;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int64 a, b;
    cin >> n >> a >> b;

    vector<int64> h(n);
    for (int i = 0; i < n; i++)
        cin >> h[i];

    vector<Interval> intervals;

    for (int i = 0; i < n; i++) {
        int64 x, y;
        cin >> x >> y;

        int64 S = x * y;

        int64 L = (a + S - 1) / S;
        int64 R = b / S;

        if (L <= R)
            intervals.push_back({L, R, false});
    }

    sort(h.begin(), h.end());

    int ans = 0;

    for (int64 board : h) {
        int best = -1;

        for (int i = 0; i < (int)intervals.size(); i++) {
            if (intervals[i].used) continue;
            if (intervals[i].L <= board && board <= intervals[i].R) {
                if (best == -1 || intervals[i].R < intervals[best].R)
                    best = i;
            }
        }

        if (best != -1) {
            intervals[best].used = true;
            ans++;
        }
    }

    cout << ans << "\n";
}

Optimálne riešenie

Skúsme sa bližšie pozrieť na hľadanie toho správneho intervalu. Potrebujeme dátovú štruktúru, ktorá nám vie rýchlo povedať ten najbližší interval a odstrániť ho. Túto operáciu vieme realizovať napríklad haldou. Budeme mať teda haldu, v ktorej budeme mať aktuálnych kandidátov na intervaly. Táto halda bude minimová, zoradená podľa hodnôt $R_j$. Keď nám teda príde číslo $h_i$, vieme ho v logaritmickom čase odstrániť z haldy a spárovať ho s tým najoptimálnejším intervalom.

Musíme ešte zariadiť, aby v halde boli len dobrí kandidáti, teda takí, ktorí sa ešte budú dať spárovať s nejakým číslom. Keďže čísla postupne rastú vieme všetky intervaly, kde $h_i \leq L_j$ z haldy odstraňovať. Už sa k nim nemá ako nájsť pár. Intervaly kde $L_j \leq h_i$ do haldy zase musíme pridať, lebo tie sa teraz, alebo niekedy v budúcnosti budú dať spárovať.

Pre rýchle hľadanie intervalov na pridanie do haldy si ich na začiatku utriedime podľa $R_j$ a potom si pamätáme index, že pokiaľ sme tie intervaly do haldy pridali. Samotné pridávanie bude znamenať posúvanie tohoto indexu a pridanie intervalu do haldy.

Každý interval sa práve raz pridá do haldy a práve raz z nej odoberie. Časová zložitosť tohoto riešenia teda bude $O(n \cdot log(n))$. Pamäťová zložitosť je $O(n)$, keďže si pamätáme len haldu a samotný vstup - obe lineárnej veľkosti.

import heapq

n, a, b = map(int, input().split())

dosky = list(map(int, input().split()))

intervaly = []

for _ in range(n):
    x, y = map(int, input().split())
    s = x * y

    L = (a + s - 1) // s
    R = b // s

    if L <= R:
        intervaly.append((L, R))

dosky.sort()
intervaly.sort()

heap = []

ans = 0
ptr = 0
m = len(intervaly)

for h in dosky:
    while ptr < m and intervaly[ptr][0] <= h:
        heapq.heappush(heap, intervaly[ptr][1])
        ptr += 1

    while heap and heap[0] < h:
        heapq.heappop(heap)

    if heap:
        heapq.heappop(heap)
        ans += 1

print(ans)
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Interval {
    int64 L, R;
    bool operator<(const Interval &other) const {
        if (L != other.L) return L < other.L;
        return R < other.R;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int64 a, b;
    cin >> n >> a >> b;

    vector<int64> h(n);
    for (int i = 0; i < n; i++)
        cin >> h[i];

    vector<Interval> intervals;

    for (int i = 0; i < n; i++) {
        int64 x, y;
        cin >> x >> y;

        int64 S = x * y;

        int64 L = (a + S - 1) / S; // ceil(a / S)
        int64 R = b / S;           // floor(b / S)

        if (L <= R)
            intervals.push_back({L, R});
    }

    sort(h.begin(), h.end());
    sort(intervals.begin(), intervals.end());

    priority_queue<int64, vector<int64>, greater<int64>> pq;

    int ptr = 0;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        while (ptr < (int)intervals.size() && intervals[ptr].L <= h[i]) {
            pq.push(intervals[ptr].R);
            ptr++;
        }

        while (!pq.empty() && pq.top() < h[i])
            pq.pop();

        if (!pq.empty()) {
            pq.pop();
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty