Задача B Підрахунок голосів Pascal програма

Львівська районна учнівська олімпіада з інформатики 2015

Задача B Підрахунок голосів

О восьмій годині вечора всі виборчі дільниці зачиняються, і виборчі комісії починають підрахунок голосів. Розглянемо процес підрахунку голосів деякою виборчою комісією. Нехай в ній присутній Голова комісії та N членів комісії (без голови). Також нехай на виборчій дільниці всього є M урн для голосування. Кожна урна має свій унікальний номер (ціле число від 1 до M). Відомо, що урна з номером i містить ai бюлетенів. Отож, члени комісії сідають за великий стіл, а Голова комісії розподіляє їм урни для підрахунку голосів. Кожен член комісії отримає деяку кількість урн, при чому номери цих урн повинні йти підряд. Тобто член комісії може отримати урни з номерами (4, 5, 6, 7), або (1, 2, 3), але не може отримати урни з номерами (4, 7, 47). Після розподілу може статися так, що деяка кількість членів виборчої комісії залишиться без роботи — їм не дістанеться жодної урни. Ваше завдання — знаючи максимальну кількість бюлетенів K, яку може порахувати один член комісії, сказати, яка максимально можлива кількість членів комісії може залишитися без роботи.

Вхідні дані: Перший рядок містить три натуральні числа: кількість членів комісії N, кількість урн для голосування M, та максимальну кількість бюлетенів, які може порахувати один член комісії K. Другий рядок містить M натуральних чисел ai — кількості бюлетенів в урнах.

Вихідні дані: Одне ціле невід’ємне число — максимально можлива кількість членів комісії, що залишиться без роботи, або «-1» (без лапок), якщо членів комісії не вистачить, щоб порахувати всі бюлетні. Обмеження: 1 ≤ N, M ≤ 100 000 1 ≤ ai ≤ K ≤ 1 000 000 000

Приклад вводу: 7 4 11 7 4 8 5

Приклад виводу: 4

Підказка: Першому члену комісії дістануться урни з 7 і 4 бюлетенями, другому дістанеться урна з 8 бюлетенями, третьому дістанеться урна з 5 бюлетенями. Решта членів комісії залишаться без роботи.

program  b;
var a: array [1..100000] of integer;
n,m,k,i,s:integer;
begin
readln(n,m,k);
for i:=1 to m do
read(a[i]);
s := 0;
for i:= 1 to m do
begin
s := s + a[i];
if s = k then begin n:= n-1; s:=0 end;
if (s < k) and ((s+a[i+1])=k) then begin n:= n -1; s:= 0;end;
if (s < k) and ((s+a[i+1])>k) then begin n:= n-1; s :=0 end;
if (s < k) and (a[i+1]=0) then begin n:= n-1 end;
end;

if n<0 then writeln(-1) else writeln(n);
end.

Comments

comments

Ви можете залишити коментар

Залишити коментар


− п'ять = 4