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

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

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

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

Роман, скорее всего алгоритм, т.к. нужно вычислить на каком-нибудь высокоуровневом языке (желательно 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, тут интересный момент.

в примере что вы дали, также округляют слева в большую сторону :
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.
На мой взгляд в этой задаче право-лево это всего лишь условность и роли не играют. Но если всеже принципиально, то просто поменяйте в коде округление.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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