Районная олимпиада по информатике. 2016-2017 учебный год.

Есеп F. Массив

Ограничение по времени:

2 секунд

Ограничение по памяти:

64 мегабайт

Сізге ұзындығы $n$ болатын $A$ массиві берілген. Сіз осы массивтің элементтерін алып тастай аласыз. Сізге элементтерді алып тастау арқылы массивті оспелі ету қажет. Соңында пайда болған өспелі массивтің ең үлкен бола алатын ұзындығын табу керек.

Формат входного файла

Енгізу файлының бірінші жолында $N$ $(1 \le N \le 100000)$ саны берілген — тізбектегі сандардың саны. Екінші жолда кемістікпен (пробел) бөлінген $N$ сан берілген — $A$ тізбегінің сандары. Əрбір санның абсолют мəні 1000000000-нан аспайды.

Формат выходного файла

Бір ғана сан — есептің жауабын шығару керек.

Примеры:

Вход

4
4 1 2 3 

Ответ

3

Замечание

4 санын алып тастау керек, сонда шығатын массив 1 2 3 массивы болады.

Комментарий/решение

asd

кодты корсету/жасыру

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int n;
	cin >> n;
	int arr[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	int maxSeq[n];
	maxSeq[0]=1;
	for (int i = 1; i < n; i++){
		maxSeq[i]=1;
		for (int j = 0; j < i; j++){
			if (arr[j]<arr[i] && maxSeq[i]<maxSeq[j]+1)
				maxSeq[i]=maxSeq[j]+1;
		}
	}
	cout << *max_element(maxSeq,maxSeq+n);
    return 0;
}

Но ведь работает же :)

кодты корсету/жасыру

with open('input') as file: 
    inner, data = file.readlines()[1].split('\n')[0].split(), list()

for elem in range(0, len(inner)): data.append(int(inner[elem]))

# Начинаем срезать с левой стороны
for elem in range(0, len(data)): 
    if data[elem:len(data)] == sorted(data[elem:len(data)]): res1 = data[elem:len(data)]

# Начинаем срезать с правой стороны
for elem in range(len(data), 0, -1): 
    if data[elem:len(data)] == sorted(data[elem:len(data)]): res2 = data[elem:len(data)]

# Сравниваем лучший результат
if len(res1) >= len(res2): result = len(res1)

else: result = len(res2)

with open('output', 'w') as file: file.write(str(result))

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int arr[n];

int res[n];

res[0] = arr[0];

for (int i = 0; i < n; i++) {

cin >> arr[i];

}

int j = 0;

for (int i = 1; i < n; i++) {

if (arr[i] < res[j]) {

res[j] = arr[i];

} else {

res[++j] = arr[i];

}

}

cout << j + 1;

}

кодты корсету/жасыру

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int arr[n];

int res[n];

res[0] = arr[0];

for (int i = 0; i < n; i++) {

cin >> arr[i];

}

int j = 0;

for (int i = 1; i < n; i++) {

if (arr[i] < res[j]) {

res[j] = arr[i];

} else {

res[++j] = arr[i];

}

}

cout << j + 1;

}

кодты корсету/жасыру

#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    int res[n];
    res[0] = arr[0];
    for (int i = 0; i < n; i++) {
    cin >> arr[i];
}
    int j = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] < res[j]) {
            res[j] = arr[i];
        } else {
            res[++j] = arr[i];
        }
    }
    cout << j + 1;
}

#include<bits/stdc++.h>

using namespace std;

#define ll long long

stringstream f;

int main () {

ios_base::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

ll n, ans=0;

cin>>n;

ll a[n];

for(ll i=0;i<n;i++)cin>>a[i];

for(ll i=0;i<n;i++){

if(a[i]>a[i+1])ans++;

}

cout<<n-ans;

}

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main () {

ios_base::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

ll n, ans=0;

cin>>n;

ll a[n];

for(ll i=0;i<n;i++)cin>>a[i];

for(ll i=0;i<n;i++){

if((a[i]>a[i+1] || a[i-1]+1!=a[i]) && i>0)ans++;

}

cout<<n-ans;

}

input()

d=list(map(int, input().split()))

for i in range(len(d)):

if d[i] + 1 == d[1]:

print(len(d))

else:

d.pop(i)

print(len(d))

break

коды людей ниже вполне работоспособны, но у многих при вводе данных

/{ 1, 2, 3, 1, 2, 3/} код выдает неправильный рез, ведь они удаляют лишь последний неправильный элемент, в то время как их может быть больше(способ решения напоминает стеки)

кодты корсету/жасыру

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int INF = 1e9;

const pair<ll,ll> INF_PAIR = {-1e9,-1e9};

int main(){

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

int n;

cin >> n;

vector<int> a(n);

for(int &el : a) cin >> el;

vector<int> res;

res.push_back(a.front());

for(int i = 1; i < n; ++i){

int ai = a[i];

if(res.back() >= ai){

while(!res.empty() && res.back() >= ai){

res.pop_back();

}

}

res.push_back(ai);

}

//for(int &el : res) cout << el << ' '; // to easyCheck

cout << res.size();

}

кодты корсету/жасыру