Однажды у BS была ужасная бессонница. Потому, он решил прогуляться по западной части ночного Копенгагена. На западе столицы Дании расположен комплекс из нескольких озер, к которым и пришел наш странник. BS выбрал самую удобную скамейку и сел на неё. Скамейка располагалась таким образом, что ему прекрасно были видны два озера и плавающие в каждом из них лебеди. Неожиданно Bjarne достал свой фотоаппарат и сделал фотографию двух озер. Готовился выход нового стандарта С++ 2025, потому бессонница автора продолжалась. И ещё много дней он ходил по ночам на озера, садился на самую удобную скамейку, смотрел на звезды, людей, собак и на другие вещи, но самое главное, каждый день он фотографировал два озера и лебедей. Бессонница прошла и его ночные походы прекратились. Тогда, BS решил изучить сделанные им снимки. По счастливой случайности, оказалось так, что на всех фотографиях комбинация мощностей множеств лебедей в озерах принимала всевозможные значения, при этом отсутствовали симметричные ситуации, это значит, что например двух таких дней с комбинациями (5,200) и (200,5) не было. При этом максимальное значение мощности каждого множества не превышало . Автор решил распечатать все свои фотографии. 1 лебедь занимает 1 пиксель на фотографии, других затрат - нет. Принтер заправлен таким образом, что может распечатать не более чем пикселей.
1. Хватит ли этого, чтобы распечатать все фотографии?
2. Если картриджа не хватит, то как минимум насколько должен быть он заправлен для того, чтобы все фотографии были успешно напечатаны?
3. Подготовьте код программы на С/С++, входным параметром является n, на выходе общее количество лебедей на всех фотографиях.

Для лучшего понимания стоит уточнить: "на всех фотографиях комбинация мощностей множеств лебедей в озерах принимала всевозможные уникальные значения"

Допустим n=2, в таком случае у него были следующие фотографии:
0 0
0 1
0 2
1 1
1 2
2 2

12 лебедей на всех фотографиях

White OwlSashaMercury,
Сочиняя задачи, не используй реальных людей в условиях. Глупо смотрится.

Если бы я боялся показаться глупым, я бы тут вообще не одного сообщения не отправил. А BS здесь не просто так, ибо решение задачи имеет некоторые детали связанные с языком С++

maytonА разве

00
11
22

не являются симметричными комбинациями?

Нет, симметричные комбинации вида (x,y) и (y,x). Одна комбинация (x,x) не может быть симметричной

Anatoly MoskovskyЛебеди, хоть, не черные? )))

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

Кроме того, предполагал сделать три озера, но потому подумал, что решать её никто не станет)))

Пока Дмитрий ближе всех, однако решения в любом случае нет.


MasterZivDima TИМХУ для лучшего понимания надо ТЗ перевести с русского на понятный.
присоединяюсь.

Уже перевел, контрпример очень хороший
SSДопустим n=2, в таком случае у него были следующие фотографии:
0 0
0 1
0 2
1 1
1 2
2 2

12 лебедей на всех фотографиях

SashaMercuryДопустим n=2, в таком случае у него были следующие фотографии:
0 0
0 1
0 2
1 1
1 2
2 2

12 лебедей на всех фотографиях

С трудом представляю, что непонятного в этом примере?
Аналогично для 3:
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3
30 лебедей на всех фотографиях.

SSкомбинация мощностей множеств лебедей в озерах принимала всевозможные значения, при этом отсутствовали симметричные ситуации, это значит, что например двух таких дней с комбинациями (5,200) и (200,5) не было.

Ниже я добавил, что каждая фотография уникальна, т.е. не было двух дней (x,y)

Dima T Тогда надо сумму всех чисел 0 ... n сложить n+2 раз, т.е. формула

Почему n+2 раза ?

Dima TSashaMercuryпропущено...


Почему n+2 раза ?
Потому что парные есть (11, 22 и т.д.) Если считать все комбинации, то в каждом разряде, каждое значение повторяется n+1 раз, т.е. все комбинации 2(n+1), т.к. нам надо только половину, то получаем (n+1), но так мы учли только половину из парных (1 из 11, 2 из 22 и т.д.) поэтому еще +1, т.e. итого (n+2)

Логика понятна. Остался такой вопрос: почему каждое значение должно встретиться ровно n+1 раз?

Довольно необычная точка зрения(и способ решения) на эту задачу, даже не думал в эту сторону когда решал её(тремя способами). Функция найдена верно:)

Было бы интересно увидеть другие решения, и, код на С/С++ :)

Здравствуйте. Выкладываю решение:
1. - достаточно было реализовать двойной цикл
2. Однако, небольшой анализ данного цикла и использование формулы суммы арифметической прогрессии приводит нас к следующему тождеству: . Собственно таким образом я эту задачу и решил первым делом.
3. Кроме того, данную формулу можно получить как , при к=2. Если кому-то интересно, попробуйте самостоятельно объяснить то, как она получается.

Дмитрий предложил 4 вариант рассуждений, о котором я даже не думал.

Что мне хотелось сказать относительно С++ и опять в контексте типизации. Только через несколько минут понял, почему мой код для аналогичной задачи не работает. При этом условная n была инициализирована и объявлена намного ранее чем вычисление результата.



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

Dima TSashaMercury, 7000 в кубе уходит далеко за разрядность int (int32_t) Я знаю что ты математик, но на землю иногда спускайся, учитывай формальные ограничения. Ты наступил на обычные грабли переполнения.

Уходит, и что? С точки зрения логики всё было корректно, Результат имел тип long long. Аргумент имел тип int. С точки зрения программирования возникают ошибки. Язык позиционирующий себя как язык с сильной типизацией, должен был оградить любого программиста от такой ошибки