Advertisement
gmusya

Untitled

Dec 12th, 2022
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.74 KB | None | 0 0
  1. include "testlib.h"
  2. #include <iostream>
  3. #include <sstream>
  4. #include <map>
  5.  
  6. using ld = long double;
  7.  
  8. int n, k, m;
  9.  
  10. ld Evaluate(const std::string& str) {
  11. if (str.empty()) {
  12. throw std::runtime_error("Cannot evaluate empty expression");
  13. }
  14. for (int64_t i = 0; i < str.size(); ++i) {
  15. if (str[i] == '(') {
  16. int64_t j = i + 1;
  17. int64_t balance = 1;
  18. while (balance) {
  19. if (j == str.size()) {
  20. throw std::runtime_error("Bad brackets");
  21. }
  22. if (str[j] == '(') {
  23. ++balance;
  24. } else if (str[j] == ')') {
  25. --balance;
  26. }
  27. ++j;
  28. }
  29. std::string new_str = str.substr(i + 1, j - i - 2);
  30. ld result_in_brackets = Evaluate(new_str);
  31. std::string string_result = std::to_string(result_in_brackets);
  32. return Evaluate(str.substr(0, i) + string_result + str.substr(j, str.size() - j));
  33. }
  34. }
  35. for (int64_t i = 0; i < str.size(); ++i) {
  36. if (str[i] == '+') {
  37. std::string left = str.substr(0, i);
  38. std::string right = str.substr(i + 1, str.size() - i - 1);
  39. return Evaluate(left) + Evaluate(right);
  40. }
  41. }
  42. for (int64_t i = static_cast<int64_t>(str.size()) - 1; i >= 0; i--) {
  43. if (str[i] == '-') {
  44. if (i != 0) {
  45. std::string left = str.substr(0, i);
  46. std::string right = str.substr(i + 1, str.size() - i - 1);
  47. return Evaluate(left) + Evaluate(right);
  48. } else {
  49. std::string right = str.substr(i + 1, str.size() - i - 1);
  50. return -Evaluate(right);
  51. }
  52. }
  53. }
  54. for (int64_t i = 0; i < str.size(); ++i) {
  55. if (str[i] == '*') {
  56. std::string left = str.substr(0, i);
  57. std::string right = str.substr(i + 1, str.size() - i - 1);
  58. return Evaluate(left) * Evaluate(right);
  59. }
  60. }
  61. for (int64_t i = static_cast<int64_t>(str.size()) - 1; i >= 0; i--) {
  62. if (str[i] == '/') {
  63. std::string left = str.substr(0, i);
  64. std::string right = str.substr(i + 1, str.size() - i - 1);
  65. return Evaluate(left) / Evaluate(right);
  66. }
  67. }
  68. if (str[0] == ' ') {
  69. return Evaluate(str.substr(1, str.size() - 1));
  70. }
  71. if (str.back() == ' ') {
  72. return Evaluate(str.substr(0, str.size() - 1));
  73. }
  74. if (str == "n") {
  75. return n;
  76. } else if (str == "k") {
  77. return k;
  78. } else if (str == "m") {
  79. return m;
  80. }
  81. std::stringstream ss;
  82. ss << str;
  83. ld result;
  84. ss >> result;
  85. return result;
  86. }
  87.  
  88. std::string correct = "(n - k) / 2 * (m - k - (n - k) / 2)";
  89. const ld EPS = 1e-6;
  90.  
  91.  
  92.  
  93. std::map<std::string, int> kek = {{"(n - k) / 2 * (m - k - (n - k) / 2)", 100},
  94. {"(n - k) * (m - k - (n - k) / 2)", 50},
  95. {"(m - k) / 2 * (n - k - (m - k) / 2)", 70},
  96. {"(n * m - (n - k) / 2 * (n - k) / 2 - n * k - m * k) / 2", 50},
  97. {"(n * m - (n - k) / 2 * (n - k) / 2 - n * k - m * k)", 30},
  98. {"(n-k)*(n-k)/4", 20},
  99. {"(m*n-k*n-k*m)/2-(n-k)/4*(n-k)", 40},
  100. {"m-(n-k)/2-k", 30},
  101. {"(n-k)/2*(m-(n-k)/2)", 50},
  102. {"m-k-(n-k)/2*(n-k)/2", 70},
  103. {"(n-k)/2*(m-(n-k)/2+k)", 60},
  104. {"(n-k)*(m-k)/4", 40},
  105. {"(n-k)/2*(m-1)-k", 10},
  106. {"(n-k)*(2*m-n-3*k)/4", 10},
  107. {"(n-k/2)*(m-k-n+k/2)", 20},
  108. {"(m*n-k*n-k*m+k*k-((n-k)*(n-k))/4)/2", 60},
  109. {"(m-n/2)*(n/2-k)", 10},
  110. {"(n-k)/2*(m-(n-k)-k)", 20},
  111. {"(n-k)/2*(m-n-k/2)", 20},
  112. {"(n-k)/2*(m-k-1)", 20},
  113. {"(n-k)*(m-k)/2", 20},
  114. {"(n-k/2)*(m-k-(n-k)/2)", 60},
  115. {"(n-k)/2*(n-k)", 10},
  116. {"((n-k)/2)*((n-k)/2-k)", 10},
  117. {"(n-k)/2+(m-k-(n-k)/2)", 60},
  118. {"((n*m-(n*k+m*k)-(n-k)/2*4*2))/2", 20},
  119. {"(m*n-k*(m+n)-k*k+((n-k)*(n-k))/4)/2", 60},
  120. {"(n-k)/2*(m-n-k)", 20},
  121. {"(n-k)/2*(m-k)/3", 10},
  122. {"(n-k)*(2*m+n-3*k)/4", 10},
  123. {"((n-k)/2)*(m-k*3)", 10},
  124. {"(m*n-k*m-k*n)/2", 10},
  125. {"(m*n-n+k-k*m-k*n)/2", 10},
  126. {"(n-k)/2*m-((n-k)/2-k)", 60},
  127. {"((n - k) / 2) / (m - ((n - k) / 2) - k)", 60},
  128. {"(n*m-(n-k)/2-n*k-m*k)/2", 20},
  129. {"(n-k)*(m-n)/4", 20},
  130. {"(m/2+k)*(n/2-k/2)", 10},
  131. {"n*m-k*(m+n)", 10},
  132. {"(n/2-k/2)*(m/2+k/2)", 10},
  133. {"m-((n-k)/2)-k*((n-k)/2)", 60},
  134. {"(n*m-(n-k)/2*(m-k)/2-n*k-m*k)/2", 20},
  135. {"((n-k)/2)*((n-k)/2*m-k-(n-k)/2*(n-k)/2)", 10},
  136. {"(n-k)*(2*m-n-k)", 10},
  137. {"(n-k)/2*(m/2)", 10},
  138. {"n*m-((k*n+k*m)-k*k)-((n-k)/2*(n-k)/2)/2", 70},
  139. {"m*n-k*(n+m)-(n-k)/2*(n-k)", 50},
  140. {"(n-2)/2*(m-(n-2)/2-k)", 20},
  141. {"((n-k)/2)*(m-((n-k)/2))-k", 30},
  142. {"((n-k)/2)*((m-k)-n/2)", 20},
  143. {"(n*m-k*m-n*k)/2-((n/2)*(n/2))", 20},
  144. {"(n/2-k/2)*(m-m/3-k)", 20},
  145. {"(n-k)*(m-k)/2-(n-k)", 10},
  146. {"(n*m)-(k*m+k*n)/2", 10},
  147. {"((n*m)-(n*k+m*k))*(2/6)", 10},
  148. {"(n * m - n * k - m * k - (n - k) * (n - k)) / 2", 40},
  149. {"(m*n-(k*m-k*n-k*k))/2-((n-k)/2*(n-k)/2)", 50},
  150. {"n * m - (n - k) / 2 * (n - k) / 2 - k * n - k * m / 2", 20},
  151. {"n*m-((n-k)*(n-k)/2-k*m-k*n+k*k)/2", 60},
  152. {"(n - k) / 2 * (m - (n - k)) / 2", 20},
  153. {"(n-k)/2*(m-k-(n-k)/2*(n-k)/2)", 30},
  154. {"(m * n - k * n - m * k + k * k - (m - k) * (m - k) * 2) / 2", 30},
  155. {"(n*m-(n-k)/2*(n-k)/2-n*k)/2-m*k", 50},
  156. {"((n-k)/2+k-m)*((n-k)/2)", 30},
  157. {"n*m-(k*m+k*n-k*k)/2-(n/2-k/2)*(n/2-k/2)", 60},
  158. {"m*n-k*(m+n-k)-(((k*n-k*k)/2)*((k*n-k*k)/2))*2", 60},
  159. {"((n-k)/2)*(m-(((n-2)/2)*m)-k)", 20},
  160. {"(n*m-n*k-(m-k)*k)/2-k*k", 40},
  161. {"n-k/2*m-k-n-k/2", 60},
  162. {"m - (n - k) / 2 * (n - k) / 2", 10},
  163. {"(n-k)/2*(m-(k+(n-k)*2))", 60},
  164. {"(n - k) / 2 * (m - ((n - k) / 2 + 2))", 20},
  165. {"m*n-m*k--n*k+k*k-(n-k)*(n-k)/4-(n-k)/2*(m-(n-k)/2-k)", 60},
  166. {"((n * m) - (((n / 2 *( n / 2)) * 2) + ((k * m) + (k * n) - (k * k)))) / 2", 20},
  167. {"((n*m-(k*n+k*m))/2-((n-k)*2))/2", 20},
  168. {"(m - (n - k) - 2 * k) / 2 * (n - k) / 2", 40},
  169. {"1/2*(m*k-((m*k+n*k)+1/2*(n-k)*(n-k)))", 10},
  170. {"(n-k)*(2*n-m-k)/4", 10},
  171. {"(n * m - (n - k)) / 2 * ((n - k) / 2 - n * k - m * k) / 2", 10},
  172. {"n*m-k*(n+m)-(n-k)*(n-k)", 10},
  173. {"(n*m-n*k)/2-((n-k)/2)*((n-k)/2+k)", 20},
  174. {"(n * m - (k * m + k * n - k * k - 2 * (n - k) * (n - k))) / 2", 50},
  175. {"m*n-(m*(n+1/2*k)+1/2*n*(1/2*m+k))", 10},
  176. {"(n*m-(n*-k)/2*(n-k)/2-n*k-m*k)/2", 10},
  177. {"n*m - (n*k + m*k - k*k - (n-k)*(n-k)/2)", 50},
  178. {"(n*m)/2 - (k*n)/2 - (k*m)/2 - (k*k)/2 - ((n-k)/2)*((n-k)/2)", 20},
  179. {"(m*n-k*(m+n)-k*k-((n-k)*(n-k))/4)/2", 20},
  180. {"((n-k)/2)*((m-k)*(2/3))", 10},
  181. {"(2*m-3*k-n)*((n-k)/2)", 10},
  182. {"m*n-(((n-k)/2*(n-k)/2)*2-(k*m+k*n))/2", 20},
  183. {"(n * m - (n - k) * (n - k) - k * n - k * m - k * k) / 2", 20},
  184. {"(1 / 2) * (m * n - m * k - n * k) - (1 / 4) * (n + 4) * (n + k)", 20},
  185. {"(n-k)/2*(m-k-n-k/2)", 30},
  186. {"(n * m) - 2 * (n * k / 2) - n * k - m * k + k * k", 10},
  187. {"m * n / 2 - k * ( m + n - k) / 2 - (n - k) * (n + k) / 8", 20},
  188. {"(n * m - k * (m + n) - k * k) / 2 - (n - k / 2) * (n - k / 2)", 60},
  189. {"(n*m-((n-k)*(n-k)/2))/2", 20},
  190. {"m*n-(k*n+k*m)-((m-k)*(n-k)/3)", 10},
  191. {"(n - k) * 2 / (m - k - (n - k) / 2)", 60},
  192. {"(m * n - (m * k + (k * n - k * k))) / 2 - (n * 2 * k) / 2", 20},
  193. {"(n*m-(n-k)/2*(n-k)/-n*k-m*k)/2", 20},
  194. {"(n/2-k/2)*(m/2-k)", 10},
  195. {"n*m/2-m*k/2-(n*k-k*k)/2-(n-k/2)*(n-k/2)", 20},
  196. {"(((m - k) * (n - k) + k * k) - (((n - k) / 2) * ((n - k) / 2) * 2)) / 2", 20},
  197. {"(m * n - k * m - k * n - k * k - ((n - 2) / 2) * ((n - 2) / 2) * 2) / 2", 20},
  198. {"((k - n) * (k + (2 * m) - n)) / 4", 10},
  199. {"(m-(n-k))*((n-k)/2)", 10},
  200. {"( ( ((n-k)/2)*((n-k)/2) )*2 + ( ((n-k)/2) * (m - ((n-k)/2) ) * 2) )", 10},
  201. {"(m - n) * (n - k) - (n - k) * ((n - k) / 2) / 2", 20},
  202. {"(m * n - k * (n - k) + k * k - ((k - n)*(k - n)*2))/2", 20},
  203. {"(m - n / 2 + k / 2) * (n / 2 - k / 2 - k)", 10},
  204. {"n * m - (n - k) * (n - k) - (k * ((n - k) / 2)) - (n * k) - ((n - k) / 2) * (m - ((n - k) / 2 + k)) - (m -((n - k) / 2 + k)) * k", 10},
  205. {"(n*m-n*k-k*m-((n/2-k)*4)*2)/2", 10},
  206. {"((n-k)/(2+1))*(m-k-((n-k)/(2+1)))", 20},
  207. {"m * n - k * (n + m) / 2 - (n - k)* (n - k) / 4", 10},
  208. {"(n - k) * (m - k) - ((n - k) * (n - k) / 4)", 60},
  209. {"(n * m - (n - k) / 2 * (n - k) / 2 - n * k - m * k)", 20},
  210. {"(n*m - (n/2 + k)*m) - ((n - k)/2 * (n-k)/2 + k*(n-k)/2)", 20},
  211. {"(n * m - (n * k - n * m + k * k) - (n - k) * ((n - k) / 2)) / 2", 20},
  212. {"((n-k)/2)*((m-k-(n-k)/2)/2)", 60},
  213. {"(n*k-((k*m)+(n-k)*k)+(((n-k)/2*(n-k)/2)*2))/2", 10},
  214. {"m*n-k*n-(k*m+k*k-(n-k)/2*(n-k)/2)/2", 20}};
  215.  
  216. int Test(const std::string& str) {
  217. for (int k1 = 1; k1 <= 5; ++k1) {
  218. for (int n1 = k1 + 2; n1 <= 100; ++n1) {
  219. for (int m1 = n1 + 1; m1 <= 30; ++m1) {
  220. k = k1;
  221. n = n1;
  222. m = m1;
  223. std::vector<std::string> expressions;
  224. for (auto& now : kek) {
  225. expressions.push_back(now.first);
  226. }
  227. bool nice = false;
  228. for (auto& now : expressions) {
  229. try {
  230.  
  231. ld f1 = Evaluate(now);
  232. nice = true;
  233. ld f2 = Evaluate(str);
  234. if (abs(f1 - f2) >= EPS) {
  235. kek.erase(now);
  236. }
  237. } catch (...) {
  238. if (!nice) {
  239. return 0;
  240. }
  241. kek.erase(now);
  242. }
  243. }
  244. }
  245. }
  246. }
  247. int result = 0;
  248. for (auto& now : kek) {
  249. if (now.second > result) {
  250. result = now.second;
  251. }
  252. }
  253. return result;
  254. }
  255.  
  256. int main(int argc, char** argv) {
  257. setName("check");
  258. registerTestlibCmd(argc, argv);
  259. std::string str = ouf.readLine();
  260. if (str.size() > 1000) {
  261. quitf(_pe, "too long");
  262. }
  263. int result = Test(str);
  264. if (result == 100) {
  265. quitf(_ok, "nice");
  266. }
  267. if (result == 0) {
  268. quitf(_wa, "bad");
  269. }
  270. quitp(_pc(result - 16));
  271. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement