Fişierul intrare/ieşire:dif2.in, dif2.outSursăONI 2016, clasa a 9-a
AutorGheorghe ManolacheAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.7 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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=(X1,X2,…,Xn) de numere naturale nenule şi două numere naturale p1 şi p2, unde p1 < p2. Sandu trebuie să construiască un nou şir Y=(Y1,Y2,…,Yn*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 Xi * Xj, 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ţă

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 va 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 şi 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

  • 3 < n < 300.000
  • 1 ≤ p1 < p2 ≤ n2
  • 1 ≤ Xi < 300.000, pentru 1 ≤ i ≤ 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

Exemplu

dif2.indif2.outExplicaţie
1
4
3
5
2
6
32
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.
dif2.indif2.outExplicaţie
2
4 5 11
3
5
2
6
8
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 Y5-Y11=18-10=8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?