Районная олимпиада по информатике. 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 )
посмотреть в олимпиаде

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

  -2
2018-12-14 12:23:35.0 #

AC

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

  0
2018-12-25 08:42:47.0 #

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

  -1
2019-01-08 21:09:10.0 #

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

  -1
2019-05-17 13:39:12.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 );

}

  0
2019-12-03 22:30:56.0 #

#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);

}

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

  0
2020-11-30 14:19:02.0 #

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

  0
2020-11-30 14:17:16.0 #

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

пред. Правка 5   0
2021-10-02 12:05:48.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;

}

}

  1
2021-10-04 14:59:55.0 #

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