Задача G: Шестиугольная ладья.
Входной файл
В первой строке записано натуральное число N (1 <= N <= 102) - количество клеток в доске. В доске всегда присутствуют первые N клеток, то есть N клеток с наименьшими номерами. В следующей строке записано
N / 2 чисел - номера клеток, с которых Кирилл делал ходы. В третьей строке записано натуральное число K
(0 < K <= 20) - количество клеток, на которое может пойти ладья. В четвертой строке записано K натуральных чисел (непревосходящих 100) - стоимость (в конфетах) движения ладьи на 1, 2 и так далее клеток.
Выходной файл
Выведите единственные два числа – наименьшее и наибольшее количество конфет, которые могли остаться у Кости.
В случае, если Кирилл ошибся в записях и такого обхода быть не могло, выведите Impossible. (без точки на конце)
Пример входного файла:
2
1
2
1 2
Пример выходного файла:
2 2
Пояснение:
Ограничение времени: 1 секунда
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Погуляли
Поездили на арендованной машине, посмотрели на окрестности.
Из этого снимка понятно, что у нас всё хорошо.
Вёл репортаж:
Задача 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 запрещено, потому что в нем есть провода, которые ни с чем не пересекаются.
Сан-Антонио, день второй
ibm thinkpada. А интернет все не отключают :)
В Сан-Антонио все замечательно, за исключением того, что очень жарко. Сегодня мы встали в 9 утра (некоторые встали в 7, но я не из их числа). Гуляли по даунтауну, аламо. Катались в центре города на лодке по реке. После обеда (да обеда, собственно, у нас и не было) мы поехали на минивэне, который взяли в рент, за город. Целью нашей поездки был шнифельбах (шницельбух, шнидельбен?:) waterpark resort. В общем, в аквапарк мы ехали, но он оказался закрыт. На обратном пути отведали китайской еды. Самыми вкусными оказались рис и креветки. Остальное даже есть страшно.
В общем, всем спасибо, всем до завтра, скоро будут новые фотки.
Как и где мы живём
Сегодня и завтра мы живём в большом доме с красной крышей.
Задача 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
San Antonio
Вот этот пришелец встречает всех в аэропорту Атланты.
Мы в Атланте
Команда, измученная долгим перелётом без еды пошла искать, что бы поесть, а я немного пофотографировал.
Кроме того, мне пришлось взломать аэропортовый wi-fi, потому что он тоже хотел денег. Но не пускает только http, а ssh работает совершенно бесплатно. Надеюсь, понятно, что нас такие смешные ограничения остановить не смогут.
Видимо, нам нужно продвигаться на следующий самолёт, поэтому фотографии из Атланты будут позже.
Перед вылетом
Поэтому, сидя в интернете дедовским способом - через GPRS и пользуясь случаем, хочу передать привет всем читателям и пожелать успехов в решении задач.
Следующий выход в эфир - из Атланты.
А дьюти-фри в Шереметьево 2 - единственное дьюти-фри, где спиртное и выпивка дороже, чем в соседнем магазине.
настроение: Боевое
Задача 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
Задача C: Брусок
В лаборатории проводятся эксперимент: в таз глубины h метров помещают кубический деревянный брусок размером A x A x A (A задан в метрах). В начале эксперимента таз полностью заполнен жидкостью.
Жидкость имеет плотность R1 кг/м^3, а дерево, из которого сделан брусок - плотность R2 кг/м^3.
Брусок помещается так, чтобы одна из граней была параллельна дну таза. Выясните, сколько воды выльется из таза в процессе эксперимента.
Входной файл:
В файле написаны четыре целых положительных числа: h, A,R1 и R2.
Все числа не превосходят 3000.
Выходной файл:
Выведите объем жидкости в м^3, которая выльется из таза, с точностью до 4 знаков.
Пример входного файла:
100 10 1000 2000
Пример выходного файла:
Ограничение времени: 2 секунды
Ограничение памяти: 32 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
День отъезда
Последние недели были насыщены тренировками (для команды) и просто подготовкой (для всех). Так что сложа руки мы не сидели. Команда готова всех
А в нашем мини-чемпионате зарегистрировалось уже 16 участников, и кое-кто из них даже решил кое-какие задачи :)
Задача B: Слова
Изучая в школе литературные произведения, Андрей заметил, что некоторые слова встречаются гораздо
чаще, чем другие. Андрея очень заинтересовал вопрос, какие же слова встречаются в тексте чаще всего?
Входной файл:
Во входном файле записан текст. Слова в нем - это последовательности из прописных латинских букв.
Они разделены пробелами, переводами строк или знаками препинания.
В тексте не более 1000 слов, каждое длиной не более 20 символов.
Выходной файл:
Выведите все слова, которые встречаются в тексте в порядке убывания их частоты.
На отдельной строке выведите слово и сколько раз оно встречается в тексте.
Если несколько слов встречаются в тексте одинаковое количество раз, то выведите их в алфавитном порядке (как в словаре).
Пример входного файла:
to be or not to be?
Пример выходного файла:
be 2
to 2
not 1
or 1
Ограничение времени: 2 секунды
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Расшифровка результатов тестирования
Accepted - тест пройден
Wrong answer - неверный ответ
Presentation error - ответ не соответствует формату выходных данных
Time limit exceeded - превышен лимит времени выполнения
Memory limit exceeded - превышен лимит использования памяти
Runtime error - ошибка времени выполнения, ваша программа завершилась с ненулевым кодом возврата
Задача 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
настроение: Никакое
Добро пожаловать в мини-чемпионат по программированию!
Решениями задач являются исходные тексты программ на одном из следующих языков программирования:
- Borland Pascal 7.0 (PAS)
- Borland C/C++ 3.1 (C, CPP)
- Borland Delphi 7 (DPR)
- Microsoft Visual Studio .NET 2003 C++ (CXX)
- Java - J2SE 1.5 (JAVA)
Обсуждение правил проходит в этой теме
[ ещё! → ]
настроение: Боевое
План
3 апреля - начало мини-чемпионата по программированию для наших читателей
5 апреля - отъезд делегации СГУ из Саратова в Москву
6 апреля - вылет вышеупомянутой делегации из Москвы в Сан-Антонио через Атланту
6 апреля, вечер по времени Сан-Антонио - мы в Сан-Антонио.
(далее в плане белое пятно, которое мы будем заполнять сообщениями с места событий)
9 апреля - регистрация команд-участников финальных соревнований
10 апреля - открытие соревнований, пробный тур
11 апреля - день Java Challenge
12 апреля - основной тур соревнований, награждение, закрытие
(ещё одно белое пятно)
16 апреля - вылет из Сан-Антонио
17 апреля - мы в Москве
18 апреля - подведение итогов мини-чемпионата мира по программированию для наших читателей.
настроение: Внимательное
Test-The-Best
В Минске же мои дела обстояли не лучшим образом. Скажу лишь, что я занял не последнее место :) На своем опыте я убедился, что занятое место на соревновании обратно пропорционально занятому месту при вечерней игре в боулинг. Наверное, это не случайно, и этому есть какое-то разумное объяснение.
настроение: Задумчивое
Дополнения к java challenge
Но вот на этом сайте можно скачать условие и окружение для стравливания машинок друг с другом.
настроение: Виноватое
Финал 2003-2004
Творилось там примерно следующее:
Но если вы думаете, что кроме самого финала, это единственное интересное что там ещё происходило - вы глубоко заблуждаетесь.
Тот финал 2003-2004 года в Беверли-Хиллз был ознаменован появлением шпионов. Да-да, вы не ослышались, именно шпионов.
Они - люди, которые никого не стеснясь, приехали воровать чужой код! Они просто подходили, вставали за спиной и высматривали
все исходники. От начала до конца. На просьбы отойти не реагировали.
Да, и ещё. Мелинда Пучер. Дочь директора финальных соревнований. Комментарии излишни. :)
Java Challenge
Вкратце правила таковы: участникам выдаётся интерфейс родительского класса, говорится, какие методы надо переопределить, и каковы условия выигрыша. После чего выделяется 2 часа времени на написание программы.
Условие формулируется так, чтобы классы реализовывали какой-нибудь искусственный (противоестественный) интеллект, и их в результате можно было стравить друг с другом. Дабы травля была веселее, организаторы заранее пишут обвязку - графическое представление и турнирную систему.
Мне довелось поучаствовать в этой забаве 1 раз, в 2003 году. В нужное время команду СГУ№3 сопроводили в зал, в котором на следующий день проведут основной тур, и изолировали от остальных членов нашей делегации на следующие 2 часа. В том числе и от меня - ведь я в тот раз был в качестве тренера.
Однако тренерам тоже дали повеселиться. В другом зале была объявлена свободная регистрация команд, и мы с пользователем ralekseenkov@mail.ru, взяв в команду ещё одну девушку из Белоруссии (или из Украины?) засели за компьютер, писать противоестественный интеллект для управления адским гоночным болидом.
Болид умел разгоняться, тормозить, поворачивать, ездить задним ходом. Кроме этого адская машина умела включать неуязвимость, стрелять запасными колёсами, и останавливаться, если у неё кончился керосин.
Так как организаторы собирались устроить гонки, на трассе были checkpointы, которые нужно было посещать по порядку и за которые давали очки. Очки также давали за удачный удар по вражеской машине, за удачное попадание колесом по вражеской машине. Самой вражеской машине от удара становилось плохо, и она теряла какое-то количество керосина.
От надругательств со стороны вражеских машин (а также от последствий своих ударов) спасал вовремя включённый режим неуязвимости, который был сделан очень правдоподобно - на крыше появлялась мигалка и включался спецсигнал. Однако, включённый спецсигнал приводил к удвоенному расходу керосина, и это нужно было учитывать при выборе стратегии поиска заправок, которые присутствовали на трассе.
Все вышеперечисленные апгрейды на машину привели к тому, что вместо мирной гонки получилось адское мочилово. Очевидно, что в данных правилах побеждает та машина, которая сможет продержаться на трассе как можно дольше. При этом ездить по чекпойнтам практически бессмысленно, посколько больше очков давали за банальную драку. В результате в тот противоестественный интеллект, который вымучали мы со Snailом, были заложены следующие гениальные тактические решения:
1. Если остаётся меньше чем полбака керосина - нужно немедленно ехать на ближайшую заправку (по возможности расталкивая все машины, кто не спрятался - я не виноват)
2. Если поблизости находятся враги - немедленно включаем неуязвимость и не выключаем, пока враги не уберутся подальше
3. Если больше заняться нечем - едем к следующему чекпойнту.
Эта поистине гениальная стратегия позволила в неофициальном зачёте машине по имени kg занять четвёртое место. Или третье? Чуть чуть не дотянули :)
А вот с Java Challenge нашей основной команды вышел жестокий облом. Просмотр боёв по классической формуле "хлеба и зрелищ" был совмещён с ужином, смертельные гонки проецировались на большие экраны в большом зале.
До середины мероприятия всё было хорошо, машина наших чемпионов уверенно лидировала, выживая в самых безнадёжных ситуациях, и всерьёз претендовала на
До тех пор, пока по неизвестной причине организаторы не решили перезапустить чемпионат заново.
Во втором прогоне, результаты которого и пошли в зачёт, машину как будто подменили. Совпадение, скажете вы.
Спонсором боёв без правил в тот раз, как и всегда, выступила компания IBM...
настроение: Грустное
Вид спереди
Команда СГУ №2 готовится всех
Обратите внимание на надпись на доске и время.
Стена
настроение: С чувством выполненного долга
Водка - лучший подарок
Человеку, который живёт в Америке, а о городе Саратове знает то, что это "рядом со Сталинградом" (с).
В 2003 году мы поехали на такой же финал чемпионата мира. Поехали с другой командой. Финал проходил в гостинице Merv's Beverly Hilton (это в беверли-хиллз, в трёх кварталах от дома Алиссы Милано) в то же время, что и церемония награждения Оскарами. Мы даже сумели поймать в фойе отеля Шона Коннери и вынудили его расписаться на наших бумажках.
В тот раз я умудрился провезти с собой в багаже две огромные бутылки водки. Это удивительно, что с ними ничего не случилось - железную кружку, ехавшую в том же багаже, аэрофлот сплющил в овал.
Одну бутылку я вручил моему другу, гражданину России, уже не первый год живущему на чужбине. А вторую - торжественно, в присутствии всей нашей делегации подарил директору соревнований, профессору Бэйлорского университета Биллу Пучеру.
Так была создана традиция. В прошлом году на Ottawa Linux Symposium в качестве подарков тоже была использована водка "Русский Стандарт", правда, несколько меньшего объёма. Получатели подарков окрестили ЭТО "Stingray's firewater" и расправлялись с ней на протяжении всей конференции.
Но я до сих пор не знаю - хорошо ли пошла та, самая первая?
настроение: Пьяное
Четырёхколёсные проблемы
Как вам идея - арендовать в Сан-Антонио машину и прокатиться к морю?
Аренда машины в США - обычное мероприятие. Типичное путешествие на дальнее расстояние состоит из авиаперелёта и арендованной машины, которая ждёт тебя в аэропорту. Люди говорят, что цена аренды машины - около 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.
Так что, видимо, нам ничего в этой конторе не светит. Очень жаль :)
В целом, я изложил очень пессимистичный взгляд на вещи человека, который ни разу в америке машину не арендовал. Может быть, нам не повезёт и у нас получится взять машину и покататься по незнакомым дорогам, с незнакомыми знаками и правилами (а также дорожной полицией) :)
Одно я знаю точно - я сам за руль не сяду!
Мне ещё задачи проверять.
настроение: Задумчивое
Чтобы их читать, Вам нужно вступить в группу
