Loading...
TonyDimitrov avatar TonyDimitrov 27 Точки

Идеи за решаване на задачка, която я няма в Judge системата?

Срещнах една задача в нета и нещо не се сещам за решение или поне за такова които покрива всички варианти.

Това е условието ако някои има идея може да я сподели, дори и да не е написал кода.

One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).

 

Inspired by this observation, Jamie created a simple game. You are given two s: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:

  • Add the letter A to the end of the string.
  • Add the letter B to the end of the string and then reverse the entire string. (After the reversal the newly-added B becomes the first character of the string).

Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".

Constraints

- The length of initial will be between 1 and 49, inclusive.

- The length of target will be between 2 and 50, inclusive.

target will be longer than initial.

- Each character in initial and each character in target will be either 'A' or 'B'.

Examples

0)

"A"

"BABA"

Returns: "Possible"

Jamie can perform the following moves:

  • Initially, the string is "A".
  • Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BA".
  • Jamie adds a 'B' to the end of the string and then reverses the string. Now the string is "BAB".
  • Jamie adds an 'A' to the end of the string. Now the string is "BABA".

Since there is a sequence of moves which starts with "A" and creates the string "BABA", the answer is "Possible".1)

"BAAAAABAA"

"BAABAAAAAB"

Returns: "Possible"

Jamie can add a 'B' to the end of the string and then reverse the string.

2)

"A"

"ABBA"

Returns: "Impossible"

3)

"AAABBAABB"

"BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"

Returns: "Possible"

4)

"AAABAAABB"

"BAABAAABAABAABBBAAAAAABBAABBBBBBBABB"

Returns: "Impossible"

Тагове:
1
C# Advanced 03/02/2017 23:55:50
ThePSXHive avatar ThePSXHive 436 Точки
Best Answer

Това е популярна задача от динамичното оптимиране. В книгата на Добриков и Наков (Преслав) е описан алгоритъм за намиране на минималния брой операции, които трябва да бъдат извършени при трансформацията на първият низ във вторият, а тази задача е подобна на описаната. За подходящ алгоритъм, можеш да проучиш edit distance.

0
TonyDimitrov avatar TonyDimitrov 27 Точки

Значи задачата не е толкова тривиална, колкото си помислих. Полезен отговор.

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.