Выведите количество пар индексов (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):

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

YuS_2 · 10.12.2023, 12:27

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

или я задачу не понял?

Скорее всего... но я и сам не совсем понимаю, чего там в условиях накрутили... но это не комбинаторика.
Учитываются номера строк (необходимые пары индексов), длина строк, в том числе целевой строки при конкатенации, которая должна быть ещё и "хорошей" (по сути невозрастающей)... и всё это с условиями определенных ограничений...

Добавлено через 55 секунд
а сортировка здесь вообще противопоказана, судя по всему.

@Red white socks · 10.12.2023, 17:20

YuS_2, упорядочены, хдесь означает, что порядок слагаемых в конкатенации имеет значение.
eaa, боюсь, что так не получится

@eaa · 10.12.2023, 19:52

Red white socks, похожая задача.
мое решение Большое число

Добавлено через 18 секунд
только тут нужен подсчет.

@Red white socks · 10.12.2023, 19:59

eaa, мне кажется, что тут совсем другое. В той задаче куски не привязаны к индексу.

YuS_2 · 11.12.2023, 07:53

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

что порядок слагаемых в конкатенации имеет значение.

Да, понятно, что терминологию можно применять в отведенных рамках...
т.е. в данном случае, считаем, что условие i<=j (почему-то в формате выходных данных указано другое условие: i<j, но не суть) приводит к упорядоченности внутри пар? Это имеется в виду?
Или это:
То, что любая интересующая строка, должна быть невозрастающей - задано условием, тем самым, которое ограничивает итоговую строку как "хорошую".
?

Вообще, задача сводится к фильтру невозрастающих строк и попарному сравнению первого и крайнего элемента строк. При удовлетворении условиям, пары индексов запоминаются и выводятся. И если правильно понял, то пересечения индексов возможны, т.к. нет ограничения на повторное использование строк, т.е. на подобное : (2,3), (3,7) (2,9) и т.д....

@Red white socks · 11.12.2023, 09:39

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

условие i<=j (почему-то в формате выходных данных указано другое условие: i<j, но не суть) приводит к упорядоченности внутри пар? Это имеется в виду?

Примерно так. Первое решение, которое предложил, считало по всем парам (i,j). Условие (i<j) делает задачу на порядок сложней.

YuS_2 · 11.12.2023, 16:04

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

(по сути ~~невозрастающей~~)

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

к фильтру ~~невозрастающих~~ строк

неубывающие же нужны...

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

выполнено неравенство t_i−1 <= t_i.

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

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

делает задачу на порядок сложней.

Почему? Если в лоб, то перебор индексов с исключением уже проверенных...

@Red white socks · 11.12.2023, 16:10

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

Почему? Если в лоб, то перебор индексов с исключением уже проверенных...

YuS_2, проблема в том что перебор - это О(n^2)

YuS_2 · 11.12.2023, 16:48

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

проблема в том что перебор

Это да... ну, это же в лоб

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
arr = []
for v in range(n):
    s = input()
    a,b = s[0],s[-1]
    if b > a:
        for g in range(1,len(s)):
            if s[g] >= s[g-1]:
                if g == len(s)-1:
                    arr.append([v,a,b])
            else:
                break
 
ijarr = []
for ind,(xi,yi,zi) in enumerate(arr):
    for ij in range(ind,len(arr)-1):
        xj,yj,zj = arr[ij+1]
        if zi <= yj:
            ijarr.append((xi+1,xj+1))
 
print(ijarr)

@Red white socks · 11.12.2023, 17:45

YuS_2, ну так я примерно этого от ТС и ждал

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

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

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

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

YuS_2 · 11.12.2023, 18:11

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

так я примерно этого от ТС и ждал

Ну, я смотрю он совсем потерялся после предложения написать хотя бы его... может поможет кому-то ещё.

@eaa · 11.12.2023, 18:57

ну если "в лоб", то так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
def is_good(s):
    return all(s[i - 1] <= s[i] for i in range(1, len(s)))
 
 
a = [input() for _ in range(int(input()))]
*a, = filter(is_good, a)
n = len(a)
count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        count += is_good(a[i] + a[j])
print(count)

Новые блоги и статьи Все статьи Все блоги /
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .	Теория всего 12. ВГК на планете в стратегической игре "терра" anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	10.12.2023, 17:20
	YuS_2, упорядочены, хдесь означает, что порядок слагаемых в конкатенации имеет значение. eaa, боюсь, что так не получится 1

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

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	10.12.2023, 19:59
	eaa, мне кажется, что тут совсем другое. В той задаче куски не привязаны к индексу. 1