Задача "Роман в томах"

[Poma][a]

uses Math;
var a : array[1..100] of word;
    s, m, i, j, N, K, x : word;
begin
   Reset(input,'input.txt'); assign (output, 'output.txt');
   Read(N);
   for i := 1 to N do begin
      Read(a[i]); s := s + a[i]
   end;
   Read(K);
   m := Ceil(s/K);
   i := 1;
   for j := 1 to K - 1 do begin
      s := a[i];  i := i + 1;
      while (((m - s) >= ((a[i] div 2) + 1)) AND (i < N)) do begin
         s := s + a[i];  i := i + 1
      end;
       if x < s then
         x := s;
   end;
   m := a[i];
   for j := i + 1 to N do
      m := m + a[j];
   Write(Max(x, m));
end.

355 Wrong Answer на 4 тесте..

[ViktorR]

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



Как-то так, ...

[Poma][a]

При сильной ассиметрии решение, с таким алгоритмом, можно и не получить.

Ага..

Кстати, про Вашу "неизвестность".. Слева в "информации" ищем "паспорт", тыкаем на него и будет Вам счастье

Кстати, наверное, можно создать "общефорумный аккаунт" с "общефорумной почтой" и слить туда все существующие решения для всех задач, которые обсуждались..

[Poma][a]

А можно я аппну тему? Спасибо..

Всё же с задачей я, видимо, разобрался не до конца..
Посему прошу намекнуть..
Очевидно, что при S(n, 1) ответом будет являться a[1]+a[2]+..+a[n]
А что делать при S(n, 2)? При S(n, 3)
Я прошу не давать готовых решений и формул.. Я сам хочу до конца разобраться с задачей.. Не могли бы подсобить? Спасибо

[Poma][a]

Могу предложить такое решение..
Только все же интересен момент с формулой..

#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
 
using namespace std;
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
int n, k;
vector<int> v;
 
bool solution_exist(int m)
{
    int j = 1, sum = 0;
 
    for (int i = 0; i < n && j <= k; i)
    {
        int t = sum + v[i];
 
        if (t > m)
        {
            j++; sum = 0;
        }
        else
            sum += v[i++];
    }
 
    return j <= k;
}
 
int main()
{
    cin >> n;
     
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        v.push_back(t);
    }
 
    cin >> k;
 
    int left = *(max_element(v.begin(), v.end()));
    int right = accumulate(v.begin(), v.end(), 0);
     
    while (left != right)
    {
        int m = left + (right - left) / 2;
        if (solution_exist(m))
            right = m;
        else
            left = m + 1;
    }
 
    cout << left;
}