По маршруту едет автобус. На маршруте имеется 100 остановок, для нашего удобства они пронумерованы от 1 до 100. В автобусе 100 пассажиров, для нашего удобства они опять таки пронумерованы от 1 до 100. В принципе каждому из пассажиров надо сойти на остановке номер которой совпадает с его собственным номером.
Водитель, дабы ускорить движение, предложил следующий алгоритм. Ппри подъезде к каждой очередной остановке проводится голосование "останавливаться или ехать безостановочно". Решение принимается простым большинством голосов. Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей к нужной.
Вопрос — на каких остановках автобус будет останавливаться.
В принципе очевидны как минимум два варианта решений вытекающих из стратегий поведения пассажиров
1 все пассажиры тупы и не делают прогнозы
2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
задача достаточно логическая и наверное может быть "запрограммирована" даже в Excele
Здравствуйте, SanSoft, Вы писали:
SS>1 все пассажиры тупы и не делают прогнозы
Тогда они очевидно будут голосовать "против" до остановки со своим номером, а далее будут голосовать "за" до тех пор пока автобус не остановится. И тогда все голосовавшие за, сойдут и ситуация повторится, только остановок останется меньше.
Если считать, что при равенстве голосов принимается решение "остановиться", то очевидно остановки будут иметь номера 50,75,88,94,97,99,100.
SS>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
Ответ тот же
Автобус проедет маршрут без остановок.
SS>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
Автобус проедет маршрут со всеми остановками.
А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.
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 голосовать за вторую остановку? Нет не имеет! Потому что второй будет всегда начиная со второй остановки голосовать "за". И т.д. Т.е. получается никому нет смысла голосовать "за" до своей остановки Поэтому ответ получается такой же, как и в первом случае.
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 остановок пути)
"останавливаться или ехать безостановочно". Решение принимается простым большинством голосов. Если пассажиру не удаётся сойти на своей остановке то он сходит на ближайшей к нужной.
Поэтому ответ получается такой же, как и в первом случае.
