pp05

Задачите за тренинг са две от трите:
- пермутации с повторения
- вариации без повторения
- комбинации с повторения.

Интересни комбинаторни задачи:

Задача. Индекс на Шапли-Шубик за политическа сила при да-не система за гласуване
[ Пети междууниверситетски турнир по програмиране, 19 май 2002 г., БСУ ]

    Във всеки съюз или обединение от политически субекти (напр. държави) се налага да се приеме система за вземане на решения. Една такава система е да се гласува с "да'' или "не'', като всяка държава да има определен брой гласове. Решение да се взема когато броят на гласовете "да'' е по-голям или равен на определена граница. Коалиция се нарича група държави, която гласува
с "да'' за дадено предложение. Ако сумата от гласовете на държавите в коалицията е по-голяма или равна на определената граница, то предложението се приема и тази коалиция се нарича печеливша.
    Например през 1958 г. се създава Европейския съюз с точно такава система за вземани на важни решения. Участващите в съюза държави и гласовете им са:
    Франция, Германия, Италия - по 4 гласа,
    Белгия, Холандия - по 2 гласа,
    Люксембург - 1 глас.
    Предложение се приема, ако за него са гласували с "да'' 12 от общо 17 гласа. Две печеливши коалиции в съюза са например Франция, Германия и Италия или Франция, Германия, Белгия, Холандия и Люксембург.
    Една от няколкото известни мерки за политическата сила на дадена държава в един съюз е индексът на Шапли-Шубик. Ето как се дефинира този индекс. Нека съюзът се състои от n държави - p₁, p₂, ..., p_n. Разглеждаме всички възможне наредби на n-те държави. Нека индексите
i₁, i₂,..., i_n задават една конкретна наредба. Държавата p_ik се нарича централна за тази наредба, ако коалицията, състояща се от p_i1, p_i2, ..., p_{i(k
- 1)} не е печеливша, а коалицията p_i1, p_i2, ..., p_ik е печеливша. Индекс на Шапли-Шубик за държавата p се нарича отношението на броя на наредбите, в които p е централна към броя на всички възможни наредби. Да се напише програма за пресмятане на индекса на Шапли-Шубик.

Входен файл - shsh.in
Съдържа няколко тестови примери. Данните за всеки от примерите са записани на два последователни реда във файла. Първият ред за всеки от примерите съдържа две цели числа, разделени с един интервал - броят N на държавите в съюза (1 < N < 11) и необходимият брой гласове V за вземане на решение. На следващия ред има N цели числа (разделени с по един интервал), които са гласовете на участниците в съюза. Файлът завършва с ред, съдържащ числото 0.

Изходен файл - shsh.out
За всеки пример трябва да се изведат N цели числа, по едно на ред, всяко равно на индекса на Шапли-Шубик, изразен в проценти за поредния участник в съюза. Числата да са закръглени (по общоприетите правила за закръгляване) с 1 значеща цифра след десетичната точка. Между изходните данни за отделните примери трябва да се оставя по един празен ред.

Пример:
3 51
50 49 1
6 12
4 4 4 2 2 1
0

Решение на примера:
66.6
16.6
16.6

<>23.3
23.3
23.3
15
15
0

Задача. Политическа сила
[ Междууниверситетско състезание по програмиране, 24 март 2002 г., БСУ ]

    Всички важни решения в Eвропейския съюз се вземат чрез да-не гласуване на дадено предложение, като участващите в съюза държави имат различен брой гласове. Ето разпределението на гласовете по държави:
Франция, Германия, Италия и Англия - по 10 гласа,
Испания - 8,
Белгия, Холандия, Португалия и Гърция - 5,
Австрия и Швеция - 4,
Дания, Ирландия и Финландия - 3,
Люксембург - 2 гласа.
    Предложение се приема при събрани 62 от общо 87 гласа.
    Една мярка са политическата сила на една държава в съюза е индексът на Банзаф. Нека p е дадена държава. Обща политическа сила O(p) на p се нарича броя на коалициите C, изпълняващи следните 3 условия:
    1. p е член на коалиция C;
    2. C е печеливша коалиция (събира необходимите брой гласове за приемане на дадено предложение);
    3. Когато p излезе от C, получената коалиция е губеща (не е печеливша).
    Индекс на Банзаф B(p) за държавата p се пресмята по формулата: B(p) = O(p)/s, където s е сумата от общата политическа сила на всички участници в съюза. Да се напише програма за пресмятане на индекса на Банзаф.

    Входен файл - banzaf.inp
Първият ред от един пример съдържа две цели числа - броя на държавите N в съюза (1<N<32) и необходимия брой гласове V за вземане на решение. Следващите N цели числа са гласовете на участниците в съюза. Във файла се съдържат много примери, като последно число във файла е стойност 0 за N.

    Изходен файл - banzaf.out
За всеки пример се извеждат N цели числа - индекса на Банзаф в проценти за участниците в съюза (закръглен до цяло число). Между примерите се оставя празен ред.

Пример:
15 62
10 10 10 10 8 5 5 5 5 4 4 3 3 3 2
2 50
49 51
0

Решение на примера:
11
11
11
11
9
6
6
6
6
5
5
4
4
4
2

0
100