roboforum.ru

Вот мое ИМХО, я не профи и не спортивный программист, но вот как я увидел решение, возможно оно не верно, хз.

Код: Выделить всё

ПРИШЛА ВЕСНА

РАСТАЯЛ СНЕГ

Преобразовываем к виду

Код: Выделить всё

РЛАЕСНА

РАСАЛСНЕ

Берем первую бувку первого слова, смотрим сколько
до такого же символа во второй строке
В данном случае они находятся в первой позиции.
Записываем этот символ в ответ: "Р"

Следовательно смотрим на символы 'Л' и 'A'.

Берем для начала символ 'Л' и считаем "отступы"( не знаю как грамотно сказать ) до такого же символа
в другой строке.

Код: Выделить всё

Л
     \
А С А Л

Их - 3 отступа.

Считаем для второй строки, то есть берем символ А.

Код: Выделить всё

Л А
/
А

Всего 1 отступ.

Записываем символ в ответ,получается уже "РА"

Символ который мы нашли не учитываем в следующей итерации

Код: Выделить всё

Л (А)
  /
А

Не используемые символы обозначены "( )"

Код: Выделить всё

(Р) (Л) (А) Е С Н А

(Р) (А)  С  А Л С Н Е

Считаем дальше * Я не пишу целиком фразы для простоты *

Код: Выделить всё

(А) Е С
     /
С


Отступов - 2

Код: Выделить всё

(А) Е
        \
С  А Л Н Е

Отступов - 4

Следовательно выбираем С и добавляем к ответу: "РАС"
Вот вид оставшегося:

Код: Выделить всё

(Р) (Л) (А) (Е) (С) Н А

(Р) (А) (С)  А   Л  С Н Е

Идем дальше..

Код: Выделить всё

(Е) (С) Н А
         /
А

Отступа - 3

Код: Выделить всё

(Е) (С) Н
          \
А   Л  С Н Е

Отступа - 1

Выбираем Н и добавляем к ответу "РАСН", так как слово кончилось, то это
будет окончательный ответ.

Montoya писал(а):Блин, кому-то не сложно, а у кого-то уже мозг кипит от динамического программирования...

Ну скажем так, чтобы мозг не кипел, этой темой надо прозаниматься достаточно долго

Я думаю на моём счету побольше сотни задач будет, решенных этим методом.

Добавлено спустя 1 минуту 47 секунд:
2Сергей: А можно как-то более свёрнуто описать решение?

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

Вы бы этот принцип как-то русским языком описали, что ли

Может сегодня вечером напишу если будет еще актуально.

Чета вспомнилась задачка со школьной окружной(или городской ли? хз) олимпиады по программированию, год, наверна, 2000-2001 или около того. На вход дается строка - десятичная дробь произвольной длинны. Нужно определить, периодичная она или нет, записать в виде, с указанием периода. При этом периодичность может начинаться не с первого знака дроби. Как-то так. По сути примерно то же самое.

hudbrog писал(а):На вход дается строка - десятичная дробь произвольной длинны. Нужно определить, периодичная она или нет, записать в виде, с указанием периода. При этом периодичность может начинаться не с первого знака дроби. Как-то так.

Ежели дробь периодичная - как же она может быть произвольной длины? Она бесконечная должна быть!

Dead, я так думаю, что произвольной длины строка, в которой записана дробь.

У него сказано "десятичная" а периодическая десятичная дробь по определению бесконечна

К тому же если обычная дробь не конечна в десятичном виде, то она однозначно периодическая

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

hudbrog писал(а):По условиям там вроде должно быть минимум два периода полностью указаны, если она периодична, последний период может быть указан не до конца естественно.

Если так принимать, тогда можно считать, что последний всегда до конца указан и там есть минимум 2 периода.

А значит можно задачу перебором решить за O(N^2). Что-то за меньшее время не приходит в голову сразу решение

Сергей писал(а):Может сегодня вечером напишу если будет еще актуально.

Конечно актуально! Мне лично очень полезно будет разборать твой вариант решения

=DeaD= писал(а):Ну скажем так, чтобы мозг не кипел, этой темой надо прозаниматься достаточно долго

Естественно) просто я программированием "профессионально" занимаюсь меньше года, и самому довольно трудно разбирать новый материал((

Montoya писал(а):Естественно) просто я программированием "профессионально" занимаюсь меньше года, и самому довольно трудно разбирать новый материал((

Это не профессиональное, это олимпиадное (спортивное) программирование - очень помогает в смысле вырабатываемых навыков в сложных задачах в профессиональном программировании, хотя имеет не очень много общего.

Поэтому слово Профессионально в кавычках

ээ.. не понял почему последний можно считать до конца указанным.
тебе может быть дано 3.14159265358965358965
на выходе оно должно дать 3.141592(653589)

В общем задача вроде не сложная, я тогда вроде даже решил. Но по тестам (там проводилось автоматизированное тестирование на закрытом наборе входных данных) у меня получилось чета около 40% попадания в правильный результат =)

А олимпиадное программирование имхо может понадобица тока при работе в гугле =) В остальном, работа программиров - вообще другое.