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

Задача F. Массив

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

2 секунда

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

64 мегабайта

Вам дан массив $A$ длины $n$. Вы можете удалить некоторые элементы из него, при этом после всех удалении элементы должны стоять в строго возрастающем порядке. Выведите максимальную возможную длину массива после всех удалении.

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

Первая строка входного файла содержит целое число $N$ $(1 \le N \le 1000000)$ — длину последовательности. Вторая строка входного файла содержит $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;
}

C++

Copy

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

показать/скрыть код

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))

C++

Copy

#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;

}

показать/скрыть код

C++

Copy

#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;
}

C++

Copy

#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