Sono date N tessere di domino, dove ogni tessera contiene due numeri compresi da 0 a 6 in
corrispondenza delle sue due estremità. Le tessere possono essere ruotate e la regola impone che due
tessere possono essere concatenate se le loro estremità in contatto hanno inciso lo stesso numero. Aiuta a
trovare il maggior numero di tessere che si possono concatenare a formare un’unica catena: non è detto
che si riescano sempre a usare tutte le tessere; inoltre, possono esserci due o più tessere uguali a meno di
rotazioni.
Dati di input
Il file input.txt è composto da N+1 righe. La prima riga contiene l’intero positivo N, il numero delle
tessere a disposizione. Ciascuna delle successive N righe contiene due interi positivi (compresi da 0 a 6)
separati da una spazio, che rappresentano i numeri incisi sulle estremità delle tessere.
Dati di output
Il file output.txt è composto da una sola riga contenente il massimo numero di tessere che possono
essere concatenate con le regole del domino.
Assunzioni
2 ≤ N ≤ 10.
Esempi di input/output
File input.txt File output.txt
6 5
3 0
4 0
2 6
4 4
0 1
1 0
Il risultato è dato dalla somma delle metà di tutte le somme di presenze di un numero meno 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<cstdlib> #include<iostream> #include<fstream> #include<cstring> #define N 10 using namespace std; ifstream in; ofstream out; int n, t1,t2,v[7],tes=1; int main(){ in.open("input.txt"); out.open("output.txt"); in>>n; memset(v,0,7); for (int i=0; i<n;i++){ in>>t1>>t2; v[t1]++; v[t2]++; } for (int i=0;i<7;i++){ if (v[i]%2==1) v[i]--; tes+=v[i]/2;} out<<tes; return 0;} |
