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

Задача B. Потерянное число

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

1 секунда

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

64 мегабайта

Вам даны все целые числа от $1$ до $N + 1,$ кроме одного. Найдите отсутствующее число.

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

В первой строке входных данных записано целое число $1 \le N \le 10^5.$ Во второй строке через пробел даны $N$ целых чисел в диапазоне от 1 до $N + 1.$

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

Выведите ответ к задаче.

Примеры:

Вход

5
3 2 1 5 6

Ответ

4

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

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    bool found[n+2]={};
    for (int i=0; i<n; i++) {
        int cur;
        cin >> cur;
        found[cur]=true;
    }
    for (int i=1; i<=n+1; i++) {
        if (found[i]==false) {
            cout << i << '\n';
            break;
        }
    }
    return 0;
}

C++

Copy

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

with open('input') as file:

    inner, data, fixed = file.readlines(), list(), list()

    for line in inner: data.append(line.split('\n')[0])

    for elem in data[1].split(): fixed.append(int(elem))

    clear, fixed = [x for x in range(1, int(inner[0]) + 1)], sorted(fixed)

    for elem in range(0, len(fixed)):

        for obj in range(0, len(clear)):

            if fixed[elem] == clear[obj]: fixed[elem] = clear[obj] = None

    for elem in range(0, len(clear)):
        if clear[elem] != None: result = str(clear[elem])

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

C++

Copy

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

#include <bits/stdc++.h>
using namespace std;
int *a;
int n;
int main(){
	cin>>n;
	a=new int[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(i==a[i]){
			continue;
		}
		else {
			return cout<<i,0;
		}
	}
}

C++

Copy

DELETED

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

#include <iostream>
#define speed ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main() {
    speed;
    long long n;
    cin >> n;
    long long a[n];
    long long summ = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        summ += a[i];
    }
    long long formula = (n + 1) * ((n + 1) + 1) / 2;
    cout << formula - summ;
}

C++

Copy

#include<bits/stdc++.h>

using namespace std ;

int main () {

int n ;

cin >> n ;

vector <int> a(n) ;

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

cin >> a[i] ;

}

sort(a.begin() , a.end()) ;

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

if(a[i+1] != a[i] + 1){

cout << a[i] + 1 ;

return 0 ;

}

else

{

a[i] = i + 1 ;

}

}

}

input()

s = sorted(list(map(int, input().split())))

for i in range(len(s)):

if 1+i != s[i]:

print(i+1)

break

else:

pass