Rezolvare completă PbInfo #1685 Dif2

Sandu a studiat la ora de informatică mai multe aplicații cu vectori de numere naturale, iar acum are de rezolvat o problemă interesantă. Se dă un șir X=(X[1],X[2],…,X[n]) de numere naturale nenule și două numere naturale p1 și p2, unde p1<p2. Sandu trebuie să construiască un nou șir Y=(Y[1],Y[2],…,Y[n*n]) cu n*n elemente obținute din toate produsele de câte două elemente din șirul X (fiecare element din șirul Y este de forma X[i]*X[j], 1<=i, j<=n). Sandu are de calculat două valori naturale d1 și d2 obținute din șirul Y. Valoarea d1 este egală cu diferența maximă posibilă dintre două valori ale șirului Y. Pentru a obține valoarea d2, Sandu trebuie să considere că șirul Y are elementele ordonate descrescător iar d2 va fi diferența dintre valorile aflate pe pozițiile p1 și p2 în șirul ordonat descrescător. Sandu a găsit rapid valorile d1 și d2 și, pentru a le verifica, vă roagă să le determinați și voi.

Cerința

Dându-se șirul X cu n elemente și valorile p1 și p2, determinați valorile d1 și d2.

Date de intrare

Fișierul de intrare dif2.in conține pe prima linie un număr natural C care poate fi doar 1 sau 2. Dacă C=1, atunci pe linia a doua se va afla numărul natural n. Dacă C=2, atunci pe linia a doua se vor afla numerele naturale n p1 p2 separate prin câte un spațiu. În ambele cazuri, pe următoarele n linii se vor afla elementele șirului X, câte un număr natural pe fiecare linie a fișierului.

Date de ieșire

În cazul C=1, fișierul de ieșire dif2.out va conține pe prima linie valoarea d1 egală cu diferența maximă dintre oricare două valori din șirul Y. În cazul C=2 fișierul de ieșire va conține pe prima linie un număr natural d2 reprezentând diferența dintre valorile aflate pe pozițiile p1 și p2 din șirul Y, presupunând că ar fi ordonat descrescător.

Restricții și precizări

  • 3 < n < 300 000
  • 1 ≤ p1 < p2 ≤ n2
  • 1 ≤ X[i] < 300 000, i=1..n
  • Pentru teste valorând 30 de puncte vom avea C=1, iar pentru teste valorând 70 de puncte vom avea C=2.
  • Pentru teste valorând 10 puncte vom avea C=2 și n≤100

Exemplul 1

dif2.in

1
4
3
5
2
6

dif2.out

32

Explicație

Atenție, C=1, deci se rezolvă doar cerința 1!
Valoarea maximă d1 va fi 32 și se obține efectuând diferența dintre 6*6 și 2*2.

Exemplul 2

dif2.in

2
4 5 11
3
5
2
6

dif2.out

8

Explicație

Atenție, C=2, deci se rezolvă doar cerința 2!
Se obțin în Y următoarele 16 valori: 3*3, 3*5, 3*2, 3*6, 5*3, 5*5, 5*2, 5*6, 2*3, 2*5, 2*2, 2*6, 6*3, 6*5, 6*2, 6*6.
Valoarea d2 va fi 8, deoarece dacă vom considera șirul Y ordonat descrescător (36, 30, 30, 25, 18, 18, 15, 15, 12, 12, 10, 10, 9, 6, 6, 4), atunci Y[5]-Y[11]=18-10=8

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

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int MAXN = 300000 + 10;
int V[MAXN], n;

long long countSmall(long long x) {
    long long ans = 0;

    for(int i = 1, j = n; i <= n; ++i) {
        while(1LL * V[i] * V[j] > x)
            --j;
        ans += j;
    }

    return ans;
}


long long kth(long long pos) {
    long long ans = 0;
    for(long long i = (1LL << 40); i; i >>= 1LL) {
        int x = countSmall(ans + i);
        if(x < pos) {
            ans += i;
        }
    }
    return ans + 1;
}

int32_t main() {
    ifstream cin("dif2.in");
    ofstream cout("dif2.out");
    
    int t;
    long long a, b;

    cin >> t >> n;

    if(t == 2) cin >> a >> b;

    for(int i = 1; i <= n; ++i) {
        cin >> V[i];
    }

    sort(V + 1, V + n + 1);

    if(t == 1) {
        cout << 1LL * V[n] * V[n] - 1LL * V[1] * V[1] << endl;
    } else {
        cout << kth(1LL * n * n - a + 1) - kth(1LL * n * n - b + 1) << endl;
    }


    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 #1685 Dif2

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