Не могу разобраться с алгоритмом деления романа на отдельные тома

@qwert73 · Регистрация: 08.05.2016

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

Помогите разобраться с алгоритмом деления на тома. По какому принципу они делятся?

строки из файла input.txt прочитал и записал в массив. Могу работать со второй строкой как элементами массива типа int. А дальше?

Полный текст задания:

Кликните здесь для просмотра всего текста

Задача 4. Роман

Писатель принес в издательство роман, состоящий из 𝑁 глав. Каждая глава содержала
𝐴𝑖 страниц, 𝑖 = 1..𝑁. Чтобы максимизировать свою прибыль, издательство решило издать
роман в нескольких томах, причем страничный объем всех томов должен быть постоянным.

Писатель при этом выдвинул следующие требования:

1. все главы должны печататься последовательно,
2. каждая глава должна быть полностью напечатана в одном томе,
3. ни одна глава не должна быть напечатана дважды.

Определите, какое максимальное количество томов может выпустить издательство при
том, что роман должен быть издан полностью.

Формат входных данных
В первой строке одно натуральное число 𝑁 (1 ⩽ 𝑁 ⩽ 10000) – количество глав в романе.
Во второй строке 𝑁 целых положительных чисел 𝐴𝑖, 𝑖 = 1..𝑁, через пробел, каждое из которых
обозначает число страниц в 𝑖-ой главе романа. Суммарное число страниц не превышает
100000.

Формат выходных данных
В первой строке одно неотрицательное целое число 𝐾 – максимально возможное количе-
ство томов при издании романа с соблюдением всех условий.

Примеры

input.txt
10
1 2 3 6 3 3 2 2 1 1

output.txt
4

Среда разработки: MS Visual Studio 2013

Прошу расписать ход мысли, возможно с кодом.

@MansMI · 23.07.2016, 21:44

(1 2 3)( 6 )(3 3)( 2 2 1 1) если нет кошерного запрета на рекурсию, то я делал бы ею

@AVIK · 23.07.2016, 22:00

Смотри, во-первых, число страниц в одном томе должно делить общее число страниц => трезвая идея факторизовать число страниц (O(sqrtN)). Теперь отсортируем массив делителей по убыванию и пойдем чекать возможность деления на тома такого размера. Первый подходящий делитель и будет ответом (число страниц, деленное на него).

@qwert73 · 23.07.2016, 22:03 **[ТС]**

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

(1 2 3)( 6 )(3 3)( 2 2 1 1) если нет кошерного запрета на рекурсию, то я делал бы ею

я новичек и еще ниразу не работал с рекурсией на практике, в данном случае как ее можно применить?

@MansMI · 23.07.2016, 22:16

предложение от AVIK разумнее, ищем максимальную главу , и от нее до общей суммы глав ищем толщину тома, чтоб она делила общую сумму без остатка, нашли - пошли по главам, не устраивает - к следующей толщине

@Qulac · 23.07.2016, 22:27

qwert73, максимальное количество томов нам известно, сумма страниц тоже, можем рассчитать толщину тома. Рассчитали, проверили, если нет, повторяем для N-1 и так пока не найдем.

@MansMI · 23.07.2016, 22:50

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    ifstream fin("input.txt");
    int n;
    fin>>n;
    int *a=new int[n];
    int tm,nv;
    for(int i=0; i<n; i++)
    {
        fin>>a[i];
        if(!i) tm=nv=*a;
        else
        {
            if(a[i]>tm) tm=a[i];
            nv+=a[i];
        }
    }
    fin.close();
    for(; tm<=nv; tm++)
    if(nv%tm==0)
    {
        int g=0;
        do
        {
            int sm=0;
            for(; g<n && sm<tm; g++) sm+=a[g];
            if(sm>tm) break;
        }while(g<n);
        if(g==n)
        {
            cout<<"tm="<<tm<<" nt="<<nv/tm<<endl;
            break;
        }
    }
    delete[] a;

@qwert73 · 23.07.2016, 22:58 **[ТС]**

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

Смотри, во-первых, число страниц в одном томе должно делить общее число страниц => трезвая идея факторизовать число страниц (O(sqrtN)). Теперь отсортируем массив делителей по убыванию и пойдем чекать возможность деления на тома такого размера. Первый подходящий делитель и будет ответом (число страниц, деленное на него).

я неуверен, но вроде в таком случае не учитывается то, что размер каждого тома должен быть одинаковым ("постоянным") ? Например, последний(или один из предыдущих) том будет содержать одинаковый со всеми страничный объем, но не наполнен полностью. Или такого не может произойти?

@AVIK · 23.07.2016, 23:02

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <set>
#include <iterator>
#include <vector>
#include <string>
#include <numeric>
 
#define DEBUG
int main(void)
{
    int N;
    std::cin >> N;
    std::vector< int > V(N);
    for (int i = 0; i < N; i++)
        std::cin >> V[i];
 
    int length = std::accumulate(V.begin(), V.end(), 0);
 
    std::set< int > divisors;
    for( int i = 1; i * i <= length; i++ )
        if (length % i == 0)
        {
            divisors.insert(i);
            divisors.insert(length / i);
        }
 
    std::set< int > prefix_sum;
    int buffer = 0;
    for (int i = 0; i < N; i++)
    {
        buffer += V[i];
        prefix_sum.insert(buffer);
    }
 
    for (std::set< int >::iterator it = divisors.begin(); it != divisors.end(); it++)
    {
        bool flag = true;
        for (int i = 1; i * (*it) <= length; i++)
            if (prefix_sum.find(i * (*it)) == prefix_sum.end())
            {
                flag = false;
                break;
            }
        if (flag)
        {
            std::cout << length / *it << std::endl;
            break;
        }
    }
    return 0;
}

@MansMI · 23.07.2016, 23:05

так правильнее

C++
1
2
3
4
5
6
..................
        }while(g<n);
        if(g==n) break;
    }
    delete[] a;
    cout<<"tm="<<tm<<" nt="<<nv/tm<<endl;

IGPIGP · 24.07.2016, 01:24

qwert73, мне условие кажется странным. Вот эта фраза не красит математиков составивших условие:

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

страничный объем всех томов должен быть постоянным.

Правила русского языка говорят, что эта фраза требует, чтобы суммарный объём страниц всех томов не изменялся. Но в промежутке между выпуском книг и их продажей, их могут испортить грызуны, активные библиофобы и злые буратины. Иначе он и так будет постоянен.
Вы трактуете эту фразу так, как если бы она была: "страничный объем у всех томов должен быть одинаков" или "страничные объемы у всех томов должны быть равны".
Ну допустим с языком и логикой у составителей задачи не сложилось. Бывает. Но ещё интереснее то, что в жизни, практически, не бывает так, чтобы книгу можно было разделить, хотя бы на две части из равного количества страниц, соблюдая очерёдность и завершённость глав, а так же уникальность контента. Если не играть с ~~гирями~~ кеглями. То есть, если не менять шрифты, интервалы, не варьировать размеры и количество картинок (графики) и пр. Но если это разрешить, то томов становится столько, сколько глав и это значит, что такое разрешение не конструктивно.
Для ряда в Вашей задаче: 123633221, группировка 6 6 6 6 возможна. Но данное условие очень искусственно. Оно уже само и есть решение, нужно только набирая группу с головы (можно и из другого места), подыскивать следующую, равную по объёму. Начинаем с единицы и идем, пока не встретим невозможную следующую. Встретили, - возвращаемся к началу и увеличиваем количество глав на 1. Пока не сойдётся до конца.
Ваш пример:
1)в группу A берём первую главу (объём 1 стр.)
2)в группу B берём вторую главу (объём 2 стр.)
Проверяем равенство объёмов A==B -false и B>A (то есть наращивая B нельзя ничего исправить).
Возвращаемся:
1)в группу A берём первую главу (объём 1 стр.) и вторую главу (объём 2 стр.) итого объём A=3 (1+2)
2)в группу B берём третью главу (объём 3 стр.)
Проверяем равенство объёмов A==B -true
3)составляем группу С из 4-й главы. Объём 6 и это больше A/B (эти одинаковы), что снова возвращает нас к началу.
4)группу А составляем из 1-й, 2-й и 3-й глав и получаем объём 6 (вот она - струя)) теперь, о чудо, нам будет везти во всём и до конца. Чего в жизни не бывает.
Обидно, что люди сочиняют такие задачи. Убогость воображения просто подавляет и хочется крикнуть:-"Посмотрите кругом люди! Вся жизнь, - просто одна сплошная задача, состоящая из задач и не нужно ставить её и её задачи в такие положения! Они уже и так стоят как нужно!". Но бесполезно.
Всё же рекомендую предусмотреть случай, когда решение задачи невозможно. Например при таком наборе: 1,2,7,25.
В наше время такое не задавали. Вот почему, современных студентов мне особенно жаль. Удачи Вам и терпения, qwert73.

@Mr.X · 24.07.2016, 01:56

C++

///////////////////////////////////////////////////////////////////////////////
//Задача 4. Роман
//Писатель принес в издательство роман, состоящий из 

		
		
		
		
		
		
		
		
		
		

		
			
				
    
        
            
            1

qwert73

1 / 1 / 0

Регистрация: 08.05.2016

Сообщений: 14

25.07.2016, 01:34 [ТС]

Что означает вот эта строка (68) ?

Сообщение от Mr.X

for( auto volume_size : chapter_sizes_partial_sums )

0

Mr.X

3225 / 1752 / 436

Регистрация: 03.05.2010

Сообщений: 3,867

25.07.2016, 02:35

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

Что означает вот эта строка (68) ?

C++
1
for( auto volume_size : chapter_sizes_partial_sums )

В каком смысле?

0

qwert73

1 / 1 / 0

Регистрация: 08.05.2016

Сообщений: 14

25.07.2016, 02:46 [ТС]

Сообщение от Mr.X

В каком смысле?

Я не понимаю как это вообще прочитать. что за условие внутри? что обозначает " : "?

0

0x90h

693 / 465 / 162

Регистрация: 01.10.2015

Сообщений: 1,274

25.07.2016, 03:01

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

что за условие внутри? что обозначает " : "?

Это диапазонный цикл for - новая форма цикла for, введена стандартом С++11, перебирает все элементы в заданном массиве, диапазоне или коллекции. В других языках подобная форма цикла часто называется foreach

Будет выполнен для каждого элемента volume_size (тип которого компилятором будет выведен автоматически, тоже новшество C++11), из множества chapter_sizes_partial_sums

0

Mr.X

3225 / 1752 / 436

Регистрация: 03.05.2010

Сообщений: 3,867

25.07.2016, 03:01

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

Я не понимаю как это вообще прочитать. что за условие внутри? что обозначает " : "?

А, это новый for из С++11.

0

qwert73

1 / 1 / 0

Регистрация: 08.05.2016

Сообщений: 14

25.07.2016, 03:30 [ТС]

Сообщение от Mr.X

А, это новый for из С++11.

Ну ок, я в равно не могу разобраться как это работает. с новым for разобрался, думал это поможет мне понять в чем дело, но нет. Взаимосвязь кое как понял, а вот что что конкретно выполняют целые блоки volumes_total_max и особенно volume_size_is_right непойму. да и вообще что это? функция? класс? объект? метод?

Добавлено через 8 минут
Прошу прощения за тупые вопросы если они таковыми кажутся, мне бы вообще свой код научиться писать прежде чем читать чужой.

0

Mr.X

3225 / 1752 / 436

Регистрация: 03.05.2010

Сообщений: 3,867

25.07.2016, 07:56

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

Ну ок, я в равно не могу разобраться как это работает. с новым for разобрался, думал это поможет мне понять в чем дело, но нет. Взаимосвязь кое как понял, а вот что что конкретно выполняют целые блоки volumes_total_max и особенно volume_size_is_right непойму. да и вообще что это? функция? класс? объект? метод?

Ну, по условию первый том включает несколько первых глав романа, т.е. его размер - это одна из частичных сумм исходного ряда, а так как размеры всех томов равны, то это справедливо и для искомого размера t тома.
Следовательно нам достаточно пробежаться по всем частичным суммам и выбрать из них наименьшую подходящую.
По условию первые k томов также включают несколько первых глав романа, т.е. величина kt тоже по условию является частичной суммой.
Следовательно размер t тома является подходящим, если величина kt присутствует среди частичных сумм исходного ряда при любом допустимом k.

0

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

25.07.2016, 07:56

Помогаю со студенческими работами здесь

Задали работу, не могу разобраться. Используется делфи 10, не могу разобраться, как это сделать
В одномерном массиве, состоящем из n вещественных элементов, вычислить: минимальный элемент массива и сумму элементов массива,...

Помогите разобраться с A алгоритмом
Не могу понять работу с А алгоритмом поиска путей, а именно - как сделать так, чтобы алгоритм перебирал все возможные пути и делал это...

Разобраться с алгоритмом задачи
Помогите разобраться с алгоритмом, как работает программа. Я понимаю что здесь 38 перестановок. Но мне нужно знать как именно работает эта...

Жесткий диск разделен на 2 тома, как разделить его на 3 тома?
Всем привет!!! У меня такой вопрос: размер HDD составляет 250 Гб, он разделен и состоит из С: 25,3 Гб, Е: 152Гб, а где увидеть остальные...

Внешний HDD, не могу поделить на тома
Здравствуйте. Имею внешний хард на 1 TB, Seagate Backup Slim. Хочу вынуть его из корпуса и вставить в ноут дополнительно к SDD с системой,...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

19

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

Наверх

Не могу разобраться с алгоритмом деления романа на отдельные тома

Решение

Решение

@qwert73 1 / 1 / 0 Регистрация: 08.05.2016 Сообщений: 14

	Не могу разобраться с алгоритмом деления романа на отдельные тома 23.07.2016, 21:16. Показов 2793. Ответов 18 Метки нет (Все метки) Помогите разобраться с алгоритмом деления на тома. По какому принципу они делятся? строки из файла input.txt прочитал и записал в массив. Могу работать со второй строкой как элементами массива типа int. А дальше? Полный текст задания: Кликните здесь для просмотра всего текста Задача 4. Роман Писатель принес в издательство роман, состоящий из 𝑁 глав. Каждая глава содержала 𝐴𝑖 страниц, 𝑖 = 1..𝑁. Чтобы максимизировать свою прибыль, издательство решило издать роман в нескольких томах, причем страничный объем всех томов должен быть постоянным. Писатель при этом выдвинул следующие требования: 1. все главы должны печататься последовательно, 2. каждая глава должна быть полностью напечатана в одном томе, 3. ни одна глава не должна быть напечатана дважды. Определите, какое максимальное количество томов может выпустить издательство при том, что роман должен быть издан полностью. Формат входных данных В первой строке одно натуральное число 𝑁 (1 ⩽ 𝑁 ⩽ 10000) – количество глав в романе. Во второй строке 𝑁 целых положительных чисел 𝐴𝑖, 𝑖 = 1..𝑁, через пробел, каждое из которых обозначает число страниц в 𝑖-ой главе романа. Суммарное число страниц не превышает 100000. Формат выходных данных В первой строке одно неотрицательное целое число 𝐾 – максимально возможное количе- ство томов при издании романа с соблюдением всех условий. Примеры input.txt 10 1 2 3 6 3 3 2 2 1 1 output.txt 4 Среда разработки: MS Visual Studio 2013 Прошу расписать ход мысли, возможно с кодом. 0

@MansMI 1617 / 1182 / 553 Регистрация: 08.01.2012 Сообщений: 4,561
	23.07.2016, 21:44
	(1 2 3)( 6 )(3 3)( 2 2 1 1) если нет кошерного запрета на рекурсию, то я делал бы ею 0

@AVIK 13 / 13 / 5 Регистрация: 02.01.2014 Сообщений: 60
	23.07.2016, 22:00
	Смотри, во-первых, число страниц в одном томе должно делить общее число страниц => трезвая идея факторизовать число страниц (O(sqrtN)). Теперь отсортируем массив делителей по убыванию и пойдем чекать возможность деления на тома такого размера. Первый подходящий делитель и будет ответом (число страниц, деленное на него). 0

@MansMI 1617 / 1182 / 553 Регистрация: 08.01.2012 Сообщений: 4,561
	23.07.2016, 22:16
	предложение от AVIK разумнее, ищем максимальную главу , и от нее до общей суммы глав ищем толщину тома, чтоб она делила общую сумму без остатка, нашли - пошли по главам, не устраивает - к следующей толщине 0

@Qulac 4 / 4 / 1 Регистрация: 16.12.2014 Сообщений: 14
	23.07.2016, 22:27
	qwert73, максимальное количество томов нам известно, сумма страниц тоже, можем рассчитать толщину тома. Рассчитали, проверили, если нет, повторяем для N-1 и так пока не найдем. 0