@lena 11

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

0

@mporro

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

0

@pycture

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

0

@mporro

pycture, Вы не умеете читать условия.

Составить алгоритм для равномерного расползания муравьёв -- это некоторая общая задача.
Но есть ограничения. Муравьи могут анализировать только соседние клетки. Муравьям не нравится толчея и не нравится переползать через верёвку.

Если условие про верёвку выкинуть, то завершаемый алгоритм не удастся построить. Так как один единственный муравей будет бесконечно прыгать по пустой плоскости.

Добавлено через 3 минуты
P.S. Если же Вам просто хочется "потроллить", то можете притвориться, что не поняли задание даже после объяснения.

0

@pycture

какие условия, такое и понимание. как грится адекватно сформулированная задача это половина ответа. граммотно сформулированное и непротиворечивое условие не требует никакого "объяснения" вернемся к веревке. она делит поверхность на 21 прямоугольник в один ряд. в левый прямоугольник высыпаем 3-х муравьев. они смогут равномерно разместиться в этом ряду из 21-го прямоугольника? не смогут, а значит условие "максимально равномерно распределиться по поверхности" не выполнимо хоть с вревкой хоть без нее.

0

@mporro

pycture, Это не задача научного характера, которую Вы сами поставили и потом решили. Это не задача от технического писателя, который сформулировал для вас чёткую схему вариантов использования ПО.

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

Что касается линии из большого числа прямоугольников и малого количества муравьёв, то можно указать формальное условие неразличимости прямоугольников с числом муравьёв, отличающимся на единицу.

0

@pycture

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

0

@_Ivana

Если позволите позанудствовать, то не будет. И веревка никакая не нужна. Если, допустим, логика будет - отправлять в соседнюю клетку целую часть от половины разницы количеств.

0

@Mr.X

Понятие "максимально равномерно" в условии не определено. Значит настолько равномерно, насколько позволит решение. У кого равномернее, тот и победил.

0

@mporro

_Ivana, если "позанудствовать", то не получится удовлетворить условию о "тесноте". Предположим, что муравьи видят, что в соседней клетке меньше муравьёв, чем в их собственной. Тогда они точно видят, что в соседней клетке "свободнее", и хотят отправить туда муравья. =)

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

0

@_Ivana

mporro, еще 2 раза перечитал условие, и не обнаружил в нем требования обязательно отправлять муравья в клетку, где количество меньше. По-моему это как раз ваше выдуманное требование. Именно что Вот они оценивают и не отправляют.

0

@mporro

_Ivana, может быть это и вправду моё предвзятое мнение.

В задачах параболического типа, чтобы ограничить область "прогревания" как раз вводят минимальную эффективную порцию и затем решают клеточным автоматом. Соединяя вместе как раз получается: верёвка -- барьер, не нравится толчея -- градиентный перенос.

Наиболее разумное мнение, конечно, высказал Mr.X. Нужно предъявить некий алгоритм и доказать завершаемость. У кого меньше вариация -- тот и молодец.

0

@Igor3D

А почему в 4, 11 и 18? Чем это "равномернее" чем, скажем, 1, 10 и 21? Равномерность можно измерить отношением кол-ва мин заполненной к макс заполненной. Если клеток больше чем муравьев, она всегда = 0

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

0

@_Ivana

Понимаете, при бесконечной делимости муравьев задачка достаточно тривиальна, и вы правильно заметили, что , я на паяльниках проверял. Но с целыми муравьями задача не имеет решения в заданной постановке. Моооожет быть в отдельных случаях она имеет решение, если в каждом квадрате лежит бумажка с историей - сколько на каком шаге из этого квадрата куда отправлялось и сколько откуда приходило, и муравьи могут ее читать - но тогда задачка перестает быть томной А простейшие алгоритмы, которые видны невооруженным взглядом (и ваш в том числе), не осилят не только пример pycture, но и линию
2 1 1 1 0 или
5 4 3 2 1 0 0 0

0

@pycture

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

0

@Igor3D

Это легко проверить. Возьмем первую ячейку. Сумма 2+1 = 3 на 2 ячейки, среднее 1.5 ("полтора землекопа" в старом мультике). Но расчленять муравьев никто не хотел, поэтому берем просто целую часть 1. Имеем 2, значит одного бойца посылаем в правую ячейку. Так что осилит, а Вы глаз-то вооружайте

Продолжим эти рассуждения: есть аж ОДИН муравей на 100 клеток. Ну как же его "равномерно" распределить? Как видите, мы быстро пришли к полному абсурду

Чему посвящены 2 листа постов? В основном - упорному доказательству того что "задача нерешаема". Зачем? Если "даже вопрсов не было б" - то почему бы сначала не предложить решение, а потом уж, если так интересно, ковыряться в частном случае (о котором никто не спрашивал)

0

@pycture

очевидно что посередине (+- клетка не имеет значения). т.е. равно удаленно от границ. никакого абсурда не наблюдается и зачем предлагать решение для задачи которую никто не спрашивал? никому не требуется равномерное размещение по кол-ву. в задаче другое условие. если ктото хочет решать другую задачу чем в условии, никто не запрещает, но выдавать это за решение исходной задачи ни есть правильно

0

@Mr.X

Условие задачи неопределенное, а такая задача определенного решения в принципе иметь не может. Типичное олимпиадное мозгозасир@тельство.

0

@mporro

Mr.X, всё уже было всем объяснено и разжёвано. Просто pycture упорно продолжает троллить условие. И про намёки в условии говорили, и на олимпиадный характер указывали. Кто хотел, тот разобрался, кто не хочет -- тот не хочет.

0

@Igor3D

А может это называется "симметрично"? Впрочем уже давно толчем воду в ступе, позвольте Вам больше не отвечать.

Напротив, прекрасная задачка. Цель не "определенное решение", требуется "разработать локальную стратегию" (как ни помпезно звучит). В жизни это встречается часто, напр когда "клетки" (или их аналоги) надо обсчитывать параллельно. И приходится смириться с неточностью/не-аналитичностью решения т.к. оно должно быть локально. Преодолеть этот барьер в сознании не так уж легко - как видно из обсуждения

0

@Mr.X

Да-да, вся "помпёздность" в том и состоит, что непонятно стратегию чего. Ребята уже мозги сломали. А так ничего задачка. Как там у Зощенко в его рассказе про крупу "Геркулес": есть можно, единственно только глотать нельзя.

0