Заочные олимпиады: Короткий тур заочного этапа

@pgr · Регистрация: 28.03.2023

Студворк — интернет-сервис помощи студентам

Не могу решить задачу, помогите, пжл.
Объединение чисел
Дан массив натуральных чисел a1,a2,…,an, в котором хотя бы одно число встречается хотя бы два раза. За одну операцию вы можете выбрать любое число x из массива и удалить все вхождения числа x в массив. Найдите минимальное число операций, которое необходимо применить к массиву, чтобы в нём были два подряд идущих равных числа.

Можно показать, что если в массиве изначально было 2 равных числа, то данными операциями можно получить массив, в котором условие выполняется.

Входные данные
Первая строка содержит единственное целое число n (2≤n≤200000) — длина массива.

Вторая строка содержит n целых чисел a1,a2,…,an(1≤ai≤n) — элементы массива. Существуют такие 1≤i<j≤n, что ai=aj.

Выходные данные
В первой строке выведите одно число m— минимальное число операций.

Далее выведите m строк. i-я строка должна содержать единственное число xi — число, выбранное в i-й операции.

Если есть несколько оптимальных решений, можно вывести любое из них.

Примеры
входные данные
5
1 2 3 1 2
выходные данные
2
2
3
входные данные
4
1 2 2 1
выходные данные
0

@Parramon · 29.03.2023, 11:21

Python
1
2
3
4
5
6
7
8
9
_ = input()
a = list(map(int, input().split()))
res = []
for i in [x for x in a if a.count(x) > 1]:
    p1 = a.index(i) + 1
    p2 = a[p1:].index(i)
    res.append([p2, a[p1:p2 + p1]])
res.sort()
print(res[0][0], *res[0][1], sep='\n')

@Red white socks · 29.03.2023, 11:46

Parramon,

Сообщение от Parramon

Python
1
a.count(x) > 1

Вот тут похоже слабое место, которое делает алгоритм квадратичным. Лучше за один проход создать словарь с индексами вхождения. Тогда будет линейным.

Добавлено через 4 минуты
И ваш алгоритм заточен на вхождение не более 2 раз. Словарь решит и эту проблему

@Parramon · 29.03.2023, 12:18

Red white socks, тут вы правы. На [1, 2, 3, 1, 2, 1] ответ будет неверный... Попозже попробую.

@Red white socks · 29.03.2023, 13:46

Python
1
2
3
4
5
6
7
8
9
10
11
12
from collections import defaultdict
from itertools import pairwise, chain
 
_ = input()
a = list(map(int, input().split()))
indexes = defaultdict(list)
for i, x in enumerate(a):
    indexes[x] += [i]
 
pairs = chain.from_iterable(pairwise(s) for s in indexes.values())
i, j = min(pairs, key=lambda x: x[1] - x[0])
print(j - i - 1, *a[i+1:j], sep = '\n')

@Gdez · 29.03.2023, 13:56

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from random import randint                  
 
n = diff = 200000 #int(input())
a = [randint(1, n) for _ in range(n)] #list(map(int, input().split()))
 
dct = {}
ind = 0
for i, num in enumerate(a):
    if num in dct and i - dct[num] < diff:
        ind = dct[num]
        diff = i - ind - 1
    dct[num] = i 
print(diff)
if diff:
    print(*a[ind+1:ind+1+diff], sep='\n')

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@pgr 0 / 0 / 0 Регистрация: 28.03.2023 Сообщений: 2

	Заочные олимпиады: Короткий тур заочного этапа 28.03.2023, 18:43. Показов 749. Ответов 5 Метки python 3.9 (Все метки) Не могу решить задачу, помогите, пжл. Объединение чисел Дан массив натуральных чисел a1,a2,…,an, в котором хотя бы одно число встречается хотя бы два раза. За одну операцию вы можете выбрать любое число x из массива и удалить все вхождения числа x в массив. Найдите минимальное число операций, которое необходимо применить к массиву, чтобы в нём были два подряд идущих равных числа. Можно показать, что если в массиве изначально было 2 равных числа, то данными операциями можно получить массив, в котором условие выполняется. Входные данные Первая строка содержит единственное целое число n (2≤n≤200000) — длина массива. Вторая строка содержит n целых чисел a1,a2,…,an(1≤ai≤n) — элементы массива. Существуют такие 1≤i<j≤n, что ai=aj. Выходные данные В первой строке выведите одно число m— минимальное число операций. Далее выведите m строк. i-я строка должна содержать единственное число xi — число, выбранное в i-й операции. Если есть несколько оптимальных решений, можно вывести любое из них. Примеры входные данные 5 1 2 3 1 2 выходные данные 2 2 3 входные данные 4 1 2 2 1 выходные данные 0 0

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	29.03.2023, 12:18
	Red white socks, тут вы правы. На [1, 2, 3, 1, 2, 1] ответ будет неверный... Попозже попробую. 0