Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
6 / 6 / 1
Регистрация: 13.01.2015
Сообщений: 84
Завершенные тесты: 2
1

Алгоритм для квеста «Турбулентность»

02.11.2016, 21:38. Просмотров 859. Ответов 6
Метки нет (Все метки)

Наткнулся на крепкий орешек, не могу решить. Подскажите хотя бы алгоритм пожалуйста
спасибо.
Вот условие:

Кликните здесь для просмотра всего текста
Миша решил развлечься в свободное от решения задач время и сейчас проходит квест «Турбулентность». Задание квеста заключается в том, что Мише нужно добыть статуэтку золотого кота. Миша уже добрался до сейфа, в котором предположительно находится статуэтка, и ему осталось лишь подобрать код от замка.
Сообщник Миши оставил ему послание со словом, состоящим из строчных букв латинского алфавита. По опыту предыдущих квестов Миша догадался, что код — это слово минимальной длины, которое не является подстрокой переданного сообщником слова и состоит только из строчных букв латинского алфавита.

Также Миша решил, что перебирать все такие слова будет слишком долго, поэтому в качестве кода от сейфа среди всех подходящих слов минимальной длины он хочет попробовать лексикографически минимальное. Помогите Мише определить, какое слово ему нужно ввести.

Напомним, что подстрокой называется некоторая непрерывная часть строки. К примеру, подстроками строки abacaba являются aba, bacab, a и многие другие

Напомним также, что лексикографическое сравнение строк соответствует упорядочиванию слов в словаре, а именно, сначала идут все слова, начинающиеся на букву a, затем слова, начинающиеся на букву b, и так до конца алфавита. Если у каких-то двух слов первые буквы совпадают, то они сравниваются по второй букве. В случае повторного равенства следует сравнить третью букву и так далее. К примеру, слово game лексикографически меньше слова gate, так как первые две буквы у них совпадают, а третья идет по алфавиту раньше.


тест-1:
Кликните здесь для просмотра всего текста
входные данные
9
pascalabc
выходные данные
d


Тест-2:
Кликните здесь для просмотра всего текста
входные данные
28
aabcdefghijklmnopqrstuvwxyzz
выходные данные
ac
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.11.2016, 21:38
Ответы с готовыми решениями:

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

Штука для квеста.
Собираю для квеста что-то типа "ядерного чемоданчика" с таймером. Чтобы дать игрокам вволю...

Ответ для квеста
Ребят, решил поиграть, вот нашел сайт с квестами (http://hack-quest.com/), не могу найти правильный...

Идея для квеста
Здравствуйте, у меня к вам такой вопрос: я хочу написать игру-квест, только не могу определиться с...

6
2504 / 1125 / 582
Регистрация: 07.06.2014
Сообщений: 3,271
02.11.2016, 23:09 2
ограничения на длину строки есть?

а чем тебя перебор не устраивает?
перебираешь все символы code от 'a' до 'z' до тех пор, пока не станет Pos(code, HintString)=0
если такое не произошло, то перебираешь все двухбукваенные комбинации code от 'aa' до 'zz'
потом 3-х буквенные, потом 4-х, потом 5-ти и т.д. пока не найдётся решение.
может это и не самый быстрый способ решения, зато точно самый простой.
0
132 / 128 / 107
Регистрация: 17.03.2009
Сообщений: 364
02.11.2016, 23:33 3
Да, это быстро пишется.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
       public static string GenWord(string s)
        {
            if (s.Length == 0) return "a";
            var c = s[s.Length - 1];
            if (c == 'z') return new string('a', s.Length+1);
            c++;
            return s.Substring(0, s.Length - 1) + c;
 
        }
 
        static void Main(string[] args)
        {
 
            var code = "a";
            var s = "aabcdefghijklmnopqrstuvwxyzz";
            while (s.Contains(code))
            {
                code = GenWord(code);
            }
 
            Console.WriteLine(code);
            Console.ReadKey();
       }
2
6 / 6 / 1
Регистрация: 13.01.2015
Сообщений: 84
Завершенные тесты: 2
03.11.2016, 14:53  [ТС] 4
Формат входного файла
В первой строке содержится единственное целое число N — длина переданного сообщником слова (1 <= N <= 100).

Во второй строке содержится переданное сообщником слово.

Формат выходного файла
Выведите строку, которую Миша хочет попробовать в качестве кода от сейфа
0
2504 / 1125 / 582
Регистрация: 07.06.2014
Сообщений: 3,271
03.11.2016, 23:35 5
gregoro, тебе же дали готовый код.
что тебя не устраивает? Трудно дописать чтение исходных данных?!

и, кстати, непонятно, зачем даётся на вход N, ведь достаточно прочитать строку, чтобы по ней определить её длину!
0
.NET senior
434 / 352 / 137
Регистрация: 23.09.2016
Сообщений: 980
Завершенные тесты: 3
04.11.2016, 08:25 6
Sergio Leone, скорее всего, условие осталось ещё от C++ (в котором для динамического выделения памяти под строку при чтении её из файла нужно было сначала узнать её длину), а язык реализации изменился.
1
Sergio Leone
07.11.2016, 23:49     Алгоритм для квеста «Турбулентность»
  #7

Не по теме:

bax_tang, да, точно, скорее всего ты прав, я просто не подумал о таком варианте.

0
07.11.2016, 23:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2016, 23:49
Привет! Вот еще темы с ответами:

Идея для квеста на WPF
Есть задание сделать игру квест на С#. Но нет ни каких идей что можно сделать. У кого может есть...

Map для текстового квеста
Доброго времени суток,пишу скрипт для текстовой игры и не знаю как привязать к коду map и текст с...

Создание квеста
Подскажите, пожалуйста, среды разработки/специализированное ПО или на каком языке программирования...

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


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

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

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