QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178100#5377. $N$ 门问题zhoukangyang#40 13ms12468kbC++111.9kb2023-09-13 17:58:342024-07-04 01:56:29

Judging History

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

  • [2024-07-04 01:56:29]
  • 评测
  • 测评结果:40
  • 用时:13ms
  • 内存:12468kb
  • [2023-09-13 17:58:34]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long 
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1 << 21, L = 5e5, mod = 998244353;

double f[N];

ll n;

int k;
ll a[N], b[N];
ll rd() {
	cin >> k;
	L(i, 1, k) {
		cin >> a[i] >> b[i];
	}
	n = 0;
	while(true) {
		int win = 1;
		L(i, 1, k) {
			if(n % b[i] != a[i]) {
				win = 0;
				break;
			}
		}
		if(win) break;
		++n;
		if(n > 200) {
			n = 0;
			break;
		}
	}
	return n;
}

map < vector < double >, double > MP[10];
double slv(vector < double > a, int cur) { 
	if(sz(a) == 2) {
		return cur == 0;
	}
	if(cur > 1) 
		swap(a[1], a[cur]), cur = 1;
	sort(a.begin() + 2, a.end());
	if(MP[cur].count(a)) return MP[cur][a];
	double win = 1;
	L(p, 1, sz(a) - 1) if(p != cur) {
		double sum1 = 0, sum2 = 0;
		L(i, 0, sz(a) - 1) if(i != cur) {
			sum1 += a[i];
			if(i != p) sum2 += a[i];
		}
		sum1 /= sum2;
		vector < double > b;
		L(i, 0, sz(a) - 1) {
			if(i == cur) b.emplace_back(a[i]);
			else if(i != p) b.emplace_back(a[i] * sum1);
		}
		
		double mx = 0;
		L(i, 0, sz(b) - 1) {
			mx = max(mx, b[i]);
		}
		
		int total = 0;
		double sum = 0;
		L(i, 0, sz(b) - 1) {
			if(fabs(b[i] - mx) <= 1e-9) {
				total += 1;
				sum += slv(b, i);
			}
		}
		
		sum /= total;
		
		win = min(win, sum);
	}
	return MP[cur][a] = win;
}

int main () { 
	ios :: sync_with_stdio(false);
	cin.tie (0); cout.tie (0);
	n = rd();
	if(n < 2) {
		cout << "error\n";
		return 0;
	}
	vector < double > f(n);
	L(i, 0, n - 1) {
		f[i] = 1;
	}
	double ans = n < 13 ? (slv(f, 0) + slv(f, 1) * (n - 1)) / n : 0;
	cout.precision(6); cout << fixed;
	cout << ans << '\n';
	return 0;
}

/*
(n-1)/(n-2) 1 [(n-1)/(n-2)] (n-1)/(n-2) (n-1)/(n-2) x 
*/

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 7924kb

input:

1
2 3

output:

0.500000

result:

ok single line: '0.500000'

Test #2:

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

input:

1
3 5

output:

0.666667

result:

ok single line: '0.666667'

Test #3:

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

input:

1
4 5

output:

0.625000

result:

ok single line: '0.625000'

Test #4:

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

input:

1
0 4

output:

error

result:

ok single line: 'error'

Test #5:

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

input:

1
1 3

output:

error

result:

ok single line: 'error'

Subtask #2:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 1ms
memory: 7924kb

input:

8
1 160005726539569
1 233
0 1
1 2947295521
1 686719856393
1 54289
1 12649337
1 37281334283719577

output:

error

result:

ok single line: 'error'

Test #7:

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

input:

10
2 64
0 2
2 512
2 4
2 32
2 16
2 256
0 1
2 8
2 128

output:

0.500000

result:

ok single line: '0.500000'

Test #8:

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

input:

10
3 256
3 16
0 1
3 8
3 512
3 32
3 4
3 128
3 64
1 2

output:

0.666667

result:

ok single line: '0.666667'

Test #9:

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

input:

10
0 2
4 8
0 4
4 256
0 1
4 512
4 32
4 128
4 64
4 16

output:

0.625000

result:

ok single line: '0.625000'

Test #10:

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

input:

10
5 128
5 32
5 16
1 4
0 1
5 64
5 256
5 512
1 2
5 8

output:

0.466667

result:

ok single line: '0.466667'

Test #11:

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

input:

10
6 32
6 16
6 256
6 64
0 1
6 128
0 2
6 512
6 8
2 4

output:

0.416667

result:

ok single line: '0.416667'

Test #12:

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

input:

2
1000000007 1000000008
2 4

output:

error

result:

ok single line: 'error'

Test #13:

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

input:

3
0 1001
0 241221531
0 2

output:

error

result:

ok single line: 'error'

Test #14:

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

input:

3
6 1001
6 241221531
0 2

output:

0.416667

result:

ok single line: '0.416667'

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #15:

score: 10
Accepted
time: 1ms
memory: 7592kb

input:

8
1 160005726539569
1 233
0 1
1 2947295521
1 686719856393
1 54289
1 12649337
1 37281334283719577

output:

error

result:

ok single line: 'error'

Test #16:

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

input:

10
2 64
0 2
2 512
2 4
2 32
2 16
2 256
0 1
2 8
2 128

output:

0.500000

result:

ok single line: '0.500000'

Test #17:

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

input:

10
3 256
3 16
0 1
3 8
3 512
3 32
3 4
3 128
3 64
1 2

output:

0.666667

result:

ok single line: '0.666667'

Test #18:

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

input:

10
0 2
4 8
0 4
4 256
0 1
4 512
4 32
4 128
4 64
4 16

output:

0.625000

result:

ok single line: '0.625000'

Test #19:

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

input:

10
5 128
5 32
5 16
1 4
0 1
5 64
5 256
5 512
1 2
5 8

output:

0.466667

result:

ok single line: '0.466667'

Test #20:

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

input:

10
6 32
6 16
6 256
6 64
0 1
6 128
0 2
6 512
6 8
2 4

output:

0.416667

result:

ok single line: '0.416667'

Test #21:

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

input:

10
7 16
7 8
3 4
0 1
7 32
7 256
7 64
1 2
7 512
7 128

output:

0.342857

result:

ok single line: '0.342857'

Test #22:

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

input:

10
8 16
8 64
8 32
0 1
0 8
0 2
8 128
0 4
8 256
8 512

output:

0.291667

result:

ok single line: '0.291667'

Test #23:

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

input:

10
1 2
113 128
0 8
1 16
49 64
17 32
241 256
1 4
241 512
0 1

output:

error

result:

ok single line: 'error'

Test #24:

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

input:

10
5 8
237 512
1 2
13 32
12 16
0 1
109 128
1 4
45 64
237 256

output:

error

result:

ok single line: 'error'

Test #25:

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

input:

10
11 16
43 64
235 512
11 32
3 4
0 1
235 256
0 2
107 128
3 8

output:

error

result:

ok single line: 'error'

Test #26:

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

input:

10
9 32
1 2
41 64
233 512
233 256
1 4
0 1
9 16
1 8
115 128

output:

error

result:

ok single line: 'error'

Subtask #4:

score: 10
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 10
Accepted
time: 1ms
memory: 7764kb

input:

8
1 5
1 15
1 2
1 30
1 3
0 1
1 6
1 10

output:

error

result:

ok single line: 'error'

Test #28:

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

input:

8
2 30
2 15
0 1
2 6
2 5
2 3
2 10
0 2

output:

0.500000

result:

ok single line: '0.500000'

Test #29:

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

input:

8
0 1
0 3
0 15
0 2
0 30
0 6
0 5
0 10

output:

error

result:

ok single line: 'error'

Test #30:

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

input:

8
1 2
5 30
0 1
0 5
2 3
5 6
5 15
5 10

output:

0.466667

result:

ok single line: '0.466667'

Test #31:

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

input:

8
3 5
0 3
3 15
3 10
0 1
1 2
3 30
3 6

output:

0.666667

result:

ok single line: '0.666667'

Test #32:

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

input:

6
0 3
3 4
1 2
3 6
0 1
3 12

output:

0.666667

result:

ok single line: '0.666667'

Test #33:

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

input:

6
0 1
2 6
0 4
2 3
0 2
8 12

output:

0.291667

result:

ok single line: '0.291667'

Test #34:

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

input:

6
0 1
1 2
2 3
1 4
5 6
5 12

output:

0.466667

result:

ok single line: '0.466667'

Test #35:

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

input:

6
3 12
1 2
0 3
0 1
3 4
3 6

output:

0.666667

result:

ok single line: '0.666667'

Test #36:

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

input:

1
5 6

output:

0.466667

result:

ok single line: '0.466667'

Test #37:

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

input:

1
6 7

output:

0.416667

result:

ok single line: '0.416667'

Test #38:

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

input:

1
7 8

output:

0.342857

result:

ok single line: '0.342857'

Test #39:

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

input:

4
0 2
0 4
2 3
3 5

output:

0.291667

result:

ok single line: '0.291667'

Test #40:

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

input:

4
0 3
0 9
1 2
4 5

output:

0.253968

result:

ok single line: '0.253968'

Test #41:

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

input:

3
0 2
0 5
1 3

output:

0.225000

result:

ok single line: '0.225000'

Test #42:

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

input:

6
0 1
0 2
0 6
0 12
0 4
0 3

output:

error

result:

ok single line: 'error'

Test #43:

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

input:

6
837250 1574381
22682 54289
20 29
81 233
6139 6757
0 1

output:

error

result:

ok single line: 'error'

Test #44:

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

input:

6
12521 54289
1478324 1574381
20 29
171 233
0 1
5298 6757

output:

error

result:

ok single line: 'error'

Test #45:

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

input:

8
9430402 12649337
193 233
12831718919798818 37281334283719577
358403095623 686719856393
31260796633308 160005726539569
0 1
38405 54289
1780337582 2947295521

output:

error

result:

ok single line: 'error'

Test #46:

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

input:

8
0 2
6 30
0 1
1 5
0 3
0 6
6 15
6 10

output:

0.416667

result:

ok single line: '0.416667'

Subtask #5:

score: 5
Accepted

Dependency #1:

100%
Accepted

Dependency #4:

100%
Accepted

Test #47:

score: 5
Accepted
time: 4ms
memory: 8104kb

input:

27216
1100249873 1253754216
25197605440 29192187024
1744207706249 2277822821274
12223300097 26875346784
147492353 275539264
320696949581 377638144884
419900489 699380136
453032 1231659
266587329 890393504
7730812097 11914078176
524332817 661404744
2287601 8261694
1156980833 14524544034
967031297 145...

output:

error

result:

ok single line: 'error'

Test #48:

score: 0
Accepted
time: 4ms
memory: 7948kb

input:

27216
1887302 8343192
98702 115368
3405075396542 142252321079232
3015286 10958948
59487416 481578669
1045054 3865664
72754046 23575685952
370699174 794635556
163774430 446662944
10742784326 36887818968
2588314 130307788
1814817881150 2290728087648
59263478 81513432
105993323864 106600637682
27086905...

output:

error

result:

ok single line: 'error'

Test #49:

score: 0
Accepted
time: 13ms
memory: 8128kb

input:

50000
13191867 17093160
20006787 28265160
531754947 696215520
49540995 227505696
1073316627 1706292720
58569507 194230400
51790622607 214521407100
141120675 500919552
1207143507 1366149400
1382307 4379200
850756707 11479406400
453052323 1743565824
850756707 2203118400
231422833827 322489324080
15091...

output:

error

result:

ok single line: 'error'

Test #50:

score: 0
Accepted
time: 10ms
memory: 8064kb

input:

50000
9122968989 10897286400
1244648539 11099963875
1895367069 2400239520
35685693 52442208
3724120989 59434502400
6070719789 13899085200
8432349 39225120
131925789 306153000
101446557 226417152
2483743030749 3009900358080
13965142941 24139551744
30294839709 75157175808
317618589 535307520
39789 188...

output:

error

result:

ok single line: 'error'

Test #51:

score: 0
Accepted
time: 8ms
memory: 8252kb

input:

50000
194 83566560
194 11970504
194 3351600
194 56073378816
194 157815216
194 2336202000
194 17749670400
194 2299884678
194 2366622720
194 4135131000
194 26409240
194 13248000
194 83847224260800
194 325909584
194 6051302400
194 1944746496
194 146024424000
194 1574773200
194 2472371200
194 2351661312...

output:

0.000000

result:

ok single line: '0.000000'

Test #52:

score: 0
Accepted
time: 7ms
memory: 8356kb

input:

50000
44 736736000
44 50798720
44 22011
44 10423897344
44 120011976
44 2904720
44 50400
44 608
44 2019025008000
44 885248
44 290811628800
44 5040734899200
44 147784000
44 17634412800
44 141099678720
44 15558400
44 20286
44 20860632
44 397555200
44 12926460
44 21042028800
44 1543082112
44 49024500
44...

output:

0.000000

result:

ok single line: '0.000000'

Test #53:

score: 0
Accepted
time: 8ms
memory: 12468kb

input:

50000
134 19132344
134 98394912000
134 118503000
134 515982918528000
134 1003701600
134 17564778000
134 54725461056000
134 607733280
134 1926144
134 375921000
134 506177100
134 728377920
134 3353275800
134 242181030
134 8398
134 11286912
134 1771619850
134 1302013440
134 20155582755
134 473211847680...

output:

0.000000

result:

ok single line: '0.000000'

Test #54:

score: 0
Accepted
time: 7ms
memory: 8444kb

input:

50000
4 36679578624
4 761177088
4 15810163200
4 3086022240
4 474249006
4 46986240
4 2096760960
4 2409402996
4 4717024
4 51919795200
4 870870
4 41146963200
4 3064591530
4 3516307200
4 64700052480
4 8061768000
4 21621600
4 38085120
4 30111048000
4 91423987200
4 10585935360
4 303688
4 6974813664000
4 3...

output:

0.625000

result:

ok single line: '0.625000'

Test #55:

score: 0
Accepted
time: 7ms
memory: 8412kb

input:

50000
5 584050500
5 21810872160
5 1201200
5 520608000
5 16052801909760
5 42730688000
5 8540588160
5 271591320
5 2688940800
5 13596128
5 89226295200
5 128012774400
5 2660486400
5 168814800
5 3304324108800
5 1927522396800
5 2565255987
5 26999000
5 437184
5 182656500
5 26096241600
5 617204448000
5 9335...

output:

0.466667

result:

ok single line: '0.466667'

Test #56:

score: 0
Accepted
time: 11ms
memory: 8024kb

input:

50000
81 153830476800
81 18712512
81 113622372864
81 2457061516800
81 48456600192000
81 78450240
81 174730080
81 552484800
81 760864104000
81 70259112
81 2134080
81 490416585750
81 22207185
81 2142201600
81 5852000
81 173974944000
81 6359661000
81 4258128
81 29044915200
81 259930944
81 19673280
81 1...

output:

error

result:

ok single line: 'error'

Subtask #6:

score: 0
Wrong Answer

Test #57:

score: 0
Wrong Answer
time: 2ms
memory: 7668kb

input:

15
15 17
2 3
5 31
4 5
12 29
38 41
3 11
44 47
16 23
11 19
6 13
3 37
1 2
21 43
5 7

output:

error

result:

wrong answer 1st lines differ - expected: '0.000000', found: 'error'

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

0%