Жадность, Чтение данных, Разделяй и властвуй (2 октября 2014)

1. Задачи на сортировку и жадности
1. [sort by ratio] Есть работы. У каждой работы есть t_i − время выполнения и f_i − штраф. Нужно минимизировать ∑ T_if_i, где T_i − момент выполнения работы.
2. [events] Даны n отрезков на прямой. Для каждого k от 0 до n посчитать длину части прямой, покрытой ровно k отрезками.
3. [sort by sum] Даны n гномов. Если i-го гнома укладывать спать a_i минут, он потом спит b_i минут. Можно ли сделать так, чтобы все гномы уснули?
4. [sort by sum] Есть n спортсменов. i-й спортсмен имеет вес m_i и может держать на своих плечах суммарную массу s_i. Можно ли построить башню из всех спортсменов?
5. [sort by sum] Есть n работ. У каждой есть дедлайн d_i и время выполнения t_i. Можно ли успеть выполнить все работы?
2. Программирование: чтение и запись данных
1. C++ : cin/cout [code]
2. C++ : scanf/printf
3. C++ : getchar/putchar, gets/puts [code]
4. С++ : fread/fwrite [code]
5. Java : Scanner, System.out [code]
6. Java : BuffredReader, PrintWriter [code]
3. Разделяй и властвуй
1. Сортировка слиянием и число инверсий (код), задача про 3-инверсии
2. Алгоритм Карацубы перемножения длинных чисел [code]