Матрица минимальное количество сдвигов pascal - Помощь студентам

referent · 22.12.2012, 16:26

Был на олимпиаде по программированию. Решил 3 задачи из 4-х. А одну из легких не решил. Вообще никогда с матрицами не сталкивался:

Вам дана таблица размером N строк и M столбцов. В каждой ячейке записано число или "1" ,или "0". За один проход можно выбрать одну строку и циклически сдвинуть влево или вправо.
Циклически сдвинуть - значит переместить все значения строки вправо, а последний сделать первым. Либо передвинуть все на один влево, а первый элемент сделать последним. Например, "00101" вправо, будет "10010". А если "00101" влево, будет "01010".
Задание состоит в написании программы, которая по заданной таблице выщитывает минимальное количество сдвиго, после которых хоть в одном столбике будут только единицы.

К примеру, на входе
3 6
101010
000100
100000
На выходе
3
Если нельзя такого зачудить, вывести "-1".
Пожалуйста, вроде и не такая уж и сложная, но не знаю, то сделать.
И где же тут кто?

Serge_Bliznykov · 23.12.2012, 01:03

не уверен в оптимальности. но я бы поступил так.
написал функцию, которая по заданным i (номер строки), j (номер столбца) вычисляла расстояние до ближайшей единицы в i-й строке
MIN ( сумма значений данной функции для каждого столбца) и даст требуемый ответ.

p.s. -1 Это если в какой-то строке нет ни одной единицы. сразу можно прерывать все циклы и выдавать ответ о невозможности решения "-1".

22.12.2012, 16:26	#1
referent Пользователь Регистрация: 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.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
В последовательности определить сумму чисел,их количество,максимальное и минимальное число с их порядковыми номерами (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

23.12.2012, 01:03	#2
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	не уверен в оптимальности. но я бы поступил так. написал функцию, которая по заданным i (номер строки), j (номер столбца) вычисляла расстояние до ближайшей единицы в i-й строке MIN ( сумма значений данной функции для каждого столбца) и даст требуемый ответ. p.s. -1 Это если в какой-то строке нет ни одной единицы. сразу можно прерывать все циклы и выдавать ответ о невозможности решения "-1".