9062. Поедание булочек

 

Кратос и Атрей решили поесть булочек. Чтобы разнообразить процесс, Кратос приготовил 2k булочек и предложил устроить соревнование по скоростному поеданию.

И Кратос и Атрей будут есть по k булочек. Все закончилось также быстро, как и началось. Фрейя тайно наблюдала за этим состязанием и заметила несколько особенностей:

·        Оба участника состязания съели ровно по k булочек.

·        За одно действие Кратос либо Атрей съедали либо одну, либо две булочки.

·        Каждый раз, когда кто-то из них делал действие, он записывал сколько булочек съедал.

 

После того, как Кратос с Атреем ушли, Фрейя нашла их “протокол”. К сожалению, для каждого действия записано, сколько булочек было съедено, но не записано, кто именно их ел.

Фрейя помнит, что Кратос в некоторый момент состязания выглядел безоговорочным лидером, так как съел булочек сильно больше чем Атрей. Она просит Вас по данному протоколу определить, какой наибольший отрыв мог быть у Кратоса на протяжении состязания.

 

Вход. В первой строке заданы два целых числа n и k (2 ≤ n ≤ 105, 1 ≤ k ≤ n) – число записей в протоколе и число булочек, съеденных каждым из участников.

Во второй строке заданы n чисел ai (1 ≤ ai ≤ 2) – данные протокола. Гарантируется, что протокол корректен: можно разделить ai на два множества так, чтобы сумма чисел в обоих множествах была равна k.

 

Выход. Выведите одно целое число – наибольший отрыв Кратоса на протяжении состязания.

 

Пример входа

Пример выхода

3 2

1 2 1

1

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Ответ равен k, если только сначала Кратос съел все свои k булочек, после чего все свои булочки съел Атрей. Если существует частичная сумма, равная k, то имеет место этот случай и ответ равен k.

Иначе всегда можно организовать такое поедание булочек, при котором ответ равен k – 1. В этом случае существует частичная сумма, равная k – 1, и этих всех начальных k – 1 булочек должен съесть Кратос. Именно в этот момент отрыв Кратоса составит k – 1. Дальше по протоколу следует число 2, две булочки съедает Атрей. И в дальнейшем отрыв Кратоса от Атрея уже никак не сможет быть больше k – 2.

 

Реализация алгоритма

Читаем входные данные.

 

scanf("%d %d", &n, &k);

 

В переменной s вычисляем частичные суммы.

 

s = 0;

for (i = 0; i < n; i++)

{

  scanf("%d", &val);

  s += val;

 

Если частичная сумма в некоторый момент равна k, то ответ на задачу k.

 

  if (s == k)

  {

    printf("%d\n", k);

    return 0;

  }

}

 

Иначе выводим ответ k – 1, который всегда можно достигнуть.

 

printf("%d\n", k - 1);