НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача C1. Търговия на едро

Младеж продава чорапи на четвъртък пазар в Пловдив. Понеже младежът е нереализирал се Рокфелер, той спретнал строга система за отстъпки при покупки на едро. Определил цена за 1 чифт чорапи, после определил цена за пакет, съдържащ P₁ на брой чорапи, после цена за пакет съдържащ P₂ на брой пакети от предния тип и така нататък до N вида пакети. Цените са така определени, че винаги е по-добре да вземеш по-голяма разфасовка, вместо същия общ брой чорапи, разбити на по-малки разфасовки.

Напишете програма SOCKS, която по зададени P₁, P₂, P₃… P_N (1 ≤ N ≤ 30) и зададени цени на един чифт чорапи и на всеки от N-те вида пакети, определя минималната сума, за която можем да си купим поне K (1 ≤ K ≤ 1 000 000 000) чифта чорапи (повече не е излишно, особено за зимата). Известно е, че в един пакет, колкото и голям да е той, не може да има повече от 2³⁰ чифта чорапи.

Входните данни се четат от стандартния вход. На първи ред стоят числата 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 бракосъчетания:

            Нека означим едно бракосъчетание с наредената двойка (m_i, d_i), което значи, че се бракосъчетават младеж с номер m_i и девойка с номер d_i.. Тогава множеството от N бракосъчетания (m₁, d₁), (m₂, d₂),..., (m_N, d_N) се нарича устойчиво, ако за всеки две двойки (m_i, d_i) и (m_j, d_j) са в сила следните условия:

1. m_i харесва d_i повече отколкото d_j или d_j харесва m_j повече от m_i;
2. m_j харесва d_j повече отколкото d_i или d_i харесва m_i повече от m_j;

Напишете програма 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