Графы

@Montanaa · Регистрация: 21.03.2011

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

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

Задана строка s. За один ход можно поменять два соседних символа местами или поменять два символа через один (т.е. те, у которых позиции отличаются на величину 2).

За какое наименьшее число ходов можно получить из заданной строки s палиндром.

Входные данные
Во входном файле задана строка s. Ее длина от 1 до 9 символов. Строка состоит из строчных латинских букв.

Выходные данные
Выведите искомое наименьшее число обменов. Выведите -1 если из заданной строки невозможно получить палиндром.

Пример(ы)
ВВОД:
abacaba
ВЫВОД:
0

ВВОД:
bbcaa
ВЫВОД:
2

@Mayonez · 21.02.2012, 19:46

графы???

@Montanaa · 21.02.2012, 22:48 **[ТС]**

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

графы???

да, графы

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

Добавлено через 1 час 5 минут

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

да, графы

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

Никто не знает как решать?

Байт · 21.02.2012, 23:08

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

да, графы

Если вы так в этом уверены, попробуйте сформулировать вашу задачу в терминах графов
Я вовсе не исключаю, что это возможно. Напротив, ИМХО, мой опыт показывает, что почти любую задачу можно сформулировать в терминах графов.
Ваш ход.

@Montanaa 5 / 5 / 2 Регистрация: 21.03.2011 Сообщений: 79
		1
	Графы 21.02.2012, 19:35. Показов 1593. Ответов 3 Метки нет (Все метки) Помогите пожалуйста решить одну задачку. Буду очень благодарен! Спасибо заранее, огромное! Задана строка s. За один ход можно поменять два соседних символа местами или поменять два символа через один (т.е. те, у которых позиции отличаются на величину 2). За какое наименьшее число ходов можно получить из заданной строки s палиндром. Входные данные Во входном файле задана строка s. Ее длина от 1 до 9 символов. Строка состоит из строчных латинских букв. Выходные данные Выведите искомое наименьшее число обменов. Выведите -1 если из заданной строки невозможно получить палиндром. Пример(ы) ВВОД: abacaba ВЫВОД: 0 ВВОД: bbcaa ВЫВОД: 2 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	21.02.2012, 19:46	2
	графы??? 0

@Montanaa 5 / 5 / 2 Регистрация: 21.03.2011 Сообщений: 79
	21.02.2012, 22:48 [ТС]	3
	Сообщение от Mayonez графы??? да, графы Добавлено через 59 минут Помогите кто нибудь, друзья, пожалуйста Добавлено через 1 час 5 минут Сообщение от Montanaa да, графы Добавлено через 59 минут Помогите кто нибудь, друзья, пожалуйста Никто не знает как решать? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	21.02.2012, 23:08	4
	Сообщение от Montanaa да, графы Если вы так в этом уверены, попробуйте сформулировать вашу задачу в терминах графов Я вовсе не исключаю, что это возможно. Напротив, ИМХО, мой опыт показывает, что почти любую задачу можно сформулировать в терминах графов. Ваш ход. 2