0 / 0 / 0
Регистрация: 04.04.2019
Сообщений: 1
|
||||||
1 | ||||||
Доказательство теоремы30.12.2021, 13:20. Показов 951. Ответов 1
Метки нет (Все метки)
Уже долгое время не могу решить эту задачу из сайта ACMP. Вот описание:
887. Доказательство теоремы (Время: 1 сек. Память: 16 Мб Сложность: 47%) Преподаватель читает курс лекций, в рамках которого обычно доказывается N различных теорем. Некоторые теоремы могут ссылаться в доказательстве друг на друга. Более точно, каждая теорема Ti зависит от некоторого набора из Ci других теорем; доказать ее можно лишь доказав не менее половины теорем из данного набора. При этом структура курса такова, что нет такой теоремы, от которой зависели бы две или более различных теоремы, а также нет цепочки теорем (Ti1,Ti2, . . . , Tis) такой, что Ti1 зависит от Ti2, Ti2 зависит от Ti3, …, Tis−1 зависит от Tis, а Tis – от Ti1. Однако, в этом семестре в связи с обилием праздников, перекрывающихся с лекциями, может не удаться доказать все теоремы курса. Тем не менее, нужно доказать основную теорему курса – это центральный результат всей теории, и именно его, скорее всего, придется применять слушателям в других курсах в следующем семестре. Поэтому преподаватель хочет расположить теоремы в таком порядке, чтобы основную теорему курса удалось доказать как можно раньше. Затем, если останется время, он сможет вернуться к доказательству других, менее важных теорем. Для простоты будем считать, что все теоремы доказываются за одинаковое время. Нужно доказать такое множество теорем и в таком порядке, чтобы основная теорема оказалась доказанной и чтобы общее время доказательства было минимально. Входные данные В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 10 000) – количество теорем. Каждая из следующих N строк описывает теоремы, от которых зависит Ti−1, где i – номер этой строки во входном файле. Эти строки имеют вид Ai,1 Ai,2 ... Ai,Ci 0; здесь Ai,j – номер теоремы, от которой зависит Ti−1. Среди всех чисел Ai,j во входном файле нет двух одинаковых. Основная теорема имеет номер 1. Все числа во входном файле целые. Выходные данные В первой строке выходного файла OUTPUT.TXT выведите K – минимальное количество теорем, которые потребуется доказать. В последующих K строках выведите номера этих теорем в порядке их доказательства, по одному числу в каждой. Если ответов с минимальным K несколько, можно вывести любой из них. Вот мой код. Он проходит 9 тестов, на 10 - wrong answer.
0
|
30.12.2021, 13:20 | |
Ответы с готовыми решениями:
1
Реализация Теоремы Штурма Проверка теоремы Гольдбаха Код Китайской теоремы остатков Реализация Китайской теоремы об остатках |
30.12.2021, 19:37 | 2 | |||||
0
|
30.12.2021, 19:37 | |
30.12.2021, 19:37 | |
Помогаю со студенческими работами здесь
2
Бинарный поиск с соблюдением теоремы Пифагора Написать программу из теории чисел для теоремы Эйлера Программа выводит числа a,b и c не более 25, для которых верно равенство теоремы пифагора т.е a2+b2=c2 Составить программу доказательство, что произведение матриц А и В некоммутативно Opencv. Применение дискретной теоремы Грина к изображению Доказательство гипотезы (теоремы) Эндрю Била в контексте "Полного доказательства великой теоремы Ферма методом деления" Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |