Question

Даю 68 баллов, но решите срочно, пожалуйста =). Очередь Студенческая группа сдает зачет преподавателю. Он расположил студентов по некоторому неизвестному порядку и сообщил, кто после кого сдает зачет. Теперь студенты хотят выяснить в каком порядке им приходить, чтобы не стоять всей группой за дверью. Формат входных данных На вход программы в первой строке подается одно натуральное число nn — количество студентов в группе. 2\leq n\leq 302≤n≤30. Далее в n-1n−1 строке через пробел подается по два имени: имя студента, сдающего зачет, и имя того студента который будет сдавать перед ним. Имена не содержат пробелов и состоят только из строчных и прописных символов латиницы. Гарантируется, что очередь задана корректно, имена студентов в группе не повторяются. Формат выходных данных Требуется вывести имена всех студентов группы в том порядке, в котором они сдают зачет. Каждое имя выводится в отдельной строке. Методика проверки и пояснение к тесту В приведенном примере в группе 5 студентов. Первой сдает зачет Лиза, поскольку только для нее не указано, кто приходит раньше. После Лизы приходит Иван, далее Мария, затем Петр и последним сдает Игорь. Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется. В королевстве Логрес за круглым столом собираются рыцари. Каждый рыцарь гордится своими победами, поэтому делает на своих доспехах царапины по количеству побежденных противников. Ранг рыцаря определяется по количеству царапин. Рыцари весьма горды и тот, чей ранг ниже, должен оказывать почтение тому, чей ранг выше. Если вдруг возникает ситуация, что подряд сидят рыцари с одинаковым рангом, то они устраивают между собой турнир, по итогам которого определяется один победитель. Он ставит на доспехи новые царапины (если в турнире участвовало kk рыцарей, то победитель поставит k-1k−1 новую царапину) и возвращается за стол на свое место. Остальные участники турнира уходят залечивать раны и уязвленное самолюбие. Если после этого вновь возникает аналогичная ситуация, то проводится новый турнир, и так далее. За круглым столом собралось nn рыцарей, и они предусмотрительно расселись так, чтобы ранги соседей были различными. Но опоздавший Галахад все испортил. Он сел на случайно выбранное место, и карусель турниров снова закрутилась. Известны ранги всех nn рыцарей, изначально сидевших за столом. Также известен ранг Галахада и место на которое он сел. Напишите программу для определения количества рыцарей, которые останутся за столом после того, как все турниры завершатся. Формат входных данных В первой строке на вход подается число nn — количество рыцарей без учета Галахада. 1 \leq n\leq 3000001≤n≤300000. Во второй строке через пробел записаны nn натуральных чисел r_1,\ldots, r_nr 1 ​ ,…,r n ​ — ранги всех рыцарей. r_i\leq 10^6r i ​ ≤10 6 ; r_i\neq r_{i+1}r i ​  =r i+1 ​ ; r_1\neq r_nr 1 ​  =r n ​ . В третьей строке через пробел записаны два натуральных числа pp и tt. 1\leq p\leq n1≤p≤n; t\leq 10^6t≤10 6 . Число pp задает место, на которое сел Галахад и означает, что он оказался между рыцарями с номерами pp и p+1p+1. Если p=np=n, то Галахад находится между первым и последним рыцарем. Число tt задает исходный ранг Галахада. Формат выходных данных Требуется вывести одно число — ответ к задаче. Методика проверки и пояснение к тесту После того, как Галахад сядет за стол после второго рыцаря, ранги рыцарей за столом будут (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 балл. Тест из условия задачи при проверке не используется.

Answer 1

Ответ: здравствуй, я решил на шарпе, на 8 из 20

Прога ниже...

Объяснение:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Linq.Expressions;

namespace Task5

{

class Program

{

static void Main(string[] args)

{

Knights knights = new();

Console.ReadLine();

foreach (var i in Console.ReadLine().Split().Select(str => int.Parse(str)))

knights.knights.Add(i);

int[] input = Console.ReadLine().Split().Select(str => int.Parse(str)).ToArray();

knights.Insert(input[0], input[1]);

while (knights.Tournament()) ;

Console.WriteLine(knights.knights.Count);

}

class Knights

{

public List<int> knights = new();

private int lastInsertIndex;

public void Insert(int index, int value)

{

knights.Insert(index, value);

lastInsertIndex = index;

}

public bool Tournament()

{

int leftIndex = lastInsertIndex, rightIndex = lastInsertIndex;

int[] localKnights = knights.ToArray();

while (localKnights[leftIndex - 1 >= 0 ? leftIndex - 1 : localKnights.Length - 1] == localKnights[lastInsertIndex]) if (--leftIndex < 0) leftIndex = localKnights.Length - 1;

while (localKnights[(rightIndex + 1) % localKnights.Length] == localKnights[lastInsertIndex]) if (++rightIndex >= localKnights.Length) rightIndex = 0;

if (leftIndex == rightIndex) return false;

int knight = 0;

if (rightIndex > leftIndex)

{

knights.RemoveRange(leftIndex, rightIndex - leftIndex + 1);

knight = localKnights[lastInsertIndex] + rightIndex - leftIndex;

}

else

{

knights.RemoveRange(leftIndex, localKnights.Length - leftIndex);

knights.RemoveRange(0, rightIndex + 1);

knight = localKnights[lastInsertIndex] + rightIndex + localKnights.Length - leftIndex;

leftIndex = 0;

}

Insert(leftIndex, knight);

return true;

}

}

}

}

Answer 2

Ответ:

n = int(input())

v = []

b = []

spisok = []

for i in range(n-1):

   c = input().split()

   v.append(c[0])

   b.append(c[1])

   first = ''

   index = 0

for i in range(len(b)):

   if b[i] not in v:

       first = b[i]

       index = i

       break

spisok.append(first)

while True:

   first = v[index]

   spisok.append(first)

   if first not in b:

       break

index = b.index(first)

for i in range(len(spisok)):

   print(spisok[i])

Объяснение:

Answer 3

Давайте рассмотрим каждую из задач по отдельности и напишем алгоритмы для их решения.

## Задача 1: Очередь студенческой группы

Для решения этой задачи можно воспользоваться алгоритмом топологической сортировки, который позволит определить порядок сдачи зачетов для студентов.

1. Сначала, создайте граф, где вершины будут представлять студентов, а ребра будут означать, что один студент сдает перед другим.

2. Считайте входные данные и постройте этот граф.

3. Затем выполните топологическую сортировку для данного графа. Это можно сделать, используя алгоритм поиска в глубину (DFS).

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

5. Выведите имена студентов в этом порядке.

Пример реализации на Python:

from collections import defaultdict

def topological_sort(graph):
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        topological_order.append(node)
    
    n = int(input())
    students = [input() for _ in range(n - 1)]
    graph = defaultdict(list)
    
    for student_pair in students:
        student1, student2 = student_pair.split()
        graph[student2].append(student1)
    
    visited = set()
    topological_order = []
    
    for student in graph.keys():
        if student not in visited:
            dfs(student)
    
    topological_order.reverse()
    
    for student in topological_order:
        print(student)

if __name__ == "__main__":
    topological_sort()

## Задача 2: Рыцари и турниры

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

1. Сначала, считайте входные данные.

2. Создайте стек для хранения рыцарей, начиная с самого мощного (с наивысшим рангом) рыцаря и заканчивая Галахадом.

3. Пройдите по стеку и проведите турниры до тех пор, пока не останется один рыцарь.

4. В каждом турнире победитель ставит новую царапину (количество царапин уменьшается на 1).

5. Уберите из стека рыцарей, которые проиграли, и добавьте победителя обратно в стек.

6. После окончания всех турниров, останется только один рыцарь в стеке, и это будет ответ.

Пример реализации на Python:

def remaining_knights(ranks, galahad_rank):
    knights = []
    for rank in ranks:
        knights.append(rank)
        while len(knights) >= 2 and knights[-1] <= galahad_rank:
            a = knights.pop()
            b = knights.pop()
            knights.append(max(a, b) + 1)
    return len(knights)

if __name__ == "__main__":
    n = int(input())
    ranks = list(map(int, input().split()))
    galahad_rank = int(input().split()[1])
    
    result = remaining_knights(ranks, galahad_rank)
    print(result)

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