Polish version    English version  
  O olimpiadzie -> Zadania -> V OI 1997/1998


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
V Olimpiada Informatyczna 1997/98

Zadanie: NAJ
Autor: Wojciech Rytter
Najlżejszy język

III ETAP, PIERWSZY DZIEŃ ZAWODÓW - WTOREK 7 KWIETNIA 1998 r.  
Plik źródłowy: NAJ.??? (np. pas, c, cpp)
Plik wykonywalny: NAJ.exe
Plik wejściowy: NAJ.in
Plik wyjściowy: NAJ.out

Dany jest alfabet Ak złożony z k początkowych liter alfabetu angielskiego. Każda litera w tym alfabecie ma określoną wagę, która jest dodatnią liczbą całkowitą. Wagą słowa zbudowanego z liter alfabetu Ak nazywamy sumę wag wszystkich jego liter. Językiem nad alfabetem Ak nazywamy dowolny skończony zbiór różnych słów utworzonych z liter tego alfabetu . Wagą języka nazywamy sumę wag wszystkich jego słów. Mówimy że język jest bezprefiksowy, gdy żadne jego słowo nie jest prefiksem (początkiem) jego innego słowa.

Chcemy ustalić, jaka może być najmniejsza waga n-elementowego, bezprefiksowego języka nad alfabetem Ak.

Przykład

Załóżmy, że k = 2 , waga litery a — W(a) = 2 oraz waga litery b — W(b) = 5. Wtedy: waga słowa ab — W(ab) = 2 + 5 = 7. W(aba) = 2 + 5 + 2 = 9. Waga języka J = {ab, aba, b} — W(J) = 21. Język J nie jest bezprefiksowy, ponieważ jego słowo ab jest prefiksem słowa aba. Najlżejszym trzyelementowym bezprefiksowym językiem nad alfabetem A2 , o określonych powyżej wagach liter, jest {b, aa, ab}; jego waga wynosi 16.

Zadanie

Napisz program, który:

  • wczytuje z pliku tekstowego NAJ.IN dwie liczby naturalne n oraz k, a następnie wagi wszystkich k liter alfabetu Ak;
  • oblicza najmniejszą wagę bezprefiksowego n-elementowego języka nad alfabetem Ak;
  • zapisuje wynik w pliku tekstowym NAJ.OUT.

Wejście

W pierwszym wierszu pliku wejściowego NAJ.IN znajdują się dwie dodatnie liczby całkowite n i k oddzielone pojedynczym odstępem (2<=n<=10000, 2<=k<=26). Są to odpowiednio: liczba słów języka i liczba liter alfabetu. Drugi wiersz zawiera k dodatnich liczb całkowitych nie większych niż 10000, oddzielonych pojedynczymi odstępami — i-ta liczba jest wagą i-tej litery.

Wyjście

W pierwszym i jedynym wierszu pliku wyjściowego NAJ.OUT Twój program powinien wypisać jedną liczbę całkowita — wagę najlżejszego, bezprefiksowego, n-elementowego języka nad alfabetem Ak.

Przykład

Dla pliku wejściowego NAJ.IN:

3 2
2 5

poprawnym rozwiązaniem jest plik wyjściowy NAJ.OUT:
16

Twój program powinien szukać pliku NAJ.IN w katalogu bieżącym i tworzyć plik NAJ.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę NAJ.??? gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku NAJ.EXE.





Wersja do druku