THUSC 2024 部分题解

THUSC 2024 部分题解

五月 23, 2024

THUSC 2024 简要题解

T1 弃光魔使的能量塔

题意

题目大意，给定 $T,d$，$T$ 组数据，每组数据给出 $n_1,n_2,\dots,n_d,p,l$，求 $\sum_{i_1=0}^{n_1-1}\sum_{i_2=0}^{n_2-1} \dots \sum_{i_d=0}^{n_d-1} \max(0,i_1 \operatorname{xor} i_2 \operatorname{xor} \dots \operatorname{xor} i_d -l) \bmod p$。

其中 $T \le 10,d \le 10$，其余数据在 long long 范围内，$p,l$ 在 int 范围内。

题解

处理出三个数组即可，$f_{i,S}$ 表示到第 $i$ 位，前面不管填了什么，这一位填完之后这 $d$ 个数的数位情况为 $S$，其中如果 $S_j=0$ 代表 $i_j$ 这个数第 $i-1$ 及以下都没有填 0/1 的限制了；否则就相当于 $i_j$ 在 $i$ 位及以上都完全与 $n_j-1$ 相同，就有限制。（这一部分可以根据数位 dp 来理解）

那么我们转移的时候枚举当前第 $i$ 位每个数字选了什么，设为集合 $T$，那么我们就可以通过位运算计算出在第 $i+1$ 位数位情况为 $S$，第 $i$ 位填了 $T$ 之后数位情况是什么，设其为 $U$，那么 $f_{i,U} \gets f_{i+1,S}$。当然，这种操作有一个前提就是 $U$ 的 $1$ 的个数模 $2$ 要等于 $l$ 在第 $i$ 位的位值；如果小于，显然答案为 $0$；如果大于，那么我们就需要统计 $i-1$ 位往下合法的填法的贡献之和，设其为 $res$，那么 $ans \gets f_{i+1,S} \times res$。

观察位数的情况，发现 $res$ 由两部分组成，第一部分就是第 $i$ 位的 $(2^i-l_0) \times g_{i,U}$，其中 $g_{i,U}$ 的意思是从第 $0$ 位开始填数，填到第 $i-1$ 位并且第 $i-1$ 位的数位限制是 $U$ 的方案数（并不是代价和），$l_0$ 表示 $l$ 只保留最后 $i$ 位的值是多少，$g$ 的计算类似于 $f$，也是枚举当前位的填数情况就可以了。

第二部分就是 $\operatorname{xor}$ 值的最后 $i$ 位的位值的和，设其为 $h_{i,U}$，其中 $g_{i,U}$ 的意思是从第 $0$ 位开始填数，填到第 $i-1$ 位并且第 $i-1$ 位的数位限制是 $U$ 的时候 $\operatorname{xor}$ 的值的和，$h$ 的转移需要借助 $g$，总之转移的时候加上 $2^k \times g_{p,T_0}$ 就可以了。（$p,T_0$ 只是一个通配符，没有其他含义）

那么时间复杂度就是 $O(T 2^{2d} \log n)$，如果不 $O(1)$ 得到 $U$ 的话，时间复杂度就会多一个 $O(d)$，就可能被卡常。

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
101
102
103
104
105
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,d,a[11],l,limit,mod,now,i,j,k,ans,b[65],f[65][1<<10],cnt[65][65],g[65][1<<10],h[65][1<<10],func[1<<10][1<<10],cntt[1<<10];
inline ll getf(ll pos,ll limit,ll now){
	if(((now&limit)&b[pos])!=(now&limit)) return -1;
	return func[now][b[pos]]&limit;
}
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t = a;
	while(b){
		if(b&1) res=res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	for(i=0;i<(1<<10);i++){
		cntt[i] = __builtin_popcount(i); 
		for(j=0;j<(1<<10);j++){
			for(k=0;k<10;k++){
				if(((i>>k)&1)==((j>>k)&1)) func[i][j]|=(1<<k);
			}
		}
	}
	cin>>T>>d;
	while(T--){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		memset(h,0,sizeof(h));
		memset(b,0,sizeof(b));
		memset(cnt,0,sizeof(cnt));
		ans=0;
		for(i=1;i<=d;i++) cin>>a[i];
		cin>>limit>>mod;
		for(i=1;i<=d;i++) if(!a[i]) break;
		if(i<=d){
			cout<<0<<endl;
			continue;
		}
		for(i=1;i<=d;i++) a[i]--;
		for(i=1;i<=d;i++){
			for(j=0;j<=60;j++){
				cnt[i][j]=((a[i]>>j)&1);
				if(cnt[i][j]) b[j]|=(1ll<<i-1); 
			}
		}
		for(i=0;i<=60;i++){
			for(j=0;j<(1<<d);j++){
				for(k=0;k<(1<<d);k++){
					ll now = getf(i,j,k);
					if(now==-1) continue;
					ll num = (1ll*cntt[k]%2)<<i;
					num %= mod;
					if(i==0) g[i][j]++,h[i][j]+=num,h[i][j]%=mod;
					else{
						(g[i][j]+=g[i-1][now])>=mod&&(g[i][j]-=mod);
						h[i][j]=(h[i][j]+h[i-1][now]+g[i-1][now]*num)%mod;
					}
				}
			}
		}
		f[60+1][(1<<d)-1]=1;
		for(i=60;i>=0;i--){
			for(j=0;j<(1<<d);j++){
				if(!f[i+1][j]) continue;
				for(k=0;k<(1<<d);k++){
					ll now = getf(i,j,k);
					if(now==-1) continue;
					ll val = cntt[k]%2,vall = ((limit>>i)&1);
					if(val>vall){
						ll num = (i==0?1:g[i-1][now]);
						ll cnt = (num*((1ll<<i)%mod)%mod+num*(mod-(limit&((1ll<<i)-1))%mod+mod)%mod+(i==0?0:h[i-1][now]))%mod;
						ans = (ans+f[i+1][j]*cnt)%mod;
					}
					else if(val==vall) (f[i][now]+=f[i+1][j])>=mod&&(f[i][now]-=mod);
				}
			}
		}
		cout<<(ans%mod+mod)%mod<<endl;
	}
	return 0;
} 
/*
Input:
7 2
5 8 1 100
8 8 0 100007
25 31 0 100007
5 45 3 1000007
31 39 7 2345
545 435 342 1000007
28827050410 35165045587 7109602 13719506

Output:
5
224
11925
4323
1586
808451
5456283
*/

T2 子序列

题意

给定一个小写字母字符串 $S$ 和一个整数 $k$，你需要构造一个最短的字符串 $S_1$ 满足下列条件：

  • $S$ 是 $S_1$ 的一个前缀（两者可以完全相同）。
  • 所有长度为 $k$ 的小写字母构成的字符串都是 $S_1$ 的一个子序列。

如果有多个可能的 $S_1$ 输出一个即可。

数据范围：$1 \le k \le 10^5,1 \le |S| \le 10^6$，时间限制 0.5s。

题解

考虑对于一个字符串 $S$ 找到最大的 $k$ 满足上面第二个条件。

那么问题就等价于划分成最大的段数使得每一段都包含 $\text{a} \sim \text{z}$ 所有字母。（这个结论我不会证，我太菜了）

然后就可以 $O(n)$ 处理了。

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
#include<cstdio>
#include<cstring>
#define ll int
#define N 1000005
using namespace std;
char s[N];
ll k,i,n,j,cnt,vis[26],temp;
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
int main(){
	scanf("%s%d",s+1,&k),n=strlen(s+1);
	for(i=1;i<=n;i++){
		vis[s[i]-'a']=1;
		pc(s[i]);
		for(j=0;j<26;j++) if(!vis[j]) break;
		if(j==26){
			cnt++;
			for(j=0;j<26;j++) vis[j]=0;
		}
	}
	if(cnt>=k) return fwrite(obuf,p3-obuf,1,stdout),0;
	k -= cnt;
	for(i=0;i<26;i++) if(!vis[i]) pc((char)('a'+i));
	k--;
	if(k==0) return fwrite(obuf,p3-obuf,1,stdout),0;
	for(i=1;i<=k;i++) for(j=0;j<26;j++) pc((char)(j+'a'));
	return fwrite(obuf,p3-obuf,1,stdout),0;
}

T3 transport

题意

给定了 $n$ 个节点和 $n-1$ 条边，这 $n-1$ 条边有方向有边权，如果不考虑方向的话保证其构成一棵树。

设 $\operatorname{dis(i,j)}$ 表示如果 $i$ 能到 $j$ 的话，$i \to j$ 这条路径上的边权和；否则为 $0$。（容易发现如果存在 $i \to j$ 的路径，一定只有一条）

你需要给没有定向的边定向，满足 $\max_{1 \le i,j \le n} \operatorname{dis}(i,j)$ 最小，输出这个最小值。

数据范围：$1 \le n \le 2 \times 10^5$。

题解

二分答案 $k$，然后设 $f_i,g_i$ 分别表示 $i$ 这棵子树中最长路径长度不超过 $k$ 的时候从儿子到 $i$ 的路径最短是 $f_i$，从 $i$ 到儿子的路径最短是 $g_i$。（$f_i$ 和 $g_i$ 是独立的，也就是有可能是两种不同的定向方式得到的 $f_i$ 和 $g_i$）

转移的时候如果这条边是从儿子到父亲，用儿子的 $f$ 更新一下父亲的 $f$ 就好；如果是从父亲到儿子，用儿子的 $g$ 更新一下父亲的 $g$ 即可；最后就是没有定向的边，直接使用 sort 或其他数据结构贪心的选择一下不超过 $k$ 并且 $f/g$ 最小的方案即可。

时间复杂度显然 $O(n \log n \log V)$。

下面借用一下一个同学的代码：

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node{
	int to,o;
	ll val;
	node(int to_,ll val_,int o_){
		to=to_,val=val_,o=o_;
	}
};
vector<node>vec[200005];
ll f[200005][2];
struct pii{
	ll u,d;
}arr[200005];
int n,tot;
bool fl;
bool cmp(pii x,pii y){
	return x.u<y.u;
}
ll sum[200005];
void dfs(int now,int fa,int type,ll val){
	for(auto to:vec[now]){
		if(to.to==fa)continue;
		dfs(to.to,now,to.o,val);
	}
	tot=0;
	for(auto to:vec[now]){
		if(to.to==fa)continue;
		arr[++tot].u=f[to.to][0]+to.val;
		arr[tot].d=f[to.to][1]+to.val;
	}
	sort(arr+1,arr+1+tot,cmp);
	f[now][0]=f[now][1]=1e18;	
	sum[tot+1]=0;
	for(int i=tot;i;i--){
		sum[i]=max(sum[i+1],arr[i].d);
	}
	bool fl1=0;
	for(int i=0;i<=tot;i++){
		if(arr[i].u+sum[i+1]<=val){
			fl1=1;
			f[now][0]=min(f[now][0],arr[i].u);
			f[now][1]=min(f[now][1],sum[i+1]); 
		}
	}
	if(!fl1)fl=0;
	if(type==1)f[now][0]=1e18;
	if(type==2)f[now][1]=1e18;
}
bool ck(ll mid){
	fl=1;
	dfs(1,0,0,mid);
	return fl;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y,o;ll z;
		scanf("%d%d%lld%d",&x,&y,&z,&o);
		if(o==0)vec[x].push_back(node(y,z,0)),vec[y].push_back(node(x,z,0));
		if(o==1)vec[x].push_back(node(y,z,1)),vec[y].push_back(node(x,z,2));
	}
	ll l=0,r=1e15,ans=0;
	while(l<=r){
		ll mid=l+r>>1;
		if(ck(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}

T4 编译优化

题意

请看 THUSC2024游记 - Acoipp 的个人博客 的附件。

题解

对于前三个 Sub，要求求出最优加法链，那么用 IDA 或者一些其他搜索算法搜出来 $1 \sim 128$ 的解就可以了。

第四个 Sub 就是 $2^{30} \bmod 998244353$，所以自己累加自己 $2^{30}$ 就可以了。

第五个 Sub 是线段树区间求和，正常情况下可以通过。

第六个 Sub 是猫树 $O(1)$ 查询区间和，正常情况下可以通过。

第七个 Sub 是前缀和转化为 $a_r+a_l \times 998244352=a_r+a_l \times (2^{23}+2^{24}+2^{25}+2^{27}+2^{28}+2^{29})$，然后后面的式子先算出 $2^{23}$，再算出 $2^{23}+2^{24}+2^{25}$，最后得到全部，在 $32$ 次之内完成就可以通过。

第八个 Sub 是迪利克雷前缀和，用高维前缀和就好了。

第九个 Sub 直接高维前缀和。

第十个 Sub 需要把 $a_x=a_y+a_z$ 对答案没有帮助的删除，并且当 $a_y$ 或者 $a_z$ 恒为 $0$ 的时候改为赋值就可以做到时间 969。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
#include<bits/stdc++.h>
#define ll int
using namespace std;
ll id;
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void ps(string s){
	for(ll i=0;i<s.size();i++) pc(s[i]);
}
inline void wr(int x){ 
	if(x>9) wr(x/10); 
	pc(x%10+'0'); 
}
inline void input(ll x){
	ps("input(a[");
	wr(x);
	ps("]);\n");
}
inline void output(ll x){
	ps("output(a[");
	wr(x);
	ps("]);\n");
}
inline void equiv(ll x,ll y){
	ps("a[");
	wr(x);
	ps("]=a[");
	wr(y);
	ps("];\n");
}
inline void pllus(ll x,ll y,ll z){
	ps("a[");
	wr(x);
	ps("]=a[");
	wr(y);
	ps("]+a[");
	wr(z);
	ps("];\n");
}
namespace ans1{
	ll a[505],i,j,k,sum,up;
	int n,ans[100];
	bool finish;
	void dfs(int x,int deep){
	    if(finish) return ;
	    if(x==deep) { if(ans[x]==n)finish=1; return; }
	    for(int i=0;i<=x;i++){
	        for(int j=i;j<=x;j++) if(ans[i]+ans[j]>ans[x]&&ans[i]+ans[j]<=n){//剪枝 
	                int sum=ans[i]+ans[j];
	                for(int k=x+2;k<=deep;k++) sum<<=1;//sum *= 2;当前为x; sum存于x+1; 
	                if(sum<n) continue;//如果接下来一直是最大策略还是不能达到n，剪枝 
	                ans[x+1]=ans[i]+ans[j];
	                dfs(x+1,deep);
	                if(finish) return ;
	        }
	    }
	}
	int main(){
		input(1);
		output(0);
		for(ll i=1;i<=up;i++){
			n=i;
	        memset(ans,0,sizeof(ans));
	        ans[finish=0]=1;
	        int tmp=n,deep=0; while(tmp>>=1) deep++;//求出最大深度； 
	        while(!finish) dfs(0,deep++);
	        sum=deep;
			for(ll j=1;j<=sum;j++) a[j]=ans[j-1];
			input(1);
			for(ll j=2;j<=sum;j++){
				ll temp = 0;
				for(ll k=1;k<j;k++){
					for(ll l=1;l<j;l++){
						if(a[j]==a[k]+a[l]){
							temp=1;
							pllus(a[j],a[k],a[l]);
							break;
						}
					}
					if(temp) break;
				}
			}
			output(a[sum]);
		}
		return 0;
	}
}
namespace ans4{
	inline void solve(){	
		input(0);
		for(int i=1;i<=30;i++) pllus(0,0,0);
		output(0);
	} 
}
namespace ans5{
	inline void build(int s,int t,int p){
		if(s==t){
			input(p);
			return ;
		}
		build(s,(s+t)/2,2*p),build((s+t)/2+1,t,2*p+1);
		pllus(p,2*p,2*p+1);
	}
	inline void query(int l,int r,int s,int t,int p){
		if(l<=s&&t<=r) pllus(1000,1000,p);
		else{
			if(l<=(s+t)/2) query(l,r,s,(s+t)/2,2*p);
			if(r>(s+t)/2) query(l,r,(s+t)/2+1,t,2*p+1);
		}
	}
	inline int getval(string s){
		int i;
		for(i=0;i<s.size();i++){
			if(s[i]=='=') break;
		}
		for(int j=i+1;j<s.size();j++){
			if(s[j]>='0'&&s[j]<='9'){
				int pos = 0;
				for(int k=j;k<s.size();k++){
					if(s[k]<'0'||s[k]>'9') break;
					pos = pos*10+s[k]-'0';
				}
				return pos;
			}
		}
	}
	inline void solve(){
		build(1,128,1);
		int id,l1,l2;
		string s,s2;
		for(int i=1;i<=10;i++) cin>>id>>id;
		for(int i=1;i<=128;i++) cin>>s;
		while(cin>>s){
			cin>>s2;
			equiv(1000,0);
			l1=getval(s),l2=getval(s2);
			query(l1,l2,1,128,1);
			output(1000);
			for(int i=l1;i<=l2+2;i++) cin>>s;
		}
	}
}
namespace ans6{
	int leaf[5005],LOG[5005],ss[5005],tt[5005],tot=3000;
	vector<int> op[5005];
	inline int lca(int x,int y){
		if(x==y) return x;
		return x>>LOG[x^y];
	}
	inline void build(int s,int t,int p){
		op[p].clear();
		ss[p] = s,tt[p] = t;
		if(s==t){
			leaf[s] = p;
			input(p);
			return ;
		}
		build(s,(s+t)/2,2*p),build((s+t)/2+1,t,2*p+1);
		for(int i=s;i<=t;i++) op[p].push_back(++tot);
		int mid = (s+t)/2;		
		equiv(op[p][mid-s],leaf[mid]);
		for(int i=mid-1;i>=s;i--) pllus(op[p][i-s],op[p][i-s+1],leaf[i]);
		equiv(op[p][mid+1-s],leaf[mid+1]);
		for(int i=mid+2;i<=t;i++) pllus(op[p][i-s],op[p][i-s-1],leaf[i]);
	}
	inline int getval(string s){
		int i;
		for(i=0;i<s.size();i++){
			if(s[i]=='=') break;
		}
		for(int j=i+1;j<s.size();j++){
			if(s[j]>='0'&&s[j]<='9'){
				int pos = 0;
				for(int k=j;k<s.size();k++){
					if(s[k]<'0'||s[k]>'9') break;
					pos = pos*10+s[k]-'0';
				}
				return pos;
			}
		}
	}
	inline void solve(){
		for(int i=1;i<=2048;i++) LOG[i]=log2(i)+1;
		build(1,1024,1);
		int id,l1,l2;
		string s,s2;
		for(int i=1;i<=10;i++) cin>>id>>id;
		for(int i=1;i<=3071;i++) cin>>s;
		while(cin>>s){
			cin>>s2;
			equiv(0,100002);
			l1=getval(s),l2=getval(s2);
			if(l1==l2) output(leaf[l1]);
			else{
				int pos = lca(leaf[l1],leaf[l2]);
				int p1 = op[pos][l1-ss[pos]],p2 = op[pos][l2-ss[pos]];
				pllus(0,p1,p2);
				output(0);
			}
			while(1){
				cin>>s;
				if(s[0]=='o') break;
			}
		}
	}
}
namespace ans7{
	inline int getval(string s){
		int i;
		for(i=0;i<s.size();i++){
			if(s[i]=='=') break;
		}
		for(int j=i+1;j<s.size();j++){
			if(s[j]>='0'&&s[j]<='9'){
				int pos = 0;
				for(int k=j;k<s.size();k++){
					if(s[k]<'0'||s[k]>'9') break;
					pos = pos*10+s[k]-'0';
				}
				return pos;
			}
		}
	}
	inline void solve(){
		for(int i=1;i<=4096;i++) input(i);
		for(int i=2;i<=4096;i++) pllus(i,i,i-1);
		int id,l1,l2;
		string s,s2;
		for(int i=1;i<=10;i++) cin>>id>>id;
		for(int i=1;i<=12287;i++) cin>>s;
		while(cin>>s){
			cin>>s2;
			l1=getval(s),l2=getval(s2);
			equiv(4098,4099);
			l1--;
			if(l1==0) output(l2);
			else{
				equiv(4097,l1);
				for(int i=1;i<=23;i++) pllus(4097,4097,4097);
				equiv(4098,4097);  
				pllus(4097,4097,4097);
				pllus(4098,4098,4097);
				pllus(4097,4097,4097);
				pllus(4098,4098,4097);
				equiv(4097,4098);  
				pllus(4098,4098,4098);
				pllus(4098,4098,4098);
				pllus(4098,4098,4098);
				pllus(4098,4098,4098);
				pllus(4097,4097,4098);
				pllus(4097,4097,l2);
				output(4097);
			}
			while(1){
				cin>>s;
				if(s[0]=='o') break;
			}
		}
	}
}
namespace ans8{
	int vis[10005];
	inline void solve(){
		for(int i=1;i<=8190;i++) printf("input(a[%d]);\n",i);
		for(int i=2;i<=8190;i++){
			if(!vis[i]){
				for(int j=1;i*j<=8190;j++){
					vis[i*j]=1;
					printf("a[%d]=a[%d]+a[%d];\n",i*j,i*j,j);
				}
			}
		}
		for(int i=1;i<=8190;i++) printf("output(a[%d]);\n",i);
		printf("input(a[5]);\n");
		printf("a[7]=a[1]+a[5];\n");
		printf("output(a[7]);\n");
		printf("input(a[6]);\n");
		printf("a[6]=a[6]+a[4096];\n");
		printf("output(a[6]);\n");
	}
}
namespace ans9{
	inline void solve(){
		for(int i=0;i<1024;i++) printf("input(a[%d]);\n",i);
		for(int i=1;i<1024;i*=2){
			for(int j=0;j<1024;j+=2*i){
				for(int k=j;k<j+i;k++) printf("a[%d]=a[%d]+a[%d];\n",k+i,k+i,k);
			}
		}
		for(int i=0;i<1024;i++) printf("output(a[%d]);\n",i);
	} 
}
namespace ans10{
	vector<int> op[1005];
	int viss[1005];
	inline void dfs(int x){
		viss[x] = 1;
		for(int i=0;i<op[x].size();i++){
			if(viss[op[x][i]]) continue;
			dfs(op[x][i]);
		}
	}
	inline void solve(){		
		int id,p1,p2,p3,idt,sum=0;
		int vis[5005],id3[5005],now[5005],ttt,t1[5005],t2[5005],t3[5005],lf[5005];
		int id2=0;
		string s;
		for(int i=1;i<=10;i++) cin>>id>>id;
		while(1){
			cin>>s;
			if(s[0]=='i'){
				cout<<s<<endl;
				p1=0;
				for(int i=0,j;i<s.size();i++){
					if(s[i]>='0'&&s[i]<='9'){
						for(j=i;j<s.size();j++){
							if(s[j]<'0'||s[j]>'9') break;
							p1=p1*10+s[j]-'0';
						}
						vis[p1]=1;
						break;
					}
				}
			}
			else break;
		}
		while(1){
			if(s[0]=='a'){
				p1=0,p2=0,p3=0;
				for(int i=0,j;i<s.size();i++){
					if(s[i]>='0'&&s[i]<='9'){
						for(j=i;j<s.size();j++){
							if(s[j]<'0'||s[j]>'9') break;
							p1=p1*10+s[j]-'0';
						}
						i = j;
						while(i<s.size()){
							if(s[i]>='0'&&s[i]<='9') break;
							i++;
						}
						for(j=i;j<s.size();j++){
							if(s[j]<'0'||s[j]>'9') break;
							p2=p2*10+s[j]-'0';
						}
						i = j;
						while(i<s.size()){
							if(s[i]>='0'&&s[i]<='9') break;
							i++;
						}
						for(j=i;j<s.size();j++){
							if(s[j]<'0'||s[j]>'9') break;
							p3=p3*10+s[j]-'0';
						}
						break;
					}
				}
				ttt++,t1[ttt]=p1,t2[ttt]=p2,t3[ttt]=p3;
			}
			else break;
			cin>>s;
		}
		int t4=0;
		while(1){
			p1=0;
			for(int i=0,j;i<s.size();i++){
				if(s[i]>='0'&&s[i]<='9'){
					for(j=i;j<s.size();j++){
						if(s[j]<'0'||s[j]>'9') break;
						p1=p1*10+s[j]-'0';
					}
					break;
				}
			}
			id3[++t4]=p1;
			if(s=="output(a[395]);") break;
			cin>>s;
		}
		memset(lf,0,sizeof(lf));
		for(int i=1;i<=ttt;i++){
			vis[t1[i]]=1;
			if(vis[t2[i]]&&vis[t3[i]]);
			else if(vis[t2[i]]) t3[i]=-1;
			else if(vis[t3[i]]) swap(t2[i],t3[i]),t3[i]=-1;
			else t3[i]=-1,vis[t1[i]]=0;
		}
		for(int i=1;i<=t4;i++) now[id3[i]]=1;
		for(int i=ttt;i>=1;i--){
			if(now[t1[i]]) lf[i]=1,now[t1[i]]=0;
			for(int j=i+1;j<=ttt;j++){
				if(lf[j]&&(t1[i]==t2[j]||t1[i]==t3[j])) lf[i]=1;
				if(t1[j]==t1[i]) break;
			}
		}
		for(int i=1;i<=ttt;i++){
			if(!lf[i]) continue;
			if(t3[i]!=-1) printf("a[%d]=a[%d]+a[%d];\n",t1[i],t2[i],t3[i]);
			else printf("a[%d]=a[%d];\n",t1[i],t2[i]);
		}
		for(int i=1;i<=t4;i++) printf("output(a[%d]);\n",id3[i]);
	} 
}
int main(){
	ios::sync_with_stdio(false);
	cin>>id;
	if(id==1) ans1::up=32,ans1::main();
	if(id==2) ans1::up=64,ans1::main();
	if(id==3) ans1::up=128,ans1::main();
	if(id==4) ans4::solve();
	if(id==5) ans5::solve();
	if(id==6) ans6::solve();
	if(id==7) ans7::solve();
	if(id==8) ans8::solve();
	if(id==9) ans9::solve();
	if(id==10) ans10::solve();
	return fwrite(obuf,p3-obuf,1,stdout),0;
}