Сегодня в отборочном раунде Google Code Jam была задача A, где требовался стандартный фокус - нужно синхронно отсортировать два списка. В данном случае у нас был список длин дорожек и скоростей перемещения по ним, нужно было отсортировать список дорожек по скорости перемещения, но при этом сохраняя их длины.
На C++ это я бы сделал так: дорожка будет храниться в виде
pair <int, int>, где поле first будет равно скорости перемещения по дорожке, поле second будет равно длине дорожки, дальше заводим массив или вектор типа pair <int, int> и стандартная сортировка как раз отсортирует по возрастанию поля first.Но поскольку писал я на Питоне, а не на C++, то нужно было сделать тот же самый трюк в Питоне. К тому же я уже начал писать решение этой задачи на Питоне, потом понял, что моя первоначальная идея была неправильной и мне как раз нужно была такая "синхронная" сортировка. Причем желательно было написать быструю сортировку, т.е. воспользоваться стандартной сортировкой. А вот как раз такой "синхронной" сортировкой я никогда в Питоне не пользовался.
Оказалось, можно делать так (конечно, для некоторых это не откровение, но я так не делал никогда). Заведем список из номеров дорожек, т.е. просто список
[0, 1, 2, ...]:Idx = list(range(n + 1))
Также заведем два словаря (
dict) V и L, которые будут по ключу (номеру дорожки) возвращать ее скорость и длину. Словари заполняются при считывании данных. А дальше - пишем так:Idx = sorted(Idx, key = V.get)
То есть вызывается стандартная сортировка для списка
Idx, но в качестве ключа передается метод get списка V, который по числу (номеру дорожки) будет возвращать скорость ее движения. В результате список номеров Idx будет отсортирован по возрастанию значения V.get(k) (где k - номер дорожки).А при чем тут ЕГЭ по информатике? А при том, что в этом году на ЕГЭ по информатике была задача C4, где нужно было сделать что-то подобное. Один (неизвестный мне) московский школьник, написал решение на питоне с таким фокусом. Участвуя в проверке работ неделю назад, я увидел это решение, разобрался в нем и теперь смог увиденный в работе школьника прием использовать при решении задачек Code Jam.
Мораль: ЕГЭ может быть полезно не только школьникам, но и проверяющим работы :)
Нда, похоже, что люди, способные просто написать qsort, скоро исчезнут с лица Земли...
UPD: в левом верхнем крае таблицы результатов есть галочка Download Solutions
================================
"Для меня, как учителя, хорошее решение это то, которое просто и понятно."
Как вы находите числа фибоначчи?
По формуле Бине.
http://pastie.org/2021466
UPD: бросился защищать преподавателя, не заметив, что тот уже отписался :-)
Так могло бы выглядеть решение на Java; всё-таки батарейки в библотеке Python помощнее будут:
Не ввязываясь в теоретическую дискуссию "О пользе или вредности Питона или любого другого языка", хотелось бы узнать хронологию лично Вашего знакомства с языками программирования (именно порядок и время, понадобившееся на это) - если у Вас есть, конечно, желание поделится этой автобиографической стороной своего становления на ниве программирования.
a = []
for i in xrange(n):
a.append((f(i), i))
print sorted(a)
А так да, массив пар в питоне отлично сортируется. Причем, даже вполне быстро: 10**5 штук проходят на ура.