Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
QuickShock
1 / 1 / 0
Регистрация: 22.02.2010
Сообщений: 9
#1

Программа Фишки, нужен алгоритм - Pascal

22.02.2010, 16:48. Просмотров 857. Ответов 4
Метки нет (Все метки)

Я не понимаю суть задачи, даже алгоритм не могу составить.

Имя входного файла: c.in
Имя выходного файла: c.out

Максимальное время работы на одном тесте: 2 секунды

Последовательность клеток занумерована числами от 1 до N. В каждой клетке стоит либо черная, либо белая фишка. Группой назовем набор подряд стоящих фишек одного цвета, ограниченный с обеих сторон фишками другого цвета или концами последовательности. Следует переместить фишки так, чтобы они образовали не более двух групп.

Перемещение фишек описывается с помощью плана обмена, в котором используются понятия операция обмена и шаг. Операция обмена меняет местами две соседние группы фишек. Шаг состоит не более чем из K одновременно выполняемых обменов. Обмены можно совершать одновременно только тогда, когда в них участвуют разные группы. После каждого шага группы одного цвета, оказавшиеся рядом, объединяются. План обменов содержит описания шагов, выполняемых последовательно.

Напишите программу, определяющую план обменов, с помощью которого за наименьшее число шагов получается последовательность, состоящая не более чем из двух групп.
Входные данные
В первой строке входного файла записаны числа N и K (1≤N≤100000 и 1≤K≤10000). Исходная расстановка фишек задается в последующих строках, содержащих N чисел (0 или 1), разделенных пробелами или переводами строк. При этом 0 соответствует черной фишке, 1 — белой.
Выходные данные
Выходной файл должен содержать описание шагов плана, по одному шагу на строке. Описание шага начинается с числа L — количества обменов на этом шаге. Затем для каждого обмена указывается минимальный номер клетки, в которой стоит фишка, участвующая в этом обмене. Последняя строка плана должна содержать одно число 0.
Примеры
c.in c.out
9 3
1 0 0 1 1
0 1 1 0 2 1 6
1 1
0
3 1
1 1 0 0

Примечание
Требуется найти план, содержащий наименьшее число шагов, при этом общее число обменов может быть не минимальным.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2010, 16:48
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Программа Фишки, нужен алгоритм (Pascal):

Кто может составить алгоритм по проге? Алгоритм нужен для отчета если вам это интересно)
uses crt; var a:array of integer; b:array of integer; i,j,m,n:integer;...

Нужен алгоритм решения
Прошу помочь как составить алгоритм решения задачи???Вот собственно сама задача

Нужен алгоритм группировок
Добрый день. Задача следующая: нужно перебрать все возможные комбинации цифр...

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

Линейный алгоритм - что напечатает программа?
Линейный алгоритм 1. Объясни, что будет напечатано программой Код Pascal...

Правильно ли составлен алгоритм и программа? Просьба исправить, если имеются ошибки!
program Pro2; uses crt; var x, y:real; begin clrscr; write ('Введите x -...

4
Puporev
Модератор
54148 / 41781 / 28887
Регистрация: 18.05.2008
Сообщений: 98,330
22.02.2010, 18:38 #2
QuickShock, Олимпиадные задачи либо не нужно решать, если не можете, либо решать самому. Мозг за свои мани Вы все равно не купите.

Добавлено через 47 секунд
Кстати за мани выполняют заказы в разделе Фриланс.
0
QuickShock
1 / 1 / 0
Регистрация: 22.02.2010
Сообщений: 9
22.02.2010, 18:50  [ТС] #3
Puporev, если бы это олимпиадная задача была...(( это нам препод изверг задал!

Ведь по идее мы сначала должны более простые задачи решать. А тут вот сразу олимпиадную...на решай блин
0
Kizer
78 / 78 / 36
Регистрация: 20.11.2009
Сообщений: 326
22.02.2010, 18:58 #4
QuickShock, позвольте Вам не поверить.
0
QuickShock
1 / 1 / 0
Регистрация: 22.02.2010
Сообщений: 9
22.02.2010, 19:02  [ТС] #5
Kizer, я предлагаю поспорить да хоть на твою квартиру) он реально нам это задал и решать это у меня реально не хватает мозгов...трудно написать программу когда не понимаешь суть
0
22.02.2010, 19:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2010, 19:02
Привет! Вот еще темы с решениями:

Фишки: Сначала нужно занять последнюю клетку, затем клетку перед ней и так далее
Дана полоска из клеток, пронумерованных от 1 до N. На каждом ходе разрешено...

Каким образом можно добавить цифры,введенные пользователем в множество? (Программа почти написана, нужен совет)
Здравствуйте, форумчане! Я не прошу написать программу за меня,у меня она...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный...

Перемещение фишки в поиске другой фишки
Здравствуйте ! Помогите, пожалуйста, решить задачу по перемещению фишки по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru