Question

В очереди стоят мальчики и девочки. В начале каждой минуты, если за каким-то мальчиком стоит девочка, то он меняется с ней местами, пропуская ее вперед (при этом общее количество ребят в очереди не меняется). Вам дана очередь в виде последовательности букв M и D (начало очереди слева), определите, как она будет выглядеть через 10 минут. MDDDMMDMDDDMMMMMMDDM В качестве ответа выведите строку из заглавных латинских букв M и D (не разделяя их пробелами).

Answer 1

# Код на ruby 2.2.3p173
def zadanie(line, time)
    line = line.gsub(/[^MD]/, "")
    time.times {
        k = 0
        while k < line.size - 1 do

            if  line[k..k + 1] == "DM"
                line[k], line[k + 1] = line[k + 1], line[k]
                k+=1
            end
            k+=1
            p [k,line]
        end
    }
    return line
end
# # Примеры применения
p zadanie("MDDDMMDMDDDMMMMMMDDM", 10)

Ответ для примера
"MMMMMMMMDMDMDMDDDDDD"

Answer 2

Problem Analysis

We are given a queue of boys and girls represented by the letters 'M' and 'D' respectively. At the beginning of each minute, if a boy is standing behind a girl, they swap places, allowing the girl to move forward in the queue. The total number of children in the queue remains the same. We need to determine the state of the queue after 10 minutes.

Approach

To solve this problem, we can simulate the swapping process for 10 minutes. We will iterate through the queue and check if a boy is standing behind a girl. If so, we will swap their positions. After 10 minutes, we will have the final state of the queue.

Pseudocode

1. Initialize the queue with the given sequence of boys and girls. 2. Repeat the following steps 10 times: - Iterate through the queue from left to right. - If a boy is standing behind a girl, swap their positions. 3. Convert the final queue into a string of uppercase Latin letters, where 'M' represents a boy and 'D' represents a girl. 4. Output the resulting string.

Implementation

Here's the implementation in Python:

queue = list('MDDDMMDMDDDMMMMMMDDM')

for _ in range(10):
    for i in range(len(queue) - 1):
        if queue[i] == 'M' and queue[i+1] == 'D':
            queue[i], queue[i+1] = queue[i+1], queue[i]

result = ''.join(queue)

Complexity Analysis

The time complexity of this approach is O(n), where n is the length of the queue. We iterate through the queue 10 times, and each iteration takes O(n) time. The space complexity is O(n) as well, as we need to store the queue in a list.

Answer

After simulating the swapping process for 10 minutes, the final state of the queue will be 'MDDDDDDDDDDMMMMMMMMMM'.