Clasa din care faceţi parte merge în excursie! Principalul obiectiv este Lacul Roşu, o locaţie deosebit de frumoasă. Pentru a vă bucura cât mai mult de peisaj toţi elevii se vor plimba cu barca pe lac. Bărcile sunt de maxim două persoane şi au restricţiile următoare:

greutatea totală suportată de o barcă este C;
dacă în barcă se aşază două persoane, atunci diferența în modul dintre greutățile acestora trebuie să fie maxim B, în caz contrar barca nu este balansată și riscă să se răstoarne.

Dacă o singură persoană se aşază în barcă, nu se aplică restricția a doua.

Cerința

Care este numărul minim de bărci necesare pentru a putea plimba toţi elevii în condiţii de siguranţă?

Date de intrare

Fișierul de intrare barci.in conţine pe prima linie trei numere naturale separate prin spaţiu: N, C și B, reprezentând numărul de elevi, capacitatea maximă a unei bărci şi respectiv diferenţa maximă dintre greutatea a două persoane care se pot aşeza în aceeaşi barcă. Pe a doua linie se află N numere naturale separate prin spaţiu w[i] (1 ≤ i ≤ N), reprezentând greutăţile celor N elevi.

Date de ieșire

Fișierul de ieșire barci.out va conţine o singură linie pe care va fi scris numărul minim de bărci necesare.

Restricții și precizări

1 ≤ N ≤ 100 000
1 ≤ w[i] ≤ C ≤ 1 000 000 000, pentru 1 ≤ i ≤ N
0 ≤ B ≤ 1 000 000 000
Pentru teste în valoare de 30 de puncte, N ≤ 10
Pentru teste în valoare de 60 de puncte, N ≤ 1000

Exemplu

barci.in

8 100 10
81 37 32 88 55 93 45 72

barci.out

Explicație

Configuraţia celor 6 bărci poate fi următoarea:
1: (81)
2: (37, 32) deoarece 37+32 ≤ 100 şi 37-32 ≤ 10
3: (88)
4: (55, 45) deoarece 55 + 45 ≤ 100 şi 55 – 45 ≤ 10
5: (93)
6: (72)

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 barci:

//Paul Diac 100
#include <cstdio>
#include <string>
#include <cassert>
#include <cstdlib>
#define NMax 1000000
using namespace std;

int T = 10;

int N, C, B;
int v[NMax];

struct man {
    int w, prev, next, barked;
};
man o[NMax];

int compDesc(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

int validTogether(int i, int j) {
    return (0 <= i && i < N && 0 <= j && j < N && o[i].barked == 0 && o[j].barked == 0 &&
        i < j && o[i].w + o[j].w <= C && o[i].w - o[j].w <= B && o[j].w - o[i].w <= B);
}

void remove(int &idx) {
    o[idx].barked = 1;
    o[o[idx].prev].next = o[idx].next;
    o[o[idx].next].prev = o[idx].prev;
    idx = o[idx].next;
}

int main() {

    string fname = "barci";
    FILE *fin = fopen((fname + ".in").c_str(), "rt");   
    FILE *fout = fopen((fname + ".out").c_str(), "wt");

    fscanf(fin, "%d %d %d", &N, &C, &B);

    assert(N <= 100000);
    assert(C <= 1000000000);
    assert(B <= 1000000000);

    assert(1 <= N);
    assert(1 <= C);
    assert(0 <= B);

    for (int i = 0; i < N; i++) {
        fscanf(fin, "%d", &v[i]);
        assert(v[i] <= v[i]);
        assert(1 <= v[i]);
    }
    qsort(v, N, sizeof(v[0]), compDesc);

    for (int i = 0; i < N; i++) {
        o[i].w = v[i];
        o[i].next = i+1;
        o[i].prev = i-1;
        o[i].barked = 0;
    }
    o[N].prev = N-1;

    int left;
    for (left = N-1; left >= 0 && o[0].w + o[left].w <= C; left--);
    left++; // left end of interval with valid pair of current man

    int boats = 0;
    for (int i = 0; i < N; i++) if (!o[i].barked) {

        if (left == i) {
            left = o[left].next;
        }

        // left is always on the right (and smaller than) i.
        // and all left of i are barked

        while (o[left].prev > i && o[i].w + o[o[left].prev].w <= C) {
            left = o[left].prev;
        }

        if (validTogether(i, left)) {
            //fprintf(fout, "%d %d\n", o[i].w, o[left].w);
            remove(left);
        }
        o[i].barked = 1;
        boats++;
    }

    fprintf(fout, "%d\n", boats);

    fclose(fin);
    fclose(fout);

    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 #2186 barci

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2186 barci 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 #2186 barci