# PBinfo #2069 – roboti2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Ș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.

Cerința
Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:
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 roboti2.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 p[1], p[2], …, p[n­], separate  prin câte un spațiu, p[i] reprezentând puterea armei robotului i.

Date de ieșire
Dacă valoarea lui v este 1, atunci fişierul de ieşire roboti2.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 și precizări

2 ≤ 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 a[1], a[2], …, a[n] şi b[1], b[2], …, b[n] şi există 1≤k≤n, cea mai mică poziţie pentru care are loc a[1]=b[1], a[2]=b[2], …, a[k-1]=b[k-1] şi a[k]<b[k], atunci spunem că şirul a este mai mic lexicografic decât şirul b.
În concurs, pentru rezolvarea corectă a cerinței 1 s-au acordat 30 puncte, pentru rezolvarea corectă a cerinței 2 s-au acordat  60 de puncte, iar din oficiu s-au acordat 10 puncte. Pe site, se acordă 10 puncte pentru exemple.
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 ≤ p[1], p[2],..., p[n] ≤ 1000.

Exemplul 1:
roboti2.in

1
7
4 7 2 6 5 1 3
roboti2.out

4
Explicație
v = 1, deci se va rezolva DOAR prima cerință. Cea mai lungă secvență strict crescătoare este 1 3 4 7 și are lungimea 4.

Exemplul 2:
roboti2.in

2 
5
3 9 1 12 5
roboti2.out

1 3 9 12 5
Explicație
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.

Exemplul 3:
roboti2.in

2 
4
1 2 1 1
roboti2.out

1 1 1 2
Explicație
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.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int main()
{
    ifstream in("roboti2.in");
    ofstream out("roboti2.out");
    long p[100000],a[100000],v,x,ok;
    long n,i,max=1,s,d,ls=1,ns,nd;
    int serie,cs,antdr;
    in>>v>>n;
    for(i=0;i<n;i++)
      in>>p[i];
    if(v==1) //cerinta 1
     {
      i=1; x=p[0]; ok=0;
      while(i<n && ok<2)
       {
         if(p[i]>p[i-1])
           ls++;
         else
          {
            if(ls>max)
              max=ls;
            ls=1;
          }
         i++;
         //ciclarea cautarii
         if(i==n)
           {
             if(x>p[i-1])
               { ls++; i=1; }
             ok++; //numai inca o ciclare
           }
       }
       out<<max;
     }
    else  //cerinta 2
     {
       sort(p, p+n);
       //aranjare
       a[0]=p[0];
       s=0; d=n;
       serie=0;
       ns=0;nd=0;
       antdr=0;
       for(i=1;i<=n-1;i++)
        {
          //daca este cap de serie, adica primuldintr-o serie de nr. care se repeta
          if(i<n-1 && p[i]==p[i+1] && p[i-1]!=p[i])
            cs=1;
          else
            cs=0;
          //daca am pus mai putini sau egal in st si dr sau
          // este intr-o serie de egale sau
          // cel dinaintealui l-am pus in dreapta dar nu a fost cap de serie
          if(ns<=nd || serie || (antdr && !cs) )//merge stanga
            {
              s++;
              a[s]=p[i];
              ns++;
              antdr=0;
            }
          else //merge dreapta
            {
              d--;
              a[d]=p[i];
              nd++;
              antdr=1;
            }
          if(p[i]==p[i-1])
            serie++;
          else
            serie=0;
         }
       for(i=0;i<n;i++)
         out<<a[i]<<' ';
     }
    in.close();
    out.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2069)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2069/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2069/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)