Cerința
După ce arhitectul Gigel a reușit să rezolve sarcina primită de la primărie ( #Arhitectura ), el și-a dat seama că aspectul zonei nu va fi unul după preferințele sale. Astfel, s-a stabilit că în oraș nu există clădiri cu înălțimea mai mare decât hmax. Acum primăria îi cere afișarea clădirilor în ordine descrescătoare, precum și verificarea, pentru fiecare clădire din lista ordonată, dacă înălțimea ei este egală cu media aritmetică a înălțimilor celor două clădiri vecine.
Gigel vă cere ajutorul ca să-și termine proiectul care a devenit mult prea greu .
Date de intrare
Fișierul de intrare arhitectura2.in conține pe prima linie numărul n, iar pe următoarele linii n numere naturale separate prin spații. Fiecare linie conține maxim 100.000 de valori.
Date de ieșire
Fișierul de ieșire arhitectura2.out va conține doua linii cu n valori fiecare. Prima linie va conține înălțimile în ordine descrescătoare , iar a doua linie va conține n valori 1 sau 0, după cum înălțimea clădirii curente este sau nu egală cu media aritmetică a înălțimilor celor două clădiri vecine.
Restricții și precizări
1 ≤ n ≤ 2000000hmax ≤ 100000- Pentru 40% din teste
n ≤ 50000 - Pentru 80% din teste
n ≤ 500000 - Considerăm că înaintea primei clădiri și după ultima clădire se află câte o pseudoclădire de înălțime
0– care va interveni în verificarea cerută.
Exemplu
arhitectura2.in
10 5 10 10 9 5 2 5 8 5 2
arhitectura2.out
10 10 9 8 5 5 5 5 2 2 0 0 1 0 0 1 1 0 0 0
Explicatie:
Șirul devine 10 10 9 8 5 5 5 5 2 2
Doar 9 si cei doi de 5 din mijloc respectă condiția.
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 Arhitectura2:
/*
Aceasta problema se bazeaza pe un algoritm de sortare numit Counting Sort ( algoritm de numarare )
Solutii alternative :
- algoritm de sortare de complexitate O ( N * N ) - 40p
- algoritm de sortare rapida prin comparare O ( N * log N ) - 80p
*/
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std ;
ifstream fin ("arhitectura2.in") ;
ofstream fout ("arhitectura2.out") ;
int n ;
int a[2000005] ; //memoreaza inaltimile
int b[2000005] ; //memoreaza inaltimile sortate
int c[2000005] ; //memoreaza frecvente
int main ()
{
//citim
fin >> n ;
int inaltime_maxima = 0 ;
for ( int i = 0 ; i < n ; ++i )
{
fin >> a[i] ;
if ( a[i] > inaltime_maxima )
inaltime_maxima = a[i] ;
}
//sortarea prin numarare
int k = inaltime_maxima ;
for ( int i = 0 ; i < n ; ++i )
c[a[i]]++ ;
for (int i = 1 ; i < k + 1 ; ++i )
c[i] += c[i-1] ;
for (int i = n - 1 ; i >= 0 ; --i )
b[--c[a[i]]] = a[i] ;
//raspundem la problema
for ( int i = n - 1 ; i >= 0 ; --i )
fout << b[i] << " " ;
fout << "\n" ;
for ( int i = n - 1 ; i > 0 ; --i )
{
if ( b[i] * 2 == b[i-1] + b[i+1] )
fout << "1 " ;
else
fout << "0 " ;
}
if ( b[1] == 2 * b[0] )
fout << "1" ;
else
fout << "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 #1192 Arhitectura2
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1192 Arhitectura2 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!