QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#837691#3074. Express As The SumwtcTL 1ms3972kbC++141.1kb2024-12-30 11:50:292024-12-30 11:50:31

Judging History

This is the latest submission verdict.

  • [2024-12-30 11:50:31]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3972kb
  • [2024-12-30 11:50:29]
  • Submitted

answer

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
const int N=45007;
int n,bz[N],tot,p[N],b[N],c[N],o,pd;
void init(int n)
{
	fo(i,2,n)
	{
		if(!bz[i])
		{
			p[++tot]=i;
			for(int j=i+i;j<=n;j+=i) bz[j]=1;
		}
	}
}
void pt(int n,int l,int r)
{
	printf("%d",n);
	fo(i,l,r) printf(" %c %d",i==l?'=':'+',i);
	printf("\n");
}
void dfs(int x,int y)
{
	if(pd) return;
	if(x==o+1)
	{
		int z=n/y;
		if(y==1||!((y&1)^(z&1))) return;
		if(z<y) return;
		pt(n>>1,(z-y+1)>>1,(z+y-1)>>1);
		pd=1;return;
	}
	fu(i,0,c[x]) dfs(x+1,y),y*=b[x];
	dfs(x+1,y);
}
void work()
{
	scanf("%d",&n);n*=2;
	int m=n;o=0;pd=0;
	for(int i=1;i<=tot&&p[i]*p[i]<=m;++i)
	{
		if(m%p[i]==0)
		{
			m/=p[i];b[++o]=p[i];c[o]=1;
			while(m%p[i]==0) m/=p[i],c[o]++;
		}
	}
	if(m>1) b[++o]=m,c[o]=1;
	dfs(1,1);
	if(!pd) printf("IMPOSSIBLE\n");
}
int main()
{
	init(45000);
	int T;scanf("%d",&T);
	while(T--) work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3972kb

input:

3
8
10
24

output:

IMPOSSIBLE
10 = 1 + 2 + 3 + 4
24 = 7 + 8 + 9

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

10866
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
10...

output:

IMPOSSIBLE
IMPOSSIBLE
3 = 1 + 2
IMPOSSIBLE
5 = 2 + 3
6 = 1 + 2 + 3
7 = 3 + 4
IMPOSSIBLE
9 = 2 + 3 + 4
10 = 1 + 2 + 3 + 4
11 = 5 + 6
12 = 3 + 4 + 5
13 = 6 + 7
14 = 2 + 3 + 4 + 5
15 = 1 + 2 + 3 + 4 + 5
IMPOSSIBLE
17 = 8 + 9
18 = 5 + 6 + 7
19 = 9 + 10
20 = 2 + 3 + 4 + 5 + 6
21 = 6 + 7 + 8
22 = 4 + 5 + ...

result: