Олимпиадные задачки. Натолкните в правильном направлении

@konkretik · Регистрация: 24.11.2018

Студворк — интернет-сервис помощи студентам

Необязательно помогать со всеми(но я был бы вам очень благодарен). Можете помочь с одной или двумя, если не хотите тратить много времени.

1) Вася наконец-то ушел в отпуск! А чтобы начальство не нашло его и не заставило работать во время отпуска - отключил телефон, перестал читать почту, мессенджеры, объявления в газетах, сделал пластическую операцию и сменил имя.

Вася решил совершить путешествие по Европе и, естетственно, не сказал своему начальнику в какие именно города он собирается (иначе начальник прилетел бы туда и заставил Васю работать во время отпуска). Однако у Васи есть одна слабость - каждый раз, когда он переезжает из города в город, то пишет в твиттере о том, на каком виде транспорта он едет. Например, он может написать "я лечу на самолете", "я еду на автобусе" или "я плыву на пароме". Вася может возвращаться в города, в которых он уже был в процессе путешествия.

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

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

Формат входных данных
В первой строке входных данных задается два числа N (1 ≤ N ≤ 500) - количество городов в Европе и M (1 ≤ M ≤ 50000) - количество маршрутов транспорта, соединяющих города.

Города занумерованы от 1 до N, а количество видов транспорта не превосходит 1000 (виды транспорта также занумерованы от 1 до 1000).

Следующие M строк содержат по три числа A, B и C (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ C ≤ 1000). Это означает, что из города A в город B (и обратно) можно попасть с помощью вида транспорта C.

В следующей строке задается число K (1 ≤ K ≤ 500) - количество записей в твиттере Васи.

Следующая строка содержит K чисел от 1 до 1000 - последовательность видов транспорта, которыми пользовался Вася.

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

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

2) Вдоль бульвара растет аллея из N деревьев, занумерованных от 1 до N. По результатам обследования удалось выяснить, что H деревьев оказались заражены вредителями и обречены на гибель, кроме того, со временем вредители переберутся и на соседние деревья.

В этой ситуации помогла бы санитарная рубка, но это вызвало бы возмущение общественности. Есть возможность построить стену между любыми парами деревьев - через стену вредители перебраться не могут. Однако урбанисты считают, что строительство более чем F стен изуродует облик города.

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

В первой строке входных данных задаются числа N (1 ≤ N ≤ 109), H и F (1 ≤ H, F ≤ min(N, 100000)).

Во второй строке задается H чисел в порядке возрастания - номера зараженных деревьев.

Формат результата
В первой строке выведите максимальное количество деревьев, которые удастся спасти.

3) Разбиение на команды
Перед проведением инновационной командной олимпиады по программированию организаторы провели опрос потенциальных участников, узнав у каждого, в команде какого размера ему будет комфортно работать. Каждый участник назвал одно число - размер команды, в которой ему было бы комфортно. В команде другого размера участник работать категорически не хочет.

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

Формат входных данных
В первой строке входных данных задается число N (1 ≤ N ≤ 100000) - количество потенциальных участников.

Во второй строке задается N чисел Ai (1 ≤ N ≤ 109) - пожелание i-го потенциального участника к размеру команды.

Формат результата
Выведите одно число - максимальное количество участников, которые смогут комфортно участвовать в олимпиаде.

@Viktorrus · 25.11.2018, 02:18

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random
N = 500
M = 2000
C = 1000
K = 40
routes = []
LC = []
for A in range(1, N+1):
    L = list(range(1,N+1))
    L.remove(A)
    for B in L:
        R = random.randint(1, C)
        routes.append([A,B,R])
        LC.append(R)
print(len(routes))
random.shuffle(LC)
ListC = LC[1:(K+1)]
#input('Stop')
#print(routes)

Теперь собственно можно писать саму программу и тестировать ее с помощью этого блока.

Добавлено через 54 минуты
В стартовом блоке обнаружил ошибку. Маршрут из А в В транспортом одного вида, а из В в А другого вида. Но я думаю для тестирования и так сгодится, а если нужно будет, потом подправлю.

Добавлено через 9 часов 42 минуты
Вот написал программу. Все работает, но программа громоздка и медленна. Может профессионалы напишут компактнее.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import random
N = 200                          # Количество городов
M = 2000                         # Количество маршрутов
C = 100                          # Количество видов транспорта
K = 40                           # Количество записей в твитере
routes = []                      # Список маршрутов
LC = []                          # Список видов транспорта
for A in range(1, N+1):
    L = list(range(1,N+1))
    L.remove(A)
    for B in L:
        R = random.randint(1, C)
        routes.append([A,B,R])
        LC.append(R)
random.shuffle(LC)
listC = LC[1:(K+1)]               # Список записей в твиторе о видах использовавшегося транспорта
listСities = list()               # Список посещаемых городов
locationN = 1                     # Город из которого отправляется
way = list()
w = 0
step = 0
def trip(loc, C):                       # Поездка, loc - город отправления, C - вид транспорта
    global listСities, w, way, step
    if step == 0:
        w += 1
    for B in range(1, 500+1):
        if [loc, B, C] in routes:        # loc - город отправления, B - город прибытия, C - вид транспорта,
            step += 1                    # (эти три цифры вместе определяют маршрут)
            way.append([loc, B, C])
            A = B
            if len(listC) <= step:
                trip(A, listC[step])
            else:
                listСities.append(loc)
                step = 0
                return 
        else:
            return
 
for locationN in range(1, (500+1)):
    for listN in listC:
        trip(locationN, listN)
listСitiesUniq = list()
for i in listСities:
    if listСities[i] in listСitiesUniq:
        break
    else:
        listСitiesUniq.append(listСities[i])
listСitiesUniq.sort()
print('Количество городов: %s' % len(listСitiesUniq))
print(listСitiesUniq)
 
input('END')

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

Добавлено через 6 минут
Пример, показан вывод:

Количество городов: 5
[28, 34, 53, 65, 70]
END

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@konkretik 0 / 0 / 0 Регистрация: 24.11.2018 Сообщений: 1

	Олимпиадные задачки. Натолкните в правильном направлении 24.11.2018, 09:17. Показов 1398. Ответов 1 Метки нет (Все метки) Необязательно помогать со всеми(но я был бы вам очень благодарен). Можете помочь с одной или двумя, если не хотите тратить много времени. 1) Вася наконец-то ушел в отпуск! А чтобы начальство не нашло его и не заставило работать во время отпуска - отключил телефон, перестал читать почту, мессенджеры, объявления в газетах, сделал пластическую операцию и сменил имя. Вася решил совершить путешествие по Европе и, естетственно, не сказал своему начальнику в какие именно города он собирается (иначе начальник прилетел бы туда и заставил Васю работать во время отпуска). Однако у Васи есть одна слабость - каждый раз, когда он переезжает из города в город, то пишет в твиттере о том, на каком виде транспорта он едет. Например, он может написать "я лечу на самолете", "я еду на автобусе" или "я плыву на пароме". Вася может возвращаться в города, в которых он уже был в процессе путешествия. Васин начальник составил карту городов Европы с указанием того, какие виды транспорта соединяют пары городов. Одну и ту же пару городов может соединять несколько видов транспорта. Начальник не знает, откуда начал свое путешествие Вася (это может быть любой город Европы), однако надеется, что по известному списку видов транспорта, использованного Васей, удастся узнать, в каких городах он может находиться в данный момент. Помогите начальнику узнать, в каких городах может находиться Вася, чтобы начальник смог найти Васю и заставить его работать во время отпуска. Формат входных данных В первой строке входных данных задается два числа N (1 ≤ N ≤ 500) - количество городов в Европе и M (1 ≤ M ≤ 50000) - количество маршрутов транспорта, соединяющих города. Города занумерованы от 1 до N, а количество видов транспорта не превосходит 1000 (виды транспорта также занумерованы от 1 до 1000). Следующие M строк содержат по три числа A, B и C (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ C ≤ 1000). Это означает, что из города A в город B (и обратно) можно попасть с помощью вида транспорта C. В следующей строке задается число K (1 ≤ K ≤ 500) - количество записей в твиттере Васи. Следующая строка содержит K чисел от 1 до 1000 - последовательность видов транспорта, которыми пользовался Вася. Формат результата В первой строке выведите количество городов, в которых может находиться Вася. Во второй строке выведите номера городов, в которых может находиться Вася, в возрастающем порядке (если их количество больше нуля). 2) Вдоль бульвара растет аллея из N деревьев, занумерованных от 1 до N. По результатам обследования удалось выяснить, что H деревьев оказались заражены вредителями и обречены на гибель, кроме того, со временем вредители переберутся и на соседние деревья. В этой ситуации помогла бы санитарная рубка, но это вызвало бы возмущение общественности. Есть возможность построить стену между любыми парами деревьев - через стену вредители перебраться не могут. Однако урбанисты считают, что строительство более чем F стен изуродует облик города. Определите, между какими парами деревьев необходимо построить стены, чтобы сохранить как можно больше деревьев. В первой строке входных данных задаются числа N (1 ≤ N ≤ 109), H и F (1 ≤ H, F ≤ min(N, 100000)). Во второй строке задается H чисел в порядке возрастания - номера зараженных деревьев. Формат результата В первой строке выведите максимальное количество деревьев, которые удастся спасти. 3) Разбиение на команды Перед проведением инновационной командной олимпиады по программированию организаторы провели опрос потенциальных участников, узнав у каждого, в команде какого размера ему будет комфортно работать. Каждый участник назвал одно число - размер команды, в которой ему было бы комфортно. В команде другого размера участник работать категорически не хочет. Организаторы олимпиады хотят разбить потенциальных участников на команды так, чтобы всем было комфортно и всего в олимпиаде приняло участие как можно больше людей. Помогите органиазаторам определить, какое максимальное количество людей может участвовать в олимпиаде. Формат входных данных В первой строке входных данных задается число N (1 ≤ N ≤ 100000) - количество потенциальных участников. Во второй строке задается N чисел Ai (1 ≤ N ≤ 109) - пожелание i-го потенциального участника к размеру команды. Формат результата Выведите одно число - максимальное количество участников, которые смогут комфортно участвовать в олимпиаде. 0