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

Question

[Alex Gutter]

Здравствуйте. Прошу помочь с решением учебной задачи, т.к. не очень понимаю суть задачи и поэтому не знаю с чего начать.
Задача следующая:
Жуки не любят находиться рядом друг с другом и каждый прячется под отдельным камнем и старается выбирать камни, максимально удаленные от соседей. Так же жуки любят находится максимально далеко от края. Как только жук сел за камень, он более не перемещается. Всего в линии лежат X камней. И туда последовательно бежит прятаться Y жуков. Найти сколько свободных камней будет слева и справа от последнего жука. X может быть до 4 млрд.

Примеры:
X=8, Y=1 – ответ 3,4
X=8, Y=2 – ответ 1,2
X=8, Y=3 – ответ 1,1

Answer 1

[Роман]

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

Comments

[Alex Gutter]

Извините, не силен во фракталах. Вот эта методология подойдет?

[Роман]

Alex Gutter, я наверно все таки толкнул вас не в том направлении, несмотря на то, что задача имеет схожесть с фракталами, в силу условия она дискретна и имеет сугубо целочисленный характер, поэтому при увеличении Y ошибка будет пропорционально возрастать (в случае если свободное пространство имеет четное количество позиций жук будет занимать позицию близкую к середине но округленную до целого, и с каждым новым шагом эти ошибки будут накладываться)
Отсюда следует, что рассчитать через фракталы можно лишь приблизительную (оценочную) величину.
С другой стороны о моей неправоте говорит сам характер задачи (если я правильно понял тэг АЛГОРИТМЫ).

Я так понимаю решение должно быть алгоритмическим (некий алгоритм и программа его реализующая) ?

[Alex Gutter]

Роман, скорее всего алгоритм, т.к. нужно вычислить на каком-нибудь высокоуровневом языке (желательно python, js или php )
Вот вроде как решение на javа, но я в этом япе совсем никак

public static void Main()
 {
 var list = new LinkedList();
 list.AddLast(long.Parse(Console.ReadLine()));
 var y = long.Parse(Console.ReadLine());
 LinkedListNode lastAfter = null;
 for (long i = 0; i < y; ++i)
 {
 var first = list.First;
 var left = (first.Value >> 1) + (first.Value & 1);
 var right = first.Value - left--;
 list.Remove(first);
 var last = list.Last;
 lastAfter = last != null && right > last.Value? list.AddAfter(lastAfter, right) : list.AddLast(right);
 list.AddLast(left);
 }
 Console.WriteLine(string.Format("{0} {1}", list.Last.Value, lastAfter.Value));
 Console.ReadKey();
 }

[Роман]

Сейчас попробую описать ход мыслей:

1. если пойти в лоб, то делаем массив размером Х и заполняем его жуками.
2. не учитываем многовариантность о которой говорил Rsa97 , считая задачу симметричной и соответственно решения (3,4) и (4,3) равнозначными. То есть заполнять будем от середины (условия максимального удаления от края)
3. таким образом на каждом шаге (жуке) сканируем массив в поиске свободных зон. сканирование начинаем от центра, и выбираем зону, в которой до жуков и краев максимальное расстояние.
4 расставив всех жуков находим расстояния слева и справа от последнего.

Данное решение однозначно не то что нам надо, громоздкое, при огромных значения Х и Y работать будет очень долго, памяти жрать много. Улучшаем:
5. по сути на каждом шаге расстояние делится примерно пополам. при этом имеется закономерность, количество жуков, необходимое для уменьшения всех свободных участков в 2 раза на каждом шаге будет удваиваться. Это позволит вообще не создавать массив камней а подойти к решению аналитически.
6. пробуем составить алгорим:
6.1 вычисляем количество жуков, необходимых для сокращения пространства в 2 раза (на первом шаге 1, на втором 2 на третьем 4 и т.д)
6.2 вычисляем количество шагов, для которых хватает жуков )
6.3 определяем размерность оставшегося после этих шагов пространства (тут необходимо немного подумать, так как есть нюансы)
6.4 оставшееся пространство делим пополам, округляем и получаем значения справа и слева.

Сейчас попробую все это реализовать на js

[Роман]

Alex Gutter, ну вот, вроде готово:)))

[Роман]

Alex Gutter, посмотрел решение что вы дали, используемый в нем подход по сути идентичен тому, к которому пришел я. Отличается лишь в мелких деталях и синтаксических особенностях языка )))

Так что считаем что подход уже опробирован и утвержден, а значит и решение верное ))))

PS: немного пояснений.
от 6.1-6.2 отказался, теперь алгоритм выглядит так:
1. создаем массив, в котором будем хранить размеры свободных от жуков областей камней (изначально в массиве всего 1 запись равная начальному количеству камней.
2. для каждого жука делаем:
2.1 вынимаем из массива первую ячейку (она будет самым большим куском)
2.2 отнимаем от ее размера 1 (это жук занял 1 камень)
2.3 делим ее пополам, при этом если пополам не делится, то левую часть будем считать большей а правую меньшей (например 7/5 = 3.5, тоесть левая=4 а правая=3)
2.4 вставляем в конец массива обе части, при этом потенциально большую (левую) вставляем в первую очередь а потенциально меньшую (правую) во вторую. Это даст нам то, что в первой ячейке массива всегда будет самая большая часть из имеющихся
2.5 если еще есть жуки возвращаемся на 2.1
3. дойдя до сюда, получаем ответ (лево и право вычисленные для последнего жука :)

[Alex Gutter]

Роман, спасибо, все понятно. Только, судя по примеру, левую часть округляем в меньшую сторону, соответственно правую в большую.

[Роман]

Alex Gutter, тут интересный момент.

в примере что вы дали, также округляют слева в большую сторону :
var left = (first.Value >> 1) + (first.Value & 1);

данная операция (побитовый сдвиг вправо) эквивалентна делению на 2 с округлением в меньшую сторону:
first.Value >> 1

а эта всегда на выходе даст 1 если число нечетное или 0 если четное
(first.Value & 1)

то есть если число было например 7 то первая часть даст 3 а вторая 1, в результате левая сторона будет 3+1 = 4

правая же вычисляется как само число - левая
var right = first.Value - left--;

отличие лишь в том, что в вашем примере когда берут число свободных посадочных мест не забирают одно под жука. У вас просто уменьшают лево на 1 left-- при вычислении право.

При таком подходе действительно получается с точностью донаоборот, лево-меньшая часть, право большая. Вопрос тут лишь в том насколько принципиально получить при X=8, Y=1 – ответ 3,4 а не 4,3.
На мой взгляд в этой задаче право-лево это всего лишь условность и роли не играют. Но если всеже принципиально, то просто поменяйте в коде округление.

[Alex Gutter]

Роман, согласен, что право-лево не существенный момент в данном случае, а в коде так и сделал:

part1 = Math.floor(place/2);
part2 = Math.ceil(place/2);

[Роман]

Alex Gutter, Пусть так и будет.

Есть еще 1 момент. Что в моем что в Вашем варианте, каждый последующий жук увеличивает колличество элементов массива, содержащего свободные участки пространства на единицу. В случае с 4 милиардами жуков js однозначно загнется (начинает тупить на массивах, с количеством элементов больше 1000000), а вот вытянет или нет java не скажу.

[Alex Gutter]

Роман, ну я начинающий. Так что для меня за счастье хотя бы какое-то решение получить. До оптимизации кода мне еще далеко, т.к. я даже не оптимальное решение фактически на халяву от вас получил, за что еще раз спасибо =) Немного грустно, что сам не могу такие вещи решать даже в общем виде, видимо нужно что-то почитать / посмотреть.

[Роман]

Alex Gutter, мне бабушка с детства подсовывала книги типа Математическая смекалка. Б.А. Кордемского и они мне очень нравились, я часами и днями мог сидеть, и разгадывать эти задачки. Когда в школе началась геометрия, я на первом же уроке, достал учителя на столько что был вызван к доске со словами "раз такой умный - докажи теорему". Доказал 3-я способами) Далее по жизни все что касается математики, геометрии, инженерной графики в институте, логики и программирования шло как помаслу, ввергая учителей и преподавателей в шок. Я это говорю не для того, чтобы похвастаться, просто уверен, что проведя в раннем детстве много времени за решением математических, геометрических задачек и задачь на смекалку выработал в голове умения видеть пути решения. Я абсолютно не представляю, сколько сил и времени надо потратить взрослому человеку, чтобы добиться такого же эффекта, но думаю, что в разы если не на порядки большего, чем ребенку. Поэтому пожелаю Вам удачи, и посоветую не распылятся на много разных областей.

[Alex Gutter]

Роман, я еще с дошкольного детства любил решать математические задачи, мне в школе очень легко давалась алгебра, все решал и сидел скучал ждал, когда решит остальной класс. Потом даже учительница дополнительно давала индивидуальные задания, а от экзамена освобождала. А вот с геометрией не очень почему-то было. В итоге отучился на экономиста, до красного диплома пару пятерок не хватило (но я не ставил себе это целью). Сейчас увлекся программированием, активно самообучаюсь, но к сожалению в ученики / стажеры никто не берет (видимо в силу возраста), довольствуюсь тем что есть такие как вы и Тостер =)

[Роман]

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

[Alex Gutter]

Роман, отправил ваш вариант решения на проверку, и вот что прислал проверяющий

задача решена с ошибкой. Х=9, Y=5, правильный ответ 1,0, программа выдает 0,0.

[Роман]

Alex Gutter, сейчас посмотрю

[Роман]

Alex Gutter, да, действительно есть хитрая неточность. сейчас попробую исправить

[Роман]

Alex Gutter, есть проблема, не могу понять почему должно получится 1,0, если делаю вручную (с учетом того что правая часть больше) то должно получатся 0,1.

Исправленный скрипт тоже дает 0,1

[Alex Gutter]

Роман, если не секрет, сколько лет занимаетесь разработкой? Спрашиваю для того, чтобы оценить на сколько адекватны работодатели, когда дают такие тестовые задания новичкам =)

[Роман]

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

[Роман]

задание вполне адекватное, я бы даже сказал, что оно проще чем уровень олимпиадных задачь, но есть пара подковырок за которые я и зацепился:))

[Роман]

Alex Gutter, вы напишите Ваше мнение, почему при Х=9, Y=5, правильный ответ 1,0 а не 0,1. Сам я что то не догоняю, и единственное что приходит на ум, это то что жуки более приоритетны чем края при выборе места, но это уже мои домыслы))))

[Роман]

Alex Gutter, для проверки воспроизвел на JS ваш вариант кода, но результат тот же - 0,1

[Alex Gutter]

Роман, как будет время попробую разобраться

[Роман]

Alex Gutter, не отправляли исправленное решение? Что на него ответили, правильное/неправильное?

[Alex Gutter]

Роман, нет не отправлял

Answer 2

[Rsa97]

Вообще, в таком виде задача может не иметь однозначного решения.
Первый же пример X=8, Y=1 даёт два решения - (3,4) и (4,3).

Comments

[Alex Gutter]

Не уверен, но вы вроде как не правы на счет 4-го жука. Для него все варианты будут (1,1).

[Rsa97]

Alex Gutter, Угу, я невнимательно прочитал условие задачи и смотрел интервалы слева и справа от всех жуков. Убрал этот вариант.
Но и в таком случае будут случаи с двумя ответами.

[Alex Gutter]

Rsa97, да тут согласен.

Answer 3

[EVGENY T.]

Тут конечно есть аж три подхода:

1. Смоделировать ситуацию рассаживания жуков, хотя замечание о 4 млрд намекает, что от нас ждут не этого. А если завтра их будет 4 триллиона?

2. Можно заметить, что расстояние например левого жука (при рассадке слева направо) от края отрезка длиной X в зависимости от числа жуков представляет собой ряд: L(1) = X/2, L(2) = X/4, L(3) = X/4, L(4) = X/8, L(5) = X/8, L(6) = X/8, L(7) = X/8... и т.д. Осталось сообразить, что же это за формула тут прячется. Степень двойки? Треугольник Паскаля? Теплеет. Ах зачем программисту высшее образование? Не, не нужно!

3. Про фракталы верно, это в терминах вычислений значит рекурсия. Алгоритм может выйти изящным, но скопытится от полчища жуков быстрее, чем вариант 1.

Comments

[Роман]

EVGENY T., после того как вчера написал свой вариант увидел что автор выложил вариант на java. Был очень удивлен, потому что два разных человека независимо друг от друга и ЯП, в терминах которых привыкли мыслить выбрали абсолютно идентичные подходы к решению задачи. Такое на практике бывает достаточно редко. Поэтому возникла мысль, что задача сама подталкивает к такому решению, и скорее всего именно это решение и желали увидеть авторы задачи. По сути данное решение должно производить неявную сортировку массива, за счет использования его как стэка FIFO. Это вполне укладывается в тип задач, цель которых- развивать алгоритмическое решение. Таким образом, чтобы понять, какого подхода к ее решению от нас ждут, надо только выяснить, эта задача дана автору как алгоритмическая или как математическая.