Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Czarny market ( A) Limit pamięci: 256 MB Limit czasu: 1.00 s Znany w podziemiu netrunner o pseudonimie Bajtazar stworzył absolutnie przełomowy exploit (tzw. B-day), który pozwala na ominięcie ICE największych megakorporacji. Bajtazar postanowił zmonetyzować swoje dzieło i sprzedawać do niego dostęp w modelu subskrypcyjnym na anonimowym forum w Barknecie. Na forum znajduje się N potencjalnych kupców. Każdy z nich ma swój określony budżet i jest w stanie zapłacić maksymalnie ci kryptokredytów za dostęp. Bajtazar musi ustalić jedną sztywną cenę P dla wszystkich. Jeśli ustalona cena będzie wyższa niż maksymalny budżet danego kupca (P > ci), ten zrezygnuje z zakupu. W przeciwnym razie kupiec nabywa subskrypcję. Bajtazar chce ustalić taką cenę P, aby zsumowany zysk C (C = P× ile osób kupi subskrypcję) kupców był jak największy. Pomóż mu obliczyć maksymalny możliwy zysk C oraz cenę P, która go daje. Jeśli istnieje kilka cen dających ten sam maksymalny zysk C, wybierz najniższą z nich. Wejście W pierwszym wierszu znajduje się jedna liczba całkowita N. W drugim wierszu znajduje się N liczb całkowitych c1, c2, …, cN oddzielonych pojedynczymi odstępami, oznaczających maksymalny budżet poszczególnych kupców. Wyjście Twój program powinien wypisać dwie liczby całkowite oddzielone spacją: Maksymalny zysk C, jaki może osiągnąć Bajtazar oraz optymalną cenę subskrypcji P dającą ten zysk. Jeśli istnieje kilka cen dających ten sam maksymalny zysk C, wybierz najniższą z nich. Ograniczenia 1 ≤ N ≤ 106, 1 ≤ ci ≤ 106 Podzadania Podzadanie Warunki Punkty 1 ci ≤ 1 000 20 2 N ≤ 1 000 20 3 brak dodatkowych ograniczeń 60 Przykład Wejście Wyjście Wyjaśnienie 4 1 6 4 6 12 4 Przy cenie równej 4 produkt kupią trzy osoby (te z budżetem 4, 6 i 6), co daje maksymalny zysk 12 (4 ⋅ 3). Ten sam zysk osiągniemy przy cenie 6 (6 ⋅ 2), jednak zgodnie z poleceniem w przypadku remisu wybieramy najniższą kwotę, dlatego poprawny wynik to zysk 12 przy cenie 4. Wejście Wyjście 8 1 2 3 4 5 6 7 8 20 4 Wejście Wyjście 2 1 4 4 4

Wejście	Wyjście	Wyjaśnienie
`4 1 6 4 6`	`12 4`	Przy cenie równej 4 produkt kupią trzy osoby (te z budżetem 4, 6 i 6), co daje maksymalny zysk 12 (4 ⋅ 3). Ten sam zysk osiągniemy przy cenie 6 (6 ⋅ 2), jednak zgodnie z poleceniem w przypadku remisu wybieramy najniższą kwotę, dlatego poprawny wynik to zysk 12 przy cenie 4.

Wejście	Wyjście
`8 1 2 3 4 5 6 7 8`	`20 4`

Wejście	Wyjście
`2 1 4`	`4 4`

Podzadanie	Warunki	Punkty
1	c_i ≤ 1 000	20
2	N ≤ 1 000	20
3	brak dodatkowych ograniczeń	60