In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Prace wykończeniowe w nowym domu Bajtazara dobiegają
końca.
Pozostało tylko wkręcić po jednej żarówce w każdym z
pokoi.
Dla każdego pokoju ustalił minimalną moc żarówki,
która dostatecznie dobrze oświetli ten pokój.
Bajtazar kupił żarówek, lecz teraz zauważył, że nie
spełniają one do końca jego oczekiwań.
Być może nie jest możliwe dobre doświetlenie wszystkich
pokoi, a być może niektóre żarówki niepotrzebnie mają tak dużą moc.
Bajtazar postanowił więc wybrać się do sklepu i wymienić
niektóre żarówki, tak aby móc wystarczająco oświetlić wszystkie pomieszczenia,
a jednocześnie jak najbardziej ograniczyć łączną moc żarówek.
Sklep dysponuje żarówkami o dowolnych dodatnich mocach.
Plecak Bajtazar pozwala zabrać na wymianę co najwyżej
żarówek -
jest to maksymalna liczba żarówek, które gotów jest wymienić.
Pomóż Bajtazarowi wybrać, które żarówki należy wymienić na inne, tak aby wszystkie pokoje były wystarczająco oświetlone i jednocześnie by maksymalnie ograniczyć łączną moc żarówek.
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
i
(
), oznaczające
odpowiednio liczbę pokoi (jest to jednocześnie liczba żarówek)
oraz liczbę żarówek, które można zmieścić w plecaku Bajtazara.
Pokoje są ponumerowane od
do
.
W drugim wierszu wejścia znajduje się
liczb całkowitych
(
) oznaczających moce żarówek, które aktualnie posiada Bajtazar.
W trzecim wierszu wejścia znajduje się
liczb całkowitych
(
) oznaczających
wymagania dotyczące oświetlenia w kolejnych pokojach -
w pokoju
należy wkręcić żarówkę o mocy co najmniej
.
Jeśli nie da się tak wymienić co najwyżej żarówek, by wszystkie pokoje były
dostatecznie oświetlone, na wyjście należy wypisać NIE.
W przeciwnym wypadku należy wypisać jedną liczbę całkowitą,
oznaczająca minimalną sumaryczną moc wszystkich żarówek użytych
do oświetlenia domu po wymianie co najwyżej
żarówek.
Dla danych wejściowych:
6 2 12 1 7 5 2 10 1 4 11 4 7 5
poprawną odpowiedzią jest:
33
Wyjaśnienie do przykładu:
Wystarczy wymienić żarówkę o mocy na żarówkę o mocy
oraz żarówkę o mocy
na żarówkę o mocy
.
Wówczas prawie wszystkie pokoje będą miały żarówki o dokładnie takiej mocy jak minimalne wymaganie.
Wyjątkiem będzie pokój, który wystarczyłoby oświetlić żarówką o mocy
, który zostanie oświetlony żarówką
o mocy
.
Autor zadania: Adam Karczmarz.