Fişierul intrare/ieşire:roboti3.in, roboti3.outSursăOJI 2017, clasa a 9-a
AutorLiliana ColinAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.05 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Roboti3

Ştefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulţi roboţi, fiecare dotat cu o armă de o anumită putere. El a aşezat toţi roboţii în jurul său, pe circumferinţa unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-şi puterile armelor. 
Cunoscând numărul de roboţi, precum şi puterea fiecăruia, să se scrie un program care determină:

Cerinţe

  1. Dimensiunea celei mai lungi secvenţe de roboţi pentru care puterile armelor lor formează un şir strict crescător.
  2. O aranjare a roboţilor pe cerc, astfel încât suma produselor de câte două puteri vecine să fie maximă. Dacă există mai multe modalităţi de aranjare astfel încât să se obţină aceeaşi sumă maximă, se va determina cea minimă din punct de vedere lexicografic.

Date de intrare

Pe prima linie a fişierului de intrare roboti3.in se găseşte un număr natural v a cărui valoare poate fi doar 1 sau 2.
Pe a doua linie a fişierului de intrare se găseşte un singur număr natural n reprezentând numărul de roboţi.
Pe a treia linie a fişierului de intrare se găsesc n numere naturale p1, p2, ..., pn, separate prin câte un spaţiu, pi reprezentând puterea armei robotului i.

Date de ieşire

Dacă valoarea lui v este 1, atunci fişierul de ieşire roboti3.out va conţine pe prima linie un singur număr natural reprezentând dimensiunea celei mai lungi secvenţe de roboţi pentru care puterile armelor lor formează un şir strict crescător.
Dacă valoarea lui v este 2, atunci fişierul de ieşire va conţine pe prima linie n numere naturale separate prin câte un spaţiu, reprezentând puterile celor n roboţi aşezaţi pe cerc astfel încât suma produselor de câte două puteri vecine să fie maximă, iar aşezarea să fie minimă din punct de vedere lexicografic.

Restricţii

  • 1 ≤ n ≤ 100.000
  • Pentru cerinţa 1, secvenţa de lungime maximă se alege pe cerc în sensul acelor de ceasornic.
  • Dacă avem două şiruri de numere a1, a2, ..., an şi b1, b2, ..., bn şi există 1 ≤ k ≤ n cea mai mică poziţie, pentru care are loc a1 = b1, a2 = b2, ..., ak-1 = bk-1 şi ak = bk, atunci spunem că şirul a este mai mic lexicografic decât şirul b.
  • Pentru rezolvarea corectă a cerinţei 1 se acordă 30 puncte, pentru rezolvarea corectă a cerinţei 2 se acordă 60 de puncte, iar din oficiu se acordă 10 puncte.
  • Pentru cerinţa 2, dacă soluţia afişată nu este minimă lexicografic, dar produce suma maximă corectă se acordă 50% din punctajul testului respectiv.
  • Pentru cerinţa 2, teste în valoare totală de 36 puncte vor avea n ≤ 1000.
  • 1 ≤ p1, p2, ..., pn ≤ 1000

Exemplu

roboti3.inroboti3.outExplicaţii
1
7
4 7 2 6 5 1 3
4
v = 1, deci se va rezolva DOAR prima cerinţă.
4 7 2 6 5 1 3
Cea mai lungă secvenţă strict crescătoare este 1 3 4 7 şi are lungimea 4.
2
5
3 9 1 12 5
1 3 9 12 5
v = 2, deci se va rezolva DOAR a doua cerinţă.
1 * 3 + 3 * 9 + 9 * 12 + 12 * 5 + 5 * 1 = 203,
şi este suma maximă care se poate obţine.
Această aranjare nu este singura pentru care se obţine suma maximă, dar este cea mai mică lexicografic.
2
4
1 2 1 1
1 1 1 2
v = 2, deci se va rezolva DOAR a doua cerinţă.
1 * 1 + 1 * 1 + 1 * 2 + 2 * 1 = 6,
şi este suma maximă care se poate obţine.
Această aranjare nu este singura pentru care se obţine suma maximă, dar este cea mai mică lexicografic.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?