Grigorel tocmai a descoperit un joc nou de care este atât de încântat încât s-a gândit să-l propună la concursul Urmaşii lui Moisil de la Iaşi. Cum probabil v-aţi aşteptat deja, el oferă 100 de puncte ca recompensă celor care rezolvă corect jocul.

Fie N nave planare aflate la diferite coordonate întregi (x,y). În fiecare secundă, poate fi efectuată o operaţie de tipul: se selectează o navă i aflată la poziţia (xi,yi) şi se mută în una dintre cele 4 poziţii vecine: (xi+1,yi), (xi-1,yi), (xi,yi+1), (xi,yi-1).

Grigorel vrea să afle numărul minim de secunde după care vor fi cel puţin K linii cu măcar o navă şi cel puţin K coloane cu măcar o navă.

Cerinţă

Cunoscând coordonatele celor N nave planare, aflaţi numărul minim de secunde cerut de Grigorel.

Date de intrare

Fișierul de intrare naveplanare.in conține pe prima linie numerele naturale N şi K separate printr-un spaţiu, iar pe următoarele N linii se află câte două numere naturale separate printr-un spaţiu, reprezentând coordonatele navelor.

Date de ieşire

Fișierul de ieșire naveplanare.out conţine pe prima linie numărul minim de secunde cerut de Grigorel.

Restricţii şi precizări

1 ≤ K ≤ N ≤ 200
-1000 ≤ x, y ≤ 1000
Pentru 15% dintre teste N ≤ 13 și 0 ≤ x, y ≤ 31
Pentru alte 25% dintre teste N ≤ 50 și -100 ≤ x, y ≤ 100
Pentru alte 30% dintre teste N ≤ 50
La o anumită poziție se pot afla în orice moment oricâte nave

Exemplu

naveplanare.in

naveplanare.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema NavePlanare:

#define TuTTy "Cosmin-Mihai Tutunaru"
#include <cstdio>
#include <vector>
#include <algorithm>
#define infile "naveplanare.in"
#define outfile "naveplanare.out"
#define nmax 203
#define xmax 1013
#define inf (1<<29)

using namespace std;

int dp[2][nmax][2*xmax + 2*nmax];
vector<int> vx, vy;
int n, k;

int abs(int x) {
    if (x < 0) {
        return -x;
    }

    return x;
}

int solve(vector<int> v, int k) {
    int n = v.size();
    sort(v.begin(), v.end());

    for (size_t i = 0; i < v.size(); ++i) {
        v[i] += xmax + 2 * nmax;
    }

    for (int j = 0; j < nmax; ++j) {
        for (int t = 0; t < 2*xmax + 2*nmax; ++t) {
            dp[0][j][t] = inf;
        }
    }

    for (int t = 0; t < 2*xmax + 2*nmax; ++t) {
        dp[0][1][t] = abs(t - v[0]);

        if (t) {
            dp[0][1][t] = min(dp[0][1][t], dp[0][1][t-1]);
        }
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n+1; ++j) {
            for (int t = 0; t < 2*xmax + 2*nmax; ++t) {
                dp[i&1][j][t] = abs(t - v[i]) + dp[(i-1)&1][j][t];

                if (j && t) {
                    dp[i&1][j][t] = min(
                        dp[i&1][j][t],
                        abs(t - v[i]) + dp[(i-1)&1][j-1][t-1]
                    );
                }

                if (t) {
                    dp[i&1][j][t] = min(dp[i&1][j][t], dp[i&1][j][t-1]);
                }
            }
        }
    }

    int ret = inf;

    for (int j = k; j < n+1; ++j) {
        for (int t = 0; t < 2*xmax + 2*nmax; ++t) {
            ret = min(ret, dp[(n-1)&1][j][t]);
        }
    }

    return ret;
}


int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d %d", &n, &k);

    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        vx.push_back(x);
        vy.push_back(y);
    }

    printf("%d
", solve(vx, k) + solve(vy, k));

    fclose(stdin);
    fclose(stdout);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1167 NavePlanare

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1167 NavePlanare de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1167 NavePlanare