Проверочный тест к предыдущим лекциям

1. Решите задачу 1: даны N положительных чисел a_i, нужно выбрать K таких, что их (sum a_i) была максимальна. Получилось ли у вас придумать решение за NlogN?
2. Решите задачу 2: даны N пар положительных чисел a_i, b_i, нужно выбрать K таких, что (sum a_i) / (sum b_i) максимальна. Получилось ли у вас придумать решение за Nlog²N?
3. Пусть вы уже успешно запустили Флойда. Как теперь проверить, есть ли в графе отрицательный цикл за время O(V)?
4. Пусть расстояние между любыми двумя вершинами в графе равно -1. Запустите мысленно Флойда. До конца. Сделав все V³ операций. В чем опасность?
5. Игра: дана кучка из N камней, за один ход можно с любой кучкой делать следующее: или забрать один камень, или забрать два камня, или, если N четно, разделить кучку ровно пополам. Выпишите функцию Гранди для N = 0,1,2,3,4,5,6.