Выведите количество пар индексов (i, j), таких что строка si + sj является хорошей

@Maxim1704g · Регистрация: 25.08.2018

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

Одна известная команда впервые за несколько месяцев решила написать тренировку. Но друзья
решили, что им чужды старые технологии, поэтому они попросили нейросеть сгенерировать задачу,
а потом решить ее (ведь зачем решать задачи самим). Сама задача звучала довольно просто.
Вам даны n строк s₁, s₂, . . . , s_n, состоящих из цифр от 0 до 9. Необходимо посчитать количество пар индексов (i, j) 1 <= i <= j <= n, таких что строка s_i + s_j является хорошей, где s_i + s_j — это конкатенация строк s_i и s_j . Строка t длины m называется хорошей, если для любого индекса 1 < i <= m
выполнено неравенство t_i−1 <= t_i.
Сгенерировать задачу нейросеть смогла, а вот решить ее — нет. Но друзья уже очень устали,
поэтому решать эту задачу придется вам.

Формат входных данных

Первая строка содержит одно целое число n (1<=n<=100000) — количество строк.
Каждая из следующих n строк содержит строку s_i. Гарантируется, что строки s_i состоят только из цифр от 0 до 9.
Гарантируется, что сумма длин строк не превосходит 100 000.

Формат выходных данных

Выведите количество пар индексов (i, j) 1 <= i < j <= n, таких что строка s_i + s_j является хорошей.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Пример
Ввод:
4
456
01
1239
701

Вывод:
1

Замечание
В примере подходит только одна пара индексов: (2, 3). Полученная строка 011239 является хорошей.

Помогите решить, пожалуйста ...

Добавлено через 1 час 13 минут

Python
1
2
3
4
5
6
7
n=int(input())
s=[]
for i in range(n):
    t=input()
    s.append(t)
print(s)
for i in range(n):

Вот что написал пока. Как оптимально пройтись по всем строкам, чтобы затратить меньшее количество времени?

@Red white socks · 09.12.2023, 12:24

Не по теме:

Maxim1704g, укажите источник задачи

@Maxim1704g · 09.12.2023, 12:26 **[ТС]**

Red white socks, муниципальный этап ВсОШ Волгограда 2021 года, хочу разобрать, помогите ...

@Red white socks · 09.12.2023, 12:27

Maxim1704g, к чему тогда такая спешка?)

@Maxim1704g · 09.12.2023, 12:35 **[ТС]**

Red white socks, могу и подождать, за сегодня просто хотел бы решить ...
просто вижу, что на другие темы отвечают, а мою пропускают ... вот и пытаюсь обратить на себя внимание)

@Red white socks · 09.12.2023, 12:44

Алгоритм такой.
Сначала отфильтровываете только неубывающие строки.
Далее для каждой цифры подсчитываете сколько таких строк начинается с этой цифры и сколько строк заканчивается.
Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i$ - число неубывающих строк начинается с цифры $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_i$ - заканчивается цифрой $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ .
Тогда ответом будет
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i \ge j} a_i\cdot b_j$

Добавлено через 35 секунд
Код не пишу, олимпиадник сам хоть что-то да и должен уметь

@Maxim1704g · 09.12.2023, 12:46 **[ТС]**

Сообщение от Red white socks

отфильтровываете только неубывающие строки

их в порядке возрастания?

@Red white socks · 09.12.2023, 12:47

не понял вопроса

@Maxim1704g · 09.12.2023, 12:49 **[ТС]**

Red white socks, что значит "отфильтровываете"? кроме неубывающих строк всё стереть?

@Red white socks · 09.12.2023, 13:00

а, стоп. Конкатенация упорядоченная. Так просто не пойдет, тут или Divide&conquer или дерево Фенвика нужно.

@Maxim1704g · 09.12.2023, 13:05 **[ТС]**

Red white socks, и как мне это реализовать? про дерево Фенвика уже прочитал ...

@Red white socks · 09.12.2023, 13:24

Прочитайте, здесь реализация для подсчета инверсий методом Divide&conquer.
Ваша задача является разновидностью данной.
Итак, отфильтровываете неубывающие строки - интересуют только они.
Далее, каждому индексу i вы сопоставляете 2 числа a_i и b_i: цифру с которой i-я строка начинается и которой заканчивается соответственно. Вам надо посчитать число пар i<j, таких что b_i <= a_j

Добавлено через 5 минут

Не по теме:

Upd. Вы не обманули, задача, особенно для новичка (и не только) действительно интересная. Но я рекомендовал бы вам начать знакомство с олимпиадами с задач попроще.

@Maxim1704g · 09.12.2023, 13:27 **[ТС]**

Red white socks, если бы вы выложили решение на python/c++, я был бы безмерно благодарен ...
я новичок и займусь задачами попроще ... но теперь эту добить надо))

@Red white socks · 09.12.2023, 14:27

Maxim1704g, у меня встречное предложение. Вы откладываете задачу на пару месяцев/полгода и возвращаетесь к ней когда будете готовы. А сейчас пишете брут-форс перебор О(n^2) по тому, что я вам сказал. Для n до 1000 тесты пройдете, какие-то баллы заработаете. Для новичка совсем неплохо.

@iSmokeJC · 09.12.2023, 14:47

Red white socks, чето твое предложение энтузиазма не вызвало...

@Red white socks · 09.12.2023, 14:49

Не по теме:

iSmokeJC, Уверен что Максим последовал моему совету и сейчас пишет код с брутфорсом.

YuS_2 · 09.12.2023, 17:55

Сообщение от Red white socks

Конкатенация упорядоченная.

А мне вот стало интересно... почему упорядоченная?

@Red white socks · 09.12.2023, 23:54

YuS_2, здесь я имел в виду, то что формируются s_i+s_j только для i>j, то есть для упорядоченной пары.

YuS_2 · 10.12.2023, 10:35

Сообщение от Red white socks

то что формируются s_i+s_j только для i>j, то есть для упорядоченной пары.

Всё равно, не понял...
1.
Почему i>j? Ведь:

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

Необходимо посчитать количество пар индексов (i, j) 1 <= i <= j <= n, таких что строка si + sj является хорошей, где si + sj — это конкатенация строк si и sj .

2.
По какому признаку именно, упорядочены они? Ведь, строки могут быть и не по порядку расположены... например, так: (2,4) или (3,7) и т.д.

@eaa · 10.12.2023, 11:08

Red white socks, здесь же сортировка + комбинаторика. или я задачу не понял?

Новые блоги и статьи Все статьи Все блоги /
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .

@Red white socks
	09.12.2023, 12:24
	Не по теме: Maxim1704g, укажите источник задачи 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	09.12.2023, 12:26 [ТС]
	Red white socks, муниципальный этап ВсОШ Волгограда 2021 года, хочу разобрать, помогите ... 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 12:27
	Maxim1704g, к чему тогда такая спешка?) 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	09.12.2023, 12:35 [ТС]
	Red white socks, могу и подождать, за сегодня просто хотел бы решить ... просто вижу, что на другие темы отвечают, а мою пропускают ... вот и пытаюсь обратить на себя внимание) 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 12:44
	Алгоритм такой. Сначала отфильтровываете только неубывающие строки. Далее для каждой цифры подсчитываете сколько таких строк начинается с этой цифры и сколько строк заканчивается. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_i$ - число неубывающих строк начинается с цифры $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?b_i$ - заканчивается цифрой $https://www.cyberforum.ru/cgi-bin/latex.cgi?i$ . Тогда ответом будет $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i \ge j} a_i\cdot b_j$ Добавлено через 35 секунд Код не пишу, олимпиадник сам хоть что-то да и должен уметь 5

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 12:47
	не понял вопроса 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	09.12.2023, 12:49 [ТС]
	Red white socks, что значит "отфильтровываете"? кроме неубывающих строк всё стереть? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 13:00
	а, стоп. Конкатенация упорядоченная. Так просто не пойдет, тут или Divide&conquer или дерево Фенвика нужно. 1

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	09.12.2023, 13:05 [ТС]
	Red white socks, и как мне это реализовать? про дерево Фенвика уже прочитал ... 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 13:24
	Прочитайте, здесь реализация для подсчета инверсий методом Divide&conquer. Ваша задача является разновидностью данной. Итак, отфильтровываете неубывающие строки - интересуют только они. Далее, каждому индексу i вы сопоставляете 2 числа a_i и b_i: цифру с которой i-я строка начинается и которой заканчивается соответственно. Вам надо посчитать число пар i<j, таких что b_i <= a_j Добавлено через 5 минут Не по теме: Upd. Вы не обманули, задача, особенно для новичка (и не только) действительно интересная. Но я рекомендовал бы вам начать знакомство с олимпиадами с задач попроще. 1

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	09.12.2023, 13:27 [ТС]
	Red white socks, если бы вы выложили решение на python/c++, я был бы безмерно благодарен ... я новичок и займусь задачами попроще ... но теперь эту добить надо)) 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 14:27
	Maxim1704g, у меня встречное предложение. Вы откладываете задачу на пару месяцев/полгода и возвращаетесь к ней когда будете готовы. А сейчас пишете брут-форс перебор О(n^2) по тому, что я вам сказал. Для n до 1000 тесты пройдете, какие-то баллы заработаете. Для новичка совсем неплохо. 2

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	09.12.2023, 14:47
	Red white socks, чето твое предложение энтузиазма не вызвало... 2

@Red white socks
	09.12.2023, 14:49
	Не по теме: iSmokeJC, Уверен что Максим последовал моему совету и сейчас пишет код с брутфорсом. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.12.2023, 23:54
	YuS_2, здесь я имел в виду, то что формируются s_i+s_j только для i>j, то есть для упорядоченной пары. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	10.12.2023, 11:08
	Red white socks, здесь же сортировка + комбинаторика. или я задачу не понял? 0