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

Новые блоги и статьи Все статьи Все блоги /
Установка нескольких штампов электронной подписи в строго определенных местах файла docx ВладимирСамохин 19.07.2026 (В!) Работа с Электронной подписью - это неотъемлемая часть современного документооборота. Но что делать, если нужно поставить несколько штампов электронной подписи в строго определенных местах. . .	сукцессия 35. Научная статья о проделанной работе anaschu 19.07.2026 Написал в формате латекс и пдф	Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер. Hrethgir 19.07.2026 Эта публикация сейчас в песочнице и ждёт приглашения. https:/ / habr. com/ ru/ sandbox/ 295048/ начало и оглавление - Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование. . .	сукцессия 33. открытые вопросы от клауде anaschu 19.07.2026 "Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .
32 сукцессия anaschu 19.07.2026 сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .	сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических anaschu 18.07.2026 Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .	сукцессия 30. Массив проверяющих друг друга моделей anaschu 18.07.2026 Архитектура сети взаимопроверяющих моделей микоризной сукцессии (v2. 0) Развитие тензорного ОДУ-ядра и создание кросс-платформенного калибровочного полигона Уважаемые коллеги! В продолжение. . .	Грибы - это женщины, деревья - это мужчины. Анти инь янь для союза мужчины и женщины. anaschu 18.07.2026 ГЛАВНЫЙ НАУЧНО-ФИЛОСОФСКИЙ ВЫВОД: Сексуально-Репродуктивный Капитализм против Государства Моногамии Коллеги, мы вышли на финишную прямую 20-мерного ОДУ-моделирования вековой сукцессии (ветка. . .

@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