Давным давно в КВАНТЕ была вот какая задачка.

По маршруту едет автобус. На маршруте имеется 100 остановок, для нашего удобства они пронумерованы от 1 до 100. В автобусе 100 пассажиров, для нашего удобства они опять таки пронумерованы от 1 до 100. В принципе каждому из пассажиров надо сойти на остановке номер которой совпадает с его собственным номером.

Водитель, дабы ускорить движение, предложил следующий алгоритм. Ппри подъезде к каждой очередной остановке проводится голосование "останавливаться или ехать безостановочно". Решение принимается простым большинством голосов. Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей к нужной.

Вопрос — на каких остановках автобус будет останавливаться.

В принципе очевидны как минимум два варианта решений вытекающих из стратегий поведения пассажиров
1 все пассажиры тупы и не делают прогнозы
2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
задача достаточно логическая и наверное может быть "запрограммирована" даже в Excele

Здравствуйте, SanSoft, Вы писали:

SS>1 все пассажиры тупы и не делают прогнозы
Тогда они очевидно будут голосовать "против" до остановки со своим номером, а далее будут голосовать "за" до тех пор пока автобус не остановится. И тогда все голосовавшие за, сойдут и ситуация повторится, только остановок останется меньше.
Если считать, что при равенстве голосов принимается решение "остановиться", то очевидно остановки будут иметь номера 50,75,88,94,97,99,100.

SS>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
Ответ тот же

SS>1 все пассажиры тупы и не делают прогнозы

Автобус проедет маршрут без остановок.

SS>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать

Автобус проедет маршрут со всеми остановками.




А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.

Здравствуйте, Apostate, Вы писали:


SS>>1 все пассажиры тупы и не делают прогнозы

A>Автобус проедет маршрут без остановок.

Т.е. настолько тупы, что даже проехав свою остановку не желают выходить?

SS>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать

A>Автобус проедет маршрут со всеми остановками.

Ну как минимум на номере 98, автобус не остановится! Имеем 3 человека — 98,99 и 100 и автобус подьезжает к 98-й остановке. Скажите, какой смысл номерам 99 и 100 голосовать за остановку на 98-й? Об альтруизме в задаче разговора кажется не было.

A>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.

Это имхо лишнее. Достточно сказать, что каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке.

ну уж раз хочется уточнения — хорошо, хоть и не помню, было ли ли в КВАНТЕ такое уточнение
каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке
но по моему мнению такое уточнение излишне т.к. в условиях сказано "В принципе каждому из пассажиров надо сойти на остановке номер которой совпадает с его собственным номером." Таким образом каждый стремится сойти на своей остановке, но если не сошёл, то он не будет ехать до конца, а сойдёт как можно ближе.

Здравствуйте, SanSoft, Вы писали:

SS>но по моему мнению такое уточнение излишне
Это единственное из-за чего я заработал "-1"? Если нет, то хорошо бы увидить обьяснения?

Здравствуйте, SanSoft, Вы писали:

SS>ну уж раз хочется уточнения — хорошо, хоть и не помню, было ли ли в КВАНТЕ такое уточнение

А можно еще уточнение(я)?
1.Пассажиру до своей остановки разрешается выходить? — предполагаю да
2.Следует ли считать расстояния между остановками равными? — полагаю, что тоже да

Здравствуйте, SanSoft, Вы писали:

SS>1 все пассажиры тупы и не делают прогнозы
Так как сказал WeCom

Тогда они очевидно будут голосовать "против" до остановки со своим номером, а далее будут голосовать "за" до тех пор пока автобус не остановится. И тогда все голосовавшие за, сойдут и ситуация повторится, только остановок останется меньше.
Если считать, что при равенстве голосов принимается решение "остановиться", то очевидно остановки будут иметь номера 50,75,88,94,97,99,100.

SS>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
Тогда они будут понимать что с каждым вышедшем пассажиром их голос будет более весом,все они будут голосовать на каждой остановке

Здравствуйте, Octane, Вы писали:

SS>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
O>Тогда они будут понимать что с каждым вышедшем пассажиром их голос будет более весом,все они будут голосовать на каждой остановке

А как же ? :

Ну как минимум на номере 98, автобус не остановится! Имеем 3 человека — 98,99 и 100 и автобус подьезжает к 98-й остановке. Скажите, какой смысл номерам 99 и 100 голосовать за остановку на 98-й?

Порассуждаем еще.
Посмотрим есть ли смысл кому-то кроме номера1 голосовать за первую остановку? Никакого смысла! Потому что сам первый будет всегда голосовать "за". Теперь рассмотрим имеет ли смысл кому-то кроме номера2 и номера1 голосовать за вторую остановку? Нет не имеет! Потому что второй будет всегда начиная со второй остановки голосовать "за". И т.д. Т.е. получается никому нет смысла голосовать "за" до своей остановки Поэтому ответ получается такой же, как и в первом случае.

Здравствуйте, WeCom, Вы писали:

WC>

WC>Ну как минимум на номере 98, автобус не остановится! Имеем 3 человека — 98,99 и 100 и автобус подьезжает к 98-й остановке. Скажите, какой смысл номерам 99 и 100 голосовать за остановку на 98-й?

WC>Порассуждаем еще.
WC>Посмотрим есть ли смысл кому-то кроме номера1 голосовать за первую остановку? Никакого смысла! Потому что сам первый будет всегда голосовать "за". Теперь рассмотрим имеет ли смысл кому-то кроме номера2 и номера1 голосовать за вторую остановку? Нет не имеет! Потому что второй будет всегда начиная со второй остановки голосовать "за". И т.д. Т.е. получается никому нет смысла голосовать "за" до своей остановки Поэтому ответ получается такой же, как и в первом случае.

А про то что

все пассажиры умны и делают прогнозы о том как им лучше голосовать

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

Здравствуйте, Octane, Вы писали:

O>А про то что
O>

все пассажиры умны и делают прогнозы о том как им лучше голосовать

O>нужно забыть ?
O>Каждому пассажиру кажется что ему нет смысла голосовать кроме как за свою остановку,и если они(пассажиры) понимают это ,они начнут сотрудничать и голосовать за остановки других...

Нет нельзя забывать! Утверждаешь что именно я это забыл? Тогда обьясни мне зачем кому-то кроме номера1 голосовать за первую остановку? Они ведь могут проголосовать все вместе за вторую остановку, не так ли? И тогда для всех них после второй остановки ситуация будет точно такая же как если бы они голосовали и за первую и за вторую остановку. Но доедут они до дома 100% быстрее если не будут голосовать за первую остановку. Поэтому они за первую остановку точно голосовать не станут. Уже это говорит о том, что твой ответ не верен. Вот если бы первый мог устраивать подлости (ехать до 100-й остановки), тогда было бы наверное по-другому.

Здравствуйте, WeCom, Вы писали:

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

Нет.
Например, пассажиру 51 имеет смысл голосовать за за остановки 50 или 49 и выйти на них. Потому как иначе он ещё долго будет ехать...

Здравствуйте, Boffin, Вы писали:

B>Здравствуйте, WeCom, Вы писали:

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

B>Нет.
B>Например, пассажиру 51 имеет смысл голосовать за за остановки 50 или 49 и выйти на них. Потому как иначе он ещё долго будет ехать...

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

Здравствуйте, SanSoft, Вы писали:

SS>Давным давно в КВАНТЕ была вот какая задачка.

SS>По маршруту едет автобус. На маршруте имеется 100 остановок, для нашего удобства они пронумерованы от 1 до 100. В автобусе 100 пассажиров, для нашего удобства они опять таки пронумерованы от 1 до 100. В принципе каждому из пассажиров надо сойти на остановке номер которой совпадает с его собственным номером.

SS>Водитель, дабы ускорить движение, предложил следующий алгоритм. Ппри подъезде к каждой очередной остановке проводится голосование "останавливаться или ехать безостановочно". Решение принимается простым большинством голосов. Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей к нужной.
А если она уже прошла??? (Например, если остановки 50, 75,..., то 51-ый чел мог бы не ждать 75-ой остановки...) Или они всё решили заранее? Тогда нафига голосовать?
Хотя появляется почва для размышлений...
А вот такой вопрос. Количество остановок ОГРАНИЧЕНО??? Если ограничено 100 — то решение понятно. Иначе получаем 101 задачу
Например, мне нравится данная задача, когда этих остановок 10. Тогда, понятно, 5, 15, 25, ..., 95 остановки будут... при условии, что все сговорились заранее.
Иначе встает вопрос: что чуваки думают про всех остальных. Думают, что другие будут голосовать только за свою остановку или когда проедут свою? Или что?
SS>Вопрос — на каких остановках автобус будет останавливаться.

Здравствуйте, BUran, Вы писали:

BU>Иначе встает вопрос: что чуваки думают про всех остальных. Думают, что другие будут голосовать только за свою остановку или когда проедут свою? Или что?

На выбор (стратегию) отдельного чувака стратегии всех остальных не влияют. Иначе бы эта задача не была опубликована в КВАНТе

А насчет сговора, обьясните мне кто-нибудь чем можно соблазнить пассажиров с номерами от 50 до 100 голосовать за какую-нибудь остановку до 50-й. А если они не будут голосовать, то и остановки не будет, потому что их большинство.

Здравствуйте, WeCom, Вы писали:

WC>Здравствуйте, BUran, Вы писали:

BU>>Иначе встает вопрос: что чуваки думают про всех остальных. Думают, что другие будут голосовать только за свою остановку или когда проедут свою? Или что?

WC>На выбор (стратегию) отдельного чувака стратегии всех остальных не влияют. Иначе бы эта задача не была опубликована в КВАНТе

WC>А насчет сговора, обьясните мне кто-нибудь чем можно соблазнить пассажиров с номерами от 50 до 100 голосовать за какую-нибудь остановку до 50-й. А если они не будут голосовать, то и остановки не будет, потому что их большинство.
Тем например, что 60 знает, что если сделают остановку на 30-й, то будет остановка и на 60-й, и не придется выходить на 50-й или 75-й, например.

А что ты ответишь про то, чтобы подумать о том, чтобы выйти заранее, до своей остановки??

Здравствуйте, WeCom, Вы писали:

WC>А можно еще уточнение(я)?
WC>1.Пассажиру до своей остановки разрешается выходить? — предполагаю да
WC>2.Следует ли считать расстояния между остановками равными? — полагаю, что тоже да

Если на первый пункт ответ "да", то вот какая еще интересная ситуация получается. Разрешено ли выходить на нулевой остановке. Если бы я был первым пассажиром то именно так бы и сделал. Или водитель всех запер и поставил условия? Но вроде нет, написано "предложил".
Или все же в условии должно быть

Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей следующей к нужной.

Здравствуйте, BUran, Вы писали:

WC>>А насчет сговора, обьясните мне кто-нибудь чем можно соблазнить пассажиров с номерами от 50 до 100 голосовать за какую-нибудь остановку до 50-й. А если они не будут голосовать, то и остановки не будет, потому что их большинство.
BU>Тем например, что 60 знает, что если сделают остановку на 30-й, то будет остановка и на 60-й, и не придется выходить на 50-й или 75-й, например.

Это догадки ничем не подкрепленные и на мой взгляд неверные! Неверные по следующей причине. Предположим 60-й решает голосовать за 30-ю остановку и его голос оказывается решающим на 30-й остановке... В общем я уже писал выше похожие рассуждения. 60-му будет выгоднее голосовать за 31-ю остановку, чем за 30-ю, потому что он ничего от этого не теряет!!! Но если его голос будет решающим на 31-й, то ему выгоднее голосовать на 32-й, и т.д..... А если его голос где-то не решающий, то ему нафиг не надо голосовать В итоге получается что голосовать они все будут начиная со своей остановки. А вот выходить?...

BU>А что ты ответишь про то, чтобы подумать о том, чтобы выйти заранее, до своей остановки??
Думаю имеет смысл разделить задачу на две. С разрешением этого и без.

Здравствуйте, SanSoft, Вы писали:

SS>Решение принимается простым большинством голосов.

Если при равенстве голосов остановка отсутствует, и выходить раньше своей остановки нельзя, то тогда ответ на задачу в обоих случаях — 51,77,89,95,98,100.

Здравствуйте, WeCom, Вы писали:

WC>Нет нельзя забывать! Утверждаешь что именно я это забыл? Тогда обьясни мне зачем кому-то кроме номера1 голосовать за первую остановку? Они ведь могут проголосовать все вместе за вторую остановку, не так ли? И тогда для всех них после второй остановки ситуация будет точно такая же как если бы они голосовали и за первую и за вторую остановку. Но доедут они до дома 100% быстрее если не будут голосовать за первую остановку. Поэтому они за первую остановку точно голосовать не станут. Уже это говорит о том, что твой ответ не верен. Вот если бы первый мог устраивать подлости (ехать до 100-й остановки), тогда было бы наверное по-другому.

До дома большинство быстрее доедет(даже если перед этим будут лишние остановки),чем дойдет(преодолев пешком k остановок пути)

Здравствуйте, WeCom, Вы писали:

WC>Здравствуйте, BUran, Вы писали:

WC>>>А насчет сговора, обьясните мне кто-нибудь чем можно соблазнить пассажиров с номерами от 50 до 100 голосовать за какую-нибудь остановку до 50-й. А если они не будут голосовать, то и остановки не будет, потому что их большинство.
BU>>Тем например, что 60 знает, что если сделают остановку на 30-й, то будет остановка и на 60-й, и не придется выходить на 50-й или 75-й, например.

WC>Это догадки ничем не подкрепленные и на мой взгляд неверные! Неверные по следующей причине. Предположим 60-й решает голосовать за 30-ю остановку и его голос оказывается решающим на 30-й остановке... В общем я уже писал выше похожие рассуждения. 60-му будет выгоднее голосовать за 31-ю остановку, чем за 30-ю, потому что он ничего от этого не теряет!!!
Тем более ничем не подкреплено. По-моему, как раз он теряет в этом случае возможность выйти на 60 остановке. (Цифры 30 и 60, понятно, взяты с потолка)
>Но если его голос будет решающим на 31-й, то ему выгоднее голосовать на 32-й, и т.д..... А если его голос где-то не решающий, то ему нафиг не надо голосовать В итоге получается что голосовать они все будут начиная со своей остановки. А вот выходить?...

BU>>А что ты ответишь про то, чтобы подумать о том, чтобы выйти заранее, до своей остановки??
WC>Думаю имеет смысл разделить задачу на две. С разрешением этого и без.

Здравствуйте, Octane, Вы писали:

O>Здравствуйте, WeCom, Вы писали:

WC>>Нет нельзя забывать! Утверждаешь что именно я это забыл? Тогда обьясни мне зачем кому-то кроме номера1 голосовать за первую остановку? Они ведь могут проголосовать все вместе за вторую остановку, не так ли? И тогда для всех них после второй остановки ситуация будет точно такая же как если бы они голосовали и за первую и за вторую остановку. Но доедут они до дома 100% быстрее если не будут голосовать за первую остановку. Поэтому они за первую остановку точно голосовать не станут. Уже это говорит о том, что твой ответ не верен. Вот если бы первый мог устраивать подлости (ехать до 100-й остановки), тогда было бы наверное по-другому.

O>До дома большинство быстрее доедет(даже если перед этим будут лишние остановки),чем дойдет(преодолев пешком k остановок пути)

И что ты этим сказал? Я же просил, и еще раз прошу, обьясни мне зачем кому-то кроме номера1 голосовать за первую остановку? Не общими словами, а конкретно. Покажи мне в частности, чем будет отличатся ситуация после второй остановки для пассажиров с номерами от второго до сотого в случае когда они голосуют и за первую и за вторую остановку от случая когда они голосуют только за первую остановку!!! Я утверждаю, что ничем — первый и второй уже вышли в обоих случаях, а все остальные внутри автобуса. Из того что для них ситуация ничем не отличается, я делаю вывод, что за первую остановку 99 человек голосовать не бу-дут. Неужели все еще непонятно?

A>>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.

WC>Это имхо лишнее. Достточно сказать, что каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке.


Совсем не лишнее. Возьмем несколько ярких случаев которые могут сильно изменить решение задачи

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

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


#автобус движется не по прямой (а кто вам сказал и где вы видели такие маршруты?) соотсвеннно есть такая ситуевина от 100 до 98 идти гораздо меньше чем от 99 до 98 — тогда умный 99 будет голосовать чтобы 98 вышел на своей, а не проголосовал против его выхода на 99.


SS>>>1 все пассажиры тупы и не делают прогнозы

A>>Автобус проедет маршрут без остановок.

WC>Т.е. настолько тупы, что даже проехав свою остановку не желают выходить?

SS>>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать

A>>Автобус проедет маршрут со всеми остановками.

WC>Ну как минимум на номере 98, автобус не остановится! Имеем 3 человека — 98,99 и 100 и автобус подьезжает к 98-й остановке. Скажите, какой смысл номерам 99 и 100 голосовать за остановку на 98-й? Об альтруизме в задаче разговора кажется не было.



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

Здравствуйте, Apostate, Вы писали:

A>>>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.

WC>>Это имхо лишнее. Достточно сказать, что каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке.

A>Совсем не лишнее. Возьмем несколько ярких случаев которые могут сильно изменить решение задачи

Можно совет?
Когда приходят такие мысли в голову, сделай вот как. Попробуй так проинтерпретировать непонятные вещи, чтобы задача имела однозначное решение. Если такого не получается, то из всех мыслимых тобой непротиворечивых дополнений выбери такие при которых задача будет наиболее интересной и конечно же без абсурдных с точки зрения физики и здравого смысла условий. Реши эту задачу. И предложи ответ с указанием, какие дополнения ты принял в задаче. Если ты ошибешься и в оригинальном условии другое, а автор пропустил, не волнуйся, в любом случае найдутся люди, которые оценят твой ответ по-достоинству.

А то как то на мой взгяд несерьезно получается, 1 сек пути, автобус медленнее пассажира...

Непонятна фраза "сходит на ближайшей к нужной"? — Уверен следует считать расстояние между остановками, как разность номеров.

Задумываешься о возможности сговора? — Прочитай внимательно принятое автором уточнение "каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке". Собственно ради этого одного выделенного слова я и просил автора уточнить.

Здравствуйте, WeCom, Вы писали:

Для Octane:
ошибочка:

WC>... в случае когда они голосуют и за первую и за вторую остановку от случая когда они голосуют только за вторую остановку!!!...

Может изменить формулировку так: если чел проголосовал, остановились — то он и выходит?
А иначе, чем плох вариант, что голосовать всегда "за"? И ограничений на количество остановок нет...

Тогда задача сразу становится содержательной.

ИМХО, надо попробовать решить задачу с конца.
Леммы.
1) выходят по порядку.
док-во очевидно.
2) выходит некоторый "отрезок" чуваков То есть с какого-то до какого-то.
следствие 1.
3) Среди вариантов есть вариант, при котором каждый раз голосует больше половины, причем голосующие как раз при удачном голосовании выходят.
вариантов — конечное число. Есть вариант, например, вылезти всем на первой остановке. Такой вариант неоптимальный => есть посл-сть более оптимальных вариантов. (А иначе — он — оптимальный ) => есть самый оптимальный.
4) Среди таких "наименьших" есть наименьший по цифрам. Например, 0101010...01 -неоптимален, т.к. оптимальнее 0101....10 —
(здесь 0 и 1 — делать i-ю остановку или нет)
Вот его-то и будем искать.
---
1) последняя остановка — 100.
на ней вышло 0 — возможно, если все вышли раньше.
на ней вышел 1 — возможно, это 100-ый.
на ней вышло 2 — невозможно, можно было бы выйти и на 99-ой. (ищем минимальный вариант из наилучших)
на ней вышло 3 и более — невозможно, так как большинство вышло бы раньше.

2) последняя остановка — 99
на ней вышло 0 — невозможно (нафига тогда останавливаться?)
вышло 1 — последний? невозможно. доедет до 100.
вышло 2 — запросто.
вышло 3 — вряд ли. Последний доедет в одиночку до своей.
Брр, неправильно обозначил. Начнем снова, только указывать, сколько осталось, и сколько выйдет:

1) 100-ая. осталось:
0: выйдет 0
1: выйдет 1
2: невозможно (выйдут раньше в силу леммы 4)
...
2) 99-ая
0: выйдет 0
1: выйдет 0
2: выйдет 2 (будем считать, что голосовало большинство, т.е. 2)
3: выйдет 2
4: выйдет 3
5: выйдет 4 (впрочем, опять же невозможно)
...
3) 98-я
0: 0
1: 0
2: 0
3: 2 (вариант 0 не проходит по л.4)
4: 3 (есть 4:0 и 4:4 — они хуже)
5: 3
6: 4
...
4) 97-я
0: 0
1: 0
2: 0
3: 0
...
Блин, сложно, долго, нудно... надо программу писать...

Правила следующие: для каждой остановки и каждого количества смотрим: если не 0 — то это большинство, которое реально выходит. Если не выходим щас — смотрим, когда сможем выйти. Это мы знаем. Можем соптимизировать значит. Вот.

WC>Можно совет?
WC>Когда приходят такие мысли в голову, сделай вот как. Попробуй так проинтерпретировать непонятные вещи, чтобы задача имела однозначное решение. Если такого не получается, то из всех мыслимых тобой непротиворечивых дополнений выбери такие при которых задача будет наиболее интересной и конечно же без абсурдных с точки зрения физики и здравого смысла условий. Реши эту задачу. И предложи ответ с указанием, какие дополнения ты принял в задаче. Если ты ошибешься и в оригинальном условии другое, а автор пропустил, не волнуйся, в любом случае найдутся люди, которые оценят твой ответ по-достоинству.

=), спасибо за совет, он хороший, но мне кажется он немного не к месту и вот почему


WC>Задумываешься о возможности сговора? — Прочитай внимательно принятое автором уточнение "каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке". Собственно ради этого одного выделенного слова я и просил автора уточнить.

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


http://www.rsdn.ru/Forum/Message.aspx?mid=295558&only=1

Автор: Apostate
Дата: 13.06.03

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

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


Вообщем, я белый, пушистый и в меру упитанный.

A>Если настолько туп, что рефлексии нет — автобус проедет без остановок.

Хотя насчет тупизны спорно тем что в природе существует бесконечное разнообразие тупизны и только одна едиственная разумность.

Вообщем возможны варианты тупости/незнания.

Не знает что в автобусе другие люди. Не знает что для каждой остановки есть люди которые хотят на ней выйти. Не знает что он тоже люди. Не знает что автобус едет от 1 остановки до 100 последовательно, и если проехал свою остановку то дальше он будет только удалятся. Не знает какая сейчас остановка. Не знает что он может проехать свою остановку до тех пор, пока он ее не проедет. Не знает что он уже проехал свою остановку. Не знает какая остановка его. Не умеет считать (дети тоже пассажиры, да?). И т.д.

Так вот, тупость о которой идет речь. Допустим его остановка N и у него единственное желание выйти как можно ближе к этой остановке, голосования —
1 нет бывает и ближе,
...
N-1 нет бывает и ближе
N да, ближе не бывает
N+1 нет, бывает и ближе
...
100 нет, бывает и ближе


Если он туп но умеет делать прогнозы относительно движения автобуса но не знает о голосовании другими
1 нет бывает и ближе. И еще будет.
...
N-1 нет бывает ближе. И еще будет.
N да, ближе не бывает
N+1 да, бывает и ближе. Но уже не будет.
N+2 да, бывает и ближе. Но уже не будет.

...
до тех пор пока не выйдет


То решение (при равенстве голосов остановка) 50, 75, 88, 94, 97, 99,100
соотвественнои вышло на этой остановке 50, 25, 13, 6, 3,2,1
и на момент да-голосования в автобусе было 100,50 ,25, 12,6,3,1

при равенстве голосов неостановка, решение такое

51 76 89 95 98 100
51 25 13 6 3 2
100 49 24 11 5 2



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

1 нет бывает и ближе. И еще будет. И голосование будет положительным.
...
N-1 нет бывает ближе. И еще будет. И голосование будет положительным.
N да, ближе не бывает
N+1 да, бывает и ближе. Но уже не будет.
N+2 да, бывает и ближе. Но уже не будет.
...
до тех пор пока не выйдет

То решения те же что и выше
50 75 88 94 97 99 100
51 76 89 95 98 100



Тоже но если они полные пессимисты
1. нет бывает и ближе. И еще будет. Но голосование во всех случаях будет отрицательным.
— все выйдут на первой же


и т.д. и т.п.



И только один умный вариант

1. да, а зачем парится и голосовать против?
...
до тех пор пока не выйдет

Здравствуйте, Octane, Вы писали:

Ситауция аналогичная как при голосовании скажем всей страны. Разве ваш один голос что-то решает? Но если вы проголосуете так как считаете нужным — есть шанс что также поступят остальные.
В данном случае всем выгодно всегда голосовать "за".
Прямо золотое правило морали — "относись к другим так, как хочешь что-бы относились к тебе".

Здравствуйте, IO, Вы писали:

IO>В данном случае всем выгодно всегда голосовать "за".
Учитывая, что по условию задачи, "все руководствуются единственным желанием..." зачем номеру100 голосовать за какую-нибудь остановку кроме его личной?

---

100 остановок — это конечно много. Сложно уловить все возможные комбинации...
Если посмотреть на ту же задачу с пятью остановками-пассажирами, то вот, что интересное получается. Полагаем, для того чтобы автобус остановился нужно строгое большинство голосов. Номер пятый собирается голосовать "за" только на пятой остановке. Номер первый — на всех. Номер второй — начиная со второй (или даже с первой — неважно) остановки. — Это для них оптимальные варианты поведения.
Так вот, если четвертый проголосует за вторую остановку, то он сделает доброе дело для первого и второго, подлянку в отношении третьего и обеспечит себе выход на своей остановке (вместе с третим). Если же он за вторую голосовать не будет, то на третей остановке выйдут 1-3, а он (четвертый) вместе с пятым поедет до конечной.
Получается, что то решение, которое я проталкивал, будет верным только с дополнительной оговоркой, что выходят все голосовавшие "за".

Здравствуйте, WeCom, Вы писали:

WC>Учитывая, что по условию задачи, "все руководствуются единственным желанием..." зачем номеру100 голосовать за какую-нибудь остановку кроме его личной?

Это вообще то очень неочевидно, но мне кажется логика тут есть.
Поставлю вопрос прямо: если я буду голосовать всегда "за", как изменится вероятность того, что все остальные тоже всегда будут голосовать "за"?
Мне кажется, что возрастет.

Здравствуйте, IO, Вы писали:

IO>Поставлю вопрос прямо: если я буду голосовать всегда "за", как изменится вероятность того, что все остальные тоже всегда будут голосовать "за"?
IO>Мне кажется, что возрастет.

В условии задачи об этом не говорится! Нооборот, неявно указывается, что каждый сам за себя. Т.е. как минимум нельзя расчитывать на то, что своими голосами "за" удасться пробудить совесть. И более того, учитывать, что голосуя "за" можно и навредить себе. Например, 3 остановки — 3 пассажира. Для остановки надо строгое большинство. Второй решает действовать твоим методом. И... помогает первому сойти на своей остановке. А вот третий — он асоциальный элемент и его устроят 30 сэкономленых на второй остановке секунд и поэтому он не даст второму сойти на своей остановке. Хотя второй мог бы при желании (а оно по условию у него должно было бы быть) обеспечить себе выход на своей остановке.

Здравствуйте, WeCom, Вы писали:

WC>Здравствуйте, SanSoft, Вы писали:

SS>>Решение принимается простым большинством голосов.

WC>Если при равенстве голосов остановка отсутствует, и выходить раньше своей остановки нельзя, то тогда ответ на задачу в обоих случаях — 51,77,89,95,98,100.

по моему все таки таки
51 76 89 95 98 100

76 потому что их было 49 в автобусе и 25 из них захотели выйти
89 потому что их было 24 в автобусе и 13 из них захотели выйти

остальное аналогично

Здравствуйте, Apostate, Вы писали:

SS>>>Решение принимается простым большинством голосов.

WC>>Если при равенстве голосов остановка отсутствует, и выходить раньше своей остановки нельзя, то тогда ответ на задачу в обоих случаях — 51,77,89,95,98,100.

A>по моему все таки таки
A>51 76 89 95 98 100

A>76 потому что их было 49 в автобусе и 25 из них захотели выйти
A>89 потому что их было 24 в автобусе и 13 из них захотели выйти

A>остальное аналогично

Да, я ошибся.
Только теперь я уже почти уверен, что это не будет верным решением...
См. http://www.rsdn.ru/Forum/Message.aspx?mid=295558&only=1

Автор: Apostate
Дата: 13.06.03

Здравствуйте, WeCom, Вы писали:


WC>См. http://www.rsdn.ru/Forum/Message.aspx?mid=297028&only=1

Автор: WeCom
Дата: 16.06.03

Здравствуйте, WeCom, Вы писали:

SS>>1 все пассажиры тупы и не делают прогнозы
WC>Тогда они очевидно будут голосовать "против" до остановки со своим номером, а далее будут голосовать "за" до тех пор пока автобус не остановится. И тогда все голосовавшие за, сойдут и ситуация повторится, только остановок останется меньше.
WC>Если считать, что при равенстве голосов принимается решение "остановиться", то очевидно остановки будут иметь номера 50,75,88,94,97,99,100.
Согласен. При тупом поведении — логика проста => чистая математика.

SS>>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
все пассажиры умны — это что, автобус с РСДН-овцами? Мужики — это намек! Пора собирать большую реалку и переть куда-нить на экскурсию с пивом Заодно помучим водилу автобуса

А вообще:

1. Они могут пойти по пути демократии и устроить голосование, через сколько остановок тормозить.
При голосовании о варианте "через 1" поднимут руки все четные пассажиры.
"через 2" — каждый третий.
"через 3" — каждый четвертый.
"через 4" — каждый пятый.
и т.д.
Т.е. имеем: либо на каждой, либо через одну, если таки решат, что на каждой не катит

2. Можно так-же проголосовать, кто из пассажиров на какое максимальное количество остановок от своей согласен выйти.
Тогда, если, скажем, решится, что большинство согласно выйти максимум на соседней со своей остановкой, следует останавливаться на каждой третьей(две подряд пропускаем), если согласны максимум через одну от своей — на каждой пятой(четыре пропускаем), и т.д.

Я лично из этих двух вариантов больше склоняюсь ко второму, как к более разумному.

Здравствуйте, DSD, Вы много и умнО писали,

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

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

Здравствуйте, Mikhail_T, Вы писали:

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

Все будет именно так, как ты говоришь. Точнее, почти так...
Потому что на полпути молодого человека под номером сто только что сдавшего сессию , невыспавшегося и к тому же отметившего успешную сдачу с друзьями слегка разморит в душном автобусе и он заснет (ему-то бояться нечего, он свою остановку не пропустит). В итоге проспит он все остановки вплоть до своей конечной, на которой его и растолкают водитель да бабушка под номером девяносто девять , которая не спала и честно голосовала на всех остановках "за" (хотя спрашивается зачем она за 98 голосовала, но это уже не важно).
И будет той бабушке так обидно , что не ее остановку пропустили, что она мало того, что молодому человеку выскажет все, что о нем думает, так она еще и к диспетчеру зайдет и на водителя так нажалуется , что тот дабы сберечь свои нервы и место работы должен будет взять свой личный автотранспорт и довезти бабушку прямо до дома рядом с 98-й остановкой.
Мораль сей басни такова. Коли возишь людей, так вози людей, а не загадывай ребусов! Тем более, что все равно себе выйдет дороже.

Здравствуйте, WeCom, Вы писали:

WC>но я просто фигею, как народу хочется превратить задачку из математической, в задачку по социальной психологии.
Математически ИМХО слишком нечеткое условие, понимание задачи плавает.
Единственное четкое, что здесь можно выделить, это вариант 1, предложенный тобой(с рядом чисел, когда "все тупые").
Но автор темы хочет чего-то еще, задавая вопрос "когда все умные".... а вот чего, не понятно...

Здравствуйте, DSD, Вы писали:

DSD>все пассажиры умны — это что, автобус с РСДН-овцами? Мужики — это намек! Пора собирать большую реалку и переть куда-нить на экскурсию с пивом Заодно помучим водилу автобуса

Только остановки наоборот будут: останавливаться нужно, чтобы подобрать жаждущего, а не ссадить ненужного. И голосовать — останавливаться или нет, берем или нет, есть ли в руках пиво или нет. Интересно, кто первым голосовать будет?! Водитель?

Здравствуйте, Mikhail_T, Вы писали:

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

Это в корне неверно — например 100 ВСЕГДА сойдет на своей остановке и ни за какую их предыдущих голосовать не будет (ему от этого ничего не прибудет, хотя и не убудет ) => если в автобусе осанется 2 человека то на 99 остановке будет один голос за(99) и один проитив (100) => автобус остановится только на 100, и 99 не выйдет на своей остановке.

Здравствуйте, nikholas, Вы писали:

N>Здравствуйте, Mikhail_T, Вы писали:

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

N>Это в корне неверно — например 100 ВСЕГДА сойдет на своей остановке и ни за какую их предыдущих голосовать не будет (ему от этого ничего не прибудет, хотя и не убудет ) => если в автобусе осанется 2 человека то на 99 остановке будет один голос за(99) и один проитив (100) => автобус остановится только на 100, и 99 не выйдет на своей остановке.

На месте 100 я бы не был так уверен, например 99 и 98 тупые и всегда голосуют по принципу — не моя остановка, значит голосовать буду против. Если их на своих не высадить — автобус не остановится и на 100.

Здравствуйте, Apostate, Вы писали:

A>На месте 100 я бы не был так уверен, например 99 и 98 тупые и всегда голосуют по принципу — не моя остановка, значит голосовать буду против. Если их на своих не высадить — автобус не остановится и на 100.

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

Хорошим доп. условием ИМХО будет такое: человек голосует за остановку в том и только в том случае, если при сравнении варианта остановки и не остановки для него более выгодным является вариант остановки
Под более выгодным мы понимаем меньшее расстояние от его остановки до ближайшей, на которой реально остановится автобус

При таких условиях набор остановок предопределен, правда налицо обратная связь: набор остановок -> кто когда выйдет -> знаем кто за что голосует -> набор остановок

При помощи итеративного алгоритма можно определить стратегию каждого.

При таких условиях для любого количества оставшихся пассажиров сужествует только одна последовательность остановок:
Если остался 1 (№100) — остановка на 100
Если осталось 2 (№99, 100) — остановка на 100
Если осталось 3 (№98, 99, 100) — остановка на 99 -> остался 1
Если осталось 4 — остановка 99, 100

Будем находить значения следующих функций(последовательностей? ... а вот назову как нравится )
в порядке убывания номера остановки:

S(N) — кол-во людей оставшихся в автобусе если произошла остановка в N (после остановки)
(S(100) = 0, S(99) = 1, S(98) = 1, ...)
P(N) — последовательность остановок после остановки в N
V(N) — кол-во людей с номерами >N, которые будут голосовать за остановку в N
START(N) — количество людей, начиная с которого остановка произойдет не позже, чем в N

Очевидно, что START(N) = (100 — N — V(N)) * 2 + 1

Рассматривая очередное N, используем следующий алгоритм для нахождения данных значений:
(Предполагаем, что для всех больших N мы уже все знаем)

S(N) — из общих соображений
Из тех же соображений — P(N)
Нахождение V(N) нетривиально но возможно — каждый из находящихся в автобусе может определить набор остановок если остановка в N произойдет и если ее не произойдет, и если первый вариант для него более выгодный — то проголосовать за остановку в N.

Будет время — реализую этот алгоритм и выложу результат

N>Будет время — реализую этот алгоритм и выложу результат

лучше почитай топик, писатель

Здравствуйте, Apostate, Вы писали:

N>>Будет время — реализую этот алгоритм и выложу результат

A>лучше почитай топик, писатель

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

Здравствуйте, Apostate, Вы писали:


SS>>1 все пассажиры тупы и не делают прогнозы

A>Автобус проедет маршрут без остановок.

SS>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать

A>Автобус проедет маршрут со всеми остановками.

A>


A>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.

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

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

Зашибись задачка получилась

Здравствуйте, SanSoft, Вы писали:

SS>Давным давно в КВАНТЕ была вот какая задачка.

SS>По маршруту едет автобус. На маршруте имеется 100 остановок, для нашего удобства они пронумерованы от 1 до 100. В автобусе 100 пассажиров, для нашего удобства они опять таки пронумерованы от 1 до 100. В принципе каждому из пассажиров надо сойти на остановке номер которой совпадает с его собственным номером.

SS>Водитель, дабы ускорить движение, предложил следующий алгоритм. Ппри подъезде к каждой очередной остановке проводится голосование "останавливаться или ехать безостановочно". Решение принимается простым большинством голосов. Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей к нужной.

SS>Вопрос — на каких остановках автобус будет останавливаться.

SS> все пассажиры умны и делают прогнозы о том как им лучше голосовать
SS>задача достаточно логическая и наверное может быть "запрограммирована" даже в Excele

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

Так как наиболее важным параметром является не пройденное число остановок а оставшееся до конечной, будем считать что автобус едет с остановки № N до остановки № 1.

Каждый пассажир будет рассуждать так: если в автобусе останется N человек, то первой остановкой может быть остановка с номером K, N/2<=K<=N. После этой остановки в автобусе останется N' человек, N'<K<=N — т.е. задача свелась сама к себе, только с меньшим числом людей.
Для любого числа людей меньше N я знаю набор остановок, поэтому определю остановку K по следующему алгоритму:
После остановке в K в автобусе может остаться от 0 до K-1 человек, для каждого кол-ва людей набор оставшихся остановок известен => каждый из оставшихся решит выходить ему или нет — найдем N'(K) (очевидно, что выходить будут все пассажиры с промежутка, поэтому надо найти пассажира с минимальным номером, который выйдет)
Если авт. не остановился на остановках с номерами > K', то если он не остановится и в K', следующая остановка будет в K'' (предполагаем известным, потому что мы итерируем по K') — каждый решит, что ему выгоднее — остановка в K' или ее отсутствие. Наибольшее K, за которое проголосует больше половины N и будет первой остановкой.

const unsigned amountLimit = 1000;

unsigned nextStop[amountLimit] = {0, 1, 1};
unsigned nextStopByStop[amountLimit] = {0, 1, 1};

unsigned getDistance(unsigned passNo, unsigned stopNo)
{
    if(stopNo <= passNo)
        return passNo - stopNo;
    unsigned prevStop;
    do 
    {
        prevStop = stopNo;
        stopNo = nextStopByStop[stopNo];
    } 
    while(stopNo > passNo);
    return min(passNo - stopNo, prevStop - passNo);
}

void main()
{
    unsigned amountPassangers;
    for(amountPassangers = 3; amountPassangers != amountLimit; ++amountPassangers)
    {
        int possibleStop;
        unsigned nextAmountPassangers[amountLimit];
        for(possibleStop = amountPassangers/2; possibleStop <= amountPassangers; ++possibleStop)
        {
            int nextAmount = 0;
            while(nextAmount - nextStop[nextAmount] < possibleStop - nextAmount)
                ++nextAmount;
            nextAmountPassangers[possibleStop] = --nextAmount;
            nextStopByStop[possibleStop] = nextStop[nextAmount];
        }
        unsigned stopNo = amountPassangers/2;
        for(possibleStop = amountPassangers/2 + 1; possibleStop != amountPassangers; ++possibleStop)
        {
            unsigned vouters = amountPassangers - possibleStop + 1;
            for(int passWithStop = 1; passWithStop != possibleStop; ++passWithStop)
            {
                unsigned distWithStop = getDistance(passWithStop, possibleStop);
                unsigned distWithoutStop = getDistance(passWithStop, stopNo);
                if(distWithStop < distWithoutStop)
                    vouters++;
            }
            if(2*vouters > amountPassangers)
                stopNo = possibleStop;

        }
        nextStop[amountPassangers] = stopNo;
        cout << amountPassangers << " : " << stopNo << " ";
        do 
        {
            stopNo = nextStopByStop[stopNo];
            cout << stopNo << " ";
        } 
        while(stopNo != 1);
        cout << "\n";
    }

}

И вот собственно ответ для 100: 37 70 84 91 96 99 100
На удивление непредсказуем!
Например для 127 пассажиров (и остановок) ответ 22 64 97 111 118 123 126 127

Здравствуйте, nikholas, Вы писали:

N>Каждый пассажир будет рассуждать так: если в автобусе останется N человек, то первой остановкой может быть остановка с номером K, N/2<=K<=N. После этой остановки в автобусе останется N' человек, N'<K<=N — т.е. задача свелась сама к себе, только с меньшим числом людей.

Мы диалектику учили не по Беллману

Первая остановка все-таки получается меньше N/2, то есть первоначальное предположение неверно. Но, кажется, оно не настолько критично. Кстати, 37 очень похоже на N/e.

Здравствуйте, desperado_gmbh, Вы писали:

_>Здравствуйте, nikholas, Вы писали:

N>>Каждый пассажир будет рассуждать так: если в автобусе останется N человек, то первой остановкой может быть остановка с номером K, N/2<=K<=N. После этой остановки в автобусе останется N' человек, N'<K<=N — т.е. задача свелась сама к себе, только с меньшим числом людей.

_>Мы диалектику учили не по Беллману

_>Первая остановка все-таки получается меньше N/2, то есть первоначальное предположение неверно.
См. мой ответ здесь

Автор: BUran
Дата: 13.06.03

_>Но, кажется, оно не настолько критично. Кстати, 37 очень похоже на N/e.
Ну-ну, а еще больше на 100*3/8,

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

P. S. Читал не всю ветку, уж больно длинная. Простите, если повторил чей-то ответ