Author: | Far-Eastern Subregional | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 8 Mb | |
Output file: | output.txt |
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ., aN) be any sequence (ai1, ai2, ., aiK), where 1 ≤ i1 < i2 < ... < iK ≤ N. For example, the sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences of this sequence are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.
В выходной файл выведите длину найденной наибольшей возрастающей подпоследовательности, а затем номера входящих в нее элементов в порядке возрастания.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | Г. Гренкин, И. Туфанов | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:
Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно mj > mi, pj > pi, tj > ti.
Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.
Входной файл содержит натуральное число n — количество преподавателей. Далее следует n троек натуральных чисел mi pi ti.
Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.
1 ≤ n ≤ 105
1 ≤ mi, pi, ti ≤ 109
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|