Задача взята з сайту e-olymp

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leqslant N \leqslant 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Тести

№	Inputs	Outputs
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	4 4 1 2 2 3 3 4 1 4	1
3	5 5 1 2 2 3 3 5 1 4 1 5	1

Код

#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 3e2+5;
ll arr[INF][INF];
void power(ll n){
    ll arr1[n][n];
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr1[i][j]=0;
            for(int k = 0 ; k < n ; k ++){
                arr1[i][j]+=arr[i][k]* arr[k][j];
            }
            
        }
    }
    for(int i  = 0 ; i < n ; i++){
        for(int j = 0 ; j < n; j++){
            arr[i][j]=arr1[i][j];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m ;
    cin>>n>>m;
    ll a,b;
    for(int i = 0 ; i < m ; i++){
        cin>>a>>b;
        a--;
        b--;
        if(a!=b){
            arr[a][b]++;
            arr[b][a]++;    
        }
    }
    power(n);
    ll to_del[n];
    for(int i = 0 ; i < n; i++){
        to_del[i]=0;
        for(int j = 0 ; j < n; j++){
            if(i==j){
                arr[i][i] = 0;
            }else{
                to_del[i]+=arr[i][j];
            }
        }
    }
    power(n);
    ll answer =0;
    for(int i = 0 ; i < n ; i++){
        answer +=arr[i][i]-to_del[i];
    }
    cout<<answer/8;
    return 0;
}

#include <iostream>

using namespace std;

typedef long long ll;

const ll INF = 3e2+5;

ll arr[INF][INF];

void power(ll n){

ll arr1[n][n];

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

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

arr1[i][j]=0;

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

arr1[i][j]+=arr[i][k]* arr[k][j];

}

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

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

arr[i][j]=arr1[i][j];

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int n,m ;

cin>>n>>m;

ll a,b;

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

cin>>a>>b;

a--;

b--;

if(a!=b){

arr[a][b]++;

arr[b][a]++;

}

power(n);

ll to_del[n];

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

to_del[i]=0;

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

if(i==j){

arr[i][i] = 0;

}else{

to_del[i]+=arr[i][j];

}

power(n);

ll answer =0;

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

answer +=arr[i][i]-to_del[i];

}

cout<<answer/8;

return 0;

}

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

Related Images:

Задача

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). $(4 ≤ N ≤ 300)$. У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Объяснение:

Існує два варіанти з’єднання: $(3,4) – (4,2) – (2,5) – (5,3)$ та $(1,4) – (4,5) – (5,3) – (3,1)$ У сусідніх деталях існують однакові замки. Це також справедливо для першої та останньої(четвертої) деталі.

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 7 1 3 1 4 2 4 2 5 3 4 3 5 4 5	2
2	5 8 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5	5

ВХОДНЫЕ ДАННЫЕ

ВЫХОДНЫЕ ДАННЫЕ

5 7
1 3
1 4
2 4
2 5
3 4
3 5
4 5

5 8
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5

Код программы

#include <iostream>
#define MAX 301
using namespace std;

int x[MAX][MAX];
int y[MAX][MAX];
int main() {
    int n,m,i,j,e,u,v,q,z,r=0;
    scanf("%d%d",&n,&m);
    for (i=0; i<m; i++) {
        scanf("%d%d",&u,&v);
        x[u-1][v-1]=1; x[v-1][u-1]=1;
    }
    for (i=0; i<n-1; i++) {
        for (j=i+1; j<n; j++) {
            q=0;
            for (e=0; e<n; e++) {
                if (x[i][e]==1 && x[j][e]==1) q++;
            }
            y[i][j]=q;
        }
    }
    for (e=0; e<n; e++) {
        for (i=e+1; i<n; i++) {
            if (x[e][i]==1) {
                for (j=i+1; j<n; j++) {
                    if (x[e][j]==1) {
                        z=y[i][j];
                        if (z>1) {
                            z--;
                            r+=z;
                            y[i][j]=z;
                        }
                    }
                }
            }
        }
    }
    printf("%d",r);
    return 0;
}

#include <iostream>

#define MAX 301

using namespace std;

int x[MAX][MAX];

int y[MAX][MAX];

int main() {

int n,m,i,j,e,u,v,q,z,r=0;

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

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

scanf("%d%d",&u,&v);

x[u-1][v-1]=1; x[v-1][u-1]=1;

}

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

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

q=0;

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

if (x[i][e]==1 && x[j][e]==1) q++;

}

y[i][j]=q;

}

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

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

if (x[e][i]==1) {

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

if (x[e][j]==1) {

z=y[i][j];

if (z>1) {

z--;

r+=z;

y[i][j]=z;

}

printf("%d",r);

return 0;

}

Решение задачи

В ячейке $x[u-1][v-1]$ стоит единица тогда и только тогда, когда у нас есть звено, имеющее на одном конце замок номер $u$, а на другом $- v$. Теперь построим таблицу, где будет записано в ячейке $y[u-1][v-1]$ количество их общих пар замков, где $u$ и $v$ это пара замков. Потом в первой таблице будем проходить по каждой строке и искать все возможные пары единиц в столбиках, пусть $u$ и $v$ это индекс выбранных столбиков. И если ячейка $y[u-1][v-1]$ больше единицы, то будем отнимать единицу в этой ячейке, чтобы отбросить случай, когда в браслете первый и четвёртый замок одинаковой. Полученное число в этой ячейке будем добавлять к ответу. А запоминать в эту же ячейку на единицу меньше, чтобы потом при подсчёте результата не посчитать один и тот же браслет два раза. Рассмотрим для наглядности пример: когда дано $5$ типов замков и $7$ типов деталей: $1-3, 1-4, 2-4, 2-5, 3-4, 3-5, 4-5$. То есть для каждой пары запомним количество общих замков, так как нам нужно, чтобы количество общих замков для пар было больше единицы, выпишем для наглядности нужные: $1-5$ имеет $2$, $2-3$ имеет $2$, $3-4$ имеет $2$, $4-5$ имеет $2$ общих замка. В первой строке в первой таблице единственная пара это $3-4$, так как общих замков этой пары больше единицы, то пара нам подходит. То есть варианты браслета $1-3-4-1$ и $1-3-4-5$, поэтому отнимем единицу и получим количество нужных браслетов, то есть один браслет уже есть, это $1-3-4-5$. Смотрим дальше, во второй строке тоже одна пара $4-5$. Варианты получаемый браслетов $2-4-5-2$ и $2-4-5-3$, опять отнимем один вариант и остальные браслеты запомним, то есть браслет $2-4-5-3$. В третей строке получится пара $4-5$, но там один вариант $3-4-5-3$, что не подходит, если бы мы ранее не запоминали на единицу меньше, то сейчас мы бы посчитали второй раз тот же браслет $3-4-5-2$, который уже есть. В итоге мы получили $2$ браслета, то есть $1-3-4-5$ и $2-4-5-3$, что есть верным ответом.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: браслеты

e-olymp 8651. Браслети (Bangles)

Вхідні дані

Вихідні дані

Тести

Код

Рішення

Посилання

Related Images:

e-olymp 8651. Браслети (Bangles)

Задача

Вхідні дані

Вихідні дані

Объяснение:

Тесты

Код программы

Решение задачи

Ссылки

Related Images: