Question

De ce iau 80p/100p pe aceasta problema?
Cerința

Un şir se numeşte şir munte, dacă are un singur maxim pe poziţia v, numit vârf şi respectă următoarele proprietăţi:
•În stânga şi în dreapta vârfului există cel puţin câte un element.
•Secvenţa a[1], a[2], ... , a[v] este strict crescătoare.
•Secvenţa a[v], a[v+1], ... , a[n] este strict descrescătoare.


Se citeşe un şir cu n elemente. Să se verifice dacă este şir munte.
Date de ieșire

Programul va afișa pe ecran unul dintre mesajele DA sau NU în funcţie că este şir munte sau nu.
Exemplu 1:

Intrare
5
1 2 3 4 5


Ieșire
NU


Exemplu 2:

Intrare
5
1 2 3 4 3


Ieșire
DA



CODUL:


#include

using namespace std;

int main()
{
int i,n,a,max,d;
cin >> n;
int v[n],b[n],c[n];
if(n%2==0)
cout<<"NU";
else
{
for(i=1; i<=n; i++)
cin >> v[i];
max=v[1];
d=n/2+1;
for(i=1; i<=d; i++)
if(v[i]>max)
{
max=v[i];
a=i;
}
if(a!=d)
cout<<"NU";
else
{
int k=0,z=0;
for(i=1; i {
k++;
b[k]=v[i];
}
for(i=d+1; i<=n; i++)
{
z++;
c[z]=v[i];
}
int aux=0,j;
for(i=1; i for(j=i+1; j<=k; j++)
if(b[i] aux++;
int d=0;
for(i=1; i for(j=i+1; j<=z; j++)
if(c[i]>c[j])
d++;
if(aux==k-1 && d==z-1)
cout<<"DA";
else
cout<<"NU";
}
}
return 0;
}

Answer 1

Tot algoritmul tau este concentrat pe faptul ca acel punct de maximum s-ar afla la mijlocul simetric al sirului. Din cerinta, rezulta ca maximum respectiv nu este nevoit sa fie intr-o pozitie relativa la sir cu 2 restrictii: sa nu fie pe prima sau pe ultima pozitie(altfel nu ai putea face muntele)

In rest, de exemplu, 1 2 3 4 3 ar trebui sa fie un sir valid pentru munte, la fel si 1 5 4 3 2, atata timp cat ai un maxim si cel putin un element in stanga si dreapta

Deci pe langa restrictia de pozitie mai avem urmatoarele conditii:
1) doua numere consecutive nu pot sa fie egale(strict crescator,strict descrescator)
2) atata timp cat nu a fost gasit un varf, v[i-1]<v[i]. Daca v[i-1]>v[i], atunci seteaza nr_varfuri=1
3) Daca ai nr_varfuri=1, acum esti pe panta muntelui si trebuie sa vezi doar v[i-1]>v[i]. Daca in schimb ai v[i-1]<v[i] atunci inseamna ca nu mai esti pe panta, urci din nou spre alt maxim, si vei avea cel putin 2 varfuri.

Aceste conditii conduc catre un cod mai simplu, pentru ca ai nevoie doar de vectorul v(de fapt, pentru ca tu verifici doar 2 variabile mereu, nici nu ai nevoie de vector), o singura parcurgere a sirului, pe care o poti face la citire, si iesire din program rapida in cazul in care una dintre restrictii este incalcata.
O versiune a programului e mai jos. Nu pot sa garantez ca iti va aduce 100 puncte pentru ca nu am testat-o intensiv, dar este cea mai simpla varianta pe care mi-o pot imagina.

#include <iostream>
using namespace std;

int main(){
int i,n,nr_varfuri=0;
cin>>n;
int v[n+1];
cin>>v[1]>>v[2];
//daca un maxim este pozitionat pe prima sau ultima pozitie
//atunci nu poate sa reprezinte un munte
if(v[1]>v[2]||v[1]==v[2]){
cout<<"NU";
return 0;
}
for(i=3;i<n;i++){
cin>>v[i];
//daca oricare 2 elemente consecutive sunt egale
//nu se respecta strictetea: crescator sau descrescator
if(v[i]==v[i-1]){
cout<<"NU";
return 0;
}
//daca avem un prim caz in care e mai mare precedentul decat urmatorul
//atunci nr_varfuri devine 1 si incepem partea descendenta
else if(nr_varfuri==0&&v[i-1]>v[i]){
nr_varfuri++;
}
//daca suntem deja pe partea descendenta, dar precedentul e mai mic decat urmatorul
//atunci nu suntem pe un munte
else if(nr_varfuri==1&&v[i-1]<v[i]){
cout<<"NU";
return 0;
}
}
cin>>v[n];
//daca un maxim este pozitionat pe prima sau ultima pozitie
//atunci nu poate sa reprezinte un munte
if(v[n-1]==v[n]||v[n-1]<v[n]){
cout<<"NU";
return 0;
}
cout<<"DA";
return 0;
}

Answer 2

-doua nr. consecutive nu pot fi egale -daca nu gaseti un vf seteaza nr. vfm 1 - daca il schimbi cu v [i-1]< v 1] vei avea cel putin 2 vf Trebuoe sa verifici doar doua variabile