Студенты СПбГУ стали чемпионами мира по программированию, обойдя Гарвард и MIT
"Наши студенты — Игорь Пышкин, Алексей Гордеев, Станислав Ершов — под руководством Андрея Лопатина решили несколько сложных задач за кратчайшее время и показали лучшие результаты", — говорится в сообщении, опубликованном на сайте СПбГУ.
Студенты вуза обошли соперников из Гарвардского университета, Массачусетского технологического института, Шанхайского университета Джао Тонг, Московского университета, а также земляков из Университета информационных технологий, механики и оптики.
Для СПбГУ победа в чемпионате мира по программированию стала уже четвертой по счету: команда выигрывала состязания в 2000, 2001 и 2014 гг.
На протяжении последних тридцати лет чемпионат ICPC — самое престижное в мире интеллектуальное состязание молодых программистов. Оно проводится под эгидой международной Ассоциации вычислительной техники ACM при поддержке компании IBM.
Источник:
84 комментария
8 лет назад
ну и другие качества: общение с коллегами,работа в команде и т.п. даже если он гений,но никто его код не понимает и ни с кем он не работает, будет сложно работать с таким человеком
ну а так кконечно молодцы,было бы интересно узнать что именно они там за задания решали
Удалить комментарий?
Удалить Отмена8 лет назад
Представьте, что у нас есть n машин с двумя чипами на каждой, а каждый чип питается от k батарей. Удивительно, но не имеет значения, сколько энергии потребляют чипы, однако важно, чтобы выходные мощности чипов как можно меньше отличались друг от друга, так как в этом случае машина работает наилучшим образом. Выходная мощность чипа — это минимальная выходная мощность среди всех k батарей в чипе. Вы располагаете 2nk батареями, которые вам необходимо распределить по чипам машин. Может оказаться, что нет способа распределить батареи так, чтобы выходные мощности чипов были равны для всех машин. Тем не менее, вам нужно минимизировать разность мощностей. Подробнее, вы хотите гарантировать вашим заказчикам, что разность выходных мощностей чипов во всех машинах не превосходит d, при этом стараясь минимизировать d. Для этого вам нужно найти оптимальное распределение батарей по чипам.
Входные данные. Состоят из одного теста, содержащего две строки. В первой строке два числа n и k (2nk ≤ 106), во второй 2nk целых чисел pi (1 ≤ pi ≤109).
Выходные данные. Выведите минимальное d такое, что существует распределение батарей по чипам, чтобы разность выходных мощностей чипов в каждой машине не превосходила d.
Удалить комментарий?
Удалить Отмена8 лет назад
Удалить комментарий?
Удалить Отмена8 лет назад
Эта задача одна из простых. Нужно из 2nk выбрать n пар (назовем их представителями) батареек, каждая из которых
имеет минимальную мощность на своем чипе, чтобы максимум разности выходных мощностей батареек в паре был минимален. Предположим, что зафиксировано d, тогда можно узнать, существуют ли представители такие, что максимум не превосходит d. Отсортируем мощности p1 ≤ p2… ≤ p2nk и будем жадно набирать пары: в первую пару попадут батареи p1 и p2. Если p2 — p1 > d, то представителей выбрать нельзя. Во вторую пару возьмем батареи (pi2, pi2+1) с разностью не больше d и минимальным индексом i2 ≤ 2k + 1, если это возможно. Аналогично в третью пару — (pi3, pi3 + 1), i3 ≤ 4k + 1.
Если с помощью этого алгоритма не удается набрать n пар, то этого сделать нельзя. Ответ найдем бинарным поиском.
Удалить комментарий?
Удалить Отмена8 лет назад
Удалить комментарий?
Удалить Отмена8 лет назад
Нам нужны только программисты 1С и клепатели говносайтов. Программисты которые занимаются разработкой всяких мудреных алгоритмов нужны только на западе, они там любят выдумывать всякие инновации, САПРы, системы управления и прочую ненашенскую хрень.
Удалить комментарий?
Удалить Отмена8 лет назад
Удалить комментарий?
Удалить Отмена8 лет назад
Удалить комментарий?
Удалить Отмена8 лет назад
Удалить комментарий?
Удалить Отмена