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

C# для начинающих

Войти
Регистрация
Восстановить пароль
 
gregoro
6 / 6 / 0
Регистрация: 13.01.2015
Сообщений: 84
Завершенные тесты: 2
#1

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

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

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

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

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

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

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


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


Тест-2:
Кликните здесь для просмотра всего текста
входные данные
28
aabcdefghijklmnopqrstuvwxyzz
выходные данные
ac
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2016, 21:38
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм для квеста «Турбулентность» (C#):

Помогите пожалуйста с написанием кода для текстового квеста игры - C#
Помогите пожалуйста с написанием кода для тестового квеста, сценарий написан. Написать надо не через одни if, а с функциями и прочим ...

Какой алгоритм getHashCode использовать как для больших значений, так и для маленьких - C#
Есть некий класс с какими-то числовыми полями. Причем значения полей могут варьироваться во всей области значений инта. Какой алгоритм...

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

Алгоритм для программы - C#
Необходимо написать небольшую программку(оконную), в которую вводят числа(возраст людей) а программа сортирует следующим образом и выдает...

Алгоритм для маджонга - C#
У меня есть игровое поле 8X8. При нажатии на одну ячейку потом нажимаем на другую . Нужно что бы если условие соответствовало, они...

Идея для квеста
Здравствуйте, у меня к вам такой вопрос: я хочу написать игру-квест, только не могу определиться с сценарием (квест будет 3D), можете...

6
Sergio Leone
2461 / 1106 / 403
Регистрация: 07.06.2014
Сообщений: 3,259
02.11.2016, 23:09 #2
ограничения на длину строки есть?

а чем тебя перебор не устраивает?
перебираешь все символы code от 'a' до 'z' до тех пор, пока не станет Pos(code, HintString)=0
если такое не произошло, то перебираешь все двухбукваенные комбинации code от 'aa' до 'zz'
потом 3-х буквенные, потом 4-х, потом 5-ти и т.д. пока не найдётся решение.
может это и не самый быстрый способ решения, зато точно самый простой.
0
mishau
128 / 126 / 51
Регистрация: 17.03.2009
Сообщений: 359
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
gregoro
6 / 6 / 0
Регистрация: 13.01.2015
Сообщений: 84
Завершенные тесты: 2
03.11.2016, 14:53  [ТС] #4
Формат входного файла
В первой строке содержится единственное целое число N — длина переданного сообщником слова (1 <= N <= 100).

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

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

и, кстати, непонятно, зачем даётся на вход N, ведь достаточно прочитать строку, чтобы по ней определить её длину!
0
bax_tang
.NET senior
406 / 327 / 91
Регистрация: 23.09.2016
Сообщений: 945
Завершенные тесты: 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 - C# WPF
Есть задание сделать игру квест на С#. Но нет ни каких идей что можно сделать. У кого может есть какие идеи на реализацию заданий, буду рад...

Помогите вспомнить название квеста
помогите вспомнить название квеста....вообщем играл у друга давно уже с 2004-2008 точную дату не помню вообще он комп купил и ему дали диск...

Создание текстового квеста на Visual Basic 6 - Visual Basic
Возникла такая задача: после ввода текста в TextBox необходимо подтвердить его нажатием клавиши Enter. В принципе, можно было бы сделать...

GTA4: не звонит телефон при прохождении квеста - Action/FPS игры
Не проходится миссия где надо угнать машину для Влада, проблема в том что не звонит телефон по которому Влад что-то должен сказать и это...


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

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

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