API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
68
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.56 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. int*** games;
  6. int number_of_games = 0;
  7. int* number_of_points;
  8. int** pieces;
  9. int num_pieces , counter = 0;
  10. int** points;
  11. int cmp(int *a, int *b){
  12. int* xi = (int*)a;
  13. int* xj = (int*)b;
  14. if(xi[0] < xj[0])return -1;
  15. if(xi[0] > xj[0]) return 1;
  16. if(xi[1] < xj[1])return -1;
  17. if(xi[1] > xj[1])return 1;
  18. return 0;
  19. }
  20. int* input(){
  21. int *visited;
  22.  
  23. int out = 0;
  24. int pos = 0;
  25. int contador = 0;
  26. int i,j,aux_x,aux_y;
  27. scanf("%d",&num_pieces);
  28. visited = (int*)malloc(num_pieces*sizeof(int));
  29. for(i=0;i<num_pieces;i++){
  30. visited[i] = 1;
  31. }
  32. pieces = (int**)malloc(num_pieces*sizeof(int*));
  33. for(i = 0; i < num_pieces; i++){
  34. scanf("%d %d",&aux_x,&aux_y);
  35. for(j=0;j<pos;j++){
  36. if((aux_x==pieces[j][0] && aux_y==pieces[j][1]) || (aux_y==pieces[j][0] && aux_x==pieces[j][1])){
  37. visited[j]++;
  38. contador++;
  39. out = 1;
  40. break;
  41. }
  42. }
  43. if(out==0){
  44. pieces[pos] = (int*) malloc(2*sizeof(int));
  45. pieces[pos][0] = aux_x;
  46. pieces[pos][1] = aux_y;
  47. pos++;
  48. }
  49. out=0;
  50. }
  51. num_pieces -= contador;
  52. return visited;
  53. }
  54. int** insere(int** points, int num_points,int index,int x1,int y1,int x2,int y2,int n){
  55. //if(n ==1 && num_points>6){
  56. //printf("Antes %d %d %d %d %d %d %d\n",n,num_points,x2,y2,x1,y1,index);
  57. // printarray(points,num_points);
  58. //}
  59. int i, j ,aux1,aux2;
  60. int** aux = (int**) malloc((num_points+n)*sizeof(int*));
  61. if(n == -1){
  62. for(i = 0; i< (num_points+n); i++){
  63. aux[i] = (int*) malloc(2 * sizeof(int));
  64. if( i >= index){
  65. aux[i][0] = points[i+1][0];
  66. aux[i][1] = points[i+1][1];
  67. }
  68. else{
  69. aux[i][0] = points[i][0];
  70. aux[i][1] = points[i][1];
  71. }
  72. }
  73. }
  74. else if(n == 0 || n == 1){
  75. for(i = 0 ; i<(num_points + n) ; i++){
  76. aux[i] = (int*) malloc(2 * sizeof(int));
  77. if( i == index){
  78. aux[i][0] = x1;
  79. aux[i][1] = y1;
  80. }
  81. else if(i < num_points){
  82. if(aux[i][0] == NULL){
  83. //printarray(points,num_points);
  84. //printf("%d \n",points[i][0]);
  85. }
  86. aux[i][0] = points[i][0];
  87. aux[i][1] = points[i][1];
  88. }
  89. }
  90. if(n == 1){
  91. aux[num_points][0] = x2;
  92. aux[num_points][1] = y2;
  93. }
  94. }
  95. // if(n==1 && num_points>6){
  96. //printf("DURING\n");
  97. // printarray(aux,num_points+n);
  98. //}
  99. for(i = 1;i < (num_points + n);i++){
  100. j = i - 1;
  101. aux1 = aux[i][0];
  102. aux2 = aux[i][1];
  103. while(j >= 0 && aux[j][0] > aux1){
  104. aux[j+1][0] = aux[j][0];
  105. aux[j+1][1] = aux[j][1];
  106. j--;
  107. }
  108. aux[j+1][0] = aux1;
  109. aux[j+1][1] = aux2;
  110.  
  111. }
  112. return aux;
  113.  
  114.  
  115. }
  116. void printarray(int** array,int size){
  117. int i;
  118. for(i = 0;i<size;i++){
  119. printf("%d %d\n",array[i][0],array[i][1]);
  120. }
  121. printf("\n");
  122. }
  123.  
  124. int check(int** currently_game,int points){
  125. int i,j;
  126. for(i=0;i<number_of_games;i++){
  127. if(number_of_points[i]!=points)
  128. continue;
  129. for(j=0;j<points;j++){
  130. if(games[i][j][0] != currently_game[j][0] || games[i][j][1] != currently_game[j][1]){
  131. break;
  132. }
  133. if(j==points-1){
  134. return 0;
  135. }
  136. }
  137. if(i == number_of_games - 1){
  138. return 1;
  139. }
  140. }
  141. return 0;
  142.  
  143. }
  144. int ** sort(int** pieces, int size){
  145. int i,j;
  146. int* aux = (int*)malloc(2*sizeof(int));
  147. int** arr = (int**)malloc(size*sizeof(int*));;
  148. for(i=0;i<size;i++){
  149. arr[i] = (int*)malloc(2*sizeof(int));
  150. arr[i][0] = pieces[i][0];
  151. arr[i][1] = pieces[i][1];
  152. }
  153. for(i = 0;i<size;i++){
  154. for(j = i+1;j<size;j++){
  155. if(cmp(arr[i],arr[j]) == 1){
  156. aux[0] = arr[i][0];
  157. aux[1] = arr[i][1];
  158. arr[i][0] = arr[j][0];
  159. arr[i][1] = arr[j][1];
  160. arr[j][0] = aux[0];
  161. arr[j][1] = aux[1];
  162. }
  163. }
  164. }
  165. return arr;
  166.  
  167. }
  168. void algo(int** points, int* visited,int num_points,int** currently_game,int points_game){
  169. int i, j, k, max, limx,limy,m = 0;
  170. int** aux;
  171.  
  172. if(num_points <= 2){
  173. for(i = 0; i < num_pieces; i++){
  174. if(visited[i] != 0){
  175. m = 1;
  176. break;
  177. }
  178. if(m != 1 && i == num_pieces-1){
  179. currently_game = sort(currently_game,points_game);
  180.  
  181.  
  182. if(number_of_games != 0){
  183. if(check(currently_game,points_game) == 1){
  184.  
  185. counter++;
  186. number_of_games++;
  187. for(k=0;k<points_game;k++){
  188. games[number_of_games-1][k][0] = currently_game[k][0];
  189. games[number_of_games-1][k][1] = currently_game[k][1];
  190. }
  191. number_of_points[number_of_games-1] = points_game;
  192. }
  193. }else{
  194.  
  195. for(k=0;k<points_game;k++){
  196. games[number_of_games][k][0] = currently_game[k][0];
  197. games[number_of_games][k][1] = currently_game[k][1];
  198. }
  199. number_of_points[0] = points_game;
  200. number_of_games++;
  201. counter++;
  202. }
  203. return;
  204. }
  205. }
  206. }
  207.  
  208.  
  209. for(j = 0;j < num_points; j++){
  210. for(i = 0;i < num_pieces; i++){
  211. if(visited[i] > 0){
  212.  
  213. if(j == 0){
  214. limx = points[j+1][0];
  215. limy = INT_MAX;
  216. }
  217. else if(j == (num_points-1)){
  218. limx = INT_MAX;
  219. limy = points[j-1][1];
  220. }
  221. else{
  222. limx = points[j+1][0];
  223. limy = points[j-1][1];
  224. }
  225. if(pieces[i][0] == pieces[i][1])
  226. max = 1;
  227.  
  228. else
  229. max = 2;
  230. for(k = 0; k < max; k++){
  231.  
  232. if((points[j][0] + pieces[i][k]) <= limx && (points[j][1] + pieces[i][abs(k-1)]) <= limy ){
  233. if(points[j][0] + pieces[i][k] < limx && points[j][1] + pieces[i][abs(k-1)] == limy){
  234. points_game++;
  235. currently_game[points_game-1][0] = points[j][0]+pieces[i][k];
  236. currently_game[points_game-1][1] = points[j][1];
  237.  
  238. aux = insere(points,num_points,j,points[j][0]+pieces[i][k],points[j][1],0,0,0);
  239. visited[i]--;
  240. algo(aux,visited,num_points,currently_game,points_game);
  241. points_game--;
  242. visited[i]++;
  243. }
  244. else if(points[j][0] + pieces[i][k] < limx && points[j][1] + pieces[i][abs(k-1)] < limy){
  245. points_game+=2;
  246. currently_game[points_game-2][0] = points[j][0];
  247. currently_game[points_game-2][1] = points[j][1]+pieces[i][abs(k-1)];
  248. currently_game[points_game-1][0] = points[j][0]+pieces[i][k];
  249. currently_game[points_game-1][1] = points[j][1];
  250. aux = insere(points,num_points,j,points[j][0],points[j][1]+pieces[i][abs(k-1)],points[j][0]+pieces[i][k],points[j][1],1);
  251. num_points++;
  252. visited[i]--;
  253. algo(aux,visited,num_points,currently_game,points_game);
  254. visited[i]++;
  255. num_points--;
  256. points_game-=2;
  257. }
  258. else if(points[j][0] + pieces[i][k] == limx && points[j][1] + pieces[i][abs(k-1)] == limy){
  259. aux = insere(points,num_points,j,0,0,0,0,-1);
  260. visited[i]--;
  261. num_points--;
  262. algo(aux,visited,num_points,currently_game,points_game);
  263. num_points++;
  264. visited[i]++;
  265. }
  266. else if(points[j][0] + pieces[i][k] == limx && points[j][1] + pieces[i][abs(k-1)] < limy){
  267. points_game++;
  268. currently_game[points_game-1][0] = points[j][0];
  269. currently_game[points_game-1][1] = points[j][1]+pieces[i][abs(k-1)];
  270. aux = insere(points,num_points,j,points[j][0],points[j][1]+pieces[i][abs(k-1)],0,0,0);
  271. visited[i]--;
  272. algo(aux,visited,num_points,currently_game,points_game);
  273. visited[i]++;
  274. points_game--;
  275. }
  276.  
  277. }
  278.  
  279.  
  280. }
  281. }
  282. }
  283. }
  284. }
  285.  
  286. int main()
  287. {
  288. int i, j, max;
  289. int** points;
  290. int* used_pieces = input();
  291. points = (int**)malloc(30*sizeof(int*));
  292. games = (int***)malloc(100*sizeof(int**));
  293. number_of_points = (int*)malloc(100*sizeof(int));
  294. int** currently_game = (int**)malloc(30*sizeof(int*));
  295. for(i=0;i<100;i++){
  296. games[i] = (int**)malloc(30*sizeof(int*));
  297. for(j = 0;j<30;j++){
  298. games[i][j] = (int*)malloc(2*sizeof(int));
  299. }
  300. }
  301. for(i = 0; i < 30 ; i++){
  302. points[i] = (int*)malloc(2*sizeof(int));
  303. currently_game[i] = (int*)malloc(2*sizeof(int));
  304. }
  305.  
  306. for(i=0;i<num_pieces;i++){
  307. points[0][0] = pieces[i][0];
  308. points[0][1] = 0;
  309. points[1][0] = 0;
  310. points[1][1] = pieces[i][1];
  311. points = insere(points,3,2,0,0,0,0,-1);
  312. if(pieces[i][0] == pieces[i][1]){
  313. max = 1;
  314. }
  315. else
  316. max = 2;
  317. for(j = 0;j < max; j++ ){
  318. if(j == 1){
  319. points[0][0] = pieces[i][1];
  320. points[0][1] = 0;
  321. points[1][0] = 0;
  322. points[1][1] = pieces[i][0];
  323. points = insere(points,3,2,0,0,0,0,-1);
  324. }
  325. currently_game[0][0] = points[0][0];
  326. currently_game[0][1] = points[0][1];
  327. currently_game[1][0] = points[1][0];
  328. currently_game[1][1] = points[1][1];
  329. used_pieces[i]--;
  330. algo(points,used_pieces,2,currently_game,2);
  331. used_pieces[i]++;
  332. }
  333. }
  334. printf("%d\n",counter);
  335. return 0;
  336. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!