Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы

Есеп D. Теңестіру

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

1 second

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

256 megabytes

Жарасханда $N$ саннан тұратын $a$ массивы бар. Жарасхан берілген массивтың әр санына тек бір операция қолдана алады. Операциялардың 3 түрі бар:

1. Санға бірді қосу.
2. Саннан бірді азайту.
3. Санға нөлді қосу.

Массивтың әр санына берілген үш операцияның тек біреуін ғана қолдана отырып, массивтегі ұқсас элементтердің санын барынша арттыру керек.

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

Бірінші жолда бүтін сан $N$ берілген. Келесі жолда массивтың элементтері берілген $ a_{i} $.

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

Жауап ретінде бір сан шығарыңыз — берілген операцияларды орындағаннан кейінгі массивте кездесетін ұқсас элементердің саны.

Система оценки

Бағалау 4 бөлімнен тұрады:

1. $1 \le N \le 2$. $10$ ұпай.
2. $1 \le N \le 10^2$ және $1 \le a_{i} \le 10$. $20$ ұпай.
3. $1 \le N \le 10^5$ және $1 \le a_{i} \le 2$. $20$ ұпай.
4. $1 \le N \le 10^5$ және $1 \le a_{i} \le 10^5$. $50$ ұпай.

Примеры:

Вход

7
3 1 4 1 5 9 2

Ответ

4

Вход

10
1 2 3 4 5 6 7 8 9 10

Ответ

3

Замечание

Бірінші мысалда массивты былай өзгертуге болады: 2,2,3,2,6,9,2. ( Meirkhan Ormanov )

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

AC

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

#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#define ll long long int
using namespace std;
int main () {
	ll n,x,mx=0;
	map<ll,ll>s;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		s[x]++;
	}
	for(int i=1;i<=1e5;i++){
		mx=max(mx,s[i]+s[i+1]+s[i+2]);
	}
	cout<<mx;
}

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

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	
	int n;
	cin >> n;
	int a[n];
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	
	int mx = *max_element(a+1, a+n+1);
	int b[mx];
	fill(b+1,b+mx+1, 0);
	
	for(int i=1; i<=n; i++){
		b[a[i]]++;
		b[a[i]+1]++;
		b[a[i]-1]++;
	}
	
	mx = *max_element(b+1, b+mx+1);
	cout << mx;
	return 0;
}

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

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

const int N = 1e5 + 5;
int cnt[N]={};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        int cur;
        cin >> cur;
        cnt[cur]++;
    }
    int mx=-1;
    for (int i=1; i<N-1; i++) {
        mx = max(mx, cnt[i-1] + cnt[i] + cnt[i+1]);
    }
    cout << mx << '\n';
    return 0;
}

#include<bits/stdc++.h>

#define ll long long

#define N 200005

#define MAX 1000000000

#define rt return

#define pr printf

#define vec vector

#define pb push_back

#define sz size()

#define rev reverse

#define srt sort

#define cn continue

#define sc scanf

#define pll pair< ll, ll >

#define ff first

#define ss second

#define dd long double

#define SS stringstream

#define graph g[ a ].pb( b ), g[ b ].pb( a )

#define pause system("PAUSE")

#define off exit( 0 )

#define speed ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0)

using namespace std;

ll n, m[ N ], mx, a[ N ];

int main(){

sc( "%I64d", &n );

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

sc( "%I64d", &m[ i ] );

a[ m[ i ] ] ++;

}

if( n <= 2 )

{

if( abs( m[ 0 ] - m[ 1 ] ) <= 1 ) pr( "2" );

else pr( "1" );

return 0;

}

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

mx = max( mx, a[ i - 1 ] + a[ i ] + a[ i + 1 ] );

}

pr( "%I64d", mx );

}

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n,a,m=0;cin>>n;int mas[10]={0,0,0,0,0,0,0,0,0,0};

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

{

scanf("%d", &a);mas[a]++;

}

for(int i=0;i<8;i++)

{

m=max(m,mas[i]+mas[i+1]+mas[i+2]);

}

printf("%d", m);

}

что за ошибка исполнения

нашел? Создай массив mas на 10^5 элементов.

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

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair < pii, int > piii;
typedef pair <ll, ll> pll;
typedef pair < pll, ll > plll;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;
typedef vector < pll > vll;
typedef set < int > si;
const int N = 1e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n, a[N], cnt[N], ans;

void solve() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for(int i = 2; i <= N - 1; i++) {
		ans = max(ans, cnt[i - 1] + cnt[i] + cnt[i + 1]);
	}
	cout << ans;
}

int main () {
	start
	solve();
	return 0;
}

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

{

#include <bits/stdc++.h>

#define speed ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define ll long long

using namespace std;

int main() {

speed;

ll n;

cin >> n;

ll ans[100007];

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

ans[i] = 0;

}

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

ll x;

cin >> x;

ans[x]++;

}

ll cnt = 0;

for(ll i = 1; i <= 100006; i++) {

if(cnt < ans[i + 1] + ans[i] + ans[i - 1]) {

cnt = ans[i + 1] + ans[i] + ans[i - 1];

}

}

cout << cnt;

}

}

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

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

int main() {
  int n, mx = 0;
  cin >> n;
  int arr[n];
  map<int, int> k;
  for(int i = 0; i < n; i++){
    cin >> arr[i];
    k[arr[i]]++;
  }
  sort(arr, arr + n);
  for(int i = 0; i < n; i++){
      mx = max(mx, (k[arr[i]] + k[arr[i] - 1] + k[arr[i] + 1]));
  }
  cout << mx;
}