Warp Sürəti II
Gələcəkdə, kosmik mühəndislər kosmosda səyahət üçün yeni bir texnologiya icad edə bilərlər və ona "warp-drive" adını verə bilərlər. Bu warp-drive, bir kosmik gəminin işıq sürətindən daha sürətli hərəkət etməsinə imkan yarada bilər. O, kosmosda müəyyən bir məsafəni əyərək və gəminin bu əyilmiş kosmosdan bir "tullanış" ilə keçməsini təmin edərək işləyir. Kosmosda səyahət etmək üçün, warp-drive ilə təchiz olunmuş bir kosmik gəmi başlanğıc və son nöqtələr arasında bir neçə tullanış etməli ola bilər. Tullanış üçün lazım olan enerji/güç warp-drive-ın cari vəziyyətinə/konfiqurasiyasına bağlıdır. Həmçinin, warp-drive-ın istənilən vəziyyətinə keçmək və ya hazırlamaq üçün də müəyyən miqdarda enerji sərf olunur.
Məqsəd
Tutaq ki, siz döyüş kosmik gəmisində mühəndissiniz. Sizin vəzifəniz warp-drive-ı elə idarə etməkdir ki, hər hansı bir səyahət üçün mümkün qədər az enerji sərf edilsin. Hər bir səyahət üçün sizə tullanışlar ardıcıllığı veriləcək və siz bu tullanış ardıcıllığına uyğun ən az enerji istifadə edən warp-drive konfiqurasiyaları ardıcıllığını tapmalısınız.
Vəzifənizi yerinə yetirmək üçün, hər hansı bir verilmiş tullanış ardıcıllığı üçün warp-drive konfiqurasiyaları ardıcıllığının ən az enerji ilə tapılması üçün bir kompüter proqramı qurmalısınız. Bunun üçün iki warp-drive enerji istehlakı cədvəlindən istifadə edəcəksiniz. Birinci cədvəl hər hansı iki vəziyyət arasında keçid üçün enerjini göstərir. İkinci cədvəl isə warp-drive vəziyyətləri və tullanışlarla əlaqəli enerji istehlakını göstərir.
Giriş verilənləri
Giriş standart girişdir və 4 hissədən ibarətdir, boş sətirlə ayrılır.
Birinci hissə warp-drive vəziyyətlərinin və tullanış növlərinin ölçülərini müəyyən edir.
Yalnız bir sətirdən ibarətdir. Bu sətir boşluqla ayrılmış 2 rəqəm ehtiva edir. Bu 2 rəqəm:
Warp-drive vəziyyətlərinin ölçüsü (N), 1 ilə 100 arasında.
Vəziyyət id-si 0 ilə N-1 arasında başlayır.
Birinci vəziyyət (id #0) boş vəziyyətdir. Bu və yalnız bu vəziyyətdə, warp-drive heç bir tullanış edə bilmir. (Bu, hər hansı bir çıxış vəziyyət ardıcıllığı üçün standart başlanğıc və son vəziyyətdir.)
Müxtəlif tullanış növlərinin ölçüsü (H), 1 ilə 1000 arasında.
Tullanış id-si 0-dan H-1-ə qədərdir.
İkinci hissə warp-drive vəziyyətləri arasında keçid üçün enerjini göstərən bir cədvəldir. Cədvəlin ölçüsü N sətir və N sütundur, bu da N^2 enerji dəyərləri ehtiva edir.
N sətir var. Hər sətir N enerji dəyəri ehtiva edir. Bu dəyərlər 1 ilə 100 arasında.
Hər enerji dəyəri öz sətir və sütun indeksi ilə indekslənə bilər. Sətir və sütun indeksləri cari və növbəti warp-drive vəziyyətlərinin id-ləridir. Bu iki indeksin 0-dan başladığını unutmayın.
Məsələn, (sətir indeksi, sütun indeksi) = (5,0) olan dəyər warp-drive vəziyyətini 5-dən 0-a keçirmək üçün enerjidir. (Bu dəyər altıncı sətirdəki ilk rəqəmdir.)
Üçüncü hissə hər bir vəziyyət sürücüsü üçün tullanışları yerinə yetirməkdə enerji istehlakını göstərən bir cədvəldir.
Cədvəlin ölçüsü N sətir və H sütundur, bu da N ilə H arasında dəyərlər ehtiva edir.
N sətir var. Hər sətir H enerji dəyəri ehtiva edir. Bu dəyərlər 1 ilə 100 arasında.
Hər enerji dəyəri öz sətir və sütun indeksi ilə indekslənə bilər. Sətir indeksi cari warp-drive vəziyyətinin id-sidir. Sütun indeksi tullanışın id-sidir. Bu iki indeksin 0-dan başladığını unutmayın.
Məsələn, (sətir indeksi, sütun indeksi) = (1,9) olan dəyər warp-drive vəziyyətində #1 tullanışını #9 yerinə yetirmək üçün enerjidir. (Bu dəyər ikinci sətirdəki onuncu rəqəmdir.)
Bu hissənin ilk sətirində, vəziyyət #0 və ya boş vəziyyətə uyğun olan bütün rəqəmlərin sıfır olduğunu unutmayın. Bu, bu vəziyyətdə heç bir tullanışın yerinə yetirilə bilməyəcəyini göstərir.
Dördüncü hissə tullanış ardıcıllıqlarından ibarətdir. Bu dəstdəki ardıcıllıqların sayı 1 ilə 1000 arasında.
Sətirlərin sayı 1 ilə 1000 arasında.
Bu hissədəki hər sətir bir tullanış ardıcıllığı ehtiva edir.
Bir ardıcıllıqda tullanışların sayı 1 ilə 1000 arasında.
Hər tullanış bir rəqəmdir (başlanğıc 0-dan H-1-ə qədər) və boşluqla ayrılır.
Dördüncü hissədən sonra boş sətir girişin sonunu göstərir.
Çıxış verilənləri
Girişin dördüncü hissəsindəki hər bir tullanış ardıcıllığı üçün, çıxışın 2 hissəsini yazın:
Birinci sətirdə, minimum olması lazım olan ümumi enerji miqdarını yazın.
Növbəti sətirdə həlli yazın. Həll, verilmiş tullanış ardıcıllığına uyğun warp-drive vəziyyətlərinin ardıcıllığını ehtiva edir. (Giriş və çıxış ardıcıllığının ölçüsü bərabər olmalıdır.) Əgər eyni miqdarda enerji sərf edən iki və ya daha çox mümkün həll varsa, soldan sağa ən aşağı vəziyyətləri ehtiva edən ardıcıllığı yazın.
Əlavə İzahlar
Nümunə girişdə 15 sətir və nümunə çıxışda 4 sətir var.
Birinci nümunə çıxışında (giriş sətiri #13 üçün həll), minimum ümumi enerji 9-dur. Warp-drive vəziyyət ardıcıllığı [3 2] və ya [0- 3 2 -0]-dır. 0 → 3, 3 → 2, və 2 → 0 keçidləri üçün 3 vəziyyət dəyişiklikləri var ki, bu da 1 + 1 + 2 = 4 enerji sərf edir. Və 3 və 2 vəziyyətlərində 0 və 4 tullanışları üçün 4 +1 = 5 enerji sərf olunur. Beləliklə, ümumi enerji 4 + 5 = 9-dur.
Son nümunə çıxışında, minimum enerji 23-dür. Həll [0- 1 1 2 3 -0]-dır ki, bu da ümumilikdə 23 enerji sərf edir.