fork download
copy 
  1. #include<iostream>
  2. #include<cstdlib>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6. #define TEST_DATA false
  7. #define PRINT_DEBUG_INFO false
  8. #define PRINT_RESULT true
  9.  
  10. int Newton( int n, int k) 
  11. {
  12.     int Wynik = 1;
  13.  
  14.     for( int i = 1; i <= k; i++)
  15.     {
  16.         Wynik = Wynik * ( n - i + 1 ) / i;
  17.     }
  18. return Wynik;
  19. }
  20.  
  21. int main()
  22. {
  23. 	int d, n, all;
  24. 	d = n = all = 0;
  25. 	int dwu_New = 0;
  26.  
  27. 		#if TEST_DATA == true
  28.  
  29. 		d = 7;
  30. 		n = 3;
  31. 		int tab[3] = {1, 2, 5};
  32. 		int tab_all[5];
  33. 		all = 5;
  34.  
  35. 		for (int i=0; i<=all; i++)
  36. 		{
  37. 			if ( i == 0)
  38. 				tab_all[i] = 0;
  39. 			else if (i == (all - 1))
  40. 				tab_all[all-1] = d;
  41. 			else if ( i != 0 && i != (all - 1))
  42. 			tab_all[i] = tab[i-1];
  43. 		}
  44.  
  45. 		#else
  46. 	    cin >> d;
  47. 		cin >> n;						//d - dlugosc miarki ; n - ilosc podzialek
  48. 		int *tab = new int [n];			// tabela ktora przetrzymuje wprowadzone wskazniki
  49. 		all = n + 2;
  50. 		int *tab_all = new int [all];	//tabela ktora przetrzymywac bedzie wszystkie podzialki z 0 i koncem
  51.  
  52. 		for (int i=0; i<n; i++)		//tutaj sa zapisane wartosci tych podzialek
  53. 		{
  54. 			cin >> tab[i];
  55. 		}
  56.  
  57. 		for (int i=0; i<all; i++)
  58. 		{
  59. 			if ( i == 0)
  60. 				tab_all[i] = 0;
  61. 			else if (i == (all - 1))
  62. 				tab_all[all-1] = d;
  63. 			else if (i != 0 && i != (all - 1))
  64. 				tab_all[i] = tab[i-1];
  65. 		}										// 59-67 zapisane do tab_all wyszskich podzialek wlocznie z 0 i koncem
  66.  
  67. 		#endif
  68.  
  69. 		dwu_New = Newton( n + 2 , 2);			// policzenie ilosci komibnacji dwuelementowych
  70. 		int *tab_scale = new int [dwu_New];		// stowrzenie tablice na te kombinacje
  71.  
  72. //tablica która zawieta wszytkie podziałki to [tab_all] rozmiar 5 (test)
  73. 		int k = 0;
  74. 		for (int j=all-1; j>0; j--)
  75. 		{	
  76. 			for (int i=0; i<j; i++)
  77. 			{
  78. 				tab_scale[k] = tab_all[j] - tab_all[i];
  79. 				k++;
  80. 			}
  81. 		}
  82.  
  83. 			#if PRINT_DEBUG_INFO == true
  84. 			cout << endl << "dwumian Newtona: " << dwu_New << endl;
  85. 			cout << endl << "Tablica wszystkich podzialek: " << dwu_New << endl;
  86. 			for (int i=0; i<all; i++)
  87. 			{
  88. 				cout << tab_all[i] << ", ";
  89. 			}
  90. 	//ta tablica wyswietla wysztkie mozliwe do uzyskania wyniki, nie uwzglednia 0		
  91. 			cout << endl << "*****tablica z wszystkimi różnicami: " << endl;
  92. 			for (int i=0; i<dwu_New; i++)
  93. 			{
  94. 				cout << tab_scale[i] << ", ";
  95. 			}
  96. 			#endif
  97.  
  98. 		sort(tab_scale, tab_scale+dwu_New);		//funkcja sortujaca 
  99.  
  100. 			#if PRINT_DEBUG_INFO == true
  101. 			cout << endl << "*****tablica z wszystkimi różnicami posegregowana: " << endl;
  102. 			for (int i=0; i<dwu_New; i++)
  103. 			{
  104. 				cout << tab_scale[i] << ", ";
  105. 			}
  106. 			#endif
  107.  
  108. 		int *niepowtarzalne = new int [dwu_New];
  109. 		int l = 0;
  110. 		for (int i=0; i<dwu_New; i++)
  111. 		{
  112. 			if (tab_scale[i] != tab_scale[i+1])
  113. 			{
  114. 				niepowtarzalne [l] = tab_scale[i];
  115. 				l++;
  116. 			}
  117. 		}
  118.  
  119. 			#if PRINT_DEBUG_INFO == true
  120. 			cout << endl << "*****tablica z różnicami posegregowana bez duplikatow: " << endl;
  121. 			for (int i=0; i<l; i++)
  122. 			{
  123. 				cout << niepowtarzalne[i] << ", ";
  124. 			}
  125. 			#endif
  126.  
  127. 		int *miarki = new int [l];								// tu sprawdzam czy sa wszyskie miarki
  128. 		for (int i=0; i<l+1; i++)
  129. 		{
  130. 			miarki[i] = niepowtarzalne[i+1] -  niepowtarzalne[i];
  131. 		}
  132.  
  133. 			#if PRINT_DEBUG_INFO == true
  134. 			cout << endl << "Czy sa wszystkie miarki " << endl;
  135. 			for (int i=0; i<l-1; i++)
  136. 			{
  137. 				cout << miarki[i] << ", ";
  138. 			}
  139. 			cout << endl;
  140. 			for (int i=0; i<l-1; i++)
  141. 			{
  142. 				if (i == l-2 && miarki[l-2] == 1)
  143. 				{
  144. 					cout << endl << "Mozna wyznaczyc wszystkie mierki. Tak. " << endl;
  145. 				}
  146. 				else if (miarki[i] != 1)
  147. 				{
  148. 					cout << endl << "Nie mozna zmierzyc wszystkich miarek. Nie." << endl;
  149. 					break;
  150. 				}
  151. 			}		
  152. 			#endif
  153. 		#if PRINT_RESULT == true	
  154. 		for (int i=0; i<l-1; i++)
  155. 		{
  156. 			if (i == l-2 && miarki[l-2] == 1)
  157. 			{
  158. 				cout << endl << "Tak" << endl;
  159. 			}
  160. 			else if (miarki[i] != 1)
  161. 			{
  162. 				cout << endl << "Nie" << endl;
  163. 				break;
  164. 			}
  165. 		}	
  166. 		#endif
  167.  
  168. 		delete [] tab; 
  169. 		delete [] tab_scale;
  170. 		delete [] tab_all; 
  171. 		delete [] niepowtarzalne; 
  172. 		delete [] miarki; 
  173.  
  174. 	return 0;
  175. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
6 2
1 4
10 4
1 4 7 9
22 6
2 8 10 17 18 21
6 2
2 3
stdout
copy 
Tak
https://ideone.com/dDIiEh
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!