Advertisement
Guest User

Untitled

a guest
Oct 20th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None | 0 0
  1.  
  2. #include <stdio.h>
  3.  
  4. #define MAX_N 100
  5. #define MAX_VALUE 100
  6. #define FLAG -5
  7.  
  8. int n,t;
  9. int numbers[MAX_N];
  10. int signs[MAX_N];
  11.  
  12. FILE *fp;
  13.  
  14. void read_input(void)
  15. {
  16. int i;
  17.  
  18. // reading from "SUBTRACT.IN"
  19.  
  20. fp = fopen("SUBTRACT.IN","rt");
  21.  
  22. fscanf(fp,"%d %d",&n,&t);
  23.  
  24. for (i = 0;i < n;++i)
  25. fscanf(fp,"%d",numbers + i);
  26.  
  27. fclose(fp);
  28. }
  29.  
  30. void solve(void)
  31. {
  32. int i,j;
  33. int sum,target,number;
  34. int table[2 * MAX_VALUE * MAX_N + 1];
  35.  
  36. // calculating "sum" of all numbers and "target"
  37. // first number in sequence must be plus, second must be minus
  38.  
  39. sum = 0;
  40.  
  41. for (i = 2;i < n;++i)
  42. sum += numbers[i];
  43.  
  44. target = sum - (t - (numbers[0] - numbers[1]));
  45.  
  46. // dynamically generating "table", looking for target
  47.  
  48. table[0] = -1;
  49.  
  50. for (i = 1;i <= target;++i)
  51. table[i] = FLAG;
  52.  
  53. for (i = 2;i < n;++i)
  54. {
  55. for (j = target - 1;j >= 0;--j)
  56. if (table[j] != FLAG)
  57. {
  58. if (table[j + 2 * numbers[i]] == FLAG)
  59. table[j + 2 * numbers[i]] = i;
  60.  
  61. if (table[target] != FLAG)
  62. break;
  63. }
  64.  
  65. if (table[target] != FLAG)
  66. break;
  67. }
  68.  
  69. // generating "signs", some numbers will have plus sign in front of them
  70. // some numbers will have minus sign
  71.  
  72. signs[0] = 1;
  73.  
  74. signs[1] = -1;
  75.  
  76. for (i = 2;i < n;++i)
  77. signs[i] = 1;
  78.  
  79. number = target;
  80.  
  81. do
  82. {
  83. if (!number)
  84. break;
  85.  
  86. signs[table[number]] = -1;
  87. number -= 2 * numbers[table[number]];
  88. } while (1);
  89.  
  90. }
  91.  
  92. void write_output(void)
  93. {
  94. int i;
  95. int number,counter,temp;
  96.  
  97. // writing to "SUBTRACT.OUT"
  98.  
  99. fp = fopen("SUBTRACT.OUT","wt");
  100.  
  101. // transforming "signs" to sequence of contractions
  102. // going from end of "signs", looking for subsequence with minus sign on
  103. // the beginning and plus signs on the rest of subsequence
  104.  
  105. number = n - 1;
  106. counter = 0;
  107.  
  108. do
  109. {
  110. while (signs[number] == -1)
  111. --number;
  112.  
  113. if (!number)
  114. break;
  115.  
  116. temp = 0;
  117.  
  118. while (signs[number] == 1)
  119. {
  120. --number;
  121. ++temp;
  122. }
  123.  
  124. for (i = 0;i < temp;++i)
  125. {
  126. fprintf(fp,"%d\n",number + 1);
  127. ++counter;
  128. }
  129.  
  130. --number;
  131. } while (1);
  132.  
  133. // other contractions is 1, total number of contractions must be n-1
  134.  
  135. for (i = 0;i < n - 1 - counter;++i)
  136. fprintf(fp,"1\n");
  137.  
  138. fclose(fp);
  139. }
  140.  
  141. int main(void)
  142. {
  143. read_input();
  144.  
  145. solve();
  146.  
  147. write_output();
  148.  
  149. return 0;
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement