QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177258#6395. Equation Discoveringmendicillin2WA 132ms151332kbC++173.6kb2023-09-12 19:23:442023-09-12 19:23:44

Judging History

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

  • [2023-09-12 19:23:44]
  • 评测
  • 测评结果:WA
  • 用时:132ms
  • 内存:151332kb
  • [2023-09-12 19:23:44]
  • 提交

answer

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int N; cin >> N;
	
	using D = double;
	vector<D> xs(N), ys(N);
	for (int i = 0; i < N; i++) {
		cin >> xs[i] >> ys[i];
	}

	auto check = [&](string expr, vector<D> cur) -> void {
		for (int i = 0; i < N; i++) {
			if (abs(cur[i] - ys[i]) / max<D>(1, abs(ys[i])) > 1e-3) return;
		}
		cout << expr << '\n';
		exit(0);
	};

	const int L = 10;
	vector<vector<pair<string, vector<D>>>> vals(L);
	vals[0].push_back({"x", xs});
	vector<D> t(N);
	for (int c = 1; c < L; c++) {
		// sin/cos
		for (const auto& [expr, s] : vals[c-1]) {
			{
				for (int i = 0; i < N; i++) {
					t[i] = sin(s[i]);
				}
				auto new_expr = "sin(" + expr + ")";
				check(new_expr, t);
				vals[c].push_back({new_expr, t});
			}
			{
				for (int i = 0; i < N; i++) {
					t[i] = cos(s[i]);
				}
				auto new_expr = "cos(" + expr + ")";
				check(new_expr, t);
				vals[c].push_back({new_expr, t});
			}
		}
		for (int c0 = 0; c0+1 <= c-1-c0; c0++) {
			int c1 = c-1-c0;
			for (const auto& [expr0, s0] : vals[c0]) {
				for (const auto& [expr1, s1] : vals[c1]) {
					for (int i = 0; i < N; i++) {
						t[i] = s0[i] + s1[i];
					}
					auto new_expr = "(" + expr0 + ")+(" + expr1 + ")";
					check(new_expr, t);
					vals[c].push_back({new_expr, t});
				}
			}
			for (const auto& [expr0, s0] : vals[c0]) {
				for (const auto& [expr1, s1] : vals[c1]) {
					for (int i = 0; i < N; i++) {
						t[i] = s0[i] - s1[i];
					}
					auto new_expr = "(" + expr0 + ")-(" + expr1 + ")";
					check(new_expr, t);
					vals[c].push_back({new_expr, t});
				}
			}
			for (const auto& [expr0, s0] : vals[c0]) {
				for (const auto& [expr1, s1] : vals[c1]) {
					for (int i = 0; i < N; i++) {
						t[i] = s1[i] - s0[i];
					}
					auto new_expr = "(" + expr1 + ")-(" + expr0 + ")";
					check(new_expr, t);
					vals[c].push_back({new_expr, t});
				}
			}
			for (const auto& [expr0, s0] : vals[c0]) {
				for (const auto& [expr1, s1] : vals[c1]) {
					for (int i = 0; i < N; i++) {
						t[i] = s0[i] * s1[i];
					}
					auto new_expr = "(" + expr0 + ")*(" + expr1 + ")";
					check(new_expr, t);
					vals[c].push_back({new_expr, t});
				}
			}
			for (const auto& [expr0, s0] : vals[c0]) {
				for (const auto& [expr1, s1] : vals[c1]) {
					bool works = true;
					for (int i = 0; i < N; i++) {
						if (abs(s1[i]) < 1e-2) {
							works = false;
							break;
						}
						t[i] = s0[i] / s1[i];
					}
					if (!works) continue;
					auto new_expr = "(" + expr0 + ")/(" + expr1 + ")";
					check(new_expr, t);
					vals[c].push_back({new_expr, t});
				}
			}
			for (const auto& [expr0, s0] : vals[c0]) {
				for (const auto& [expr1, s1] : vals[c1]) {
					bool works = true;
					for (int i = 0; i < N; i++) {
						if (abs(s0[i]) < 1e-2) {
							works = false;
							break;
						}
						t[i] = s1[i] / s0[i];
					}
					if (!works) continue;
					auto new_expr = "(" + expr1 + ")/(" + expr0 + ")";
					check(new_expr, t);
					vals[c].push_back({new_expr, t});
				}
			}
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5268kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

(x)*((sin(x))+((x)-(sin(x))))

result:

ok great!!

Test #2:

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

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: 4764kb

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)+((sin(x))/(x))))

result:

ok great!!

Test #4:

score: 0
Accepted
time: 2ms
memory: 5320kb

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: -100
Wrong Answer
time: 132ms
memory: 151332kb

input:

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

output:

((x)+((cos(x))*((x)-((x)*(cos(x))))))/(x)

result:

wrong answer complexity too big, 12