Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к столбу веревкой так, что веревка обмоталась вокруг царевны ровно I раз по часовой стрелке. Иванушка хочет освободить царевну и взять ее в жены. Проблема заключается в том, что плавать в болоте невозможно и ему приходится прыгать по кочкам. При каждом таком прыжке за ноги Иванушки зацепляется определенное количество зеленых водорослей. 

Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну).

Требуется определить такой маршрут движения Иванушки, при котором за его ноги зацепится минимально возможное количество водорослей.

Входные данные
Первая строка входного файла содержит три целых числа: N – количество кочек в болоте (3 ≤ N ≤ 10), I – количество оборотов веревки (1 ≤ I ≤ 6) и S – номер кочки, на которой в начальный момент стоит Иванушка (1 ≤ S ≤ N). Каждая из следующих N строк содержит вещественные координаты одной из кочек, записанные через пробел. Известно, что никакой отрезок, соединяющий две кочки, не проходит через центр болота, имеющий по соглашению координаты (0, 0).

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

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

Пример входного файла
3 1 1
-1 0
0 1
1 -2
0 1 1
1 0 1
1 1 0

Пример выходного файла
3.00
1 3 2 1

   Решение

Страница: 1 [Всего задач: 1]      

Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к столбу веревкой так, что веревка обмоталась вокруг царевны ровно I раз по часовой стрелке. Иванушка хочет освободить царевну и взять ее в жены. Проблема заключается в том, что плавать в болоте невозможно и ему приходится прыгать по кочкам. При каждом таком прыжке за ноги Иванушки зацепляется определенное количество зеленых водорослей. 

Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну).

Требуется определить такой маршрут движения Иванушки, при котором за его ноги зацепится минимально возможное количество водорослей.

Входные данные
Первая строка входного файла содержит три целых числа: N – количество кочек в болоте (3 ≤ N ≤ 10), I – количество оборотов веревки (1 ≤ I ≤ 6) и S – номер кочки, на которой в начальный момент стоит Иванушка (1 ≤ S ≤ N). Каждая из следующих N строк содержит вещественные координаты одной из кочек, записанные через пробел. Известно, что никакой отрезок, соединяющий две кочки, не проходит через центр болота, имеющий по соглашению координаты (0, 0).

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

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

Пример входного файла
3 1 1
-1 0
0 1
1 -2
0 1 1
1 0 1
1 1 0

Пример выходного файла
3.00
1 3 2 1

Прислать комментарий

Решение

Страница: 1 [Всего задач: 1]