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

@Александрррррпд · Регистрация: 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

проехали

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

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

Решение

Решение

Решение

@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