Being in America

В 1-й квалификации RCC участвуют !2000 сабмитов. Решивших хотя бы одну задачу уже >600. #rcc12 #mailru

Хотя бы одну задачу Russian Code Cup сдали 553 человека (за 51 минуту турнира). Уже есть решение четырех задач от Епифанова Владислава. Принимают участие не меньше полутра тысяч человек.

Задача №3, тоже посложнее, «Война». Решена правильно Капуном Евгением на 16-й минуте.

«На одну маленькую нефтеносную страну было совершено нападение высокотехнологичной армии другой враждебной страны. Для защиты была мобилизована армия, состоящая из n солдат. Перед началом решающего боя все n солдат выстроились в шеренгу перед генералом. Он всегда считал, что все солдаты в его войске одинакового роста, однако это оказалось не так. Генерал понял, что такая армия малоэффективна, и решил разбить ее на подразделения. Под подразделениями генерал подразумевал непустые группы солдат, стоящих друг за другом в шеренге. Также генерал решил ввести понятие “мощность подразделения”, которое определялось как:

* количество солдат в подразделении, если в шеренге они стоят в порядке невозрастания или неубывания их роста;

* 0 в противном случае.

Также генерал решил, что мощность армии равна произведению мощностей всех подразделений.

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

Первая строка содержит целое число n (1 ≤ n ≤ 50000)— количество солдат. В следующей строке содержится n целых чисел ai (0 ≤ ai ≤ 109) — рост i-го солдата.

В первой строке выведете число k — количество подразделений, на которое генералу следует раздить шеренгу. Во второй строке следует вывести k чисел bi — номер в шеренге самого правого солдата в i-м подразделении. Числа надо вывести в порядке возрастания. Если существует несколько разбиений, то можно вывести любое разбиение.

Например, при следующих входных данных

5

1 2 3 5 4

нужно выводить

2

3 5

»

Задача №2, посложнее: «Перестройка». Первое правильное решение засабмичена Максимом Ивановым на 18-й минуте раунда. Вот она:

«В некоторой стране было ровно n городов и m дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:

* между любыми двумя городами не больше одной дороги;

* никакая дорога не соединяет город с самим собой.

После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:

* разрушить одну из существующих дорог;

* построить новую дорогу, которой раньше не было, не ведущую из города в

него же.

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

Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000). Следующие m строк содержат два числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — номера городов, которые соединяет i-я дорога.

Выведите одно целое число — количество способов провести реформу.

Например, при следующих входных данных

4 4

1 2

2 3

1 3

3 4

должно выводиться

8

»

Задача №1 из Russian Code Cup. Первое правильное решение сдано за 2:08 с момента открытия задачи на сайте.

«Вопреки известной поговорке «спички детям не игрушка», один мальчик очень любит играть со спичками. Но он не балуется ими, не разжигает огонь, а решает различные головоломки. Например, он умеет приравнивать число девять к числу одиннадцать, переложив только одну спичку.

Недавно родители этого мальчика подарили ему несколько наборов, каждый из которых состоит из двенадцати спичек. Мальчик начал собирать из них различные геометрические фигуры. Он уже собрал много различных фигур, но теперь ему стало интересно: из каких наборов возможно склеить каркас параллелепипеда при помощи двенадцати спичек из набора и клея? Ломать спички нельзя и ни одна из спичек не должна выступать за каркас.

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

Входные данные содержат не более тысячи строк, каждая из которых содержит в себе описание набора спичек — двенадцать целых положительных чисел не превышающих 109. Ввод заканчивается строкой, состоящей из двенадцати нулей, — этот запрос обрабатывать не нужно.

Для каждого набора спичек выведите «yes», если из него возможно склеить каркас параллелепипеда, и «no» в обратном случае.

К примеру, при входных данных

1 1 1 1 2 2 2 2 3 3 3 3

1 1 1 1 2 2 2 2 3 3 3 4

0 0 0 0 0 0 0 0 0 0 0 0

вывод должен быть такой:

yes

no

»

Уже полчаса идет олимпиада по программированию RussianCodeCup 2012. За первые полчаса пришло 462 сданных решения, первую задачу сделал первым Егор Куликов за 2:08, третью задачу сделал первым Капун Евгений на 16-й минуте, на 18-й минуте пришла вторая задача от Максима Иванова.

Появится пара часов свободных. Сегодня бы сумку куда-нибудь бросить на несколько часов, чтобы плечо не отдавила. В Питере реально найти в центре какое-то подобие камеры хранения?

Интересно, это они специально в фейсбуке кнопку Share в своем мобильном клиенте не делают? Это ж core feature для соцети, типа их же лайка (он есть). Походу не разобрался, как видеть все посты, которые я лайкнул. Такого списка нет в интерфейсе?

Старбакс есть везде, кро Питера. Интересно, почему так.

IVR – зло. Я готов звонить в саппорт за деньги, а не бесплатно, но чтобы сразу брал трубку человек. Дайте мне такой номер! А фиг, роботы промурыжили меня 2 минуты 30 секунд, заставляя дослуживать до конца и нажимать всякие нелогичные цифры (типа 8 для оператора) пока не заиграла музыка, теперь же, между музыкой мне сообщают, что “сотрудник ответит через 10 минут”. Мне 5% батареи более жалко в аэропорту вылета терять. Пока пишу это сообщение, 10 минут не уменьшились….