Runda 26 - Wyścigi Futerkowych Zaprzęgów

12.04.2010 - Łukasz Zatorski
TrudnośćTrudność

 

Zawody stałe, runda 26

Limit czasowy: 1s; Limit pamięciowy: 32MB

 


Wyścigi futerkowych zaprzęgów

 

W odbywających się co co roku Otwartych Bajtockich Mistrzostwach Futerkowych Zaprzęgów biorą udział najlepsi woźnicy z całego świata. Niezaprzeczalnym faworytem zbliżających się zawodów jest Bert Bica wraz ze swoimi sympatycznymi szczurołakami. Gra toczy się o niemałą stawkę - zwycięzca, poza wieczną chwałą, otrzymuje wysokie honorarium, a wszyscy sponsorzy wręcz zabijają się o każdy centymetr na jego koszuli.
Książę Kaspar postanowił przede wszystkim odzyskać reputację po ostatniej porażce, kiedy to jego zaprzęg lemingów niespodziewanie skoczył z urwiska. Dlatego już od jesieni trenuje na ukrytym torze w lesie niedaleko swojej posiadłości. Tym razem postawił na mieszaną hodowlę świstaków - poza rodzimym Bajtockim, sprowadził jeszcze gatunek z Cobolandii.
Futerkowy zaprzęg składa się z K par gryzoni* biegnących w szeregu. Kluczem do sukcesu wydaję się wybranie nie tylko najsprawniejszych osobników, ale również ich odpowiedni rozkład. Okazuje się że dwie pary tego samego gatunku świstaka nie mogą biec bezpośrednio jedna za drugą na jakimkolwiek fragmencie zaprzęgu - inaczej wyraźnie traci on manewrowość na zakrętach. Podobnie ma się sprawa w przypadku czterech świstaków tego samego gatunku biegnących dokładnie jeden za drugim. Za moc zaprzęgu uznaje się zaś sumę sił wszystkich jego świstaków, przy czym pierwsze dziesięć liczy się dwukrotnie (narzucają one bowiem tempo pozostałym).
Książę chciałby wiedzieć, jak silny może być jego zaprzęg jeśli wykluczy te niekorzystne konfiguracje.
Poprosił Cię o pomoc w sprawdzeniu tego, i obiecał, że w razie wygranej podzieli się z Tobą nagrodą pół na pół - dla niego sława, dla Ciebie pieniądze. Taka okazja może się szybko nie powtórzyć!

Wejście:


W pierwszej linii wejścia znajdują się dwie liczby $ n $ $ k $ $ (2\leq n \leq 10000, 1\leq k \leq 100) $ - kolejno ilość świstaków w hodowli i określona w przepisach dokładna wielkość zaprzęgu.
W kolejnych $ n $ liniach znajdują się pary $ s $ $ g $ $ (0\leq s \leq 100, g \in \left\{b,c\right\})  $- siła świstaka oraz jego gatunek ('b' - bajtocki, 'c' - cobolandzki).

Wyjście:


Napis "NIE" jeśli nie da się skonstruować zaprzęgu zgodnie z podanymi kryteriami, lub jedna liczba całkowita - moc najsilniejszego możliwego zaprzęgu.

Test przykładowy:

Wejście:


8 4
2 b
3 b
8 b
6 b
4 c
3 b
2 b
1 b

Wyjście:

NIE

 

Wejście:

12 5
6 b
4 b
3 b
4 b
5 b
6 b
10 b
1 c
3 b
2 c
11 b
12 b

Wyjście:

122


----
* - obecnie przepisy nie dopuszczają lemingów oraz jeżozwierzy ze względu na drastyczne sceny z ich udziałem w poprzednich mistrzostwach.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska10540:14:30
2Kamil Łukasz941:29:33
3Przemysław Derengowski8173:23:32
4Darek Bukowski7155:03:08
5Michał Krawczak7158:04:50
6Krzysztof Drab7517:34:56
7Arek Wróbel5136:48:41
4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com