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

Задача A. Спортивные программисты

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

1 секунда

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

256 мегабайт

Ассоциация спортивных программистов Казахстана решила организовать забег перед Олимпиадой. В забеге приняло участие $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$, $p_i \neq p_j$ если $i \neq j$) — первым финишировал бегун $p_1$, вторым был $p_2$, \dots, последним — $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;

}