|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.12.2012, 16:26 | #1 |
Пользователь
Регистрация: 31.01.2012
Сообщений: 49
|
Матрица минимальное количество сдвигов pascal
Был на олимпиаде по программированию. Решил 3 задачи из 4-х. А одну из легких не решил. Вообще никогда с матрицами не сталкивался:
Вам дана таблица размером N строк и M столбцов. В каждой ячейке записано число или "1" ,или "0". За один проход можно выбрать одну строку и циклически сдвинуть влево или вправо. Циклически сдвинуть - значит переместить все значения строки вправо, а последний сделать первым. Либо передвинуть все на один влево, а первый элемент сделать последним. Например, "00101" вправо, будет "10010". А если "00101" влево, будет "01010". Задание состоит в написании программы, которая по заданной таблице выщитывает минимальное количество сдвиго, после которых хоть в одном столбике будут только единицы. К примеру, на входе 3 6 101010 000100 100000 На выходе 3 Если нельзя такого зачудить, вывести "-1". Пожалуйста, вроде и не такая уж и сложная, но не знаю, то сделать. И где же тут кто? Последний раз редактировалось referent; 22.12.2012 в 19:13. |
23.12.2012, 01:03 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
не уверен в оптимальности. но я бы поступил так.
написал функцию, которая по заданным i (номер строки), j (номер столбца) вычисляла расстояние до ближайшей единицы в i-й строке MIN ( сумма значений данной функции для каждого столбца) и даст требуемый ответ. p.s. -1 Это если в какой-то строке нет ни одной единицы. сразу можно прерывать все циклы и выдавать ответ о невозможности решения "-1". |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
В последовательности определить сумму чисел,их количество,максимальное и минимальное число с их порядковыми номерами (QBasic) | Лена1308 | Помощь студентам | 3 | 14.12.2011 22:20 |
В последовательности определить сумму чисел,их количество,максимальное и минимальное число с их порядковыми номерами (QBasic) | Лена1308 | Помощь студентам | 0 | 01.12.2011 21:19 |
Указать минимальное количество первых букв, по которым можно различить слова из заданного списка. | bingooo | Паскаль, Turbo Pascal, PascalABC.NET | 10 | 06.06.2010 10:22 |
Указать минимальное количество первых букв, по которым можно различить слова из заданного списка. | bingooo | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 18.04.2010 19:27 |