Задача по программированию

@Витос223 · Регистрация: 14.11.2015

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

Жила-была девочка Катя, и было у неё много-много денег. И подруг. Ну как подруг...

И собрались они как-то раз все вместе у Кати дома и обсуждали фильмы. Многие хвалили вкус Кати. Редко кто не соглашался с её мнением. О вкусах, конечно, не спорят, но Кате показалось это странным и она решила устроить проверку.

Катя записала m пар фильмов, которые девочки сравнивали, и для каждой такой пары пометила, какой из фильмов девочки посчитали однозначно лучше другого. А потом воспользовалась своим обаянием влиянием и убедила школьного психолога провести тестирование, в котором есть вопрос о трёх любимых фильмах. Вот так вот всё просто, когда ты – Катя.

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

Формат входных данных

В первой строке заданы числа n и m (1≤n,m≤1000).

В следующих m строках – пары фильмов, записанные у Кати. Первый фильм в паре считается лучше второго.

В следующих n строках – списки любимых фильмов девочек. Первый фильм в тройке считается лучше второго, а второй – лучше третьего.

Записи Кати непротиворечивы. Каждая пара фильмов в записях Кати встречается не более одного раза.

Так сложилось, что все фильмы, что встречаются в списках любимых фильмов девочек, встречаются и в записях Кати, а в каждом отдельно взятом списке все три фильма различны.

Для вашего же удобства названия фильмов во входных данных заменены на положительные натуральные числа, не превышающие 106.

Формат выходных данных

Выведите n строк, в i-ой из которых должно быть написано honest, если список любимых фильмов из i-го бланка не противоречит записям Кати, или liar, если противоречит.

Не выводите лишние пробелы в конце или начале строк - это будет считаться за ошибку.

Пояснение к примеру

Тройка фильмов 1 2 4 противоречит записям Кати, так как по записям Кати фильм 5 лучше фильма 4, но его нет в тройке.

Тройка фильмов 1 3 2 противоречит, так как по записям Кати фильм 2 лучше фильма 3, а в тройке фильм 3 стоит до фильма 2.

Тройка фильмов 5 4 8 противоречит, так как по записям Кати фильм 2 лучше фильма 4, но его нет в тройке.

Sample Input:

5 8
1 3
1 2
2 3
2 4
4 8
5 4
5 6
7 6
1 2 3
1 2 4
1 3 2
5 4 8
5 7 6

Sample Output:

honest
liar
liar
liar
honest

Пусть в тройке фильмов подруг первый - a, второй - b, а третий - c.
Я нашёл такие условия противоречивости:

a хуже b
b хуже c
b хуже ещё каких-то фильмов, кроме a
c хуже ещё каких-то фильмов, кроме a и b
a хуже c (опционально, прохождение тестов при его наличии почему-то не менялось)

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

Добавлено через 46 минут
За помощь могу отблагодарить денежкой

@vanks · 17.10.2019, 10:07

Решил только первую часть (n,m <= 1000) этой задачи на олимпиаде, на питоне

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
n, m = map(int, input().split())
A = []
B = []
 
for i in range (0, m):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
 
for i in range (0, n):
    j, k, l = map(int, input().split())
    JKL = [j, k, l]
    liar = 0
 
    for p in range (0,m):
        if (A[p] not in JKL) and (B[p] in JKL):
            liar = 1
            break
        try:
            if JKL.index(A[p]) > JKL.index(B[p]):
                liar = 1
                break
        except ValueError:
            liar = 0
    if liar == 0:
        print("honest")
    else:
        print("liar")

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера 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 физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .

@Витос223 4 / 4 / 1 Регистрация: 14.11.2015 Сообщений: 35

	Задача по программированию 16.10.2019, 23:13. Показов 3362. Ответов 1 Метки нет (Все метки) Жила-была девочка Катя, и было у неё много-много денег. И подруг. Ну как подруг... И собрались они как-то раз все вместе у Кати дома и обсуждали фильмы. Многие хвалили вкус Кати. Редко кто не соглашался с её мнением. О вкусах, конечно, не спорят, но Кате показалось это странным и она решила устроить проверку. Катя записала m пар фильмов, которые девочки сравнивали, и для каждой такой пары пометила, какой из фильмов девочки посчитали однозначно лучше другого. А потом воспользовалась своим обаянием влиянием и убедила школьного психолога провести тестирование, в котором есть вопрос о трёх любимых фильмах. Вот так вот всё просто, когда ты – Катя. Среди неиспорченных бланков тестирования (не спрашивайте, как она их достала) Катя нашла заполненные бланки n своих подруг. Скажите, согласовываются ли записи Кати с каждым из ответов на вопрос о трёх любимых фильмах в отдельности. Формат входных данных В первой строке заданы числа n и m (1≤n,m≤1000). В следующих m строках – пары фильмов, записанные у Кати. Первый фильм в паре считается лучше второго. В следующих n строках – списки любимых фильмов девочек. Первый фильм в тройке считается лучше второго, а второй – лучше третьего. Записи Кати непротиворечивы. Каждая пара фильмов в записях Кати встречается не более одного раза. Так сложилось, что все фильмы, что встречаются в списках любимых фильмов девочек, встречаются и в записях Кати, а в каждом отдельно взятом списке все три фильма различны. Для вашего же удобства названия фильмов во входных данных заменены на положительные натуральные числа, не превышающие 106. Формат выходных данных Выведите n строк, в i-ой из которых должно быть написано honest, если список любимых фильмов из i-го бланка не противоречит записям Кати, или liar, если противоречит. Не выводите лишние пробелы в конце или начале строк - это будет считаться за ошибку. Пояснение к примеру Тройка фильмов 1 2 4 противоречит записям Кати, так как по записям Кати фильм 5 лучше фильма 4, но его нет в тройке. Тройка фильмов 1 3 2 противоречит, так как по записям Кати фильм 2 лучше фильма 3, а в тройке фильм 3 стоит до фильма 2. Тройка фильмов 5 4 8 противоречит, так как по записям Кати фильм 2 лучше фильма 4, но его нет в тройке. Sample Input: 5 8 1 3 1 2 2 3 2 4 4 8 5 4 5 6 7 6 1 2 3 1 2 4 1 3 2 5 4 8 5 7 6 Sample Output: honest liar liar liar honest Пусть в тройке фильмов подруг первый - a, второй - b, а третий - c. Я нашёл такие условия противоречивости: a хуже b b хуже c b хуже ещё каких-то фильмов, кроме a c хуже ещё каких-то фильмов, кроме a и b a хуже c (опционально, прохождение тестов при его наличии почему-то не менялось) При данных условиях противоречивости код не проходит какие-то тесты. Пожалуйста, помогите найти ещё какие-нибудь условия Добавлено через 46 минут За помощь могу отблагодарить денежкой 0

Задача по программированию

Решение