Школьная олимпиадная задача

[GreenMan]

Доброго времени суток! Вчера проходил первый этап Всероссийской олимпиады школьников по информатике, наткнулся на вот такую задачку, но никак не смог её решить... http://savepic.su/2946051.htm
Я додумался лишь, что если ребят больше, чем грядок, то оптимальным будет время, предоставляющееся для вскапывания самой большой грядки (кэп не дремлет лол).

...
var ... {не заполнил, т.к. не решил до конца}
begin
assign(input,'input.txt');
reset(input);
readln(n,k); {прочитали n - число грядок, k - число ребят}
for i:=1 to n do {читаем время, выделяемое каждой грядке в отдельности}
  read(a[i]);
if k>=n 
  then 
    begin
    max:=0;
    for i:=1 to n do
      begin
      if a[i]>max
        then max:=a[i];
      end;
    assign(output,'output.txt');
    rewrite(output);
    write(max); {если число работников больше/равно числу грядок, то выводим максимальный элемент массива с временем грядок}
    close(output);
    end
    else ...

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

[Poma][a]

Давайте разберем 1 пример :
5 3
3 5 8 2 7

1) Отсортируем массив по возрастанию (не убыванию)
Получим 2 3 5 7 8
2) Всего у нас 3 рабочих, наградим их самыми большими грядками тоесть 5 7 8
3) Остались n-k грядок. Теперь Рабочему n-1 прибавим 1 грядку, n-2 прибавим 2 грядку, n - i'тому рабочему прибавим еще i грядку. И когда i станет > n-k закончим выполнение.
4) Теперь бежим по массиву с рабочеми и ищем наибольшее значение.
Вот собственно и всё.
Уж простите, что в словесной форме, но с этой школой времени почти нет... Возможно(маловероятно) что ближе к ночи выложу код..

[Poma][a]

Эх, да задали Вы задачку человеку на День Рождения Банкета как не бывало

type
        TArr = array [1..10000] of LongInt;
procedure Swap (var a, b : LongInt);

var
	t : LongInt;

begin
	t := a;
	a := b;
	b := t;
end;


procedure SortArr (var a : TArr; const n : LongInt);

var
	i, j : LongInt;

begin
	for i := 1 to n-1 do
		for j := 1 to n-i do
			if a[j] > a[j+1] then
				Swap (a[j], a[j+1]);
end;

var
        a : TArr; // грядки
        b : array [1..1000] of Integer; // рабы
        n, k, i, j, count, max : LongInt; // k использовать как натуральное число - это ересь

begin
        ReadLn (n, k);

        for i := 1 to n do
                ReadLn (a[i]);

        SortArr (a, n);

        i := 1;
        while (i <= k) and (i <= n) do begin
                b[i] := a[n-i+1];
                Inc (i)
        end;

        count := 0;
        for i := n-k downto 1 do
                b[i+1] := b[i+1] + a[i];

        max := b[1];

        for i := 1 to k do
                if b[i] > max then
                        max := b[i];

        WriteLn (max)
end.

Вроде так. Удачи

[GreenMan]

Оооо, спасибо огромное!!! Разобрался, все ок! Ещё раз спасибо
пы.сы. ну и с днем рождения прошедшим уже

[Poma][a]

Пожалуйста Потом отпишитесь пожалуйста, как сдали
P.S. Спасибо

[TinMan]

Всем привет,
а задачка неплохая! ))
Ромаха, твоя прога на вот таких данных:
4 2
1 50 98 100
- выдает результат 100. Боюсь, это не совсем верно ). Да и вообще, я не вижу, где твоя прога учитывает то, что каждому рабочему можно давать только смежные грядки. Ты их сортируешь сразу - и благополучно забываешь изначальный порядок..

Я навскидку применил самый обычный лом - рекурсию )). Но я не уверен, пролезет ли рекурсивное решение по времени при больших n.

const
  m= 100;

var
  t: array[1..m] of int64;

function Max(a,b: int64): int64;
begin
  if a<=b then Max:= b else Max:= a
end;

function Min(a,b: int64): int64;
begin
  if a<=b then Min:= a else Min:= b
end;

function Opt(n,k: integer): int64;
var
  s,x: int64;
  i: integer;
begin
  s:= 0;
  if k=1 then begin
    for i:=1 to n do s:= s+t[i];
    Opt:= s
  end
  else begin
    s:= 0;
    x:= High(int64);
    for i:=n downto k do begin
      s:= s+t[i];
      x:= Min(x,Max(s,Opt(i-1,k-1)))
    end;
    Opt:= x
  end
end;

var
  i,k,n: integer;

begin
  readln(n,k);
  for i:=1 to n do read(t[i]);
  if k>n then k:= n;
  writeln(Opt(n,k));
  readln
end.

Тестировал не очень тщательно, возможны ошибки.

[Poma][a]

TinMan, Вы вернулись! Ура.Ура.Ура!!!!

P.S. Ага, как-то я проморгал что грядки можно давать только последовательно...

[Poma][a]

Хорошо, а если так :

while n >  k do begin
      Ищем минимум;
      Сравниваем a[min-1] и a[min+1];
      И наименьшее число из сравниваемых(см.строку выше) прибавляем a[min];
      Сдвигаем массив;
      Dec (n)
end;

Но вдруг где-нить встретим не одно минимальное, а m минимальных грядок (тогда надо искать минимум уже среди соседей этих минимумов....)

Вообщем это как вариант, но очень накладно...

P.S. Не проверял
P.P.S. И уж сори что в таком виде просто очень, преочень нет времени (у самого командная дистанционная олимпиада...)

[New man]

TinMan, ваша программа должна выдавать ошибку при k > n

[Poma][a]

должна выдавать ошибку

а почему? и какую ошибку? компиляции? и у Вас есть какой-то контрпример? у меня никакую ошибку не выдаёт...