In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W ostatnim czasie mieszkańcy Bajtocji zaczęli podróżować częściej niż
dotychczas. Przedsiębiorczy Bajtazar wpadł na pomysł otwarcia biura
podróży. Już pierwszego dnia urzędowania do biura zgłosiło się klientów
(na potrzeby naszego zadania możemy ich ponumerować liczbami
naturalnymi od
do
), którzy chcą pojechać na wycieczkę.
Niestety każdy z nich ma swoje wymagania.
Twoim zadaniem jest pomóc Bajtazarowi w wybraniu klientów, którzy pojadą na wycieczkę, tak aby zmaksymalizować zysk Bajtazara.
Każdy klient określił, ile wynosi dla niego wartość wycieczki organizowanej przez
Bajtazara. Niech będzie taką wartością dla klienta
(
).
Jeśli
, to klient
zapłaci
bajtockich dolarów,
aby pojechać na wycieczkę, jeśli natomiast
,
to aby klient
pojechał na wycieczkę, Bajtazar musi mu
dopłacić
bajtockich dolarów.
Klienci oprócz wymagań finansowych posiadają również wymagania towarzyskie.
Klient ma
(
) takich wymagań,
-te wymaganie
-tego klienta jest reprezentowane przez parę
liczb całkowitych (
)
(
).
Wymaganie to należy rozumieć tak, że aby klient
pojechał na wycieczkę, to na wycieczkę musi pojechać również klient
lub koszt wycieczki dla klienta
musi zostać obniżony o
bajtockich dolarów (może się zdarzyć, że koszt wycieczki dla pewnych klientów
z dodatniego stanie się ujemny, co spowoduje, że Bajtazar będzie musiał dopłacić tym
klientom, żeby wzięli oni udział w wycieczce, rekompensując tym samym brak zaspokojenia
ich wymagań towarzyskich).
Pomóż Bajtazarowi wybrać grupę klientów, których ma zabrać na wycieczkę, tak aby zmaksymalizować jego zysk (liczba miejsc na wycieczce jest nieograniczona).
Dysponujesz jedenastoma zestawami danych, które możesz ściągnąć stąd.
Każdy zestaw jest zapisany w osobnym pliku biu.in, gdzie
to numer zestawu (
). Rozwiązaniem zadania powinien być
program, który wczytuje ze standardowego wejścia jedną liczbę
całkowitą
, i wypisuje na standardowe wyjście
odpowiedź dla
-tego zestawu.
Rozwiązanie zestawu biu0.in nie jest
punktowane.
W pierwszym wierszu odpowiedzi powinna się znajdować dokładnie jedna liczba całkowita (
)
- liczba klientów, których Bajtazar powinien zabrać na wycieczkę.
Jeśli liczba
jest dodatnia, w drugim wierszu powinno się znaleźć
liczb całkowitych, oddzielonych pojedynczymi odstępami,
będących numerami klientów, których Bajtazar powinien zabrać na wycieczkę.
Jeśli istnieje wiele optymalnych rozwiązań to możesz podać dowolne z nich.
Numery klientów mogą być umieszczone w wyjściu w dowolnej kolejności.
W pierwszym wierszu znajduje się dokładnie jedna liczba całkowita (
)
oznaczająca liczbę klientów biura podróży.
W kolejnych
wierszach opisani są poszczególni klienci.
W
-wszym wierszu (
) znajdują się liczby całkowite
(
) oraz
(
),
a za nimi
par liczb całkowitych
,
(
)
- wszystkie liczby w wierszu
oddzielone są pojedynczymi odstępami. Możesz założyć, że każdy klient ma co najwyżej
jedno wymaganie towarzyskie dotyczące dowolnego innego klienta.
4 5 0 6 2 1 10 3 1 -10 0 1 2 1 10 2 10poprawną odpowiedzią jest:
3 1 2 4
Jeśli Bajtazar wybierze klientów , to osiągnie zysk
bajtockich dolarów,
co jest rozwiązaniem optymalnym.
Autor zadania: Marek Cygan.