Su (Həll təhlili)

Əgər hansısa bidonun həcmi $k$-dan böyükdürsə, o zaman bütün suyu evə aparmaq mümkün deyil, "Impossible" çıxış edin.

Bidonları həcmlərinə görə artan sıraya düzün. Ən böyük bidonu ən kiçik bidon ilə birlikdə aparmağa çalışın. Əgər bu mümkün deyilsə, onda ən böyük bidonu tək aparmaq lazımdır. Əgər mümkündürsə, ən böyük və ən kiçik bidonu çıxaraq prosesi qalan bidonlar üçün eyni qaydada davam etdirin.

Misal

Tapşırıqda verilən misalı nəzərdən keçirdək. Mövcud bidonların həcmləri: 1, 2, 3, 3. Sergey bir dəfədə k = 4 litrdən çox su apara bilmir. Ən kiçik və ən böyük bidonun həcmlərinin cəmi 1 + 3 = 4-ə bərabərdir ki, bu da $k$-dan böyük deyil. Beləliklə Sergey ilkin olaraq bu iki bidonu aparacaq.

Qalan bidonlar $2$ və $3$. Ən kiçik və ən böyük bidonun həcmlərinin cəmi 2 + 3 = 5-ə bərabərdir ki, bu da $k$-dan böyükdür. Beləliklə ikinci dəfədə ən böyük bidonu tək aparmaq lazımdır.

Üçüncü dəfədə Sergey sonuncu $2$ litr həcmli bidonu evə aparacaq.

Alqoritmin reallaşdırılması

Bidonların həcmlərini $m$ massivində saxlayırıq.

vector<int> m;

Giriş məlumatlarını oxuyuruq.

v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Bidonların həcmlərini sırayla düzürük.

sort(v.begin(), v.end());

Su üçün gedişlərin sayını $res$ dəyişənində qeyd edirik.

res = 0;

İki göstərici təyin edirik: $a$ massivə başlanğıcını, $b$ — sonunu göstərsin.

a = 0; b = v.size() - 1;

Əgər ən böyük bidon $k$-dan böyükdürsə, bütün suyu aparmaq mümkün deyil.

if (v[b] > k)
{
  printf("Impossible\n"); return 0;
}

Suyu daşıyırıq.

while (a <= b)
{

Əgər ən kiçik və ən böyük bidonun həcmlərinin cəmi $k$-dan böyükdürsə, onda bir dəfədə yalnız ən böyük bidonu apara bilirik.

  if (v[a] + v[b] > k) b--;

Əks halda, iki bidonu aparırıq: ən kiçik və ən böyük.

  else { a++; b--; }

Su üçün bir gediş artıq.

  res++;
}

Nəticə çıxarırıq.

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

Python reallaşdırılması

import sys

Giriş məlumatlarını oxuyuruq.

n, k = map(int, input().split())
v = list(map(int, input().split()))

Bidonların həcmlərini sırayla düzürük.

v.sort()

Su üçün gedişlərin sayını $res$ dəyişənində qeyd edirik.

res = 0

İki göstərici təyin edirik: $a$ massivə başlanğıcını, $b$ — sonunu göstərsin.

a = 0
b = len(v) – 1

Əgər ən böyük bidon $k$-dan böyükdürsə, bütün suyu aparmaq mümkün deyil.

if v[b] > k:
  print("Impossible")
  sys.exit(0)

Suyu daşıyırıq.

while a <= b:

Əgər ən kiçik və ən böyük bidonun həcmlərinin cəmi $k$-dan böyükdürsə, onda bir dəfədə yalnız ən böyük bidonu apara bilirik.

  if v[a] + v[b] > k:
    b -= 1
  else:

Əks halda, iki bidonu aparırıq: ən kiçik və ən böyük.

    a += 1
    b -= 1

Su üçün bir gediş artıq.

  res += 1

Nəticə çıxarırıq.

print(res)