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

То есть в прогу вводится n и она должна выводить число групп. Суть в том, что в качестве n можно ввести хоть 9e99. Суть в том чтобы хватило памяти на рассчеты. Задачу можно решать на любом языке программирования (Pascal, C++, Asm) под дос.

Задачку мне показал один чел и доказывал мне минут 30, что памяти в досе ни за что не хватит на рассчеты. Самому это проверитьь и обойти нет ни времени не желания, особенно под DOS.

Есть желающие опровергнуть?

-----
Никогда не делай то, что возможно. Стремись сделать то что невозможно впринципе!

| Сообщение посчитали полезным:

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

а вот если число n чётное то тогда можно сделать так :

1 2 3 4 5 6 7 8 9 10 гири

1+10 , 2+9 , 3+8 , 4+7 , 5+6 - пять групп с массой 11

а вот с нечётными не знаю,решать как то надо

| Сообщение посчитали полезным:

GPcH пишет:
Задачку мне показал один чел и доказывал мне минут 30, что памяти в досе ни за что не хватит на рассчеты. Самому это проверитьь и обойти нет ни времени не желания, особенно под DOS.
и каким же методом он предлагал ее решать?

| Сообщение посчитали полезным:

DDA пишет:
А как быть если число n - это простое число,которое делиться только на себя и на единицу,то тогда ни о каких группах и речи быть не может( если только в каждую группы будет входить только по одной гире )
Скорее всего, в данном случае решением будет являться только одна группа из всех гирь (группы по одной гире будут иметь разную массу).
И вообще, судя по всему, здесь говорится о максимальном количестве групп (и, соответственно, минимальной массе). Например, если n=12, то есть два варианта решения:
1+12, 2+11, 3+10, 4+9, 5+8, 6+7 - 6 групп массой 13
1+2+11+12, 3+4+9+10, 5+6+7+8 - 3 группы массой 26
Наибольшее число групп - 6

| Сообщение посчитали полезным:

Вообще, число групп нужно искать среди делителей числа (n + 1)n / 2 (сумма членов арифметической прогрессии). Мне даже кажется, что решением будет отношение этой суммы к её наибольшему простому делителю (для n=10: 55 / 11 = 5 групп; для n=12: 78 / 13 = 6 групп).

| Сообщение посчитали полезным:

Есть еще такой вариант:
суммируеи массу всех гирь делим ее на n-макс массу - получаем число - мах кол-во групп на которое можно разделить данное число гирь находим делители этого числа, кроме 1 и n получим еще несколько чисел - тоже кол-во груп на которое можно разделить, но вся загвоздка в том что это будут группы с одинаковым кол-вом килограмм но разным кол-ом гирь, а для вычисления групп с один кол-ом гирь нужен массив а если n=9e99 то мамяти дос не хванит, хотя можно поизвращаться.

приведу пример а то непонятно наверно
n=11 тогда масса равна 66(1+2+...+11) делители 1,2,3,6,11 оставляем 2,3,6
- это и есть колво групп, но с разным кол-ом гирь в каждой по Н: 66/3=22 кг в каждой группе соответственно в 1 - 10,11,1 2-9,8,5 3-7,6,3,2,4, а вот для подсчета какие гири уже использованы нужен массив
по крайней мере больше в голову ничего не пришло

| Сообщение посчитали полезным:

deNULL пишет:
(группы по одной гире будут иметь разную массу).

точно , что то я запарился

| Сообщение посчитали полезным:

Любое чётное количество гирь можно поделить на группы по две гири. А вообще етить в пень все эти гири

-----
Всем не угодишь

| Сообщение посчитали полезным:

Bad_guy пишет:
Любое чётное количество гирь можно поделить на группы по две гири
если брать первую с последней, вторую с предпоследней и т.д.
Соответственно памяти для расчетов хватит.

| Сообщение посчитали полезным:

Ara пишет:
если брать первую с последней, вторую с предпоследней и т.д.
Соответственно памяти для расчетов хватит.
Угу, только вот с нечётными надо что-то придумывать будет.

-----
Всем не угодишь

| Сообщение посчитали полезным:

Bad_guy пишет:
Угу, только вот с нечётными надо что-то придумывать будет.
а ничего там не придумать - условие задачи не совсем корректно, как уже сказал DDA, нельзя простые числа (3,5,7,11...) разделить на кучи с равным кол-вом гирь.

| Сообщение посчитали полезным:

Bad_guy пишет:
А вообще етить в пень все эти гири
И я про то... меня самого этот чел достал, что с задачей доебался

-----
Никогда не делай то, что возможно. Стремись сделать то что невозможно впринципе!

| Сообщение посчитали полезным:

GPcH пишет:
И я про то... меня самого этот чел достал, что с задачей доебался
Ну по чайнику ему гирей массой n=16 кг.

| Сообщение посчитали полезным:

Ara пишет:
Ну по чайнику ему гирей массой n=16 кг.
Лучше в жопу и покрутить

-----
Никогда не делай то, что возможно. Стремись сделать то что невозможно впринципе!

| Сообщение посчитали полезным:

GPcH пишет:
Лучше в жопу и покрутить
А если серьезно - самый лучший выход:это на бабки поспорить (я всегда спорю Сразу желание у чела отпадет. А если не отпадет, то денег на пиво срубишь

| Сообщение посчитали полезным:

Ara пишет:
А если серьезно - самый лучший выход:это на бабки поспорить (я всегда спорю Сразу желание у чела отпадет. А если не отпадет, то денег на пиво срубишь
теперь он меня упрашивает написать ему это... free

-----
Никогда не делай то, что возможно. Стремись сделать то что невозможно впринципе!

| Сообщение посчитали полезным:

GPcH пишет:
теперь он меня упрашивает написать ему это... free
Ну на пиво то полюбому взять надо... это и будет FREE

| Сообщение посчитали полезным:

Ему уже это делают за 600 рублей
Своим он не платит... а чужие с него берут по полной

-----
Никогда не делай то, что возможно. Стремись сделать то что невозможно впринципе!

| Сообщение посчитали полезным:

GPcH пишет:
Ему уже это делают
скоро нечётные гири пилить начнут

-----
Всем не угодишь

| Сообщение посчитали полезным: