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

Задача D. Уравнитель

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

1 секунда

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

256 мегабайт

У Жарасхана есть массив $a$ из $N$ чисел,к каждому числу массива Жарасхан должен применить лишь одну операцию. Есть три типа операции:

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