Комбинаторные задачи теории информации

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

Задача №292.  Флаги на мачтах

Имеются n различных сигнальных флагов и k мачт, на которые их вывешивают. Значение сигнала зависит от того, в каком порядке развешены флаги. Сколькими способами можно развесить флаги, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми.

Решение

Каждый способ развешивания флагов можно осуществить в два этапа. На первом этапе мы переставляем всеми возможными способами данные n флагов. Это можно сделать n! способами. После этого берем один из способов распределения n одинаковых флагов по k мачтам. Число таких способов равно .

Пусть этот способ заключается в том, что на первую мачту надо повесить n₁ флагов, на вторую n₂ флагов, …, на k-ю n_k флагов, где . Тогда берем первые n₁ флагов данной перестановки, следующие n₂ развешиваем на второй мачте и т.д. Ясно, что используя все перестановки n флагов и все способы распределения n одинаковых флагов по k мачтам, мы получим все способы решения поставленной задачи.

Задача №293.  Полное число сигналов

Найдем полное число сигналов, которые можно передать с помощью n сигнальных флагов, вывешиваемых на k мачтах.

Решение

С помощью заданных s флагов можно передать сигналов. Но s флагов из n можно выбрать способами. Значит, полное число сигналов задается формулой:

Задача №294.  Передача сигналов по времени

Сообщение передается с помощью сигналов нескольких типов. Длительность передачи сигнала первого типа равна t₁, второго типа t₂, …, k-го типа t_k единиц времени. Сколько различных сообщений можно передать с помощью этих сигналов за T единиц времени?

При этом учитываются лишь "максимальные" сообщения, то есть сообщения, к которым нельзя присоединить ни одного сигнала, не выйдя за рамки отведенного для передачи времени.

Входные данные

В первой строке два числа T и k,не превышающие 10⁵

Во второй строкеkцелых чисел через пробел t₁t₂ … t_k–длительность передачи каждого сигнала.

Решение

Обозначим число сообщений, которые можно передать за время T через f(T).

При этом f(T)=0, если T<0 и f(0)=1

Задача №295.  Порождение комбинаторных объектов

Написать программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1..k (их количество равно k в степени n).

Рекурсивный перебор

Задача №296.  Две кучки камней (acmp.ru)

У Вас есть N камней с массами W1, W2 , … WN. Требуется разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.

Входные данные

В первой строке входного файла INPUT.TXT записано число N – количество камней (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы камней W1, W2 , … WN (1 ≤ Wi ≤ 105).

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух кучек.

Пример

input.txt	output.txt
5 5 8 13 27 14	3

Решение

#include <fstream>

#include <cstdlib>

using namespace std;

ifstream fin("input.txt");

ofstream fout("output.txt");

int ar[20], n, mi = 987654321, sum = 0;

void p(int pos, int curSum){

   if(pos == n)

           mi = min(mi, abs(sum - 2*curSum));

   else {

           p(pos+1,curSum);

           p(pos+1,curSum+ar[pos]);

   }

}

int main(){      

   fin >> n;

   for(int i = 0; i < n; i++){

           fin >> ar[i];

           sum += ar[i];

   }

   p(0,0);

   fout << mi;

}

Перебор без рекурсии

Алгоритм получения следующей перестановки в лексикографическом (алфавитном) порядке набора элементов An:

1. Просматриваем A₁, ..., A_n с конца до тех пор, пока не попадется A_i<A_i+1. Если таковых нет, то генерация закончена.

2. Рассматриваем A_i+1, A_i+2, ..., A_n. Найдем первый с конца A_m больший A_i и поменяем их местами.

3. A_i+1, A_i+2, ..., A_n переставим в порядке возрастания (для этого достаточно переписать с конца).

4. Печатаем найденную перестановку.

5. Возвращаемся к пункту 1.

Данный алгоритм уже реализован в C++. Воспользуемся функцией next_permutation(), описанной в библиотеке algorithm.

Алгоритм next_permutation() создает следующую перестановку заданной последовательности. Перестановка генерируется в предположении, что последовательность, отсортированная от меньшего к большему, представляет собой первую перестановку. Если следующей перестановки не существует, алгоритм next_permutation() сортирует последовательность в виде ее первой перестановки и возвращает значение false. В противном случае возвращается значение true.

Задача №297.  Анаграмма (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Пусть задано некоторое слово, состоящее из букв английского алфавита длинной не более 80 символов (например, “WORD”). Рассмотрим набор возможных перестановок, состоящих из букв данного слова (например, “RDOW”, “WODR” и т.д.). Требуется выбрать из этого множества слово, следующее по алфавиту за исходным.

Входные данные

В единственной строке входного записано слово, не последнее по алфавиту среди возможных его перестановок.

Выходные данные

В единственную строку нужно вывести следующее слово по алфавиту.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	abdc	acbd
2	word	wrdo

Решение

Если пользоваться алгоритмом, описанным выше, то программа, реализующая получение следующей в лексикографическом порядке перестановки строки, выглядит так:

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

int n=s.length()-1, i=n-1, m=n;

while(s[i]>=s[i+1] && i>=-1)i--;

if(i==-1) cout<<"NO";

else{

  while(s[m]<=s[i])m--;

  swap(s[i],s[m]);

  for(m=0; m<=i; m++)cout<<s[m];

  for(m=n; m>i; m--) cout<<s[m];

}

}

Другая возможность состоит в использовании функции next_ permutation()

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string s;

cin >> s;

next_permutation(s.begin(), s.end());

cout << s;

}

Этосущественноупрощаетпроцесссозданиякода, применяяпринципDRY – Don’tRepeatYourself, сиспользованиемстандартнойбиблиотекишаблоновSTL (StandardTemplateLibrary)языкаC++.

Комментарий от одного из пользователей сайта acmp.ru: «Если решая эту задачу прислушаться, то можно услышать, как в тишине плачет паскалянт[42]»J

Задача №298.  Имперский парад

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

Формат ввода данных

Две строки. В первой одно число N– количество имперских подразделений. Во второй строке через пробел Nчисел, где каждое обозначает численность штурмовиков в подразделении.

Формат вывода данных

В каждой отдельной строке должны быть варианты проведения парада

Пример

Ввод	Вывод
3 1000 700 1000	700 1000 1000 1000 700 1000 1000 1000 700

Решение

#include<algorithm>

#include<iostream>

#defineN 8

using namespace std;

intmain(){

int a[N];

for(int i=0;i<N;i++)cin>>a[i];

sort(a, a+N);

do {

   for(int i=0;i<N;i++)cout<<a[i]<<" ";

   cout<<endl;

} while (next_permutation(a, a+N));

}

Задача №299.  Все перестановки в строке

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

Пример

Ввод	Вывод
caba	aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa

Решение

Данная задача является модификацией предыдущей. Также воспользуемся алгоритмом next_permutation().

#include<algorithm>

#include<iostream>

using namespace std;

int main(){

string str, last;

cin >> str;

sort(str.begin(), str.end());

do {

     if (str != last)

       cout << str << endl;

   last = str;

} while (next_permutation(str.begin(), str.end()));

}

Задача №300.  Неподвижные точки(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Перестановкой P[1..n] размера n называется набор чисел от 1 до n, расположенных в определенном порядке. При этом в нем должно присутствовать ровно один раз каждое из этих чисел. Примером перестановок являются 1,3,4,5,2 (для n=5) и 3,2,1 (для n=3), а, например, 1,2,3,4,5,1 перестановкой не является, так как число 1 встречается два раза.

Число i называется неподвижной точкой для перестановки P, если P[i] = i. Например, в перестановке 1,3,4,2,5 ровно две неподвижных точки: 1 и 5, а перестановка 4,3,2,1 не имеет неподвижных точек.

Даны два числа: n и k. Найдите количество перестановок размера n с ровно k неподвижными точками.

Входные данные

Входной файл INPUT.TXT содержит два целых числа n (1 ≤ n ≤ 9) и k (0 ≤ k ≤ n).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	5 2	20
2	9 6	168
3	2 1	0
4	9 0	133496

Решение

Переберём все перестановки в лексикографическом порядке

#include <fstream>

#include <algorithm>

using namespace std;

int a[10], n, k, all = 1, ans=0;

int main () {

ifstream cin("input.txt");

ofstream cout("output.txt");

cin >> n >> k;

for (int i = 1; i <= n; i++) {

   a[i] = i;

   all *= i;

}

for (; all; all--) {

   int cnt = 0;

   for (int i = 1; i <= n; i++)

       if (a[i] == i) cnt++;

   if (cnt == k) ans++;

   next_permutation(a + 1, a + 1 + n);

}

cout << ans;

}

Задача №301.  Разложение числа на слагаемые

Перечислить все разбиения N на целые положительные слагаемые

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

Решение

Чтобы последовательности не повторялись, разместим их в лексикографическом порядке

от 1,1, ...,1 - Nединиц, до последней N.

#include<iostream>

using namespace std;

int x[200], l, n;

void next(){

int i=l-1, sum=x[l];

//находим i

while(i>1&&x[i-1]<=x[i])sum+=x[i--];

x[i]++;

l=i+sum-1;

for(int j=i+1;j<=l;j++)x[j]=1;

}

int main(){      

cin>>n;

l=n;

for(int i=1;i<=l;i++){

   x[i]=1;

   std::cout<<x[i]<<'';

}

std::cout<<"\n";

do{

   next();

   for(int i=1;i<=l;i++)std::cout<<x[i]<< '';

   std::cout<<"\n";

} while(l!=1);

}

Двоичный перебор

Задача №302.  Эскадры

Вофлоте, состоящемизNкораблей, каждыйкорабльимеетэкипажопределённойчисленности. Разделите корабли флота на две эскадры, так чтобы численность экипажей оказалась максимально близкой к равной. В качестве ответа выведите любую из полученных эскадр и количество моряков в ней.

#include <iostream>

#include <cstdlib>                        //функцияabs

#define N 7

using namespace std;

 

string name[N]={"Alpha","Beta","Gamma","Delta",

           "Sigma","Epsilon","Lambda"}; //именакораблей

int count[N]={12, 100, 1, 23, 47, 90, 14}; //экипажи

 

int n2 = 1 << N, all, best, numbest, s;

 

int sum(int comb){                        //суммаэкипажейдля

int s = 0;                           //заданнойкомбинации

for (int i = 0; i < N; i++){

   s += (comb & 1)* count[i];

   comb >>= 1;

}

return s;

}

 

void write(int comb){                          //выводимёнкораблей

for (int i = 0; i < N; i++){               //заданнойкомбинации

if (comb & 1) cout << name[i] << " ";

   comb >>= 1;       

}

}

int main() {

best = all = sum(n2-1);

for(int i = 1; i < n2 - 1; i++){

   s = abs(all - 2 * sum(i));

   if(s < best){

       best = s;

       numbest =i;

   }

}

write(numbest);

cout << sum(numbest);

}

Теория игр

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

Задача №303.  Игра Баше

Игра Баше имеет много различных вариантов. Рассмотрим один из них.

В игру играют двое игроков. Предположим, в банке имеется Nфишек, за 1 ход разрешается взять не менее 1 и не более K фишек. Проигрывает тот из игроков, кто заберет последнюю фишку.

Программа должна определить, у кого из игроков имеется выигрышная стратегия, а затем играть за этого игрока вплоть до победы.

Пример

 

Задача №304.  Антагонистические игры (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Одним из интересных объектов, изучаемых в теории игр, являются так называемые антагонистические игры двух лиц. Такие игры характеризуются множеством X стратегий первого игрока, множеством Y стратегий второго игрока и функцией выигрыша K(x, y) (x из X, y из Y). Если множества стратегий X и Y конечны, то такую игру принято называть матричной, так как функцию выигрыша K в этом случае удобно задавать матрицей.

Рассмотрим матричную игру, в которой X = {1,…,n}, Y = {1,…,m}. Матрицу выигрышей обозначим символом K. Нижним значением игры назовем число

Верхним значением игры назовем число

Отметим также, что игры, у которых нижнее и верхнее значение совпадают, называются играми с седловой точкой.

Задана матрица выигрышей K для некоторой матричной игры. Найдите ее верхнее и нижнее значение.

Входные данные

Первая строка содержит целые числа n и m (1 ≤ n,m ≤ 100). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно K_ij . Все K_ij по модулю не превосходят 1000.

Выходные данные

Выведите нижнее и верхнее значение игры через пробел.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3 3 4 -1 -3 -2 1 3 0 2 -3	-2 2
2	3 4 -1 0 2 1 -2 0 1 0 2 1 -1 -2	-1 1

Решение

#include <cstdio>

#define SIZE 100

int main() {

int n, m, maxmin = -1001, minmax = 1001,

       mn, mx, i, j, a[SIZE][SIZE];

scanf("%d%d", &n, &m);

for(i = 0; i < n; i++) {

   mn = 1001;

   for(j = 0; j < m; j++) {

       scanf("%d", &a[i][j]);

       if(a[i][j] < mn) mn = a[i][j];

   }

   if (mn > maxmin) maxmin = mn;

}

for(j = 0; j < m; j++) {

   mx = -1001;

   for(i = 0; i < n; i++)

       if(a[i][j] > mx) mx = a[i][j];

   if (mx < minmax) minmax = mx;

}

printf("%d %d", maxmin, minmax);

}

Задача №305.  Игра с камушками

(Автор задачи: Дмитрий Филимоненков)

Два Никифора играют в следующую игру. Перед ними лежит кучка из N камней. Никифоры по очереди берут из неё некоторое число камней. За один ход разрешается взять любое число камней, являющееся целой неотрицательной степенью числа 2 (то есть, 1, 2, 4, 8, и т.д.). Выигрывает Никифор, взявший последний камень. Требуется написать программу, которая определяла бы, какой Никифор выигрывает при правильной игре: начинающий или его партнер.

Входные данные

В единственной строке находится целое положительное число N, не превосходящее 10²⁵⁰.

Выходные данные

В первой строке должно находиться число 1, если выигрывает начинающий Никифор, либо 2, если выигрывает Никифор, который ходит вторым. В случае если выигрывает начинающий Никифор, во второй строке должно быть указано минимальное число камней, которое он должен взять первым ходом, чтобы гарантировать себе выигрыш.

Пример

Ввод	Вывод
8	1 2

Решение

Если число кратно 3, то выигрышной стратегией обладает второй игрок. Для победы ему достаточно после хода первого игрока, который заберёт 2^Kкамней (очевидно, 2^K не может быть кратно 3) брать ровно столько, чтобы число камней оставалось кратно 3. Число, не кратное 3, при делении на 3 может иметь остаток 1 или 2. Ровно столько и должен забирать второй игрок.

Если число не кратно 3, то выигрышной стратегией обладает первый игрок. Первым ходом он должен забрать столько камней, чтобы число оставшихся делилось на 3 без остатка, а затем играть по описанному алгоритму второго игрока.

Задача не требует длинной арифметики. Воспользуемся признаком делимости на 3: число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

#include<iostream>

usingnamespacestd;

intmain(){

intsum_digit = 0;

chartmp;

while ((tmp=cin.get())&&(tmp!='\n'))

   sum_digit += tmp - '0';

if (sum_digit % 3 == 0) cout << 2;

else cout << 1 <<'\n'<< sum_digit % 3;

return 0;

}

 

Задача №306.  Игра Ним

 

Задача №307.  Задача ЕГЭC3 (№26)вариант с одной кучей камней

Вариант с одной кучей камней

Приведу его для упрощения понимания следующего варианта с двумя кучками.

Куча подвергается преобразованию с помощью линейной функции

где N– число камней в куче. Таким образом, множество всех функций преобразования

 можно задать с помощью двух массивов A[0]..A[K-1] и B[0]..B[K-1], где K–общее количество таких функций (возможных ходов игрока)

В программе эти массивы задаются непосредственно в виде:

inta[]={2,1}, b[]={0,3};

Что эквивалентно двум возможным ходам

1. 2×N+0 «увеличить в 2 раза»

2. 1×N+3 «добавить к куче 3 камня»

Условие достижения победы определим с помощью макроса VICTORY. В данном примере возьмём это значение 48 (т.е. игра заканчивается победой игрока, на ходу которого получилось 48 или более камней в куче)

#include<iostream>

#define VICTORY 48

#define F a[i]*n+b[i]

int a[]={2,1}, b[]={0,3}, player[VICTORY]={0,};

 

int main(){

int k = sizeof(a)/sizeof(int);

for(int n = VICTORY - 1; n; n--){

   for(int i = 0; i<k; i++)

       if(F>=VICTORY)

           player[n] = 1;

elseif(player[F]==2)

           player[n] = 1;

       if(!player[n]) player[n]=2;

       std::cout << n << '-' << player[n] << '\n';

}

}

Задачарешаетсяметодомдинамическогопрограммирования. В массиве playerвычисляется, кто из игроков одерживает победу (1 – первый, Петя; 2 – второй, Ваня; 0 –не определено). Игрок 1 может победить в заданной позиции, если одним ходом (макрос F) приводит кучу к состоянию, не меньше VICTORYили к состоянию, когда выигрышная стратегия есть у второго (тогда в роли второго игрока выступает он сам). В других случаях выигрышной стратегией обладает второй игрок.

Программа выводит номер игрока, который одерживает победу для каждого из начальных состояний Nот 1 доVICTORY-1

Задача №308.  ЕГЭ C3 (№26) вариант с двумя кучами камней

Мало чем отличается от предыдущего, за исключением того, что начальное состояние каждой кучи определяется не одномерным массивом, а матрицей.

#include <iostream>

#define VICTORY 20

#define F(n) a[i]*n+b[i]

using namespace std;

int a[]={2,1}, b[]={0,3}, player[VICTORY][VICTORY]={0,};

 

int main(){

int k = sizeof(a)/sizeof(int), n1, n2, i;

cout << "Игра заканчивается при сумме " << VICTORY;

cout << "\nВозможныеходы:\n";

for(i=0; i<k; i++)

   cout<<i<< ". увеличитькучув " <<a[i] <<

" и прибавить " << b[i] << endl;

 

for(int n1 = VICTORY - 1; n1; n1--)

   for(int n2 = VICTORY - 1; n2; n2--){

       for(int i = 0; i<k; i++)

           if(F(n1) + n2 >= VICTORY

                || n1 + F(n2) >= VICTORY)

               player[n1][n2] = 1;

           else

               if(player[F(n1)][n2]==2 || player[n1][F(n2)]==2)

                   player[n1][n2] = 1;

       if(!player[n1][n2]) player[n1][n2] = 2;

       cout << n1 << ',' << n2 << " победа "

<< player[n1][n2] << endl;

}

}

Программа выводит номер игрока, обладающего выигрышной стратегией для всех N1, N2 (исходное количество камней в первой и второй куче) от 1 до VICTORY-1

Задача №309.  Задача «Игра-2» (acmp.ru)

Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.

Входные данные

В первой строке записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.

Выходные данные

В единственную строку нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.

Пример

Ввод	Вывод
4 3 2 5 4	1
6 5 5 5 5 5 5	0
9 2 1 3 2 9 1 2 3 1	2
10 2 5 3 12 4 6 13 7 1 3	1

Решение

Попробуем решить задачу следующим образом. Будем запоминать в элементе двумерного массиваb[i][j] наилучшую сумму, которую сможет собрать игрок на интервале от i-го элемента до j-го при условии, что соперник играет правильно, т.е. тоже пытается набрать наибольшую сумму.

Очевидно, в случае интервала из одного элемента b[i][i]=a[i]. Для интервала из двух соседних элементов b[i][i+1]=max(a[i],a[i+1]).

Учитывая стратегию соперника, игрок должен для интервала (l,r) выбрать наилучший из двух вариантов

       b[l][r]=max(a[l]+min(b[l+1][r-1], b[l+2][r] ) , a[r] + min(b[l][r-2], b[l+1][r-1] ))

Т.е. после выбора игроком слева a[l], соперник сделает наилучший ход, забрав a[l+1] либо a[r]. Таким образом, игроку достанется «худший» из двух возможных интервалов (l+1, r-1)и (l+2, r).

Если же игрок выберет справа a[r], соперник сделает наилучший ход, забрав a[l] либо a[r-1]. Таким образом, игроку достанется «худший» из двух возможных интервалов (l+1, r-1) и (l, r-2).

Если в итоге первому игроку удастся собрать больше, чем достанется второму, то он побеждает, если меньше – проигрывает. Востальныхслучаяхничья.

#include<iostream>

#include <cstdlib>

#define P 100

using namespace std;

int a[P],b[P][P];

 

int best(int l,int r){

if(b[l][r]>0){return b[l][r];}

else{

   b[l][r]=max (a[l]+min(best(l+1,r-1),best(l+2,r)) ,

               a[r]+min(best(l+1,r-1),best(l,r-2)));

   return b[l][r];

}

}

int main(){

int n,sum=0,ans;

cin>>n;

for(int i=0;i<n;i++)

   for(int j=0;j<n;j++)

       b[i][j]=0;

for(int i=0;i<n;i++){

   cin>>a[i];

   sum+=a[i];

}

for(int i=0;i<n;i++){

   b[i][i]=a[i];

}

for(int i=0;i<n-1;i++){

   b[i][i+1]=max(a[i],a[i+1]);;

}      

ans=best(0,n-1);

if(ans>sum-ans)cout<<"1\n";

if(ans<sum-ans)cout<<"2\n";

if(ans==sum-ans)cout<<"0\n";

return 0;

}

 

Задача №310.  Игра «Жизнь»