Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Tattoo-master
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 9
#1

Переполнение по времени на больших тестах - C++

12.06.2012, 11:23. Просмотров 363. Ответов 1
Метки нет (Все метки)

Максимальное время работы на одном тесте:

1 секунда

Максимальный объем используемой памяти:

64 мегабайт

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".
Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).
Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).
Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.
Формат входных данных
В первой строке вводятся два натуральных числа: N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N).
Во второй строке содержится слово S, состоящее из N строчных латинских букв.
Формат выходных данных
Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).
Примеры
Входные данные

Выходные данные

5 1
abcde
12

3 3
aaa
6


Сколько пытался и так и так, выдает переполнение по времени на больших тестах. Помогите с алгоритмом, пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2012, 11:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Переполнение по времени на больших тестах (C++):

Задача на коробки, ошибка в проверочных тестах - C++
День добрый, подскажите, в чем может быть ошибка в программе, написанной для данной задачи (сами тесты неизвестны) Есть две коробки,...

Импорт БОЛЬШИХ 3d моделей, переполнение стека - OpenGL
Здравствуйте. Пишу маленький движок на OpenGL в C++ Builder. При загрузке сцены, из файлов .obj моя программа загружает 3d модели, хранит...

Измерение больших промежутков времени. - Delphi
Кто-нибудь когда-нибудь измерял в своих программах промежутки времени длительностью более 6 часов ? Уважаемые господа, предложите...

Деление больших чисел занимает много времени - C (СИ)
Привет всем. Написал функцию для деления больших чисел, но к сожалению вычисления идут очень долго. Может кто-нибудь помочь с переделкой...

Сравнение очень больших чисел с ограничением по времени - Haskell
Здравствуйте! Сейчас я пытаюсь решить задачу задачу с CodeForces. И вроде бы, все понятно и решается, но на последних тестах не проходит по...

Уменьшение времени сборки больших проектов под линукс - C Linux
Какие есть способы уменьшения времени сборки для реально больших C/C++ проектов под линукс? Решение должно состоять из open source или...

1
AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 533
12.06.2012, 20:54 #2
Что-то мне подсказывает, что без этого не обойтись. Причём придётся придумать способ динамического хэширования для быстрого извлечения хэша подстрок. Тема интересная, но очень простая - так что Интернеты Вам в помощь.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.06.2012, 20:54
Привет! Вот еще темы с ответами:

Пинг через определенный промежуток времени возрастает до очень больших цифр - Wi-Fi
Вот через ping что получается: Ответ от 192.168.0.1: число байт=32 время=1мс TTL=64 Ответ от 192.168.0.1: число байт=32 время=1мс...

В тестах get signup_path - Ruby on Rails
Пример из книжки: test "valid signup information" do get signup_path assert_difference 'User.count', 1 do ...

Что Вы думаете о тестах? - Ruby on Rails
Всем доброго времени суток. Введу в курс что бы было ясно что и так. У меня было задание сделать CRUD for admin on articles. Я создал...

Производительность на тестах і7-39хх - Процессоры
Прокомментируйте высокую производительность этих процов на тестах, с чем это повязано. Проверял ли кто их реальную производительность на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru