257A - Sockets
Очевидно, что выгоднее использовать сетевые фильтры с наибольшим количеством розеток на них. Поэтому сначала отсортируем их по убыванию этой величины. Теперь переберем ответ, то есть, сколько фильтров мы будем использовать, пусть это значение равно p, а фильтры имеют a1, a2, ..., ap розеток. Очевидно, что если соединить эти фильтры, то итого будет доступно k - p + a1 + a2 + ... + ap розеток. Это значение надо сравнить с m и выбрать минимальное подходящее p. Если ни одно значение p не подходит, то следует вывести - 1.
257B - Playing Cubes
Для начала переберем цвет первого кубика, который поставит Петя. Вася следующим ходом захочет поставить кубик противоположного цвета, затем Петя захочет поставить кубик такого же цвета, как и поставленный Васей и т.д. Так мы можем проэмулировать всю последовательность ходов обоих мальчиков и найти их счет.
Единственное, что может изменить Петя в игре – это цвет первого кубика, и он его поставит так, чтобы его счет был как можно больше.
257C - View Angle
Сначала давайте избавимся от координат точек, а именно, заменим все точки лучами от (0, 0) до каждой из точек.
Тогда очевидно, что искомые стороны угла – это пара соседних лучей, причем из двух углов, образованных выбранными лучами, надо выбрать тот, который покрывает все остальные лучи. Получается, что выгоднее всего выбрать такую пару соседних лучей, между которыми наибольший угол, пусть он равен a, и вывести величину 360 - a (в градусах).
Отдельный случай — когда все точки лежат на одном луче, в этом случае ответ равен 0.
257D - Sum
У нас есть последовательность переменных a1, a2, …, an. Возьмем две переменные с максимальными значениеми (допустим, i и i + 1), удалим их и вставим в последовательность новую переменную x = ai + 1 - ai так, чтобы сохранилось свойство неубывания последовательности. Так будем делать до тех пор, пока не останется единственное число s, которое и будет искомой суммой. Очевидно, что если мы будем разворачивать последовательность замен с учетом знаков, то в итоге узнаем, какой знак стоит у каждой из начальных переменных так, чтобы их сумма была равна s.
Теперь осталось понять, почему число s подходит под ограничения 0 ≤ s ≤ a1. Очевидно, что оно не может быть отрицательным, так как при всех заменах мы из большего числа вычитаем меньшее. Также несложно понять, что при всех заменах минимальное число в последовательности не может увеличиваться, значит, оно до последней замены будет максимум a1. Аналогично, второе число в последовательности также не может перед последним шагом быть больше a2 и так далее. Несложно понять, что при последней замене мы получим s ≤ a2 - a1 ≤ a1.
257E - Greedy Elevator
Эта задача решается классическим методом – событиями во времени. Событиями являются: «человек встал в очередь к лифту», «человек вошел в лифт», «человек вышел из лифта».
Будем поддерживать множество будущих событий, текущее время T и текущее положение лифта x.
В каждый момент времени будем выполнять следующие действия:
- если есть люди, которые в текущее время T пришли к лифту, то поставим их в очередь на их стартовом этаже;
- если на текущем этаже есть люди, то посадим их в лифт, таким образом очередь на этом этаже опустеет;
- если в лифте есть люди, которые должны выйти на текущем этаже, то высадим их и запомним для них ответ – текущее время T;
- найдем количество людей, которые ждут выше этажа x или которые едут выше, а также найдем количество людей, которые ждут ниже этажа x или едут ниже, и согласно условию выберем направление движения.
Однако если мы на каждой итерации будем увеличивать текущее время T лишь на единицу, то решение будет работать слишком долго. Надо научиться переходить сразу к следующему моменту времени, когда появится какое-либо новое событие, и лифт передвигать сразу на несколько этажей вверх или вниз. Очевидно, что между событиями направление движения лифта не меняется.
Понятно, что нам достаточно посмотреть на следующий момент времени, когда придет какой-либо человек и встанет в очередь на этаже, а кроме того найти следующий этаж по направлению движения, на котором кто-либо выйдет или зайдет.
Это можно сделать с помощью структуры «множество» с операциями «найти следующее число в множестве после данного» и «найти предыдущее число в множестве перед данным». Это умеет стандартные структуры set в С++ или TreeSet в Java.
Также для действия номер 4 нам понадобятся две структуры данных, которые умеют находить сумму чисел на определенном отрезке в массиве, для этого можно использовать, например, деревья отрезков или деревья Фенвика. Одна из структур хранит, сколько людей ждут лифта на каждом из этажей, а вторая – сколько людей в лифте хочет выйти на каждом из этажей. В принципе, эти две структуры можно объединить в одну.
Таким образом, для каждого из людей мы будем обрабатывать ровно по три события, и итоговое время решения будет равно O(n·log(n)).
Can you check my solution for problem C? http://codeforces.net/contest/257/submission/2892972 I have wa6, but don't understand whats wrong. Thanks a lot.
n should be long integer
I don't think so =/
Hi, the answer of problem B is
max(red,blue)-1
andmin(red,blue)
, how to prove it ? thx !petya first turn is only wasted, in all the later turns both will keep on taking points but when any one of the color dice is over , vasya cannot win points anymore. Indeed later every turn will give points to petya, since there is only single color dice. NOTE: only first dice is wasted
I think this is wrong as it fails on the test
2 3
The final sequence looks like this:
RBBRB
so answer should be1 3
whereas by your algo answer would be2 2
No, the final sequence looks like
BRRBB
and the answer is indeed2 2
English , please...
In fact, you can translate the whole page into English by using http://translate.google.com
google translate: "We have a series of variables a1, a2, ..., an. Take two variables with the highest znacheniemi (say, i and i + 1)..."
znacheniemi?
It means "values" but the original word is written incorrectly in Russian.
P.S. The first time I see when illiteracy can really make harm.
257C - View Angle Can somebody tell me, how will I know, is this ray neighbor with something else?
sort by angle
I understood how decide this problem, but how will I know, is this ray neighbor with something else? Maybe between first and second rays will be others rays? So, this picture. 'alpha'- is the biggest angle, but it's wrong answer.
You should check all pairs of neigbors and choosethe best one.
I understood, that you said, but how i must check it, that be sure, that between this two rays i haven't others, as at the picture the rays between l1 and l2?
If ray A between B and C, then B and C aren't neighbors?
Yeah, if we have the other rays, that is neighbors with C and B. Maybe i just must to search the least angle for all rays, then pick the biggest from these. Is it correct?