#113584

Опасность ожирения

Темы: [Массивы]

Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 6, Опасность ожирения ]

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

У него есть возможность есть грибы, которые он находит во время прогулки. Все грибы, которые ему встречаются, различны, и он собирается съесть как можно больше различных грибов, но не превысить свою норму. Мислав действует так: он идет по лесу и в любой момент может начать действовать по следующему алгоритму. Если он может съесть гриб и не переесть, то он ест его, иначе – проходит мимо.

Вам дан массив из N весов грибов в том порядке, в котором Мислав находит их. Определите, сколько грибов он может съесть.

Входные данные

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 1000 , 1 ≤ C ≤ 10 ⁶ ).

Вторая строка содержит N целых чисел w _i ( 1 ≤ w _i ≤ 1000 ), обозначающих веса грибов.

Выходные данные

Выведите одно число – максимальное количество грибов, которое может съесть Мислав, чтобы не ожиреть.

Примечание

В первом примере если он начнет есть с первого гриба, то он съест 3 гриба (3, 1, 1). Если он начнет со второго, то он сможет съесть 4 гриба (1, 2, 1, 1).

Примеры

Входные данные

5 5
3 1 2 1 1

Выходные данные

Входные данные

7 5
1 5 4 3 2 1 1

Выходные данные

#113659

Форум. Удаление ветви

Темы: [Рекурсия] [Одномерные массивы] [Структуры]

Дано количество сообщений на некотором форуме (\(N\) натуральное, не более \(1000\)).

Также таблица, в которой указано какие сообщения на каком уровне находятся.

В первой колонке таблицы написаны номера сообщений (натуральные числа, не превосходят \(10^6\)).

Во второй колонке напротив номера сообщения стоит либо 0, если сообщение является корнем (началом) некоторой темы, либо номер того сообщения, ответом на которое является текущее.

Пример. Следующие исходные данные:

соответствуют такой структуре форума:

Гарантируется что данные во втором столбце корректны (то есть в качестве «родительского» может быть указано только существующее сообщение, а также что структура не имеет циклов и что от любого сообщения есть путь к «корню» форума).

Пусть администратор форума желает удалить сообщение с номером \(k\) (а также всю подветвь форума от этого сообщения). Сколько сообщений всего будет удалено (включая само сообщение номер \(k\))?

Входные данные

Сначала вводится натуральное число \(N\) (не превышает \(1000\)) – общее количество сообщений на форуме.

Затем вводится \(N\) строк таблицы, по \(2\) числа на строке – номер текущего сообщения и номер того сообщения, ответом на которое является текущее (или \(0\)).

В последней строке вводится натуральное число \(k\). Гарантируется, что сообщение с номером \(k\) существует.

Выходные данные

Выведите количество сообщений, которое будет удалено.

Примеры

Входные данные

1
1 0
1

Выходные данные

#113660

Форум. Путь между сообщениями

Темы: [Рекурсия] [Массивы] [Структуры]

Дано количество сообщений на некотором форуме (\(N\) натуральное, не более \(1000\)).

Также таблица, в которой указано какие сообщения на каком уровне находятся.

В первой колонке таблицы написаны номера сообщений (натуральные числа, не превосходят \(10^6\)).

Во второй колонке напротив номера сообщения стоит либо 0, если сообщение является корнем (началом) некоторой темы, либо номер того сообщения, ответом на которое является текущее.

Пример. Следующие исходные данные:

соответствуют такой структуре форума:

Гарантируется что данные во втором столбце корректны (то есть в качестве «родительского» может быть указано только существующее сообщение, а также что структура не имеет циклов и что от любого сообщения есть путь к «корню» форума).

Является ли сообщение номер \(A\) «предком» сообщения номер \(B\) (то есть можно ли перемещаясь только «вниз» по веткам форума дойти от сообщения номер \(A\) к сообщению номер \(B\)?

Входные данные

Сначала вводится натуральное число \(N\) (не превышает \(1000\)) – общее количество сообщений на форуме.

Затем вводится \(N\) строк таблицы, по \(2\) числа на строке – номер текущего сообщения и номер того сообщения, ответом на которое является текущее (или \(0\)).

В последней строке вводятся числа \(A\) и \(B\) – номера сообщений. Гарантируется, что сообщения с такими номерами существуют.

Выходные данные

Выведите слово YES, если сообщение \(A\) является «предком» сообщения \(B\), и NO – в противном случае.

Для определенности будем считать, что сообщение является предком самого себя.

Примеры

Входные данные

1
1 0
1 1

Выходные данные

YES

Входные данные

Выходные данные

NO

#113661

Форум. Номер корня

Темы: [Рекурсия] [Массивы] [Структуры]

Дано количество сообщений на некотором форуме (\(N\) натуральное, не более \(1000\)).

Также таблица, в которой указано какие сообщения на каком уровне находятся.

В первой колонке таблицы написаны номера сообщений (натуральные числа, не превосходят \(10^6\)).

Во второй колонке напротив номера сообщения стоит либо 0, если сообщение является корнем (началом) некоторой темы, либо номер того сообщения, ответом на которое является текущее.

Пример. Следующие исходные данные:

соответствуют такой структуре форума:

Гарантируется что данные во втором столбце корректны (то есть в качестве «родительского» может быть указано только существующее сообщение, а также что структура не имеет циклов и что от любого сообщения есть путь к «корню» форума).

Для сообщения номер \(A\) определить номер корневого сообщения (самого первого сообщения ветки форума, которая содержит сообщение номер \(A\)).

Входные данные

Сначала вводится натуральное число \(N\) (не превышает \(1000\)) – общее количество сообщений на форуме.

Затем вводится \(N\) строк таблицы, по \(2\) числа на строке – номер текущего сообщения и номер того сообщения, ответом на которое является текущее (или \(0\)).

В последней строке вводится число \(A\) - номер сообщения. Гарантируется, что сообщение с такими номером существует.

Выходные данные

Выведите единственное число – номер корневого сообщения для темы, в которой находится сообщение \(A\).

Примеры

Входные данные

1
1 0
1

Выходные данные

Входные данные

Выходные данные

#113662

Форум. Вывести путь

Темы: [Рекурсия] [Массивы] [Структуры]

Дано количество сообщений на некотором форуме (\(N\) натуральное, не более \(1000\)).

Также таблица, в которой указано какие сообщения на каком уровне находятся.

В первой колонке таблицы написаны номера сообщений (натуральные числа, не превосходят \(10^6\)).

Во второй колонке напротив номера сообщения стоит либо 0, если сообщение является корнем (началом) некоторой темы, либо номер того сообщения, ответом на которое является текущее.

Пример. Следующие исходные данные:

соответствуют такой структуре форума:

Гарантируется что данные во втором столбце корректны (то есть в качестве «родительского» может быть указано только существующее сообщение, а также что структура не имеет циклов и что от любого сообщения есть путь к «корню» форума).

Вывести весь «путь» от корня форума до сообщения номер \(A\) включительно, номера сообщений разделять знаком ‘#’ (решетка).

Входные данные

Сначала вводится натуральное число \(N\) (не превышает \(1000\)) – общее количество сообщений на форуме.

Затем вводится \(N\) строк таблицы, по \(2\) числа на строке – номер текущего сообщения и номер того сообщения, ответом на которое является текущее (или \(0\)).

В последней строке вводится число \(A\) - номер сообщения. Гарантируется, что сообщение с такими номером существует.

Выходные данные

Выведите строку, которая описывает полный путь от корня форума (включая начальное число \(0\)) до сообщения номер \(A\).

Примеры

Входные данные

1
1 0
1

Выходные данные

0#1

Входные данные

Выходные данные

0#1#4