Найти лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю

@Jorka · Регистрация: 25.07.2020

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

Вам дана нижнетреугольная матрица из n строк (i-й ряд состоит ровно из i элементов, расположенных в столбцах с номерами от 1 до i). В каждой ячейке матрицы записана маленькая латинская буква. Также у вас есть пустая строка s.

Вы стоите в ячейке с координатами (1, 1) (первая строка, первый столбец). На каждом ходу можно делать переход на одну ячейку ниже или на одну ячейку по диагонали вправо-вниз. То есть из ячейки с координатами (i,j) можно попасть в ячейки (i+1,j) или (i+1,j+1).

Каждый раз, когда вы попадаете в новую ячейку, к строке s в конец приписывается буква, стоящая в этой ячейке. Найдите лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю (n-ю).

Формат входных данных
В первой строке задано число n(1≤n≤5⋅10**3).Затем идёт n строк, в i-й находится строка из i символов, отвечающая первым i столбцам i-й строки матрицы.

Формат результата
Выведите искомую строку.

Примеры
Входные данные
3
o
nu
mwb
Результат работы
onm
Входные данные
4
a
bb
czc
defr
Результат работы
abcd

Написал алгоритм, но там ошибка, понял как исправить, но не могу тупо реализовать это.

@Annemesski · 01.09.2020, 18:23

Написал алгоритм...

... в студию! ©Якубович Л.А.

@Jorka · 01.09.2020, 19:09 **[ТС]**

Annemesski, Во входных данных каждая строка соответствует её размеру, можно выбрать минимальный под ним или правее под ним, я сделал такой алгоритм, но он дошёл до 8 теста, дальше ошибка, я потом подумал и понял, что ошибка из-за того, что там если две буквы одинаковы, то есть под буквой и под буквой правее, то нужно выбрать из ниже этих двух равных букв минимальную, и в соответствие с ней выбирать, но если там опять равные есть буквы, даже не 3, а 2, то ещё дальше идти, пока не будет одной минимальной, но я никак не могу это написать.

Добавлено через 2 минуты
На самом деле, мне кажется это похоже на рекурсию

@Avazart · 01.09.2020, 19:27

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

... в студию! ©Якубович Л.А.

Навеяло

@Annemesski · 02.09.2020, 08:44

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

На самом деле, мне кажется это похоже на рекурсию

Она и есть, классика жанра:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::string minStr(const std::vector<std::string> &M, const unsigned deep, unsigned i, unsigned j)
{
    std::string ret;
    ret += M[i][j];
 
    if (i < deep - 1)
    {
        if (M[i + 1][j] < M[i + 1][j + 1])
            ret += minStr(M, deep, i + 1, j);
        else if (M[i + 1][j] > M[i + 1][j + 1])
            ret += minStr(M, deep, i + 1, j + 1);
        else
        {
            std::string test1, test2;
            test1 += minStr(M, deep, i + 1, j);
            test2 += minStr(M, deep, i + 1, j + 1);
            ret += (test1 < test2 ? test1 : test2);
        }
    }
 
    return ret;
}

@Avazart · 02.09.2020, 12:40

Не по теме:

i и j оставьте для математиков, лучше использовать col, row

@Annemesski · 02.09.2020, 13:07

Не по теме:

Avazart, чем лучше? row и col надежней ассоциируются с таблицей, в задаче нижнетреугольная матрица для которой row и col могут дать ложную надежду на существование элементов выше главной диагонали. Уж если конкретизировать имена индексов для данной задачи, то следует использовать что-то вроде istring и isymbol.

@Avazart · 02.09.2020, 13:23

Хотя бы тем что i и j тяжелее визуально различать. И я не говорю о смысловой нагрузке.

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

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

в задаче нижнетреугольная матрица для которой row и col могут дать ложную надежду на существование элементов выше главной диагонали.

Столбцы есть столбцы, а строки есть строки тут не должно быть никаких левых надежд.

@Annemesski · 02.09.2020, 13:56

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

Хотя бы тем что i и j тяжелее визуально различать.

Субъективно, мне например, легче различать i, j чем row, col, особенно сопоставляя границы по i < n и j < m, чем row < rows и col < cols.

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

И я не говорю о смысловой нагрузке.

давая смысловые имена не говорить о смысловой нагрузке - бессмыслица.

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

Столбцы есть столбцы, а строки есть строки тут не должно быть никаких левых надежд.

осмысленное имя - есть контекст, данные в контексте - информация, проще говоря: осмысленные имена переменных (типов, методов, etc) - подсказка о том, что за ними скрывается. Предлагаете не обращать на это внимания? Зачем тогда вообще имена?

@Avazart · 02.09.2020, 14:03

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

собенно сопоставляя границы

Возможно потому что m и n тоже не удачное именование ?

Добавлено через 30 секунд

чем row < rows и col < cols.

можно еще лучше col_count, row_count

Задайтесь вопросом, как скоро вы заметите ошибку перепутав m и n или i и j?
Как быстро другой программист поймет что такое i,j,m,n в Вашем коде?

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

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

осмысленное имя - есть контекст, данные в контексте - информация,

Контекст четко определен - матрица, в матрице есть строки и столбцы или нет?
А вот что такое m и n в матрице совсем не очевидно.

@Annemesski · 02.09.2020, 14:04

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

col_count, row_count

Вы мне предлагаете вместо 4-ех символов печатать 24, ну нет, все(!) объявляю себя математиком (шах и мат

) и буду использовать (i, j), а программистам - программистово

@Avazart · 02.09.2020, 14:05

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

Вы мне предлагаете вместо 4-ех символов печатать 24, ну нет, все(!) объявляю себя математиком (шах и мат ) и буду использовать (i, j), а программистам - программистово

Главное это "легко читаемость" кода, а не "быстро писабильность".

@Annemesski · 02.09.2020, 14:07

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

Задайтесь вопросом, как скоро вы заметите ошибку перепутав m и n или i и j?

работая с матрицей при первом же тесте

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

Как быстро другой программист поймет что такое i,j,m,n в Вашем коде?

очевидно с ходу - это традиционные обозначения.

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

Контекст четко определен - матрица, в матрице есть строки и столбцы или нет?

есть и как правило индексируются по i и j )))

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

А вот что такое m и n в матрице совсем не очевидно.

а вот это уже лукавство.

@Avazart · 02.09.2020, 14:10

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

очевидно с ходу - это традиционные обозначения.

Для кого традиционное?

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

есть и как правило индексируются по i и j )))

Как правило математики сами путают что у них i и j.

Будем честны это скорее таблица чем матрица/2d_массив ибо нет по сути разряженных матриц.
И матрицы по определению таблицы

Ма́трица — математический объект, записываемый в виде прямоугольной таблицы ...

... которая представляет собой совокупность строк и столбцов,

https://ru.wikipedia.org/wiki/... 0%BA%D0%B0)

@Annemesski · 02.09.2020, 14:24

Avazart, да ну, математик смторит так X_i_j один идет за другим их и различать особо не надо, да и в коде примерно также, в ситуациях когда строки столбцы меняются местами и с row cols запутаться шансов не меньше.

А традиционное оно собственно из математики, так повелось и в подавляющем большинстве учебных материалов используются i, j. Ну а учеба так и закрепляется практикой. В общем-то это вопрос вкусовщины и внутрикомандных договоренностей.

@Avazart · 02.09.2020, 15:14

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

да ну, математик смторит так Xij один идет за другим их и различать особо не надо

Что один за другим строка за столбцом или столбец за строкой?

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

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

А традиционное оно собственно из математики,

Какой математики ? Русской? Английской? Арабской? Хочу обрадовать в разных странах разные обозначения. Более того думаю не составит труда найти два учебника одной страны где обозначения разные.

@Annemesski · 02.09.2020, 16:10

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

Что один за другим строка за столбцом или столбец за строкой?

Строка за столбцом.

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

Какой математики ? Русской? Английской? Арабской?

не бывает ни русской ни английской ни папуа ново гвинейской математики.

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

Хочу обрадовать в разных странах разные обозначения.

примеры в студию (что-то Аркдич зачастил в эту тему

)

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

Более того думаю не составит труда найти два учебника одной страны где обозначения разные.

опять таки, примерчик бы.

@Avazart · 02.09.2020, 16:16

Ну я точно не стану рыться сейчас по учебникам.

@Jorka · 02.09.2020, 21:14 **[ТС]**

Annemesski, а чему равно deep, i, j?

Добавлено через 1 час 23 минуты
Какие параметры передать не могу понять

Добавлено через 20 минут
Я понял что надо, но, к сожалению на тесте 9 TL

Добавлено через 55 секунд
gg чтоли?

@Annemesski · 02.09.2020, 21:39

Jorka, идея у Вас есть, попробуйте оптимизировать

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302

	Найти лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю 01.09.2020, 18:08. Показов 5363. Ответов 29 Метки нет (Все метки) Вам дана нижнетреугольная матрица из n строк (i-й ряд состоит ровно из i элементов, расположенных в столбцах с номерами от 1 до i). В каждой ячейке матрицы записана маленькая латинская буква. Также у вас есть пустая строка s. Вы стоите в ячейке с координатами (1, 1) (первая строка, первый столбец). На каждом ходу можно делать переход на одну ячейку ниже или на одну ячейку по диагонали вправо-вниз. То есть из ячейки с координатами (i,j) можно попасть в ячейки (i+1,j) или (i+1,j+1). Каждый раз, когда вы попадаете в новую ячейку, к строке s в конец приписывается буква, стоящая в этой ячейке. Найдите лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю (n-ю). Формат входных данных В первой строке задано число n(1≤n≤5⋅10**3).Затем идёт n строк, в i-й находится строка из i символов, отвечающая первым i столбцам i-й строки матрицы. Формат результата Выведите искомую строку. Примеры Входные данные 3 o nu mwb Результат работы onm Входные данные 4 a bb czc defr Результат работы abcd Написал алгоритм, но там ошибка, понял как исправить, но не могу тупо реализовать это. 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	01.09.2020, 19:09 [ТС]
	Annemesski, Во входных данных каждая строка соответствует её размеру, можно выбрать минимальный под ним или правее под ним, я сделал такой алгоритм, но он дошёл до 8 теста, дальше ошибка, я потом подумал и понял, что ошибка из-за того, что там если две буквы одинаковы, то есть под буквой и под буквой правее, то нужно выбрать из ниже этих двух равных букв минимальную, и в соответствие с ней выбирать, но если там опять равные есть буквы, даже не 3, а 2, то ещё дальше идти, пока не будет одной минимальной, но я никак не могу это написать. Добавлено через 2 минуты На самом деле, мне кажется это похоже на рекурсию 0

@Avazart
	02.09.2020, 12:40
	Не по теме: i и j оставьте для математиков, лучше использовать col, row 0

@Annemesski
	02.09.2020, 13:07
	Не по теме: Avazart, чем лучше? row и col надежней ассоциируются с таблицей, в задаче нижнетреугольная матрица для которой row и col могут дать ложную надежду на существование элементов выше главной диагонали. Уж если конкретизировать имена индексов для данной задачи, то следует использовать что-то вроде istring и isymbol. 0

@Annemesski 2674 / 1336 / 480 Регистрация: 08.11.2016 Сообщений: 3,692
	02.09.2020, 14:24
	Avazart, да ну, математик смторит так X_i_j один идет за другим их и различать особо не надо, да и в коде примерно также, в ситуациях когда строки столбцы меняются местами и с row cols запутаться шансов не меньше. А традиционное оно собственно из математики, так повелось и в подавляющем большинстве учебных материалов используются i, j. Ну а учеба так и закрепляется практикой. В общем-то это вопрос вкусовщины и внутрикомандных договоренностей. 0

@Avazart 8488 / 6155 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	02.09.2020, 16:16
	Ну я точно не стану рыться сейчас по учебникам. 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	02.09.2020, 21:14 [ТС]
	Annemesski, а чему равно deep, i, j? Добавлено через 1 час 23 минуты Какие параметры передать не могу понять Добавлено через 20 минут Я понял что надо, но, к сожалению на тесте 9 TL Добавлено через 55 секунд gg чтоли? 0

@Annemesski 2674 / 1336 / 480 Регистрация: 08.11.2016 Сообщений: 3,692
	02.09.2020, 21:39
	Jorka, идея у Вас есть, попробуйте оптимизировать 0