Question

Рыцари В королевстве Логрес за круглым столом собираются рыцари. Каждый рыцарь гордится своими победами, поэтому делает на своих доспехах царапины по количеству побежденных противников. Ранг рыцаря определяется по количеству царапин. Рыцари весьма горды и тот, чей ранг ниже, должен оказывать почтение тому, чей ранг выше. Если вдруг возникает ситуация, что подряд сидят рыцари с одинаковым рангом, то они устраивают между собой турнир, по итогам которого определяется один победитель. Он ставит на доспехи новые царапины (если в турнире участвовало k рыцарей, то победитель поставит k − 1 новую царапину) и возвращается за стол на свое место. Остальные участники турнира уходят залечивать раны и уязвленное самолюбие. Если после этого вновь возникает аналогичная ситуация, то проводится новый турнир, и так далее. За круглым столом собралось n рыцарей, и они предусмотрительно расселись так, чтобы ранги соседей были различными. Но опоздавший Галахад все испортил. Он сел на случайно выбранное место, и карусель турниров снова закрутилась. Известны ранги всех n рыцарей, изначально сидевших за столом. Также известен ранг Галахада и место на которое он сел. Напишите программу для определения количества рыцарей, которые останутся за столом после того, как все турниры завершатся. Формат входных данных В первой строке на вход подается число n — количество рыцарей без учета Галахада. 1 ≤ n ≤ 300000 . Во второй строке через пробел записаны n натуральных чисел r 1 , … , r n — ранги всех рыцарей. r i ≤ 10 6 ; r i ≠ r i + 1 ; r 1 ≠ r n . В третьей строке через пробел записаны два натуральных числа p и t . 1 ≤ p ≤ n ; t ≤ 10 6 . Число p задает место, на которое сел Галахад и означает, что он оказался между рыцарями с номерами p и p + 1 . Если p = n , то Галахад находится между первым и последним рыцарем. Число t задает исходный ранг Галахада. Формат выходных данных Требуется вывести одно число — ответ к задаче. Методика проверки и пояснение к тесту После того, как Галахад сядет за стол после второго рыцаря, ранги рыцарей за столом будут (7 5 5 6 8 9 10 12 10 8). Два рыцаря с рангом 5 проведут турнир, останется один из них, ранг которого повысится до 6 (7 6 6 8 9 10 12 10 8). Из двух рыцарей с рангом 6 вновь останется 1 с рангом 7 (7 7 8 9 10 12 10 8). После очередного турнира получим (8 8 9 10 12 10 8). Помня, что стол круглый, видим 3 рыцарей с рангом 8, сидящих подряд. Из них останется один с рангом 10 (10 9 10 12 10). Будет проведен еще один турнир, после которого оставшиеся 4 рыцаря не будут иметь соседей с одинаковым рангом (11 9 10 12) Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется. Sample Input 1: 9 7 5 6 8 9 10 12 10 8 2 5 Sample Output 1: 4

Answer 1

Ответ:

def start_game(ranks,n,position,rank):

   new_ranks = []  

   flag = False

   for i in range(0,n+1):

       if i == position:  

           new_ranks.append(rank)

           flag = True  

       else :  

           if flag :  

               new_ranks.append(ranks[i-1])

           else :

               new_ranks.append(ranks[i])

   

   i = 0  

   flag = False

   while True:

      # print ("первый i : "+ str(i))

       if(i+1<=len(new_ranks)-1 and new_ranks[i]==new_ranks[i+1]):

               k=0  

               while True :  

                   if (new_ranks[i]==new_ranks[i+1]):

                       del new_ranks[i]

                       k=k+1

                       flag= True    

                   else :  

                       new_ranks[i]=new_ranks[i]+k

                       break

                   if i+1>len(new_ranks):

                       break

                   else:

                       continue

       elif i==len(new_ranks)-1 and len(new_ranks)>1:

               if (new_ranks[i]==new_ranks[0]):

                   while True :  

                       if (new_ranks[i]==new_ranks[0]):

                           del new_ranks[i]

                           k=k+1    

                       else :  

                           new_ranks[0]=new_ranks[i]+k

                           break

                       if i+1>len(new_ranks):

                           break

                       else:

                           continue

               

       if flag:  

           i=0  

           flag = False  

          # print (new_ranks)

       elif i+1==len(new_ranks):

           break

       else:  

           i=i+1

          # print (new_ranks)

          # print ("второй i : "+ str(i))

   return len(new_ranks)

n = int(input())

ranks = []  

st = input().split()

for i in st :  

   ranks.append(int(i))

st = input().split()

print (start_game(ranks,n,int(st[0]),int(st[1])))

Объяснение: поучи питон -__-

Answer 2

Для решения этой задачи мы можем использовать структуру данных "стек" для хранения рыцарей за круглым столом. Начнем с того, что Галахад сел на место с номером p. Затем мы будем добавлять рыцарей в стек, учитывая их ранги и проводя турниры при необходимости. Когда стек будет содержать всех рыцарей и не останется турниров, мы сможем определить, сколько рыцарей останется за столом.

Вот Python-код для решения этой задачи:

pythonCopy code
def count_remaining_knights(n, ranks, p, t):
    stack = []  # Создаем пустой стек для хранения рыцарей
    p -= 1  # Преобразуем номер места Галахада в индекс списка

    # Перебираем рыцарей и добавляем их в стек, проводя турниры при необходимости
    for i in range(n):
        # Ранг Галахада равен t, добавляем его в стек
        if i == p:
            stack.append(t)
            continue

        # Пока стек не пуст и текущий рыцарь имеет меньший ранг, проводим турнир
        while stack and ranks[i] < stack[-1]:
            stack.pop()

        # Добавляем текущего рыцаря в стек
        stack.append(ranks[i])

    # Количество рыцарей в стеке после завершения всех турниров - это ответ
    return len(stack)

# Считываем входные данные
n = int(input())
ranks = list(map(int, input().split()))
p, t = map(int, input().split())

# Вызываем функцию для определения количества оставшихся рыцарей
result = count_remaining_knights(n, ranks, p, t)

# Выводим результат
print(result)

Вы можете использовать этот код для решения задачи. Он сначала создает стек, затем перебирает рыцарей, добавляя их в стек и проводя турниры при необходимости, и, наконец, выводит количество рыцарей в стеке после завершения всех турниров.