3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Есеп A. Спорттық бағдарламаушылар

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

1 second

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

256 megabytes

Қазақстанның спорттық бағдарламаушылар ассоциациясы жүгіруден жарыс өткізді. Жарысқа $N$ жүгіруші қатысты. Басында жүгірушілер $1$-ден $N$-ге дейін бірі артынан бірі орналасты. Жарыс басталғанда олар сол ретті бұзбай жүгіре бастады. Нөмірі $1$ болатын жүгіруші бірінші, ал нөмірі $N$ болатын жүгіруші — соңғы. Бірақ қандай жарыста ешкім ешкімді озбайды? Бір жүгірушінің бауы шешіліп кеткенде ғана олардың реті өзгере алады. Жүгіруші бауын байлап жатқанда одан кейін келе жатқан бірнеше адам оны озып кетуі мүмкін. Мысалы, $N = 5$ жүгіруші жарысқа қатысқан кезде бастапқы қатар осындай болады: $1$ $2$ $3$ $4$ $5$. Біраз уақыттан кейін $2$-ші жүгірушінің бауы шешіліп кетті дейік. Ол бауын байлап жатқан уақытта оны екі жүгіруші озып кетті дейік. Онда олардың ендігі реті осындай болады: $1$ $3$ $4$ $2$ $5$. Егер бұдан кейін $4$-ші жүгірушінің бауы шешілсе, және сол үшін оны бір адам озып кетсе, жаңа рет мынадай болады: $1$ $3$ $2$ $4$ $5$. Сізге $N$ және жүгірушілердің мәреге келген реті беріледі. Сізге ең кем дегенде неше жүгірушінің бауы шешіліп кеткенін айту керек.

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

Бірінші жолда бір бүтін сан $N(1 <= N <= 200000)$ — жүгірушілердің саны беріледі. Екінші жолда $N$ бүтін сан $p_1, p_2, \ldots, p_N$($1 <= p_i <= N$, $i \neq j$ болса $p_i \neq p_j$) беріледі. Мәреге бірінші болып $p_1$ келді, екінші болып $p_2$, \ldots, соңғы болып $p_N$ келді.

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

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

Примеры:

Вход

6
1 2 5 4 3 6

Ответ

2

Вход

3
1 2 3

Ответ

0

Замечание

Бірінші мысалды қарастырайық. Басында қатар: $1$ $2$ $3$ $4$ $5$ $6$. Мүмкін жағдайлардың бірі: $4$-ші жүгірушінің бауы шешіліп кетті, байлап жатқанда $5$ оны озып кетті. Ендігі рет: $1$ $2$ $3$ $5$ $4$ $6$ болды. Одан кейін $3$-ші жүгірушінің бауы шешіліп кетті және оны $5$ пен $4$ озып кетті. Ендігі қатар $1$ $2$ $5$ $4$ $3$ $6$ болды. Екіден аз адамның бауы шешіліп кетсе, онда берілген қатарға қол жеткізу мүмкін емес болатынын көрсетуге болады. ( Temirlan Satylkhanov )

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

Здравствуйте, я решил эту задачу на пайтоне, но как сменить компилятор?

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

//SULTE4
#include <bits/stdc++.h>
#define ll long long 
#define speed ios::sync_with_stdio(0);cin.tie(0).cout.tie(0);

using namespace std;

int main(){
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n;i++){
		cin >> a[i];
	}
	int p = a[0], cnt = 0;
	for(int i = 1;i < n;i++){
		if(a[i] < p){
			cnt++;
		} else {
			p = a[i];
		}
	}
	cout << cnt;
	return 0;
}

обычная Динамика, расстояние Дамерау-Левенштейна

MaxSplit=int(input())

Sportsmen=[]

Sportsmen=input().split()

for i in range(len(Sportsmen)):

Sportsmen[i]=int(Sportsmen[i])

sum=0

for i in range(len(Sportsmen)):

if(Sportsmen[i]!=i+1):

#if(Sportsmen[i]<Sportsmen[i-1] or Sportsmen[i]>Sportsmen[i+1]):

sum+=1

print(sum)

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

cin >> n;

vector<int> order(n);

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

cin >> order[i];

}

int count = 0;

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

if (order[i] < order[i-1]) {

count++;

}

}

cout << count << endl;

return 0;

}

n = int(input())

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

count = 0

for i in range(1, n):

if order[i] < order[i-1]:

count += 1

print(count)

#include<iostream>

using namespace std;

int main(){

int n,s=0,makx = 0, c;

cin>>n;

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

cin>>c;

if(makx>c){

s++;

}

makx=max(c,makx);

}

cout<<s;

}