Publish @IronPeter, @mehas: Задачки!

Вообще, обсуждать задачки уже очень традиционная тема разговоров программистов – всем надо и нанимать, и наниматься. Holy wars aside, мне кажется, эти вот на собеседованиях спрашивать не надо – слишком уж они на вдохновение, а не на технику.

Сегодня две – от @IronPeter и @mehas. Все публикуемые задачки без подвохов – решаются именно в данной формулировке, и у каждой решение известно и не бесконечно сложно.


Задачка 1:

Simon Kozlov: reply @Simon Kozlov
Да, пересказываю задачку.
IronPeter: @All
Вот, задача!
Есть комната, в ней стоит шахматная доска с расставленными на ней шашками.
В комнату заходит PM с программистом.
PM показывает рукой на одно из полей.
Программист может поставить новую шашку на любое поле, убрать с любого поля или ничего не делать.
Программист выходит из комнаты, PM остается.
Заходит второй программист, он должен назвать то же поле, что и PM
(изначально задача была про зеков и вертухая, но я переделал)

Alex Rat: reply @Simon Kozlov
шашки раставлены как попало?

Simon Kozlov: reply @Alex Rat
Да

Alex Rat: reply @Simon Kozlov
и в любых количествах?

Simon Kozlov: reply @Alex Rat
Да

Alex Rat: reply @Simon Kozlov
класс
ок, т.е. можно 1 шашку добавить или убрать, но не передвинуть:?

Simon Kozlov: reply @Alex Rat
Да

Kane: reply @Simon Kozlov
элементарно поставить перевернутую шашку на нужное поле? =)

Simon Kozlov: reply @Kane
Да, такое нельзя!

Alex Rat: reply @Simon Kozlov
шашки все одниго цвета или разного?

Simon Kozlov: reply @Alex Rat
Все одинаковые

Kane: reply @Simon Kozlov
тогда еще уточнение, шашки все стоят обычным способом, ставить тоже надо без извращений

Simon Kozlov: reply @Kane
Да, конечно

Kane: reply @Simon Kozlov
о, и еще никаких правил в расстановке нет (i.e. все на черных и т.д.?)

Simon Kozlov: reply @Kane
Никаких

Задачка 2:

mehas: reply @Simon Kozlov
Окей! Скажите если баян :)
Есть массив на N чисел a1 … an и число M
например, это показания температуры
M – это длина отрезка времени
хочется на каждом отрезке времени длиной M показаний посчитать их максимум

mehas: reply @mehas
пример
a = {1 2 3 2 3 1 }, M = 3
M = 2
ответ: 2 3 3 3 3
баян?
а, да, забыл самое главное
сложность давайте строго O(N)
не в среднем

_ShaMan_: reply @mehas
а почему M = 2, а ответ в 5 чисел? или отрезки оверлапятся?

mehas: reply @_ShaMan_
да, оверлапятся
т.е. нужен max a1..am, max a2..am+1 …

Simon Kozlov: reply @mehas
Раньше вроде не слышал. Буду думать!

Simon Kozlov: reply @mehas
И от M сложность зависеть не должна?
Кстати, ответы писать строго в привате!

mehas: reply @Simon Kozlov
ну, M = O(N)

mehas: reply @Simon Kozlov
в общем, не должна

Vasily Khudyakov: reply @mehas
а по памяти какие ограничения?

mehas: reply @Vasily Khudyakov
ну, раз времени требуется O(N), то и на память O(N) :)

Vasily Khudyakov: reply @mehas
одно не всегда связано с другим
может ты по памяти хотел O(1)

mehas: reply @Vasily Khudyakov
нет, я бы явно сказал

Решения.
Задача 1
Задача 2, у нее аж 3 решения

Это произошло на #programming

  • void

    В первой задаче надо поставить шашку так, чтобы сумма координат всех шашек по модулю восемь показывала на загаданное поле. Или не поставить.

  • http://www.microsoft.com CEMEH

    Сумма не работает – есть контрпример, когда не для всех возможных загаданных полей ты сможешь поставить/убрать фишку так, чтобы сумма давала нужное значение. Надо приводить или и так понятно?

  • bada

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