Barikādes

Divas pilsētas savieno ceļu tīkls. Katrs ceļš savieno kaut kādus divus mezgla punktus un starp katriem diviem mezglu punktiem ir ne vairāk kā viens ceļš. Katram ceļam ir noteikts platums. 
Pēdējā laikā pilsētu attiecības ir krasi pasliktinājušās un novedušas pie karadarbības. Pirmā pilsēta ir nosūtījusi uz otro karaspēku. Karaspēks var pārvietoties tikai pa ceļiem. Otrā pilsēta aizsardzības nolūkos grib dažus ceļus aizbarikādēt. Ceļus var aizbarikādēt tikai ārpus mezglu punktiem. Katras barikādes garums sakrīt ar aizbarikādējamā ceļa platumu. Pa aizbarikādētu ceļu pirmās pilsētas karaspēks pārvietoties nevar. Jūsu uzdevums ir noteikt, kurus ceļus nepieciešams aizbarikādēt, lai nepieļautu pirmās pilsētas karaspēka ienākšanu otrajā pilsētā, un kāds ir mazākais iespējamais šo barikāžu kopgarums. 

Ievaddati
Teksta faila BARRIC.IN pirmajā rindā dots naturāls skaitlis N (N<=100) - mezglu punktu skaits. Uzskatīsim, ka mezglu punkti ir sanumurēti pēc kārtas ar skaitļiem no 1 līdz N un pirmā pilsēta atrodas mezglu punktā 1, bet otrā - mezglu punktā N. Faila otrajā rindā dots naturāls skaitlis M - ceļu skaits (M<=1000). Katrā no nākošajām M faila rindām dotas trīs naturālu skaitļu  b,e un w vērtības: b un e - tie ir kāda ceļa galapunkti (mezglu punktu numuri), bet w - šī ceļa platums (b<=N, e<=N, w<=100). Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols.

Izvaddati
Teksta faila BARRIC.OUT pirmajā rindā jāizvada viens naturāls skaitlis - mazākais atrastais barikāžu kopgarums. Faila otrajā rindā jāizvada naturāls skaitlis K - aizbarikādējamo ceļu skaits. Katrā no nākošajām K rindām jāizvada divi naturāli skaitļi b un e - viena aizbarikādējamā ceļa galapunkti. Skaitļi jāatdala ar tukšumsimbolu. Starp izvadītajiem K ceļiem neviens nedrīkst atkārtoties. Ja ceļu aizbarikādēšanai iespējami vairāki varianti, tad jāizvada vienu no tiem.

Piemērs

Ievaddati (fails BARRIC.IN)	Izvaddati (fails BARRIC.OUT)
4					9
5					3
1 2 8					1 3
1 3 3					4 2
2 3 3					2 3
2 4 3
3 4 7

Баррикады.

Два города соединены сетью дорог. Каждая дорога соединяет какие-то два узловых пункта, и между каждыми двумя узловыми пунктами проходит не более одной дороги. Каждая дорога имеет некоторую ширину. 
В последнее время отношения между городами резко ухудшились и дошли до военных действий. Первый город отправил во второй город военный контингент. Войска могут двигаться только по дорогам. Второй город в целях защиты хочет перегородить некоторые дороги баррикадами. Баррикады можно строить только на дорогах - в узловых пунктах. строить баррикады нельзя. Длина каждой баррикады равна ширине дороги, которую она перегораживает. По перегороженной дороге войска пройти не могут. Требуется определить, какие дороги надо перегородить баррикадами, чтобы не допустить войска во второй город, а суммарная длина баррикад была наименьшей.

Входные данные. 
В первой строке входного файла BARRIC.IN находится одно натуральное число N (N<=100) - количество узловых пунктов. Считаем, что узловые пункты пронумерованы по порядку числами от 1 до N, первый город находится в узловом пункте 1, а второй - в узловом пункте N. Во второй строке находится одно натуральное число M - количество дорог (M<=1000). Каждая из следующих M строк содержит по три натуральных числа  b,e и w: b и e - это концевые пункты какой-нибудь дороги (номера узловых пунктов), а w - ее ширина (b<=N, e<=N, w<=100). Соседние числа в строке разделяются одним пробелом.

Выходные данные. 
В первой строке выходного файла BARRIC.OUT должно находится одно натуральное число - найденная наименьшая возможная суммарная длина баррикад, Во второй строке должно находиться одно натуральное число K - количество дорог, которые надо перегородить. В следующих K строках следует выводить по два натуральных числа b и e, разделенных одним пробелом: b и e - концы дороги, которую надо перегородить. Среди выводимых K дорог ни одна не должна повторяться. Если перегородить дороги можно несколькими способами, то достаточно выводить любой из них.

Пример.

Входной файл (BARRIC.IN)		Выходной файл (BARRIC.OUT)

4						9
5						3
1 2 8					1 3
1 3 3					4 2
2 3 3					2 3
2 4 3
3 4 7

Vidējais aritmētiskais

Dots skaitļu masīvs. Par tā apakšmasīvu sauksim jebkuru pēc kārtas sekojošu šī masīva elementu virkni. Par apakšmasīva garumu sauksim tajā esošo elementu skaitu. 
Starp visiem dotā masīva apakšmasīviem, kuru garums nav mazāks par dotu naturālu skaitli K, jāatrod apakšmasīvs, kura elementu vidējā aritmētiskā vērtība ir vislielākā.

Ievaddati
Teksta faila AVERAGE.IN pirmajā rindā dots naturāls skaitlis N (N<=10000) - masīva elementu skaits. Faila otrajā rindā dots naturāls skaitlis K, kura vērtība nepārsniedz N. Faila nākošajās N rindās dotas skaitļu masīva elementu vērtības pēc kārtas pa vienam skaitlim katrā rindā. Visi masīva elementi ir veseli skaitļi, kuri pēc absolūtās vērtības nepārsniedz 1000.

Izvaddati
Teksta faila AVERAGE.OUT pirmajā rindā jāatrodas vienam skaitlim - lielākajai atrastajai vidējā aritmētiskā vērtībai. Šo lielumu nepieciešams izvadīt ar divām decimālajām zīmēm aiz komata. Faila otrajā rindā jāizvada divi naturāli skaitļi, kas atdalīti ar tukšumsimbolu - atrastā apakšmasīva attiecīgi pirmā un pēdējā elementa kārtas numuri sākotnējā masīvā. Ja šādi apakšmasīvi ir vairāki, tad nepieciešams izvadīt vienu no tiem. Atzīmēsim, ka, ja divu apakšmasīvu vidējās aritmētiskās vērtības ir dažādas, bet tās sakrīt ar precizitāti līdz divām decimālajām zīmēm aiz komata, tad apakšmasīva ar mazāko vidējā aritmētiskā vērtību izvadīšana ir kļūda.

Piemērs
Ievaddati (fails AVERAGE.IN)	Izvaddati (fails AVERAGE.OUT)
8					6.20
3					2 6
-19
45
-32
5
-45
58
-16
-27

Среднее арифметическое.

Дан числовой массив. Будем называть подмассивом любую последовательность подряд идущих элементов массива, длиной подмассива будем называть количество элементов в нем.
Среди всех подмассивов, длина которых не меньше заданного натурального числа K, требуется найти подмассив с наибольшим значением среднего арифметического его элементов.

Входные данные. 
В первой строке входного файла AVERAGE.IN находится одно натуральное число N (N<=10000) - количество элементов массива. Во второй строке находится величина K - натуральное число, не превосходящее N. В следующих N строках файла содержится заданный числовой массив - по одному числу в строке. Все элементы массива - целые числа, не превосходящие по абсолютной величине 1000.

Выходные данные. 
В первой строке выходного файла AVERAGE.OUT должно находится одно число - найденное наибольшее значение среднего арифметического. Это значение надо выводить с двумя десятичными знаками после запятой. Во второй строке надо выводить два натуральных числа, разделенных пробелом, соответственно номера начального и конечного элементов подмассива с наибольшим средним арифметическим. Если таких подмассивов существует несколько, то достаточно выводить любой один из них. Заметим, что если у двух подмассивов, средние арифметические различаются, но совпадают с точностью до второго десятичного знака после запятой, то вывод подмассива с меньшим значением среднего арифметического является ошибкой.

Пример.

Входной файл (AVERAGE.IN)		Выходной файл (AVERAGE.OUT)

8							6.20
3							2 6
-19				
45				
-32				
5
-45
58
-16
-27

Zāģis

Par permutāciju garumā N sauksim N elementu masīvu, kas tieši vienu reizi satur katru naturālo skaitli no 1 līdz N. 
	Permutāciju (a1, a2, ... aN) sauksim par zobainu, ja izpildās nevienādības a1<a2, a2>a3, a3<a4, a4>a5, ... . Piemēram, permutācijas (2, 5, 1, 4, 3) un (6, 8, 2, 3, 1, 5, 4, 7) ir zobainas, bet permutācijas (3, 1, 4, 2, 5) un (6, 8, 2, 3, 1, 5, 7, 4) - nav.
	Uzrakstīsim visas dotā garuma zobainās permutācijas leksikogrāfiskā (vārdnīcas) kārtībā: permutācija (a1, a2, ... aN) atrodas pirms permutācijas (b1, b2, ... bN), ja eksistē tāds naturāls skaitlis k (k<N), ka ir spēkā sakarības a1=b1, a2=b2, ..., ak-1=bk-1, bet ak < bk. Piemēram, visu zobaino permutāciju garumā 4 saraksts leksikogrāfiskā kārtībā ir: (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3), (3, 4, 1, 2).
	Nepieciešams noskaidrot, kura permutācija šajā sarakstā atrodas M-tajā vietā.

Ievaddati
Teksta faila TOOTHED.IN pirmajā rindā dots naturāls skaitlis N (N<=15) - permutācijas garums. Otrajā rindā dots naturāls skaitlis M - meklētās permutācijas kārtas numurs sarakstā. Zināms, ka M nepārsniedz kopējo zobaino permutāciju garumā N skaitu un ka M ir mazāks par 2000000000.

Izvaddati
Teksta faila TOOTHED.OUT vienīgajā rindā jāizvada meklētā permutācija - N naturāli skaitļi, kur katri divi blakus esoši skaitļi ir atdalīti ar tukšumsimbolu.

Piemērs
Ievaddati (fails TOOTHED.IN)		Izvaddati (fails TOOTHED.OUT)
4						2 3 1 4
3				

Пила.

Назовем перестановкой длины N N-элементный массив, содержащий все натуральные числа от 1 до N (каждое по одному разу). 
	Пусть мы имеем перестановку (a1, a2, ... aN). Назовем перестановку зубчатой, если выполняются условия a1<a2, a2>a3, a3<a4, a4>a5, ... . Например, перестановки  (2, 5, 1, 4, 3) и (6, 8, 2, 3, 1, 5, 4, 7) являются зубчатыми, а перестановки (3, 1, 4, 2, 5) и (6, 8, 2, 3, 1, 5, 7, 4) не являются.
	Выпишем все зубчатые перестановки заданной длины N в лексикографическом (словарном) порядке: перестановка (a1, a2, ... aN) предшествует перестановке (b1, b2, ... bN), если существует такое натуральное число k (k<N), что a1=b1, a2=b2, ..., ak-1=bk-1, но ak < bk. Например, список всех зубчатых перестановок длины 4 в лексикографическом порядке выглядит так:   (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3), (3, 4, 1, 2).
	Требуется определить, какая перестановка стоит в этом списке на    M-ом месте.

Входные данные. 
В первой строке входного файла TOOTHED.IN находится одно натуральное число N (N<=15) - длина перестановки. Во второй строке находится одно натуральное число M - ее номер в списке. Гарантируется, что M не превосходит количества зубчатых перестановок длины N. Известно, что M меньше 2000000000.

Выходные данные. 
В единственной строке выходного файла TOOTHED.OUT должна находится искомая перестановка - N натуральных чисел; каждые два соседних числа должны быть разделены одним пробелом.

Пример.

Входной файл (TOOTHED.IN)		Выходной файл (TOOTHED.OUT)

4							2 3 1 4
3