НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА
ПЛОВДИВ, 27–28 МАЙ 2006

Задача C1. Търговия на едро
 
Младеж продава чорапи на четвъртък пазар в Пловдив. Понеже младежът е нереализирал се Рокфелер, той спретнал строга система за отстъпки при покупки на едро. Определил цена за 1 чифт чорапи, после определил цена за пакет, съдържащ P1 на брой чорапи, после цена за пакет съдържащ P2 на брой пакети от предния тип и така нататък до N вида пакети. Цените са така определени, че винаги е по-добре да вземеш по-голяма разфасовка, вместо същия общ брой чорапи, разбити на по-малки разфасовки.
Напишете програма SOCKS, която по зададени P1, P2, P3… PN (1 ≤ N ≤ 30) и зададени цени на един чифт чорапи и на всеки от N-те вида пакети, определя минималната сума, за която можем да си купим поне K (1 ≤ K ≤ 1 000 000 000) чифта чорапи (повече не е излишно, особено за зимата). Известно е, че в един пакет, колкото и голям да е той, не може да има повече от 230 чифта чорапи.
Входните данни се четат от стандартния вход. На първи ред стоят числата N и K – броят „оферти” за пакети на едро и броят чифтове, които са минимума, който трябва да напазарим. На ред две има N цели положителни числа, разделени с интервали – те указват по колко пакета от предния комплект се включват в следващия, т.е. ако имаме числа 2 2 3, това значи, че можем да продаваме по 1 чифт, 2 чифта (1-ви вид пакети), 2*2 = 4 чифта (2-ри вид пакети) и 3*4 = 12 чифта в пакет (3-ти вид). На последния ред от входните данни има N +1 реални числа  – цените в левове и стотинки на 1 чифт и на всеки от N-те вида пакети, които се предлагат
На стандартния изход да се изведе едно единствено реално число  с точност до втория знак– минималната сума в левове и стотинки, която трябва да платим, за да се сдобием поне с К чифта чорапи.

Примерен вход:				Примерен изход:
3 100						300.00		
3 5 6
10.00 15.00 50.00 250.00  

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА
ПЛОВДИВ, 27–28 МАЙ 2006

Задача C2.  Матрица
	
		Нека е дадена матрица от цели числа (между 1 и 10000) с N реда и M стълба (2 ≤ N, M ≤ 1000). Два реда от матрицата ще наричаме подобни, ако единият може да бъде получен от другия чрез разместване на числата, записани в него. Напишете програма MATRIX, която определя максималния брой редове в матрицата, които образуват множество, такова, че никои два реда от него не са подобни помежду си.
	Вход (от стандартния вход):
•	на първия ред са зададени числата N и M, разделени с интервал;
•	следват N реда, всеки от които съдържа по M цели числа, разделени с интервали – елементите на съответния ред от матрицата.
	Изход(на стандартния изход):
	Едно число, което представлява намерения максимален брой.

Примерен вход:						Примерен изход:
5 4									3
10 1000 5 200
70 110 70 30
5 200 10 1000
4 6 11 45
70 70 30 110

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА
ПЛОВДИВ, 27–28 МАЙ 2006

Задача C3.  Бракосъчетания

	В един район на Пловдив има N младежа и N девойки (1 < N ≤ 100). Младежите са номерирани от 1 до N и девойките са номерирани от 1 до N. Районът се отличава със следните особености:
	– Той е „затворен” по отношение на създаването на нови семейства, т.е. младежите и девойките от района могат да се бракосъчетават само помежду си.
	– Всеки младеж е оценил с оценки от 1 до N девойките от района и всяка девойка е оценила с оценки от 1 до N младежите от района (няма повтарящи се оценки от страна на един и същи човек за N-те индивида от противоположния пол и 1 означава най-малко харесване, а N – най-голямо).
	– Има решение на населението от района всички N младежа и N девойки да се бракосъчетаят в един и същи ден – празника на района.
	Районният съвет е заинтересован да няма разводи след такова „масово” мероприятие и, поради това, е сформирал следния критерий за устойчивост на множеството от планираните N бракосъчетания: 
	Нека означим едно бракосъчетание с наредената двойка (mi, di), което значи, че се бракосъчетават младеж с номер mi и девойка с номер di.. Тогава множеството от N бракосъчетания (m1, d1), (m2, d2),..., (mN, dN) се нарича устойчиво, ако за всеки две двойки (mi, di) и (mj, dj) са в сила следните условия:
1.	mi харесва di повече отколкото dj или dj харесва mj повече от mi;
2.	mj харесва dj повече отколкото di или di харесва mi повече от mj;

	Напишете програма MARRIAGE, която да помогне на районния съвет така да нареди двойките младоженци, че да се получи устойчиво множество от бракосъчетания. Ако това не е възможно, изведете на един ред 0. Ако има повече от едно устойчиво множество от бракосъчетания, намерете едно от тях.
	
Вход (от стандартния вход): 
•	На първия ред стои числото N – брой на младежите и девойките в района.
•	Следват N реда, всеки от които съдържа N числа, разделени с по една шпация –оценките на съответния младеж за N-те девойки от района.
•	Следват N реда, всеки от които съдържа N числа, разделени с по една шпация –оценките на съответната девойка за N-те младежа от района.

Изход (на стандартния изход):
	N реда, на всеки от които има две числа, разделени с шпация – първото е номер на младеж, а второто номер на девойка в съответната двойка от намереното устойчиво множество от бракосъчетания. Ако няма такова множество, изведете 0.

Примерен вход:						Примерен изход:	
4									1 4
1 2 3 4								2 1
4 3 2 1								3 3
3 1 4 2								4 2			
2 3 1 4
4 3 1 2
3 1 4 2
1 2 3 4
4 1 2 3