Простая задачка по программированию

Сергей

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

Код:

ПРИШЛА ВЕСНА

РАСТАЯЛ СНЕГ

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

Код:

РЛАЕСНА

РАСАЛСНЕ

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

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

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

Код:

Л
     \ 
А С А Л

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

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

Код:

Л А
 /
А

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

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

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

Код:

Л (А)
  /
А

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

Код:

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

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

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

Код:

(А) Е С
     /
 С

Отступов - 2

Код:

(А) Е 
        \
 С  А Л Н Е

Отступов - 4

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

Код:

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

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

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

Код:

(Е) (С) Н А
         /
 А

Отступа - 3

Код:

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

Отступа - 1

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

=DeaD=

Montoya писал(а):

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

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

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

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

Denis_Wozniak

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

=DeaD=

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

Сергей

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

hudbrog

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

=DeaD=

hudbrog писал(а):

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

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

Digit

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

=DeaD=

У него сказано "десятичная"

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

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

hudbrog

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

=DeaD=

hudbrog писал(а):

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

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

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

Montoya

Сергей писал(а):

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

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

=DeaD= писал(а):

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

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

=DeaD=

Montoya писал(а):

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

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

Montoya

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

hudbrog

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

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

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

roboforum.ru

Простая задачка по программированию

Кто сейчас на конференции