Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Пример конкурсной задачи
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию Пример конкурсной задачи - 13.04.2011, 01:59

Вот тут приведены примеры конкурсных задач. Первая же из них привела меня в легкое недоумение:

Цитата:
Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом.

Формат входных данных
Входные данные содержат строку s. Она состоит только из строчных букв латинского алфавита, не пуста, а ее длина не превышает 100000 символов.

Формат выходных данных
В выходной файл выведите ответ на задачу. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.
Поправьте, если я ошибаюсь, но мне представляется, что возможны всего 3 варианта:
1) Строка не является палиндромом - тогда сама строка и будет ответом;
2) Строка состоит из одинаковых символов - все подстроки являются палиндромами - ответ NO SOLUTION;
3) Строка является палиндромом, но содержит по меньшей мере 2 различных символа. Тогда будет ровно 2 ответа: строка без первого символа и строка без последнего символа.

Главный вопрос - какой из ответов нужно вывести? (Не забывайте, что проверка ответов предполагается автоматическая)

Риторический вопрос - зачем дана такая задача? В предположении что кто-то начнет решать ее перебором? Или они сами не знают, что перебор не нужен?
Ответить с цитированием
  (#2 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 13.04.2011, 12:17

Цитата:
Сообщение от Alexiski Посмотреть сообщение
Риторический вопрос - зачем дана такая задача? В предположении что кто-то начнет решать ее перебором? Или они сами не знают, что перебор не нужен?
Риторический ответ: ДУХ ВРЕМЕНИ.
Скандал вокруг ЕГЭ: в тестах, по которым принимали в вузы, обнаружены ошибки
Ответить с цитированием
  (#3 (permalink)) Старый
X-Cite_Forever X-Cite_Forever вне форума
Member
 
Сообщений: 536
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2006
По умолчанию 13.04.2011, 15:00

Походу не только новое поколение перестало думать, но и старое к ним подтягивается...
100% рассчитано что задача будет решаться сразу без обдумывания различных вариантов
Ответить с цитированием
  (#4 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 13.04.2011, 15:56

На каждое задание будет четыре прожки.
Конкурсант ставит галочку напротив правильной
Ответить с цитированием
  (#5 (permalink)) Старый
alekseytefly alekseytefly вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.08.2011
По умолчанию 06.08.2011, 21:56

пипец задание)
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
__v1tos __v1tos вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.07.2011
По умолчанию 09.08.2011, 12:06

Перебор не пройдет по времени. o(n^2), 10^10 не укладывается в 2 секунды.
Ответить с цитированием
  (#7 (permalink)) Старый
X-Cite_Forever X-Cite_Forever вне форума
Member
 
Сообщений: 536
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2006
По умолчанию 09.08.2011, 12:59

А при чем тут укладывание в 2 секунды?
Ответить с цитированием
  (#8 (permalink)) Старый
Clickgg Clickgg вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 19.07.2011
По умолчанию 19.08.2011, 02:16

cpp Код:
Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом.
мдя интересно это что допустим имеем строку полиндром
asdffdsa
Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом.
самый простой способ
asdffdsa строка полиндром
sdffdsa подстрока не полиндром
такое решение?(слишком просто и тупо)
да и вообще по такому принципу проверить строку если она >= 4 и четная ( на выход подается тока строки полиндромы) в ней содержится как минимум одна подстрока
Ответить с цитированием
  (#9 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 19.08.2011, 03:19

Цитата:
Сообщение от Clickgg Посмотреть сообщение
слишком просто и тупо
Так и я о том же..
Ответить с цитированием
  (#10 (permalink)) Старый
Gun-Down Gun-Down вне форума
;)
 
Сообщений: 306
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.07.2010
По умолчанию 19.08.2011, 04:41

Цитата:
Сообщение от Clickgg Посмотреть сообщение
самый простой способ
разбивается о случай строки "aaa...a"

так что это было действительно
Цитата:
Сообщение от Clickgg Посмотреть сообщение
тупо
...
-- шутка)

Цитата:
Сообщение от Clickgg Посмотреть сообщение
да и вообще по такому принципу проверить строку если она >= 4 и четная ( на выход подается тока строки полиндромы) в ней содержится как минимум одна подстрока
← что-то идея не ясна... какая разница чётная или нет? и что если <4?..
Ответить с цитированием
  (#11 (permalink)) Старый
Clickgg Clickgg вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 19.07.2011
По умолчанию 19.08.2011, 18:07

Цитата:
что-то идея не ясна... какая разница чётная или нет? и что если <4?..
угу прост загнался..
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Не запускается пример из книги sign Prolog 3 15.04.2009 18:14
Заплачу за пример! Shturmovik Задания за деньги 7 13.01.2007 07:23
Алгоритмы Евклидовой задачи и задачи с каннойскими башнями KaMaZ Вопросы начинающих программистов 4 21.12.2006 20:49
COM c VB на C# как запустить пример IQ7 .NET 0 19.02.2006 16:12
Пример TSR-программы под DOS на C++ YDA Вопросы начинающих программистов 6 11.12.2005 11:26
Ресурсы как решить пример Devill С/С++ 4 03.11.2005 00:54
Нужен пример для FastReport Dmt C++ Builder 0 15.07.2005 19:13
Пример калькулятора Filanton Visual Basic 1 21.09.2004 23:23
Программировать на конкурсной основе Anonymous Некоммерческие проекты 0 03.07.2004 21:39
Нужен пример GUI VIP 6.1 OKey Prolog 4 03.02.2004 16:02
Где найти пример RAS сервера VC++ Anonymous Visual C++ 0 01.02.2004 04:31
Как откомпелировать пример из DDK Anonymous С/С++ 3 10.10.2003 11:46



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов