Обсуждение чемпионата - 2007
Финал 2009 года
К сожалению, пишу поздно. Открытие было вчера, сегодня были пробные туры (точнее, одна практическая сессия и один пробный тур), конференция Collaborative Learning, так что мы были слегка заняты.
Я постараюсь восполнить недостаток информации, но это скорее всего будет после окончания мероприятия, так сказать, в ретроспективе (у меня есть 5 гигабайт фотографий и 2 видеоклипа ужасного качества).
В этом году всё мероприятие проходит в Стокгольме, в университете под названием KTH (не спрашивайте меня как полностью пишется, а переводится как королевский технический университет). Церемония открытия была в city hall (там где обычно вручают нобелевские премии). Подробнее программу мероприятий и всякую бесполезную информацию можно узнать, как обычно, на сайте. В этом году у них новшество - видеорепортажи :)
Ну а завтра примерно с 12:00 по москве будет основной тур, попробую здесь постить апдейты, какие будут.
Enjoy.
Метки: 2009
О совпадениях или закономерностях?
Но это еще не все!!
Номер нашей команды (ID) на полуфинале и на финале был 40. На полуфинале мы сдали задачу в последние 10 минут и на финале тоже.
P.s.
Для тех кто был на финале: Сумма всех чисел в этом сообщение до P.s. равна 56 (я ничего особенного сказать не хотел :-) )
Расшифровка результатов тестирования
Accepted - тест пройден
Wrong answer - неверный ответ
Presentation error - ответ не соответствует формату выходных данных
Time limit exceeded - превышен лимит времени выполнения
Memory limit exceeded - превышен лимит использования памяти
Runtime error - ошибка времени выполнения, ваша программа завершилась с ненулевым кодом возврата
Без заголовка
Сад оказался окружен ровом с водой и стеной. Антонина Гавриловна окрестила стену крепостной, заметив, что общая конструкция напоминает наши замки. Отличие было в том, что в рве плавали гуси-лебеди и оооогромные карпы.
В саду мы искали сам дворец императора, а нашли команду СПбГУ В)
Которая объяснила нам, что сам дворец для нас недосягаем - там действительно живет японский император. Максимум что нам удалось увидеть это
Про наш обед уже рассказал Михаил Расихович В) Пойдем искать ужин!
Рутина
Сегодня был тяжёлый день, состоящий из различных официальных мероприятий как открытие чемпионата, различные встречи, на которых мы слушали бесконечные речи организаторов и спонсоров. Это очень утомляет тем более, что у нас толком-то и свободного времени не было.
Однако организаторы все-таки постарались разбавить день различными развлечениями. Обед, например, был устроен на лужайке в HemisFair Park (http://maps.google.com/maps...), где была живая мексиканская музыка в лице ансамбля из нескольких мексиканок; а во время ужина на лужайке крепости Alamo (одной из основных местных достопримечательностей http://maps.google.com/maps...) нас развлекало некое подобие на ковбоя - крутил лассо, играл с хлыстом и пистолетами.
А еще сегодня был пробный тур и мы смогли попробовать компы и увидели то место, где нам предстоит компититься. Завтра будет тот самый Java Challenge, про который уже писалось здесь в блоге. Все очень ждут его, так как это одно из наиболее интересных мероприятий здесь помимо, собственно, финала. Stingray даже сел попробовать Eclipse (IDE, на котором предстоит девелопить) - готовится... нервничает =)
настроение: Усталое
Без заголовка
Закрытие завершилось. Мы - 6е, серебрянная медаль.
Спасибо всем болельщикам!
Нас зовут на празднование.
Но теперь у вас есть результаты Top 12. Еще раз спасибо!
Мини-чемпионат окончен
Четырёхколёсные проблемы
Как вам идея - арендовать в Сан-Антонио машину и прокатиться к морю?
Аренда машины в США - обычное мероприятие. Типичное путешествие на дальнее расстояние состоит из авиаперелёта и арендованной машины, которая ждёт тебя в аэропорту. Люди говорят, что цена аренды машины - около 30-35 долларов в день (плюс страховка - важный момент).
Однако, то, что для гражданина США, у которого кредитка есть с младенчества, а права с 16 лет - легко, для туриста из России может оказаться непреодолимо :)
Кредитка
Американские компании, предоставляющие услуги проката автомобилей, не хотят стать жертвой мошенников или обстоятельств. И, хотя машину они дают покататься за смешную сумму в 35 баксов, чтобы не вылететь в трубу они используют вашу кредитную карту: во-первых, у всяких проходимцев кредиток нет, во-вторых, с кредитки можно авторизовать стоимость машины. На всякий случай. Вдруг разобьёте.
У нас, как у бедных российских программистов, с собой только дебетовые карты. И потратить, и авторизовать с них можно только ту сумму, которая на них лежит. Стоимость минивэна (чтобы нам всем туда поместиться) наверняка превысит $10000. Откуда у бедных российских программистов такие деньжищи? :)
А для американского гражданина всё это происходит совершенно незаметно ("i really don't know, it's all happened behind the scenes" - мнение среднего американского программиста) и легко. Сел - и поехал.
Права
По сравнению с кредитной картой с правами всё до смешного просто - в дополнение к русским правам вам рекомендовано иметь International Driver Permit. Но это необязательно. Всё равно до прав при попытке взять напрокат машину вы доберётесь в последнюю очередь, потому что есть ещё
Различные условия
Есть такая контора, имеющая прямое отношение к интересующей нас теме. Называется она Alamo. А вот прямая ссылка на страницу с условиями, на которых вам эти машины даются. Несложно заметить :) что на этой странице куча ссылок на другие страницы, на которых в свою очередь подробно расписано что им можно, а нам - нельзя. Вот например: Alamo reserves the right to refuse rental of a vehicle if the renter demonstrates inability to handle road rules and conditions. Или вот: This location will not accept cash at time of rental. All payments must be made on a credit card. Renters may use cash as form of final payment upon return of the vehicle.
Так что, видимо, нам ничего в этой конторе не светит. Очень жаль :)
В целом, я изложил очень пессимистичный взгляд на вещи человека, который ни разу в америке машину не арендовал. Может быть, нам не повезёт и у нас получится взять машину и покататься по незнакомым дорогам, с незнакомыми знаками и правилами (а также дорожной полицией) :)
Одно я знаю точно - я сам за руль не сяду!
Мне ещё задачи проверять.
настроение: Задумчивое
Ждем результатов.
Попробуешь тут...
А сейчас речь пойдёт о другом.
В этом штате, и даже в этом городе, ввиду того, что налогов практически нет (нефть качают) находится штаб-картира AT&T. Но интернет здесь всё равно ужасный. Я сел закачивать фотографии и писать фотоотчёт - и на этом он отвалился. Совсем. Интернет в лобби работает хуже чем у меня дома.
Честное слово, я не предполагал, что так бывает.
Фотографий у меня много, со всех официальных и неофициальных мероприятий, и я всё-таки попытаюсь их вам организовать чуть позже.
Задача C: Автомобильные номера
В городе N на Волге ввели обязательную регистрацию всех автомобилей, проезжающих по знаменитому мосту, который соединяет два города S и N. При этом инспекторы ГИБДД фиксировали номера автомобилей в особом запоминающем устройстве, программное обеспечение которого работало таким образом, что номера в записанной последовательности не отделялись друг от друга. Специфика города и окрестности такова, что все номера - это целые числа из отрезка [L, R], не имеющие лидирующих нулей.
Вам поручено написать программу, которая по заданной последовательности цифр находит возможное разбиение заданной последовательности цифр на корректные номера или выводит сообщение, что такового не существует.
Входные данные.
В первой строке записаны числа L и R (1 ≤ L ≤ R ≤ 9999). Вторая строка содержит последовательность цифр, записанных подряд без пробелов. Длина последовательности - от 1 до 2000 символов.
Выходные данные.
Ваша программа должна вывести "YES" в первую строку, если последовательность допускает корректное разбиение, во второй строке должно содержаться количество номеров K, а в третьей - последовательность разделенных пробелами чисел Ai (L ≤ Ai ≤ R, 1 ≤ i ≤ K) для одного из возможных разбиений. Если искомого разбиения не существует, выведите "NO".
Примеры:
| input.txt | output.txt | |
| Пример #1 | 10 100 10045112310131150 | YES 8 100 45 11 23 10 13 11 50 |
| Пример #2 | 10 100 230707 | NO |
Ограничение времени: 2 секунды
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Без заголовка
Удивительно, но я не нервничал абсолютно. Начали читать задачи, и достаточно быстро обнаружилась простая задача I. Я писал, Ваня следил. Сдали на 19й минуте. После этого выяснилось, что писать нечего и все продолжили чтение задач. Мне попалась задача B с длинным условием, я прочитал его по диагонали - половину не понял. Прочел ещё раз - min cost flow, перепроверили и сели писать. Я писал, Ваня следил. Сдали. Затем сели с Игорем писать задачу A про билеты. Достаточно небыстро писали, было несколько кусков не очень тривиального кода и проблемы с памятью. Пришел runtime error. После 10 минут поиска ошибки и затем тестирования на макс тесте, выяснилось что память наэкономили так, что в знаковый байт хотели запихать число 200. Исправили byte на short - сразу локально словили java heap space. Путем недолгих усилий избавились от одного трехмерного массива и задача была сдана. Далее была задача D. Игорь писал, Ваня следил. Была придумана хорошая идея, и не рассмотрен один особенный случай (+2 лишних субмита). Признаться, времени на нее мы потратили много, и я нервничал. Это был самый тяжелый час во всем контесте. Следующая задача E по моих ощущениям была сдана очень быстро, минут через 15. Игорь придумал идею, и они с Ваней все быстро написали. Монитор заморозили - мы на первом месте. У нас 5 задач, писать больше нечего, идей нет. Мы с Игорем думаем над J, Ваня думает над G. Придумывает идею, рассказывает Игорю - он не в восторге. Остается минут 45 до конца. Иван отжигает - садится за клавиатуру, говорит - "Я попишу палево, все равно компьютер свободен" :-) Пишет решение, оно проходит семпл тесты. В решении есть одна константа. Я, отвлекаясь от раздумий над J, говорю - поставь 10^6. Товарищ сказал - товарищ сделал :-) Отсылаем. Нет ответа 5 минут. 10 минут. 15 минут. 20 минут. На протяжении этого времени обсуждаем решение отосланной задачи и понимаем что оно верное. Остылаем с большей константой 5 * 10^6, не прикинув что может не хватить памяти. За 15 минут до конца приходит accepted на первое решение и runtime на второе! Даже и не знаю что сказать, чувства не передать. Занавес. Мы - ЧЕМПИОНЫ МИРА.
настроение: С чувством выполненного долга
Задача F: Перемычки
НИИ ЧАВО разработала два новых прибора - кривулятор и декривулятор. После продолжительных экспериментов выяснилось, что эти два прибора можно применять только вместе, иначе они вызывают обширные разрушения. Более того, их надо правильно соединить.
У кривулятора имеется N разъемов, у декривулятора - M. Разъемы отличаются типом энергии, которая через них проходит. Чтобы было удобнее соединять, приборы поставили, так, что разъемы расположились в два ряда. Чтобы приборы не взорвались, необходимо соединить некоторые разъемы одного с разъемами другого, причем по следующим правилам.
1. Соединять можно только разъемы одного энергетического типа.
2. Провода должны быть строго прямыми и туго натянутыми, иначе они начнут колебаться и оторвутся.
3. Каждый провод (если смотреть сверху) должен пересекаться ровно одним другим, причем по ним должны идти энергии разных типов.
4. Разумеется, нельзя использовать никакие разветвители, поэтому из одного разъема может выходить не более одного провода (хотя может не выходить ни одного).
Чтобы минимизировать потери энергии, которые связаны с неиспользуемыми разъемами (то есть теми, к которым не подключен ни один провод), необходимо соеднинить как можно больше разъемов.
Входной файл:
Сначала записаны два числа - N и M (1 <= N, M <= 100), число разъемов в кривуляторе и декривуляторе соответственно. Далее записано N чисел - тип энергии каждого разъема кривулятора. Для вашего удобства типы пронумерованы от 1 до 100. Далее имеется M чисел - тип энергии каждого разъема декривулятора.
Выходной файл:
Выведите одно число - максимальное количество проводов, задействованных в правильном соедниении кривулятора и декривулятора.
Пример входного файла:
4 4
1 2 3 1
2 3 3 1
Пример выходного файла:
2
Ограничение времени: 1 секунда
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Пояснение:
Фактически, строки входного файла представляют собой вид сверху на планки разъемов приборов: верхний ряд - кривулятор, нижний - декривулятор.
Примеры возможных подключений (в формате: индекс в первой строке - индекс во второй)
1 - 4, 2 - 1
1 - 4, 3 - 2
1 - 4, 3 - 3
Подключение 1 - 4, 2 - 1, 3 - 2 запрещено, потому что провод 1 - 4 пересекается с двумя другими.
Подключение 2 - 1, 3 - 2, 4 - 4 запрещено, потому что в нем есть провода, которые ни с чем не пересекаются.
Без заголовка
Задача A: Джон и Мэри
пока не встретит Мэри, после чего возвращается к Джону. Потом опять бежит к Мэри и возвращается. Так происходит до тех пор, пока Джон и Мэри не встретятся. Джон, Мэри и пес двигаются с постоянной скоростью Vd, Vm и Vp м/с соответственно.
Посчитайте, какое расстояние пробежит пес до встречи Джона и Мэри.
Входной файл:
В файле написаны четыре целых положительных числа: S, Vd, Vm и Vp, не превосходящие 10000.
При этом пес бегает быстрее Джона и Мэри, то есть Vp > Vd и Vp > Vm.
Выходной файл:
Выведите расстояние, которое пробежит пес до встречи Джона и Мэри с точностью до 4 знаков.
Пример входного файла:
10 1 1 2
Пример выходного файла:
10.0000
Ограничение времени: 2 секунды
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
настроение: Никакое
Задача E: Камни
Перед Вами в ряд лежат 2 * N камней. N черного цвета и N белого. За один ход разрешается взять два камня, лежащих рядом, и поменять их местами. Необходимо добиться того, чтобы рядом лежали только камни разных цветов, причем за наименьшее число ходов.
Входной файл:
Первое число во входном файле – N (1 <= N <= 250000). Затем следует 2 * N чисел, каждое из которых 0 или 1. 0 означает, что соответствующий камень белый, а 1 – черный.
Выходной файл:
Выведите в файл единственное число – наименьшее число ходов. Далее выведите сами ходы в виде пар целых чисел Ai, Bi (abs(Ai – Bi) = 1). Если надо совершить более чем 100000 ходов, выведите только первые 100000 ходов. Среди ответов одинаковой длины можно выбирать любой.
Пример входного файла:
3
0 0 0 1 1 1
Пример выходного файла:
3
4 3
3 2
4 5
Ограничение времени: 2 секунды
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Задача D: Игра
На Mail.Ru вышла новая интернет-игра, основная задача которой добраться до приза, расположенного
на вершине дерева. Главным действующим лицом является кот Василий, который может прыгать по дереву с ветки на ветку.
Игрок совершает ход, вращая огромный виртуальный барабан. Барабан разделен на M секторов, на каждом из которых написано число. После того, как барабан остановится, кот прыгает вверх ровно на столько веток, сколько указано на барабане. Если до вершины дерева осталось меньше веток, чем число, которое выпало на барабане, то игра заканчивается победой игрока. К сожалению, некоторые ветки слишком скользкие, поэтому Василий не может удержаться на них, падает вниз и начинает свой подъем заново.
Сектора на барабане пронумерованы от 1 до M. Игровой последовательностью называется последовательность номеров секторов, выпавших на барабане (даже если на разных секторах написаны одни и те же числа, игровые последовательности все равно различны).
Выясните количество игровых последовательностей, которые приводят к победе не более чем за K ходов.
Входной файл:
В первой строке входного файла записано N - количество веток на дереве. (1 <= N <= 50).
Далее следует число B - количество скользких веток. В следующей строке записано B различных чисел с номерами скользких веток. Ветки пронумерованы от 1 до N снизу вверх.
В очередной строке записано число M - количество секторов на барабане (1 <= M <= 10000).
Далее следует M чисел - числа, написанные на соответствующих секторах (эти числа от 1 до 10).
В последней строке записано число K (1 <= K <= 50).
Выходной файл:
Выведите единственное число - количество игровых последовательностей, которые приводят к победе не более чем за K ходов, без лидирующих нулей.
Пример входного файла:
4
1
2
3
1 2 1
4
Пример выходного файла:
16
Ограничение времени: 2 секунды
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Пояснение:
Победные игровые последовательности:
1 2 2
3 2 2
1 2 1 2
1 2 3 2
3 2 1 2
3 2 3 2
1 2 1 1
1 2 1 3
1 2 3 1
1 2 3 3
3 2 1 1
3 2 1 3
3 2 3 1
3 2 3 3
2 1 2 2
2 3 2 2
Призы нашего мини-чемпионата
СумкаСтильная, эргономичная и удобная сумка с превосходной кожаной отделкой. Подходит как для переноски ноутбука 15.4", так и любых других принадлежностей.
Основное отделение закрывается на две молнии с двумя замками, благодаря которым регулируется внутренний объем сумки. Множество дополнительных отделений и кармашков. Внешние стенки и разделитель из мягкого полиэстера для защиты техники от ударов. Снаружи - фактурный полиэстер с водоотталкивающим покрытием.
Ручки из натуральной кожи. Съемный нескользкий наплечный ремень. Наличие разных вариантов расцветок поможет подобрать для себя индивидуальный вариант.
Стереогарнитура Sagem BT SH1Эргономика. Приятный, качественный пластик. На ушах сидят великолепно, ничто не мешает и не вызывает неудобства.
Звук. Естественный и детализованный. Небольшие басовые провалы, но очень мощная, плотная середина.
Портативность. Чуть больше, чем наушники Samsung SBH 100, но в сложенном виде тоже занимают мало места.
Универсальность. Подключаются к телефону и плейеру одновременно, меняют устройства на лету.
WD Passport Карманный накопительМиниатюрный накопитель с большими возможностями. На этом ультратонком накопителе найдётся достаточно места для хранения и транспортировки изрядного объёма данных: фотографий, музыки, видеофильмов и документов, больших и малых. Программа WD Sync, входящая в комплект поставки, поможет вам превратить любой ПК в надежно защищенную рабочую машину.
настроение: Вредное
Наши ведут!!!
Вид спереди
Команда СГУ №2 готовится всех
Обратите внимание на надпись на доске и время.
Стена
настроение: С чувством выполненного долга
San Antonio
Вот этот пришелец встречает всех в аэропорту Атланты.
Чемпионат окончен
настроение: Задумчивое
Второй день в Токио
Чтобы их читать, Вам нужно вступить в группу
