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)).
Какое-то у меня совсем другое решение Б:
Всё правильно). Собственно говоря, если следовать инструкциям из разбора, это и получится.
Ответ будет конечно такой же, но в разборе предлагают проэмулировать игру дважды. Итого O(2*N) вместо O(1)
Просто написать эмуляцию за пару минут обычно проще, чем придумывать формулы.
Там придумывать нечего. Достаточно не полениться, взять бумагу и ручку, увидеть закономерность и вывести формулу станет очень легко.
n+m-x-1=max(n,m)-1;
Sorry
Can you check my solution for problem C? http://codeforces.com/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 =/
Вопрос по задаче D: Тест из условия: 3 3 3 5. Мы выберем i = 1. Тогда после первой итерации у нас получится 0 5. Из пары чисел "0" и "5" число <= 3 получить не выйдет. Что с этим делать?
Да, вы правы, неувязочка получается.
В принципе, сворачивать описанным образом последовательность можно, но ,очевидно, нужно начинать с конца и идти последовательно, а не брать любую пару, как сказано в разборе.
А я делал жадно. Завел две переменных. Далее проходил с конца циклом и брал a[i] и прибавлял к меньшей переменной. А дальше все что прибавилось к однму числу — с одной сторны разности, что к второму со второй. Если слогаемое в разности меньше второго и сумма отрицательна, то менял местами. Не очень уверен в минимальной разности данного разбиения и вообще, что оно решает задачу. То есть еще над чем подумать.
Так можно довольно просто разбить множество чисел на сколько угодно групп примерно равных по размеру.
У меня так на работе распределяется нагрузка на сервера. Там есть m бирж и в каждой i-ой по a[i] символов(котировок). Далее нужно на заданое число серверов разбить эти биржи, что бы примерно уравнять нагрузку.
Простите, что-то я загнался. Конечно, надо брать два максимальных числа
The problem B, the answer is
max(red, blue)-1
andmin(red,blue)
. How to prove it? thx !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.
Зацените извращение, которое я написал по разбору 2900370. Комментарии для вас. Пожалуй, самая сложная моя реализационная задача. Критика приветствуется!
Да не извращение, у всех примерно то же самое.
Ты, видно, не решал заочку olympiads.ru :)
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?