QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471449#6395. Equation DiscoveringUESTC_Snow_HalationWA 380ms173320kbC++144.0kb2024-07-10 21:15:012024-07-10 21:15:01

Judging History

你现在查看的是最新测评结果

  • [2024-07-10 21:15:01]
  • 评测
  • 测评结果:WA
  • 用时:380ms
  • 内存:173320kb
  • [2024-07-10 21:15:01]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
constexpr int max_n = 500;
double eps = 1e-6;

struct layer {
  char op;
  int ld, rd;
  int ll, rl;
  vector<long double> value;
  layer(char op, int ld, int ll, int rd, int rl, vector<long double> value) : op(op), ld(ld), ll(ll), rd(rd), rl(rl), value(std::move(value)) {}

  string to_string();
};

vector<layer> fx[20];
vector<long double> ans;
int n;

string layer::to_string() {
  string s;
  switch (op) {
  case 's':
    s = "sin" + fx[ll][ld].to_string();
    break;
  case 'c':
    s = "cos" + fx[ll][ld].to_string();
    break;
  case '+':
  case '-':
  case '*':
  case '/':
    s = fx[ll][ld].to_string() + op + fx[rl][rd].to_string();
    break;
  case 'x':
    s = "x";
    break;
  }
  return "(" + s + ")";
}

bool equ(vector<ld>& x) {
  for (int i = 0; i < n; ++i) {
    if (abs(x[i] - ans[i]) > eps) return false;
  }
  return true;
}

void solve() {
  cin >> n;
  fx[0].emplace_back('x', 0, 0, 0, 0, vector<ld>(n));
  ans.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> fx[0][0].value[i] >> ans[i];
  }
  for (int i = 1; i <= 9; ++i) {
    for (int j = 0; j < fx[i - 1].size(); ++j) {
      fx[i].emplace_back('s', j, i - 1, 0, 0, vector<ld>(n));
      for (int k = 0; k < n; ++k) {
        fx[i].back().value[k] = sin(fx[i - 1][j].value[k]);
      }
      if (equ(fx[i].back().value)) {
        cout << fx[i].back().to_string() << '\n';
        return;
      }
      fx[i].emplace_back('c', j, i - 1, 0, 0, vector<ld>(n));
      for (int k = 0; k < n; ++k) {
        fx[i].back().value[k] = cos(fx[i - 1][j].value[k]);
      }
      if (equ(fx[i].back().value)) {
        cout << fx[i].back().to_string() << '\n';
        return;
      }
    }
    for (int j = 0, jj; j <= i - 2; ++j) {
      jj = i - 2 - j;
      for (int l = 0; l < fx[j].size(); ++l) {
        for (int r = 0; r < fx[jj].size(); ++r) {
          fx[i].emplace_back('+', l, j, r, jj, vector<ld>(n));
          for (int k = 0; k < n; ++k) {
            fx[i].back().value[k] = fx[j][l].value[k] + fx[jj][r].value[k];
          }
          if (equ(fx[i].back().value)) {
            cout << fx[i].back().to_string() << '\n';
            return;
          }

          fx[i].emplace_back('-', l, j, r, jj, vector<ld>(n));
          for (int k = 0; k < n; ++k) {
            fx[i].back().value[k] = fx[j][l].value[k] - fx[jj][r].value[k];
          }
          if (equ(fx[i].back().value)) {
            cout << fx[i].back().to_string() << '\n';
            return;
          }

          fx[i].emplace_back('*', l, j, r, jj, vector<ld>(n));
          for (int k = 0; k < n; ++k) {
            fx[i].back().value[k] = fx[j][l].value[k] * fx[jj][r].value[k];
          }
          if (equ(fx[i].back().value)) {
            cout << fx[i].back().to_string() << '\n';
            return;
          }

          fx[i].emplace_back('/', l, j, r, jj, vector<ld>(n));
          for (int k = 0; k < n; ++k) {
            if (abs(fx[jj][r].value[k]) < 0.15) {
              fx[i].pop_back();
              break;
            }
            fx[i].back().value[k] = fx[j][l].value[k] / fx[jj][r].value[k];
          }
          if (equ(fx[i].back().value)) {
            cout << fx[i].back().to_string() << '\n';
            return;
          }
        }
      }
    }
  }
//  for (int i =0; i <= 9; ++i) {
//    for (auto& item: fx[i]) {
//      cout << item.to_string();
//      for (auto& v: item.value) {
//        cout << ",  " << v;
//      }
//      cout << '\n';
//    }
//  }
}

int main() {
//  freopen("code.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
//    cin >> T;
//    scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        // cout << "Case " << i << ": ";
        solve();
    }
    return 0;
}

/*
3 3
2.4.2
.....
4.8.4
.....
2.5.3

5 5
3.4.4.4.2
.........
4.7.7.7.4
.........
4.8.7.7.4
.........
4.7.7.7.5
.........
2.4.4.4.2
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4240kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

((x)*(x))

result:

ok great!!

Test #2:

score: 0
Accepted
time: 1ms
memory: 4356kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

(((sin(x))/(x))/(x))

result:

ok great!!

Test #3:

score: 0
Accepted
time: 0ms
memory: 4100kb

input:

5
77.685777 233.057331
-66.445083 -199.335249
79.966717 239.900151
84.982130 254.946390
-31.528900 -94.586700

output:

((x)+((x)+(x)))

result:

ok great!!

Test #4:

score: 0
Accepted
time: 19ms
memory: 12292kb

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:

((x)*((sin(x))/((x)*(cos(x)))))

result:

ok great!!

Test #5:

score: 0
Accepted
time: 5ms
memory: 5548kb

input:

5
78.611917 -0.992212
-29.857271 1.011993
-75.513655 1.006611
68.512394 1.145128
7.961096 0.881661

output:

((cos(x))+((sin(x))*(sin(x))))

result:

ok great!!

Test #6:

score: 0
Accepted
time: 0ms
memory: 4196kb

input:

5
-78.733375 0.503570
-20.187183 0.735779
-38.984992 0.730890
47.859232 0.622831
-19.657164 0.641512

output:

(sin(sin(cos(cos(x)))))

result:

ok great!!

Test #7:

score: 0
Accepted
time: 5ms
memory: 5236kb

input:

5
3.241091 -32.628130
-83.514144 86.463432
33.586619 40.691607
41.123543 -147.352644
26.896326 27.404018

output:

((x)*((x)/((x)*(sin(x)))))

result:

ok great!!

Test #8:

score: -100
Wrong Answer
time: 380ms
memory: 173320kb

input:

20
-4.908422 -0.693287
3.569189 0.328182
1.946572 -0.667466
6.515336 -0.829948
-1.394076 0.752980
6.722989 0.831881
1.241795 0.835231
-2.443177 -0.143098
-4.180762 -0.803482
1.511247 0.589509
0.627755 0.554244
-1.865604 -0.470029
-4.756347 -0.656984
1.850611 -0.426016
6.580133 -0.474416
6.861815 -0....

output:


result:

wrong output format Unexpected end of file - token expected