O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune 1 × N, fiind apoi împărțit în parcele de dimensiune 1 x 1. Pe fiecare dintre cele N parcele de dimensiune 1 × 1 firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la 1 la N, altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu h₁, h₂, …, h_N altitudinile parcelelor, există un indice vf, 1 ≤ vf ≤ N, astfel încât h₁ < h₂ <... < h_vf-1 < h_vf > h_vf+1 > ... > h_N.
Clienții au înregistrat deja cereri de construcție pentru M case. Fiecare dintre aceste cereri specifică însă o restricție mai ciudată, și anume faptul că doresc ca parcela de construcție să se afle exact la altitudinea q_j (1 ≤ j ≤ M).

Cerința

Scrieți un program care determină pentru fiecare cerere j (1 ≤ j ≤ M) dacă firma poate îndeplini restricția respectivă, mai exact dacă există măcar o parcelă i (1 ≤ i ≤ N) pentru care h_i = q_j.

Date de intrare

Fișierul de intrare colina.in conține pe prima linie două numere naturale N şi M ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc N numere naturale h₁, h₂, …, h_N, reprezentând altitudinile parcelelor. Pe ultima linie se găsesc M numere naturale q₁, q₂, …, q_M, reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații.

Date de ieșire

Fișierul de ieșire colina.out va conține M linii. Pe linia j (1 ≤ j ≤ M) va fi scris mesajul NU, dacă nu este posibilă construirea unei case la altitudinea q_j. În caz contrar, pe linia j va fi scris mesajul DA, urmat de un spațiu, apoi de indicii i pentru care h_i = q_j, separați de asemenea prin câte spațiu și scriși în ordine crescătoare.

Restricții și precizări

1 ≤ N, M ≤ 100.000
0 < h_i, q_j < 2³¹ pentru orice 1 ≤ i ≤ N și 1 ≤ j ≤ M.
Valorile q_j sunt distincte (nu s-au acceptat cereri identice).
Pentru teste în valoare de 20 puncte: N × M ≤ 100.000
Pentru teste în valoare de 40 puncte: hmax ≤ 100.000 unde hmax este altitudinea maximă a parcelelor.

Exemplu

colina.in

6 5
1 5 9 7 2 1
5 6 1 9 4

colina.out

DA 2
NU
DA 1 6
DA 3
NU

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

#include <stdio.h>
#define NMax 100005

int n, m;
int h[NMax], q;

// binary search on interval [low, high]
// if condition == 0 searches for the position where the sequence becomes decreasing
// if condition == 1 searches for 'value' on a increasing sequence
// if condition == 2 searches for 'value' in a decreasung sequence
// expects the preconditions and does not check them

int binarySearch(int low, int high, int condition, int value) {

    while (high - low > 1) {
        int mi = (low + high) / 2;
    
        if ((condition == 0 && h[mi] > h[mi + 1]) ||
            (condition == 1 && h[mi] > q) ||
            (condition == 2 && h[mi] < q)) {
                high = mi;
        } else {
            low = mi;
        }
    }

    if (condition) {
        if (h[low] == value) {
            return low;
        } else if (h[high] == value) {
            return high;
        }
        return -1;
    } else {
        if (h[low] > h[low + 1])
            return low;
        else
            return high;
    }
}

int main() {
    freopen("colina.in", "rt", stdin);
    freopen("colina.out", "wt", stdout);

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

    for (int i = 0; i < n; i++) {
        scanf("%d", &h[i]);
    }
    n++;
    // this would also work in O(N)
    int posI = binarySearch(0, n - 1, 0, 0);

    for (int i = 0; i < m; i++) {
        scanf("%d", &q);

        // sequence is increasing on [0, posI]
        // sequence is decreasing on [posI, N-1]
        int posSmall = binarySearch(0, posI, 1, q);
        int posBig = binarySearch(posI + 1, n - 1, 2, q);

        if (posSmall != -1 && posBig != -1) {
            printf("DA %d %d\n", posSmall + 1, posBig + 1);
        } else if (posSmall != -1) {
            printf("DA %d\n", posSmall + 1);
        } else if (posBig != -1) {
            printf("DA %d\n", posBig + 1);
        } else {
            printf("NU\n");
        }
    }

    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 #3219 colina

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