Ș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]şib[1],b[2], …,b[n]şi există1≤k≤n, cea mai mică poziţie pentru care are loca[1]=b[1],a[2]=b[2], …,a[k-1]=b[k-1]şia[k]<b[k], atunci spunem că şirulaeste mai mic lexicografic decât şirulb. - În concurs, pentru rezolvarea corectă a cerinței
1s-au acordat30puncte, pentru rezolvarea corectă a cerinței2s-au acordat60de puncte, iar din oficiu s-au acordat10puncte. 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ă de36puncte vor avean ≤ 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.
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 roboti2:
#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;
}
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 
.
Rezolvarea problemei #2069 roboti2
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2069 roboti2 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!