?

Log in

No account? Create an account

rauf


Блог Алиева Рауфа

О жизни и о себе


Одна из очень интересных…
rauf
http://www.facebook.com/photo.php?fbid=10150868725…
Одна из очень интересных задач на разминке acm icpc 2012. Решите?



Начало отличное. Вольный перевод:



"Мы изначально планировали дать ту задачу вам завтра, как "боевую". Но там и так столько прекрасных задачек, и эта оказывается столь простой, что мы решили перетащить ее сюда, в разминку.



В этой задаче мы имеем дело с сортировкой чисел. Большинство из вас, похоже, писали алгоритмы сортировок до этого, но если что, нам несложно напомнить - нужно переставить числа в порядке от меньших к большим.



Ну покончили с теорией, теперь к практике. У вас есть несколько некоторых чисел. Нужно эти же числа поставить в отсортированном порядке. Хм, и где тут фокус, спросите вы? Ну хорошо, есть небольшое усложнение в случае, если числа встречаются одинаковые. Если два числа одинаковые, то то, которое было в исходном списке шло первым, должно и в отсортированном быть первым. Ничего больше тут нет, всего лишь - отсортировать от наименьшего к наибольшему. Просто!



А, да, еще одна штука, забыли сказать. Когда мы говорим "некоторые числа", мы имеем ввиду большие числа. Чтобы упростить вам задачу, мы их будем представлять в виде "башенки степеней". A1^A2^A3^...AN



где 1<=Ai<=100, но N может быть от 1 до 100 включительно."



примеры входных данных и выходных - на листочке.

Вот так проходила вчера…
rauf
http://www.facebook.com/photo.php?fbid=10150868833…
Вот так проходила вчера разминка ACM ICPC 2012. Сейчас начнется основная "битва", но выглядеть будет один-в-один, разве только празношатающихся будет меньше.



Есть недочеты в организации, к сожалению. Практически не работает Wi-Fi, экраны слева плохочитаемы, картинка не попадает в размер полотна и дождь за окном. Ой, последнее, это к другим организаторам.



Болеем за наших, черные футболки с желтыми надписями слева от центра зала. Справа от них сидят ребята из Stanford University, слева - СПбГУ.



Первое решение отмечается: приносят воздушный шарик с надписью FIRST PROBLEM SOLVED. Также доносят другие воздушные шарики, показывающие прогресс. Детально прогресс виден на большом экране.



Через 50 минут можно следить за успехами команд в онлайне http://icpc.baylor.edu/scoreboard/, обещают видеотрансляцию http://icpc2012.pl

Ужин проходил в главном…
rauf
http://www.facebook.com/photo.php?fbid=10150868846…
Ужин проходил в главном зале Варшавского политехнического университета. Вот где нужно было проводить турнир! А они его зачем-то на край города утащили. Между прочим, крупный ВУЗ - более 30тыс. студентов, 2тыс профессоров. Кстати, в 1914 году университет эвакуировался в Москву, после его перевозили в Нижний Новгород (не здание, конечно :-)) . Потом война закончилась, в Варшаве стали восстанавливать имя и ВУЗ. Главный холл прекрасен, но чуть дальше зайдешь - больших отличий с нашими ВУЗами по виду нет - все такое же старое и облезлое. Но это не главное ведь?..

Как же интересно, когда…
rauf
http://www.facebook.com/photo.php?fbid=10150868859…
Как же интересно, когда почти ничего не понимаешь по-польски. Вот этим объявлением встретил меня ВУЗ. По 100 злотых каждая!

Из этого отеля открывается…
rauf
http://www.facebook.com/photo.php?fbid=10150868865…
Из этого отеля открывается вид на большой баннер acm icpc, растянутый на самом грандиозном здании Варшавы - дворце культуры и науки. А отель прикольный. Я чего-то меньшего ожидал от AccorHotels.

А вот и сам дворец культуры…
rauf
http://www.facebook.com/photo.php?fbid=10150868872…
А вот и сам дворец культуры и науки. Он тут самый большой и заметный, высота - 230 метров. На нем сейчас висит рекламка олимпиады по программированию ACM ICPC 2012, куда я вот-вот выдвинусь. Так вот, дворец этот поляки подумывают сносить, мол, историческое прошлое, строили русские за свои деньги, мол, Польшу освободили и вот, чтобы помнили. В Варшаве кроме этого здания все очень обычное. Даже очень небольшой центр - старый город, похоже, тоже обычный. Но я туда еще не выбирался - работы много. Надеюсь, вечером дойду.

Факультет менеджмента…
rauf
http://www.facebook.com/photo.php?fbid=10150868878…
Факультет менеджмента Варшавского университета, где проходит ACM ICPC 2012 весь вот в таких скульптурах. Очень освежает официальный вид :-)

Вот еще одна. В холле на…
rauf
http://www.facebook.com/photo.php?fbid=10150868880…
Вот еще одна. В холле на входе. Спит и видит какие-то интересные сны)

Во время ланча народ болел…
rauf
http://www.facebook.com/photo.php?fbid=10150868887…
Во время ланча народ болел за соревнованием алгоритмов - http://icpc.baylor.edu/challenge/ Правила игры такие - есть курс - замкнутая фигура, большие и маленькие лодочки двух цветов-команд. Нужно пройти маршрут, задевая вершины ломаной фигуры. Понятно, что одна команда мешает другой, бои там нешуточные. Играют алгоритм против алгоритма, программисты уже просто наблюдают. Подробные правила тут: http://icpc.baylor.edu/challenge/rules.html

Посмотрим, какие будут…
rauf
Посмотрим, какие будут задачи сегодня на ACM ICPC 2012. На разминке попадались вместе со сложными и совсем простые. Скажем, нужно на Ab minor выдавать альтернативный G# minor, а на G minor - UNIQUE. Или написать калькулятор с польской нотацией. Или инвертировать матрицу 2х2. Или найти из потока чисел (до 30) минимальное, максимальное и разницу между ними. Понятно, что это просто тренировки, но такие задачи нужно делать не просто быстро, а очень быстро. Насколько я вижу, все задачи все команды могут решить за бОльшее время, чем дано. А в срок управляются только самые соображалистые.



Собственно вот здесь…
rauf
http://www.icpclive.com/
Собственно вот здесь трансляция acm icpc 2012 вместе со scoreboard. Болеем за наших http://www.icpclive.com/

http://icpc.baylor.edu/scoreboard/ не…
rauf
http://icpc.baylor.edu/scoreboard/
http://icpc.baylor.edu/scoreboard/ не справляется с нагрузкой. Под видео на icpclive.com такая же таблица, похоже, в принципе не обновляется. Только что МФТИ первые заслали решение, но тесты не прошли. Следом был Стенфорд с удачной попыткой. 1500 зрителей на livestream. Вот уже десяток команд бросили первые решения. Впереди пять часов, поболеем :-)



чем бы озаглавить…
rauf
http://apps.facebook.com/topface/?ref=post&fbid=57…


Сижу на прессухе ACM ICPC Worlds…
rauf
Сижу на прессухе ACM ICPC Worlds Final 2012. Сидит около 30 человек в фейсбуках, с президиума рассказывают в общем-то интересные вещи, но на призыв задать вопросы все молчат, уткнувшись. В мониторы. Кстати, сейчас хвалят СПбИТМО и Россию в целом. Приятно.



С минуты на минуту объявят,…
rauf
С минуты на минуту объявят, кто чемпион мира по программированию. Либо наши СпбИТМО, либо варшавцы. До заморозки результатов уверенно лидировали наши, но варшавцы могли в последнюю секунду что-то решить. Вот-вот будет ясно.



Ура! Наши первые!!!…
rauf
http://www.facebook.com/photo.php?fbid=10150869678…
Ура! Наши первые!!! Http://icpc.baylor.edu/scoreboard/