Определить минимальное число бусин, которые нужно вытащить, чтобы среди них гарантированно были две одинаковые

@Александрррррпд · Регистрация: 17.09.2017

Студворк — интернет-сервис помощи студентам

почему такой странный вывод что ты просто увеличиваешь число на 1?

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

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

Входные данные
Входной файл INPUT.TXT содержит одно натуральное число N - количество цветов бусин (1 ≤ N ≤ 109).

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на поставленную задачу.

INPUT.TXT OUTPUT.TXT
3 4

мои мысли
Допустим n = 3 // кол цветов
кол бусин 300
Даже если
100 синих,100 красных,100 зёленых
есть шанс не взять одинаковые.

но такое решение все тесты пройдёт

Python
1
2
n = int(input())
print(n+1)

@orestsyn · 20.07.2018, 21:00

Александрррррпд, Бред полнейший.

@Александрррррпд · 20.07.2018, 21:11 **[ТС]**

что именно?

Байт · 20.07.2018, 22:03

Александрррррпд, Тут не нужно никакого программирования. А есть принцип Дирихле (про птичек в клетках)
Ответ, да, очень простой: N+1
Так что ваш код в принципе верен. Только он написан на незнакомом языке. В С++ это будет так

C++
1
2
cin >> N;
cout << N+1;

Добавлено через 3 минуты
Интересный момент. Это условие

Сообщение от Александрррррпд

В шкатулке много бусин каждого цвета.

совершенно не нужно. Достаточно того, что общее число бусин в шкатулке >N

Добавлено через 2 минуты
А про птичек...
Дело с том, что сам Дирихле сформулировал этот принцип так.
Путь есть 100 клеток в которые рассажены 101 птичка. Так таки найдется клетка, в которой будет не меньше двух птичек.

IGPIGP · 20.07.2018, 23:40

Александрррррпд, представьте себе самый неудачный случай, - каждый раз мы вытаскиваем доселе невиданный цвет. Сколько раз это возможно? Столько раз сколько разных цветов, столько раз и будут вытащены неповторяющиеся цвета. На N+1 придётся вытащить какой-то из уже засвеченных цветов... или искать того кто "тусовал колоду" для разбоки по предъяве "Почему цветов большем чем их есть?".

Добавлено через 6 минут

Сообщение от Байт

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

У нас это называлось принципом 3 милиционеров: Если двое милиционеров вели хулигана и зашли в участок, то один милиционер точно потерялся.
В переложении на клетки, это может звучать так: Если на шахматную доску поставить 65 клеток с милиционерами, то один милиционер точно где-то слинял. Клетку продал, а деньги - пропил.

@Александрррррпд · 21.07.2018, 21:19 **[ТС]**

что я не понимаю?
Допустим в шкатулке 3 бусин различных цветов.если там всего 4 бусины мы гарантирована берём две одинаковых.
Если там 1000 бусин взяв 4 бусины у нас из этих 4 бусин могут не быть гарантировано 2 одинаковых.мы может например все 4 вытянуть одного цвета?

IGPIGP · 21.07.2018, 21:30

Сообщение от Александрррррпд

например все 4 вытянуть одного цвета?

Это 2 одинаковых + ещё 2 (то есть одна и ещё одна). В фильме "Служебный роман", главный герой говорит: -"У меня двое детей: - мальчик и... ещё (один) мальчик". Это был работник госплана и его нельзя было обмануть математическими трюками.

@Александрррррпд · 21.07.2018, 22:04 **[ТС]**

Товарище гуру вы меня извините ,но не укладывается в голове никак.
Просто логически шкатулка.в ней допустим 2 цвета.и 500 бусин(у нас n бусин может быть любое количество)
250 Зелёных и 250 красных.я закрываю глаза беру из неё 3 бусины и у меня в руке 3 зелёных.
Или тут смысл задачи ,что с большей вероятностью у меня будут в руке 2 красных и 1 зелёная или 2 зелёных и 1 красная.

Добавлено через 3 минуты

Сообщение от Байт

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

Тут всё верно.Но у нас в задаче не известно количество бусин мы знаем только количество цветов различных.

Байт · 21.07.2018, 22:40

Сообщение от Александрррррпд

не укладывается в голове никак.

Тут, видимо, чего-надо делать с головой...

Попробуем так. N = 1. Все бусы красные. Сколько нужно? Имхо, двух хватит N=1, 2 = N+1
Пусть N=2 (красные и зеленые). Вытащили 1-ю, скажем, красную. Вторая может быть красной или зеленой. (КК, КЗ). Не обращая внимания на возможную удачу тащим третью. Возможные варианты: ККЗ, ККК, КЗК, КЗЗ. Это ясно ?
Если нет, я уже не знаю чем помочь бедной вашей голове

@TRam_ · 21.07.2018, 22:44

Сообщение от Александрррррпд

чтобы среди них гарантированно были две бусины одного цвета

Сообщение от Александрррррпд

я закрываю глаза беру из неё 3 бусины и у меня в руке 3 зелёных

но 2 из этих 3 уже гарантировано зелёные, т.е. задача решена. А то что третья тоже зелёная - для задачи не важно.

Важно именно то, что взять 3 разных цвета из шкатулки с бусинами 2 цветов не получится.

Байт · 21.07.2018, 22:51

На всякий случай, если мои бормотания вас не убеждают, взгляните сюда
https://ru.wikipedia.org/wiki/... 0%BA%D0%B0)
На крайняк, положите в мешочек камешки разных (N) цветов, и проведите несколько экспериментов.

Добавлено через 2 минуты
Александрррррпд,

Сообщение от TRam_

взять 3 разных цвета из шкатулки с бусинами 2 цветов не получится.

Вот-вот! Внемлите мудрым голосам!

Добавлено через 3 минуты

Не по теме:

TRam_, Вообще-то есть такие теории, где правило исключенного третьего не работает. Но это совсем в другой раздел...:)

@Yetty · 21.07.2018, 23:48

Не по теме:

Сообщение от IGPIGP

Если двое милиционеров вели хулигана и зашли в участок, то один милиционер точно потерялся.

с чего бы это вдруг он потерялся ?

Добавлено через 3 минуты

Сообщение от Александрррррпд

Допустим в шкатулке 3 бусин различных цветов.если там всего 4 бусины мы гарантирована берём две одинаковых.

Красная, синяя, зелёная и ещё зелёная. Где гарантия ?

IGPIGP · 21.07.2018, 23:51

Не по теме:

Сообщение от Yetty

с чего бы это вдруг он потерялся ? :)

Никто не знает. В этом вся соль. Их было трое (см. название принципа), а потом двое попали в участок. Третий пропал задолго до этого всего. Хотя если серьёзнее то речь конечно о том, что если оба милициоера попали в участок, то в участке стало на 3 человека больше. Потому, что хулиган же тоже туда попал. Однако вариант, который снимает всё противоречия, это если хулиган - тоже милиционер. Сейчас такое на каждом шагу. Но в моё время такой вариант мог испортить личное дело, поэтому я нигде о нём не заикался. Сложная тема. :D

@TRam_ · 22.07.2018, 00:15

Не по теме:

Сообщение от Yetty

с чего бы это вдруг он потерялся ?

ну, погон он мог задним числом лишиться, за хулиганство

@Yetty · 22.07.2018, 00:24

Не по теме:

Сообщение от IGPIGP

а потом двое попали в участок

про двое даже речи не было в Вашей формулировке:

Сообщение от IGPIGP

Если двое милиционеров вели хулигана и зашли в участок, то один милиционер точно потерялся.

вели. зашли. в чём противоречие я что-то не догоняю.

IGPIGP · 22.07.2018, 00:25

Не по теме:

Сообщение от Yetty

про двое даже речи не было в Вашей формулировке. вели. зашли. в чём противоречие я что-то не догоняю.

проехали

@Yetty · 22.07.2018, 00:33

Не по теме:

Сообщение от IGPIGP

проехали

не хотите отвечать никто Вас не неволит. просто интересно почему такое заключение ? Может сформулировали малость не так ?

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

Определить минимальное число бусин, которые нужно вытащить, чтобы среди них гарантированно были две одинаковые

Решение

Решение

Решение

@orestsyn SETI 64 / 49 / 18 Регистрация: 09.04.2018 Сообщений: 210
	20.07.2018, 21:00
	Александрррррпд, Бред полнейший. 0

@Александрррррпд 4 / 4 / 1 Регистрация: 17.09.2017 Сообщений: 359
	20.07.2018, 21:11 [ТС]
	что именно? 0

@Александрррррпд 4 / 4 / 1 Регистрация: 17.09.2017 Сообщений: 359
	21.07.2018, 21:19 [ТС]
	что я не понимаю? Допустим в шкатулке 3 бусин различных цветов.если там всего 4 бусины мы гарантирована берём две одинаковых. Если там 1000 бусин взяв 4 бусины у нас из этих 4 бусин могут не быть гарантировано 2 одинаковых.мы может например все 4 вытянуть одного цвета? 0