Минимальный штраф.

@pigah · Регистрация: 05.07.2009

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

Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо).
Известно, что 1 <= n <= 1000, 1<= m <= 1000, программа должна работать правильно при любых допустимых значениях n и m, даже если они равны 1.
Ввод из файла “input.txt”. В первой строке через пробел содержатся значения n и m (размеры матрицы), в последующих строках – сама матрица штрафов. Вывод в файл “output.txt”. В первой строке выходного файла содержится суммарный штраф по пути следования, во второй – последовательность набранных штрафов.
Примеры входных данных
input.txt
4 5
3 2 8 6 4
4 7 12 9 1
55 8 3 2 8
20 7 4 9 1
input.txt
3 1
3
4
1
Соответствующие выходные данные
output.txt
8
4 1 2 1
output.txt
8
3 4 1

Объясните плиз что здесь нужно сделать с массивом

@TanT · 13.10.2009, 06:03

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

Если язык написания С++ то очень удобно использовать стандартные контейнеры.
Подобная задача: Коммивояжер (бродячий торговец), уже не раз поднималась на форуме. а там дальше при изучении наткнёшь на всякие графы и алгоритмы оптимального блуждания по ним.

@PAKOT · 21.10.2009, 19:43

Нашел на форуме задачку Коммивояжер ( https://www.cyberforum.ru/cpp/... 55616.html ) но никаких графов и алгоритмов я не нашел....

@odip · 21.10.2009, 21:09

2TanT: Даю подсказку - задача решается алгоритмом динамического программирования.
Я тебе рассказывал этот алгоритм.
Сможешь написать ?

Добавлено через 24 секунды
Если блуждать в потемках - это будет очень долго.

Добавлено через 31 секунду
Сама задача похоже с сайта acmp.ru

@PAKOT · 24.10.2009, 10:05

Ну так что никто не подскажет алгоритм ?

@Malecha · 25.10.2009, 20:07

Ну вот так всегда.. каждый хочет получить золотую медальку и при этом не особо напрягать свои мозги..

Всеукраинский открытый чемпионат компьютерных талантов «Золотой Байт» основан Компьютерной Академией «ШАГ» в 2008 году, ориентирован на молодое, прогрессивное поколение, которое стремится проявить и реализовать свои способности в сфере IT-технологий, дизайна и коммуникаций...

@IT_Exp · 25.10.2009, 20:12

Malecha,
Ну вот так всегда.. каждый хочет получить золотую медальку и при этом не особо напрягать свои мозги..
А какой смысл во всем этом, что-то я не пойму? Если мозгов нет, то зачем медалька?
IT вроде бы не та область, где без мозгов надолго задерживаются.

@Malecha · 25.10.2009, 20:30

Просто эта задача из конкурса "Золотой байт". После решения попадаеш во второй тур..

@odip · 26.10.2009, 10:25

По стилю оформления задача похожа на олимпиадные задачи с сайта www.acmp.ru.

@TanT · 26.10.2009, 12:03

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

Просто эта задача из конкурса "Золотой байт". После решения попадаеш во второй тур..

Не по теме:

а байт правда золотой или как всегда крашенный из нержавейки?
если золотой, то можно порешать, а скока у нас байт нынче весит?

@Malecha · 26.10.2009, 12:21

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

Не по теме:
а байт правда золотой или как всегда крашенный из нержавейки?
если золотой, то можно порешать, а скока у нас байт нынче весит?

)))
http://www.goldenbyte.org - там все расценки

@ThUNd3Rb0LT · 31.10.2009, 19:27

Вы, "неучи", которые хотят во второй тур, вот представьте себе, так же и в третий пройдете, а в третьем скажут типо "к нам подкатуйте, у нас пишите",и вы там облажаетесь более чем по полной программе; т.к. я сам участвую, то секрет решения открывать не буду, а вы, "неучи", могли бы и подумать, или вы думаете в "ШАГ"е дураки сидят?.. З.ы. Ник свой я вам не скажу. З.З.ы он не такой как тут. З.З.З.Ы. за 50 баксов могу подсказать идею

Прошу прощения если к pigah это не относится, но "некоторые" которые незнают как - бороздят просторами форума, поэтому прошу не выкладывать решение.)

@Malecha · 31.10.2009, 19:37

ThuND3Rb0LT, можеш не переживать не ты один такой умный и нашел решение..

@odip · 31.10.2009, 22:26

От темы не отвлекаемся.
Если кто не знает как делать и сам решил - пусть выкладывает код. Хоть ему одному будет какая-то польза от этого.
Ну а тем кто знает выкладывать код необязательно

@Malecha · 13.11.2009, 00:10

И так кто прошел во второй тур?

Новые блоги и статьи Все статьи Все блоги /
Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита, которое может. . .	Команды "Заполнить" и "Очистить" на форме документа Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". На примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных выбран регистр накопления, в. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip

@pigah 12 / 12 / 5 Регистрация: 05.07.2009 Сообщений: 147 Записей в блоге: 1

	Минимальный штраф. 13.10.2009, 01:09. Показов 6086. Ответов 14 Метки нет (Все метки) Задана матрица натуральных чисел A(n, m), где n – количество строк, m – количество столбцов. За каждый проход через клетку (i, j) взимается штраф A(i, j). Необходимо минимизировать штраф и пройти из какой-либо клетки первой строки (приложение должно выбрать оптимальную стартовую ячейку) в любую клетку последней n-ой строки. При этом из текущей клетки можно перейти в любую из 3-х соседних ячеек в пределах матрицы, стоящих в стpоке с номеpом на 1-цу большем (можно двигаться вниз, вниз по диагонали влево, вниз по диагонали вправо). Известно, что 1 <= n <= 1000, 1<= m <= 1000, программа должна работать правильно при любых допустимых значениях n и m, даже если они равны 1. Ввод из файла “input.txt”. В первой строке через пробел содержатся значения n и m (размеры матрицы), в последующих строках – сама матрица штрафов. Вывод в файл “output.txt”. В первой строке выходного файла содержится суммарный штраф по пути следования, во второй – последовательность набранных штрафов. Примеры входных данных input.txt 4 5 3 2 8 6 4 4 7 12 9 1 55 8 3 2 8 20 7 4 9 1 input.txt 3 1 3 4 1 Соответствующие выходные данные output.txt 8 4 1 2 1 output.txt 8 3 4 1 Объясните плиз что здесь нужно сделать с массивом 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	13.10.2009, 06:03
	с массивом делать ничего не надо. требуется перебрать все возможные комбинации перемещения и выбрать оптимальный маршрут (минимальная сумма штрафов). в начале будет основной цикл по всем элементам первой строки. а в теле будет перебор всех возможных перемещений с учётом ограничений по движению. Если язык написания С++ то очень удобно использовать стандартные контейнеры. Подобная задача: Коммивояжер (бродячий торговец), уже не раз поднималась на форуме. а там дальше при изучении наткнёшь на всякие графы и алгоритмы оптимального блуждания по ним. 1

@PAKOT 1 / 1 / 1 Регистрация: 21.10.2009 Сообщений: 44
	21.10.2009, 19:43
	Нашел на форуме задачку Коммивояжер ( https://www.cyberforum.ru/cpp/... 55616.html ) но никаких графов и алгоритмов я не нашел.... 1

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	21.10.2009, 21:09
	2TanT: Даю подсказку - задача решается алгоритмом динамического программирования. Я тебе рассказывал этот алгоритм. Сможешь написать ? Добавлено через 24 секунды Если блуждать в потемках - это будет очень долго. Добавлено через 31 секунду Сама задача похоже с сайта acmp.ru 2

@PAKOT 1 / 1 / 1 Регистрация: 21.10.2009 Сообщений: 44
	24.10.2009, 10:05
	Ну так что никто не подскажет алгоритм ? 0

@Malecha 23 / 23 / 1 Регистрация: 12.09.2009 Сообщений: 25
	25.10.2009, 20:07
	Ну вот так всегда.. каждый хочет получить золотую медальку и при этом не особо напрягать свои мозги.. Всеукраинский открытый чемпионат компьютерных талантов «Золотой Байт» основан Компьютерной Академией «ШАГ» в 2008 году, ориентирован на молодое, прогрессивное поколение, которое стремится проявить и реализовать свои способности в сфере IT-технологий, дизайна и коммуникаций... 0

@IT_Exp MCSD: APP BUILDER 8795 / 1074 / 104 Регистрация: 17.06.2006 Сообщений: 32,602
	25.10.2009, 20:12
	Malecha, Ну вот так всегда.. каждый хочет получить золотую медальку и при этом не особо напрягать свои мозги.. А какой смысл во всем этом, что-то я не пойму? Если мозгов нет, то зачем медалька? IT вроде бы не та область, где без мозгов надолго задерживаются. 0

@Malecha 23 / 23 / 1 Регистрация: 12.09.2009 Сообщений: 25
	25.10.2009, 20:30
	Просто эта задача из конкурса "Золотой байт". После решения попадаеш во второй тур.. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	26.10.2009, 10:25
	По стилю оформления задача похожа на олимпиадные задачи с сайта www.acmp.ru. 0

@ThUNd3Rb0LT 0 / 0 / 1 Регистрация: 12.05.2012 Сообщений: 6
	31.10.2009, 19:27
	Вы, "неучи", которые хотят во второй тур, вот представьте себе, так же и в третий пройдете, а в третьем скажут типо "к нам подкатуйте, у нас пишите",и вы там облажаетесь более чем по полной программе; т.к. я сам участвую, то секрет решения открывать не буду, а вы, "неучи", могли бы и подумать, или вы думаете в "ШАГ"е дураки сидят?.. З.ы. Ник свой я вам не скажу. З.З.ы он не такой как тут. З.З.З.Ы. за 50 баксов могу подсказать идею Прошу прощения если к pigah это не относится, но "некоторые" которые незнают как - бороздят просторами форума, поэтому прошу не выкладывать решение.) 0

@Malecha 23 / 23 / 1 Регистрация: 12.09.2009 Сообщений: 25
	31.10.2009, 19:37
	ThuND3Rb0LT, можеш не переживать не ты один такой умный и нашел решение.. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	31.10.2009, 22:26
	От темы не отвлекаемся. Если кто не знает как делать и сам решил - пусть выкладывает код. Хоть ему одному будет какая-то польза от этого. Ну а тем кто знает выкладывать код необязательно 0

@Malecha 23 / 23 / 1 Регистрация: 12.09.2009 Сообщений: 25
	13.11.2009, 00:10
	И так кто прошел во второй тур? 0