Пользователей всего:
517004
Выплачено ($): |
7`616`314,00 |
Выплат: |
8`124`260 |
Писем прочитано: |
1`025`014`951 |
|
Тема #140877
Внимание! В разделе запрещается:
- Мат (оскорбления)
- Частично реклама
![](img/about.png)
- Нарушение законодательства РФ
- Попрошайничество и просьбы одолжить деньги, кредиты или монеты
![](/avatar/93/89/35.jpg) |
+2 [19.10.2012 09:36] #938935 | Аааа братва помоги))) Долбаный паскаль
Задача D. Доказательство теоремы
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Преподаватель читает курс лекций, в рамках которого обычно доказывается 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 несколько, можно вывести любой из них.
| Раздел: Другое, последний комментарий: 19.10.2012 10:15 Тема закрыта пользователем takashikanoe |
Проголосовали: #940092, Lawrik |
Ответы |
Ответов всего: 22 |
тема закрыта |
![](/avatar/94/00/92.jpg) |
0 [19.10.2012 09:39] #940092 ![Все ответы пользователя Все ответы пользователя](img/message20.png)
|
|
![](/avatar/01/36/84/00.jpg) |
0 [19.10.2012 09:42] google 0.00 +14 ![Все ответы пользователя google Все ответы пользователя google](img/message20.png)
|
|
![](/avatar/96/76/07.jpg) |
+1 [19.10.2012 09:48] #967607 ![Все ответы пользователя Все ответы пользователя](img/message20.png)
|
Проголосовали: #1208359 |
![](/avatar/01/23/67/72.jpg) |
0 [19.10.2012 09:52] Lawrik 1678.86 +305 ![Все ответы пользователя Lawrik Все ответы пользователя Lawrik](img/message20.png)
|
|
![](/avatar/01/20/83/59.jpg) |
+1 [19.10.2012 09:53] #1208359 ![Все ответы пользователя Все ответы пользователя](img/message20.png)
|
Проголосовали: #967607 |
![](/avatar/96/76/07.jpg) |
+1 [19.10.2012 09:57] #967607 ![Все ответы пользователя Все ответы пользователя](img/message20.png)
|
Проголосовали: #1208359 |
![](/avatar/45/23/67.jpg) |
+1 [19.10.2012 09:59] ksb2ksb 3472.09 +287 ![Все ответы пользователя ksb2ksb Все ответы пользователя ksb2ksb](img/message20.png)
|
Проголосовали: #967607 |
![](/avatar/01/20/83/59.jpg) |
0 [19.10.2012 10:02] #1208359 ![Все ответы пользователя Все ответы пользователя](img/message20.png)
|
|
![](/avatar/96/76/07.jpg) |
0 [19.10.2012 10:04] #967607 ![Все ответы пользователя Все ответы пользователя](img/message20.png)
|
|
|
![](img/x.gif)
|