problemscpp
A collection of my answers to algorithm problems in c++.
载入中...
搜索中...
未找到
acwing.cpp
浏览该文件的文档.
1#include "acwing.h"
2#include "templates.h"
3
4#include <algorithm>
5#include <bitset>
6#include <climits>
7#include <cmath>
8#include <cstring>
9#include <iomanip>
10#include <map>
11#include <queue>
12#include <set>
13#include <sstream>
14#include <stack>
15#include <unordered_map>
16#include <unordered_set>
17#include <utility>
18#include <vector>
19
20using namespace std;
21
22namespace acwing {
23 int acwing1::main(istream &cin, ostream &cout) {
24 int a;
25 int b;
26 cin >> a >> b;
27 cout << a + b;
28 return 0;
29 }
30
31 int acwing4200::main(istream &cin, ostream &cout) {
32 int p1;
33 int p2;
34 int p3;
35 int p4;
36 int a;
37 int b;
38 cin >> p1 >> p2 >> p3 >> p4 >> a >> b;
39 int min = p1;
40 min = p2 < min ? p2 : min;
41 min = p3 < min ? p3 : min;
42 min = p4 < min ? p4 : min;
43 const int ans = min - a < b - a + 1 ? min - a : b - a + 1;
44 cout << (ans < 0 ? 0 : ans);
45 return 0;
46 }
47
48 int acwing4201::main(istream &cin, ostream &cout) {
49 int number;
50 cin >> number;
51 int copy = number;
52 int len = 0;
53 while(copy != 0) {
54 copy /= 10;
55 len++;
56 }
57 auto arr = vector<int>(len);
58 copy = number;
59 for(int i = len - 1; i >= 0; i--) {
60 arr[i] = copy % 10;
61 copy /= 10;
62 }
63
64 int sum = static_cast<int>(pow(2, len));
65 for(int i = 0; i < len; i++) {
66 if(arr[i] > 1) {
67 break;
68 }
69 if(arr[i] == 0) {
70 sum -= static_cast<int>(pow(2, len - i - 1));
71 }
72 }
73 cout << --sum;
74 return 0;
75 }
76
77 int acwing608::main(istream &cin, ostream &cout) {
78 int a;
79 int b;
80 int c;
81 int d;
82 cin >> a >> b >> c >> d;
83 cout << "DIFERENCA = " << a * b - c * d;
84 return 0;
85 }
86
87 int acwing604::main(istream &cin, ostream &cout) {
88 const double pi = 3.14159;
89 double r;
90 cin >> r;
91 cout << "A=" << setiosflags(ios::fixed) << setprecision(4) << pi * r * r;
92 return 0;
93 }
94
95 int acwing606::main(istream &cin, ostream &cout) {
96 double a;
97 double b;
98 cin >> a >> b;
99 cout << "MEDIA = " << setiosflags(ios::fixed) << setprecision(5) << (a * 3.5 + b * 7.5) / 11;
100 return 0;
101 }
102
103 int acwing609::main(istream &cin, ostream &cout) {
104 int a;
105 double b;
106 double c;
107 cin >> a >> b >> c;
108 cout << "NUMBER = " << a << endl
109 << "SALARY = U$ " << setiosflags(ios::fixed) << setprecision(2) << b * c;
110 return 0;
111 }
112
113 int acwing615::main(istream &cin, ostream &cout) {
114 int x;
115 float y;
116 cin >> x >> y;
117 cout << setiosflags(ios::fixed) << setprecision(3) << static_cast<float>(x) / y << " km/l";
118 return 0;
119 }
120
121 int acwing616::main(istream &cin, ostream &cout) {
122 double x1;
123 double y1;
124 double x2;
125 double y2;
126 cin >> x1 >> y1 >> x2 >> y2;
127 cout << setiosflags(ios::fixed) << setprecision(4) << sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
128 return 0;
129 }
130
131 int acwing653::main(istream &cin, ostream &cout) {
132 int n;
133 cin >> n;
134 cout << n << endl;
135 int arr[] = {100, 50, 20, 10, 5, 2, 1};
136 for(const int i: arr) {
137 cout << n / i << " nota(s) de R$ " << i << ",00";
138 if(i != 1) {
139 cout << endl;
140 }
141 n %= i;
142 }
143 return 0;
144 }
145
146 int acwing4203::main(istream &cin, ostream &cout) {
147 string str;
148 cin >> str;
149 int count0 = 0;
150 int count1 = 0;
151 for(const char c: str) {
152 if(c == '1') {
153 count1++;
154 count0 = 0;
155 } else {
156 count0++;
157 count1 = 0;
158 }
159 if(count1 == 7 || count0 == 7) {
160 cout << "YES";
161 return 0;
162 }
163 }
164 cout << "NO";
165 return 0;
166 }
167
168 int acwing4204::main(istream &cin, ostream &cout) {
169 int n;
170 const int N = 1010;
171 auto *g = new int *[N];
172 for(int i = 0; i < N; i++) {
173 g[i] = new int[N];
174 for(int j = 0; j < N; j++) {
175 g[i][j] = 0;
176 }
177 }
178 cin >> n;
179 for(int i = 1; i <= n; i++) {
180 g[1][i] = i - 1;
181 g[i][1] = i - 1;
182 }
183 for(int i = 2; i < n; i++) {
184 for(int j = 2; j < n; j++) {
185 if(i == j) {
186 g[i][j] = 0;//对角线为0
187 } else {
188 if(g[i][j - 1] == 0) {
189 //在0后面一格
190 g[i][j] = g[i - 1][j] + 1;//上面一格的值+1
191 } else {
192 //否则
193 g[i][j] = g[i][j - 1] + 1;//前面一格的值+1
194 }
195 if(g[i][j] == n) {
196 //达到上限
197 g[i][j] = 1;//回归到1
198 }
199 }
200 }
201 }
202 for(int i = 1; i < n; i++) {
203 set<int> s;
204 for(int j = 1; j < n; j++) {
205 s.insert(g[i][j]);
206 }
207 for(int j = 0; j < n; j++) {
208 if(!s.contains(j)) {
209 g[i][n] = g[n][i] = j;//补最后一列和最后一行的值
210 }
211 }
212 }
213
214 //输出
215 for(int i = 1; i <= n; i++) {
216 for(int j = 1; j <= n; j++) {
217 cout << g[i][j];
218 if(j != n) {
219 cout << " ";
220 }
221 }
222 if(i != n) {
223 cout << endl;
224 }
225 }
226 for(int i = 0; i < N; i++) {
227 delete[] g[i];
228 }
229 delete[] g;
230 return 0;
231 }
232
233 int acwing2058::main(istream &cin, ostream &cout) {
234 string n2;
235 string n3;
236 cin >> n2 >> n3;
237 auto s = set<long long>();
238
239 for(int i = 0; i < n2.length(); i++) {
240 long long val = 0;
241 for(int j = 0; j < n2.length(); j++) {
242 bool bit = n2[j] != '0';
243 if(j == i) {
244 bit = !bit;
245 }
246 if(bit) {
247 val += static_cast<long long>(pow(2, n2.size() - j - 1));
248 }
249 }
250 s.insert(val);
251 }
252
253 for(int n = 1; n <= 2; n++) {
254 for(int i = 0; i < n3.length(); i++) {
255 long long val = 0;
256 for(int j = 0; j < n3.length(); j++) {
257 int v = n3[j] - '0';
258 if(i == j) {
259 v += n;
260 v %= 3;
261 }
262 val += static_cast<long long>(v * pow(3, n3.size() - j - 1));
263 }
264 if(s.contains(val)) {
265 cout << val;
266 return 0;
267 }
268 s.insert(val);
269 }
270 }
271 return 0;
272 }
273
274 int acwing654::main(istream &cin, ostream &cout) {
275 int n;
276 cin >> n;
277 const int s = n % 60;
278 n /= 60;
279 const int m = n % 60;
280 n /= 60;
281 const int h = n;
282 cout << h << ":" << m << ":" << s;
283 return 0;
284 }
285
286 int acwing605::main(istream &cin, ostream &cout) {
287 int a;
288 int b;
289 cin >> a >> b;
290 cout << "PROD = " << a * b;
291 return 0;
292 }
293
294 int acwing2041::main(istream &cin, ostream &cout) {
295 auto *haystack = new int[1000010];
296 memset(haystack, 0, 1000010 * sizeof *haystack);
297 int n;
298 int k;
299 cin >> n >> k;
300 for(int i = 0; i < k; i++) {
301 int a;
302 int b;
303 cin >> a >> b;
304 haystack[a]++;
305 haystack[b + 1]--;
306 }
307 for(int i = 1; i <= n; i++) {
308 haystack[i] += haystack[i - 1];
309 }
310 sort(haystack + 1, haystack + n + 1);
311 cout << haystack[(n + 1) / 2];
312 delete[] haystack;
313 return 0;
314 }
315
316 namespace acwing2060 {
317 int acwing2060::main(istream &cin, ostream &cout) {
318 char cowhide[55][55]{};
319 bool occupy[55][55]{};
320 auto edge = unordered_set<point, pointhash, pointequal>();
321 int n;
322 int m;
323 cin >> n >> m;
324 bool flag = true;
325 point first{};
326 for(int i = 0; i < n; i++) {
327 for(int j = 0; j < m; j++) {
328 cin >> cowhide[i][j];
329 if(flag && cowhide[i][j] == 'X') {
330 occupy[i][j] = true;
331 first = point(i, j);
332 flag = false;
333 } else {
334 occupy[i][j] = false;
335 }
336 }
337 }
338
339 flood(first, occupy, &edge, cowhide, n, m);
340
341 int count = 0;
342 auto nextedge = unordered_set<point, pointhash, pointequal>();
343 while(true) {
344 for(const auto p: edge) {
345 point nexts[] = {
346 point(p.x + 1, p.y), point(p.x - 1, p.y), point(p.x, p.y + 1),
347 point(p.x, p.y - 1)};
348 for(auto next: nexts) {
349 if(0 <= next.x && next.x <= n && 0 <= next.y && next.y <= m && !occupy[next.x][next.y]) {
350 if(cowhide[next.x][next.y] == 'X') {
351 cout << count;
352 return 0;
353 }
354 cowhide[next.x][next.y] = 'X';
355 occupy[next.x][next.y] = true;
356 nextedge.insert(next);
357 }
358 }
359 }
360 count++;
361 edge = nextedge;
362 nextedge = unordered_set<point, pointhash, pointequal>();
363 }
364 }
365
366 size_t pointhash::operator()(const point &p) const { return p.x * 50 + p.y; }
367
368 bool pointequal::operator()(const point &p1, const point &p2) const { return p1.x == p2.x && p1.y == p2.y; }
369
370 void
371 flood(point first, bool occupy[55][55], unordered_set<point, pointhash, pointequal> *edge, char cowhide[55][55],
372 int n, int m) {
373 auto que = queue<point>();
374 const auto eq = pointequal();
375 que.push(first);
376 while(!que.empty()) {
377 auto p = que.front();
378 if(!eq(p, first) && occupy[p.x][p.y]) {
379 que.pop();
380 continue;
381 }
382 occupy[p.x][p.y] = true;
383 point nexts[] = {point(p.x + 1, p.y), point(p.x - 1, p.y), point(p.x, p.y + 1), point(p.x, p.y - 1)};
384 for(auto next: nexts) {
385 if(0 <= next.x && next.x <= n && 0 <= next.y && next.y <= m && !occupy[next.x][next.y]) {
386 if(cowhide[next.x][next.y] == 'X') {
387 que.push(next);
388 } else {
389 edge->insert(p);
390 }
391 }
392 }
393 que.pop();
394 }
395 }
396 }// namespace acwing2060
397
398 namespace acwing2019 {
399 int acwing2019::main(istream &cin, ostream &cout) {
400 int n;
401 int start_x;
402 int start_y;
403 auto *field = new int *[N + 10];
404 for(int i = 0; i < N + 10; i++) {
405 field[i] = new int[N + 10];
406 memset(field[i], 0, (N + 10) * sizeof(int));
407 }
408 //int field[N + 10][N + 10]; //记录状态。0=没有 1=墙 2=已经被搜索过
409
410 cin >> n >> start_x >> start_y;
411 //memset(field, 0, sizeof field);
412 int max_x = 0;
413 int max_y = 0;
414 for(int i = 0; i < n; i++) {
415 int x;
416 int y;
417 cin >> x >> y;
418 if(max_x < x) {
419 max_x = x;
420 }
421 if(max_y < y) {
422 max_y = y;
423 }
424 field[x][y] = 1;
425 }
426 cout << bfs(point(start_x, start_y, 0), field, max_x, max_y);
427 for(int i = 0; i < N + 10; i++) {
428 delete[] field[i];
429 }
430 delete[] field;
431 return 0;
432 }
433
434 int bfs(point start, int **field, int max_x, int max_y) {
435 auto que = deque<point>();
436 que.push_front(start);
437 while(!que.empty()) {
438 const auto p = que.front();
439 que.pop_front();
440 point nexts[] = {
441 point(p.x + 1, p.y, p.step), point(p.x - 1, p.y, p.step),
442 point(p.x, p.y + 1, p.step), point(p.x, p.y - 1, p.step)};
443 for(auto next: nexts) {
444 if(next.x == 0 && next.y == 0) {
445 return next.step;
446 }
447 if(0 <= next.x && next.x <= max_x + 2 && 0 <= next.y && next.y <= max_y + 2 &&
448 field[next.x][next.y] != 2) {
449 if(field[next.x][next.y] == 0) {
450 que.push_front(next);
451 } else {
452 //field[nexts.first][nexts.second]==1
453 next.step++;
454 que.push_back(next);
455 }
456 field[next.x][next.y] = 2;
457 }
458 }
459 }
460 return start.step;
461 }
462 }// namespace acwing2019
463
464 int acwing611::main(istream &cin, ostream &cout) {
465 int a1;
466 int b1;
467 int a2;
468 int b2;
469 double c1;
470 double c2;
471 cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2;
472 cout << "VALOR A PAGAR: R$ " << setiosflags(ios::fixed) << setprecision(2) << b1 * c1 + b2 * c2;
473 return 0;
474 }
475
476 int acwing612::main(istream &cin, ostream &cout) {
477 double r;
478 cin >> r;
479 cout << "VOLUME = " << setiosflags(ios::fixed) << setprecision(3) << 4.0 / 3.0 * 3.14159 * r * r * r;
480 return 0;
481 }
482
483 int acwing2014::main(istream &cin, ostream &cout) {
484 int n;
485 cin >> n;
486 auto *above = new bool[n];
487 auto heights = set<unsigned int>();
488 auto m = map<unsigned int, vector<unsigned int>>();
489 for(int i = 0; i < n; i++) {
490 int height;
491 cin >> height;
492 heights.insert(height);
493 above[i] = true;//露出水面
494 if(!m.contains(height)) {
495 m[height] = vector<unsigned int>();
496 }
497 m[height].push_back(i);
498 }
499 int count = 1;
500 int max = count;
501 for(auto height: heights) {
502 for(const auto index: m[height]) {
503 above[index] = false;
504 if(0 < index && index + 1 < n) {
505 if(above[index - 1] && above[index + 1]) {
506 count++;
507 } else if(!above[index - 1] && !above[index + 1]) {
508 count--;
509 }
510 } else if(index == 0 && !above[1] || index == n - 1 && !above[n - 2]) {
511 count--;
512 }
513 }
514 if(max < count) {
515 max = count;
516 }
517 }
518 cout << max;
519 delete[] above;
520 return 0;
521 }
522
523 int acwing607::main(istream &cin, ostream &cout) {
524 double a;
525 double b;
526 double c;
527 cin >> a >> b >> c;
528 cout << "MEDIA = " << setiosflags(ios::fixed) << setprecision(1) << (a * 2 + b * 3 + c * 5) / 10;
529 return 0;
530 }
531
532 int acwing613::main(istream &cin, ostream &cout) {
533 double a;
534 double b;
535 double c;
536 cin >> a >> b >> c;
537 cout << "TRIANGULO: " << setiosflags(ios::fixed) << setprecision(3) << a * c / 2 << endl;
538 cout << "CIRCULO: " << setiosflags(ios::fixed) << setprecision(3) << c * c * 3.14159 << endl;
539 cout << "TRAPEZIO: " << setiosflags(ios::fixed) << setprecision(3) << (a + b) * c / 2 << endl;
540 cout << "QUADRADO: " << setiosflags(ios::fixed) << setprecision(3) << b * b << endl;
541 cout << "RETANGULO: " << setiosflags(ios::fixed) << setprecision(3) << a * b;
542 return 0;
543 }
544
545 int acwing610::main(istream &cin, ostream &cout) {
546 string name;
547 double b;
548 double m;
549 cin >> name >> b >> m;
550 cout << "TOTAL = R$ " << setiosflags(ios::fixed) << setprecision(2) << b + 0.15 * m;
551 return 0;
552 }
553
554 int acwing614::main(istream &cin, ostream &cout) {
555 int a;
556 int b;
557 int c;
558 cin >> a >> b >> c;
559 const int maxab = (a + b + abs(a - b)) / 2;
560 cout << (maxab + c + abs(maxab - c)) / 2 << " eh o maior";
561 return 0;
562 }
563
564 int acwing2005::main(istream &cin, ostream &cout) {
565 char horseshoes[5][5];
566 bool picked[5][5];
567 int n;
568 cin >> n;
569 for(int i = 0; i < n; i++) {
570 for(int j = 0; j < n; j++) {
571 cin >> horseshoes[i][j];
572 }
573 }
574 memset(picked, 0, sizeof picked);
575 if(horseshoes[0][0] == ')') {
576 cout << 0;
577 return 0;
578 }
579 cout << dfs(true, horseshoes, picked, 1, 1, 0, 0, n);
580 return 0;
581 }
582
583 int acwing2005::dfs(bool stage, char horseshoes[5][5], const bool picked[5][5], int count, int level, int x, int y,
584 int n) {
585 if(level == 0 && !stage) {
586 if(count == 13) {
587 printf("13");
588 }
589 return count;
590 }
591
592 pair<int, int> nexts[4] = {pair(x - 1, y), pair(x + 1, y), pair(x, y - 1),
593 pair(x, y + 1)};
594 //复制状态
595 bool picked_cpy[5][5];
596 memcpy(picked_cpy, picked, sizeof picked_cpy);
597
598 int max = 0;
599 picked_cpy[x][y] = true;
600
601 for(const auto next: nexts) {
602 if(0 <= next.first && next.first < n && 0 <= next.second && next.second < n &&
603 !picked_cpy[next.first][next.second]) {
604 int res = 0;
605 if(stage && horseshoes[next.first][next.second] == '(') {
606 res = dfs(true, horseshoes, picked_cpy, count + 1, level + 1, next.first, next.second, n);
607 } else if(stage && horseshoes[next.first][next.second] == ')') {
608 res = dfs(false, horseshoes, picked_cpy, count + 1, level - 1, next.first, next.second, n);
609 } else if(!stage && horseshoes[next.first][next.second] == ')') {
610 res = dfs(false, horseshoes, picked_cpy, count + 1, level - 1, next.first, next.second, n);
611 }
612 if(max < res) {
613 max = res;
614 }
615 }
616 }
617 return max;
618 }
619
620 int acwing617::main(istream &cin, ostream &cout) {
621 int l;
622 cin >> l;
623 cout << 2 * l << " minutos";
624 return 0;
625 }
626
627 int acwing618::main(istream &cin, ostream &cout) {
628 long t;
629 long s;
630 cin >> t >> s;
631 cout << setiosflags(ios::fixed) << setprecision(3) << static_cast<double>(t * s) / 12;
632 return 0;
633 }
634
635 int acwing4206::main(istream &cin, ostream &cout) {
636 string str;
637 cin >> str;
638 int count = 0;
639 for(const char ch: str) {
640 if(ch == '4' || ch == '7') {
641 count++;
642 }
643 }
644 if(count == 4 || count == 7) {
645 cout << "YES";
646 } else {
647 cout << "NO";
648 }
649 return 0;
650 }
651
652 int acwing4207::main(istream &cin, ostream &cout) {
653 string str;
654 cin >> str;
655 auto *in_sub = new bool[str.length()];
656 int count = 0;
657 memset(in_sub, 0, str.length() * sizeof(bool));
658
659 int prev_left = -1;
660 for(int i = 0; i < str.length(); i++) {
661 if(str[i] == '(') {
662 prev_left = i;
663 break;
664 }
665 }
666 for(int i = prev_left; i < str.length(); i++) {
667 if(str[i] == ')' && prev_left != -1) {
668 count += 2;
669 in_sub[prev_left] = true;
670 in_sub[i] = true;
671 for(int j = prev_left + 1; j < i; j++) {
672 if(str[j] == '(') {
673 prev_left = j;
674 break;
675 }
676 }
677 if(in_sub[prev_left]) {
678 prev_left = -1;
679 }
680 } else if(prev_left == -1 && str[i] == '(') {
681 prev_left = i;
682 }
683 }
684 cout << count;
685 delete[] in_sub;
686 return 0;
687 }
688
689 namespace acwing4208 {
690 int acwing4208::main(istream &cin, ostream &cout) {
691 int n;
692 cin >> n;
693 auto records = map<string, trie_node *>();
694 for(int i = 0; i < n; i++) {
695 string name;
696 cin >> name;
697 if(!records.contains(name)) {
698 //不存在记录
699 records[name] = new trie_node(-1, nullptr);
700 }
701 int n2;
702 cin >> n2;
703 for(int j = 0; j < n2; j++) {
704 string phone_number;
705 cin >> phone_number;
706 string phone_number_trim_left;
707 for(int k = 0; k < phone_number.length(); k++) {
708 if(phone_number[k] != '0') {
709 phone_number_trim_left = phone_number.substr(k);
710 break;
711 }
712 }
713 reverse(phone_number_trim_left.begin(), phone_number_trim_left.end());
714 records[name]->insert(phone_number_trim_left);
715 }
716 }
717 cout << records.size();
718 for(auto it: records) {
719 cout << it.first << " ";
720 cout << it.second->count() << " ";
721 it.second->display();
722 }
723 return 0;
724 }
725
726 void trie_node::insert(string str) {
727 if(str.length() == 0) {
728 return;
729 }
730 if(this->nexts[str[0] - '0'] == nullptr) {
731 this->nexts[str[0] - '0'] = new trie_node(str[0] - '0', this);
732 }
733 this->nexts[str[0] - '0']->insert(str.substr(1));
734 }
735
737 bool flag = true;
738 for(auto *next: this->nexts) {
739 if(next != nullptr) {
740 flag = false;
741 next->display();
742 }
743 }
744 if(flag) {
745 const auto *current = this;
746 while(current->val != -1) {
747 cout << static_cast<char>(current->val + '0');
748 current = current->father;
749 }
750 cout << " ";
751 }
752 }
753
755 int count = 0;
756 bool flag = true;
757 for(auto *next: this->nexts) {
758 if(next != nullptr) {
759 flag = false;
760 count += next->count();
761 }
762 }
763 if(flag) {
764 return 1;
765 }
766 return count;
767 }
768 }// namespace acwing4208
769
770 int acwing1996::main(istream &cin, ostream &cout) {
771 int n;
772 cin >> n;
773 auto names = vector<string>();
774 names.resize(n);
775 auto min_names = vector<string>();
776 auto max_names = vector<string>();
777 min_names.resize(n);
778 max_names.resize(n);
779 for(int i = 0; i < n; i++) {
780 cin >> names[i];
781 const auto *min_name_const_c_str = names[i].c_str();
782 const auto *max_name_const_c_str = names[i].c_str();
783 auto *min_name_c_str = new char[names[i].length() + 1];
784 auto *max_name_c_str = new char[names[i].length() + 1];
785 strcpy(min_name_c_str, min_name_const_c_str);
786 strcpy(max_name_c_str, max_name_const_c_str);
787 sort(min_name_c_str, min_name_c_str + names[i].length() * sizeof(char));
788 sort(max_name_c_str, max_name_c_str + names[i].length() * sizeof(char), cmp);
789 const auto min_name = string(min_name_c_str);
790 const auto max_name = string(max_name_c_str);
791 min_names[i] = min_name;
792 max_names[i] = max_name;
793 delete[] min_name_c_str;
794 delete[] max_name_c_str;
795 }
796 auto min_names_sorted = vector(min_names);
797 auto max_names_sorted = vector(max_names);
798 sort(min_names_sorted.begin(), min_names_sorted.end());
799 sort(max_names_sorted.begin(), max_names_sorted.end());
800 for(int i = 0; i < n; i++) {
801 auto min_name = min_names[i];
802 auto max_name = max_names[i];
803 cout << lower_bound(max_names_sorted.begin(), max_names_sorted.end(), min_name) - max_names_sorted.begin() +
804 1
805 << " "
806 << upper_bound(min_names_sorted.begin(), min_names_sorted.end(), max_name) - min_names_sorted.begin()
807 << endl;
808 }
809 return 0;
810 }
811
812 bool acwing1996::cmp(char x, char y) { return x > y; }
813
814 int acwing656::main(istream &cin, ostream &cout) {
815 double n;
816 cin >> n;
817 int total = static_cast<int>(n * static_cast<double>(100));
818 const int denominations[] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1};
819 int count[12];
820 for(int i = 0; i < 12; i++) {
821 count[i] = total / denominations[i];
822 total %= denominations[i];
823 }
824 cout << "NOTAS:" << endl
825 << count[0] << " nota(s) de R$ 100.00" << endl
826 << count[1] << " nota(s) de R$ 50.00" << endl
827 << count[2] << " nota(s) de R$ 20.00" << endl
828 << count[3] << " nota(s) de R$ 10.00" << endl
829 << count[4] << " nota(s) de R$ 5.00" << endl
830 << count[5] << " nota(s) de R$ 2.00" << endl
831 << "MOEDAS:" << endl
832 << count[6] << " moeda(s) de R$ 1.00" << endl
833 << count[7] << " moeda(s) de R$ 0.50" << endl
834 << count[8] << " moeda(s) de R$ 0.25" << endl
835 << count[9] << " moeda(s) de R$ 0.10" << endl
836 << count[10] << " moeda(s) de R$ 0.05" << endl
837 << count[11] << " moeda(s) de R$ 0.01";
838 return 0;
839 }
840
841 int acwing655::main(istream &cin, ostream &cout) {
842 int n;
843 cin >> n;
844 cout << n / 365 << " ano(s)" << endl;
845 n %= 365;
846 cout << n / 30 << " mes(es)" << endl;
847 n %= 30;
848 cout << n << " dia(s)";
849 return 0;
850 }
851
852 int acwing665::main(istream &cin, ostream &cout) {
853 int a;
854 int b;
855 cin >> a >> b;
856 if(a % b == 0 || b % a == 0) {
857 cout << "Sao Multiplos";
858 } else {
859 cout << "Nao sao Multiplos";
860 }
861 return 0;
862 }
863
864 int acwing657::main(istream &cin, ostream &cout) {
865 int a;
866 int b;
867 int c;
868 int d;
869 cin >> a >> b >> c >> d;
870 if(b > c && d > a && c + d > a + b && c > 0 && d > 0 && a % 2 == 0) {
871 cout << "Valores aceitos";
872 } else {
873 cout << "Valores nao aceitos";
874 }
875 return 0;
876 }
877
878 int acwing1987::main(istream &cin, ostream &cout) {
879 int n;
880 cin >> n;
881 auto m = map<int, int>();
882 int current = 0;
883 for(int i = 0; i < n; i++) {
884 int length;
885 char direction;
886 cin >> length >> direction;
887 if(direction == 'R') {
888 if(!m.contains(current)) {
889 m.insert(pair(current, 1));
890 } else {
891 m[current]++;
892 }
893 if(!m.contains(current + length)) {
894 m.insert(pair(current + length, -1));
895 } else {
896 m[current + length]--;
897 }
898 current += length;
899 } else {
900 if(!m.contains(current)) {
901 m.insert(pair(current, -1));
902 } else {
903 m[current]--;
904 }
905 if(!m.contains(current - length)) {
906 m.insert(pair(current - length, 1));
907 } else {
908 m[current - length]++;
909 }
910 current -= length;
911 }
912 }
913 unsigned int layer_count = 0;
914 unsigned int count = 0;
915 bool above2 = false;
916 int prev;
917 for(const auto p: m) {
918 layer_count += p.second;
919 if(layer_count >= 2) {
920 if(above2) {
921 count += p.first - prev;
922 }
923 above2 = true;
924 prev = p.first;
925 } else {
926 if(above2) {
927 count += p.first - prev;
928 }
929 above2 = false;
930 }
931 }
932 cout << count;
933 return 0;
934 }
935
936 int acwing660::main(istream &cin, ostream &cout) {
937 const double snacks[] = {4, 4.5, 5, 2, 1.5};
938 int x;
939 int y;
940 cin >> x >> y;
941 cout << "Total: R$ " << setiosflags(ios::fixed) << setprecision(2) << snacks[x - 1] * y;
942 return 0;
943 }
944
945 int acwing671::main(istream &cin, ostream &cout) {
946 auto cities = unordered_map<unsigned int, string>();
947 cities[61] = "Brasilia";
948 cities[71] = "Salvador";
949 cities[11] = "Sao Paulo";
950 cities[21] = "Rio de Janeiro";
951 cities[32] = "Juiz de Fora";
952 cities[19] = "Campinas";
953 cities[27] = "Vitoria";
954 cities[31] = "Belo Horizonte";
955 int number;
956 cin >> number;
957 if(cities.contains(number)) {
958 cout << cities[number];
959 } else {
960 cout << "DDD nao cadastrado";
961 }
962 return 0;
963 }
964
965 namespace acwing1978 {
966 int acwing1978::main(istream &cin, ostream &cout) {
967 int n;
968 cin >> n;
969 auto *maximum = new int[n];
970 auto *minimum = new int[n];
971 memset(maximum, 0, n * sizeof(int));
972 memset(minimum, 0, n * sizeof(int));
973 auto *paths = new path[n];
974 for(int i = 0; i < n; i++) {
975 int a;
976 int b;
977 cin >> a >> b;
978 paths[i] = path(a, b);
979 }
980 sort(paths, paths + n);
981 maximum[0] = paths[0].b; //i以前b的最大值
982 minimum[n - 1] = paths[n - 1].b;//i以后b的最小值
983 for(int i = 1; i < n; i++) {
984 maximum[i] = max(maximum[i - 1], paths[i].b);
985 }
986 for(int i = n - 2; i >= 0; i--) {
987 minimum[i] = min(minimum[i + 1], paths[i].b);
988 }
989 int ans = n;
990 for(int i = 0; i < n; i++) {
991 if(maximum[i] > paths[i].b || minimum[i] < paths[i].b) {
992 ans--;
993 }
994 }
995 cout << ans;
996 delete[] paths;
997 delete[] minimum;
998 delete[] maximum;
999 return 0;
1000 }
1001
1002 bool path::operator<(const path &p) const { return this->a < p.a; }
1003 }// namespace acwing1978
1004
1005 int acwing659::main(istream &cin, ostream &cout) {
1006 double x;
1007 const string output[] = {"[0,25]", "(25,50]", "(50,75]", "(75,100]"};
1008 cin >> x;
1009 if(x < 0.0 || x > 100.0) {
1010 cout << "Fora de intervalo";
1011 } else if(x > 75.0) {
1012 cout << "Intervalo " << output[3];
1013 } else if(x > 50.0) {
1014 cout << "Intervalo " << output[2];
1015 } else if(x > 25.0) {
1016 cout << "Intervalo " << output[1];
1017 } else {
1018 cout << "Intervalo " << output[0];
1019 }
1020 return 0;
1021 }
1022
1023 int acwing662::main(istream &cin, ostream &cout) {
1024 float x;
1025 float y;
1026 cin >> x >> y;
1027 if(x == 0 && y == 0) {
1028 cout << "Origem";
1029 } else if(x == 0) {
1030 cout << "Eixo Y";
1031 } else if(y == 0) {
1032 cout << "Eixo X";
1033 } else if(x > 0 && y > 0) {
1034 cout << "Q1";
1035 } else if(x < 0 && y > 0) {
1036 cout << "Q2";
1037 } else if(x < 0 && y < 0) {
1038 cout << "Q3";
1039 } else {
1040 cout << "Q4";
1041 }
1042 return 0;
1043 }
1044
1045 int acwing1969::main(istream &cin, ostream &cout) {
1046 unsigned int n;
1047 unsigned int k;
1048 cin >> n >> k;
1049 auto um = unordered_map<unsigned int, unsigned int>();
1050 auto overcrowding = set<unsigned int>();
1051 for(unsigned int i = 0; i < n; i++) {
1052 unsigned int id;
1053 cin >> id;
1054 if(!um.contains(id)) {
1055 um.insert(pair(id, i));
1056 } else if(!overcrowding.contains(id)) {
1057 if(i - um[id] > k) {
1058 um[id] = i;
1059 } else {
1060 overcrowding.insert(id);
1061 }
1062 }
1063 }
1064 if(overcrowding.empty()) {
1065 cout << -1;
1066 } else {
1067 cout << *--overcrowding.end();
1068 }
1069 return 0;
1070 }
1071
1072 int acwing664::main(istream &cin, ostream &cout) {
1073 double a;
1074 double b;
1075 double c;
1076 cin >> a >> b >> c;
1077 cout << setiosflags(ios::fixed) << setprecision(1);
1078 if(a + b <= c || a + c <= b || b + c <= a) {
1079 cout << "Area = " << (a + b) * c / 2;
1080 } else {
1081 cout << "Perimetro = " << a + b + c;
1082 }
1083 return 0;
1084 }
1085
1086 int acwing666::main(istream &cin, ostream &cout) {
1087 double arr[3];
1088 cin >> arr[0] >> arr[1] >> arr[2];
1089 sort(arr, arr + 3);
1090 const double a = arr[2];
1091 const double b = arr[1];
1092 const double c = arr[0];
1093 if(a >= b + c) {
1094 cout << "NAO FORMA TRIANGULO";
1095 } else {
1096 if(a * a == b * b + c * c) {
1097 cout << "TRIANGULO RETANGULO" << endl;
1098 }
1099 if(a * a > b * b + c * c) {
1100 cout << "TRIANGULO OBTUSANGULO" << endl;
1101 }
1102 if(a * a < b * b + c * c) {
1103 cout << "TRIANGULO ACUTANGULO" << endl;
1104 }
1105 if(a == b && b == c) {
1106 cout << "TRIANGULO EQUILATERO" << endl;
1107 }
1108 if(a == b && b != c || b == c && a != b || a == c && a != b) {
1109 cout << "TRIANGULO ISOSCELES" << endl;
1110 }
1111 }
1112 return 0;
1113 }
1114
1115 int acwing1960::main(istream &cin, ostream &cout) {
1116 memset(fsm, -2, sizeof fsm);
1117 unsigned long long b;
1118 cin >> n >> b;
1119 unsigned int status = 0;
1120 for(int i = 0; i < n; i++) {
1121 unsigned int bulb;
1122 cin >> bulb;
1123 status += bulb;
1124 status <<= 1;
1125 }
1126 status >>= 1;
1127 fsm[status] = -1;
1128
1129 int count = 0;
1130 int round = 0;
1131 unsigned int index = 0;
1132 for(int i = 0; i < b; i++) {
1133 if(fsm[status] >= 0) {
1134 if(round == 0) {
1135 round = 1;
1136 index = status;
1137 } else if(round == 1 && status == index) {
1138 b = (b - i) % count + i;
1139 round = 2;
1140 }
1141 }
1142 if(round == 1) {
1143 count++;
1144 }
1145 status = get_next(status);
1146 }
1147 const auto *const ans = decompress(status);
1148 for(int i = 0; i < n; i++) {
1149 cout << static_cast<int>(ans[i]) << endl;
1150 }
1151 delete[] ans;
1152 return 0;
1153 }
1154
1155 unsigned int acwing1960::get_next(unsigned int status) {
1156 if(fsm[status] >= 0) {
1157 return fsm[status];
1158 }
1159 const bool *bulbs = decompress(status);
1160 auto *const next_bulbs = new bool[n];
1161 for(int i = 0; i < n; i++) {
1162 if(bulbs[(i - 1 + n) % n]) {
1163 next_bulbs[i] = !bulbs[i];
1164 } else {
1165 next_bulbs[i] = bulbs[i];
1166 }
1167 }
1168 const int next_status = compress(next_bulbs);
1169 fsm[status] = next_status;
1170 delete[] next_bulbs;
1171 delete[] bulbs;
1172 return next_status;
1173 }
1174
1175 bool *acwing1960::decompress(unsigned int status) const {
1176 auto *const bulbs = new bool[n];
1177 for(int i = n - 1; i >= 0; i--) {
1178 bulbs[i] = (status & 1) != 0U;
1179 status >>= 1;
1180 }
1181 return bulbs;
1182 }
1183
1184 unsigned int acwing1960::compress(const bool *bulbs) const {
1185 int status = 0;
1186 for(int i = 0; i < n; i++) {
1187 status += static_cast<int>(bulbs[i]);
1188 status <<= 1;
1189 }
1190 status >>= 1;
1191 return status;
1192 }
1193
1194 int acwing667::main(istream &cin, ostream &cout) {
1195 unsigned int a;
1196 unsigned int b;
1197 cin >> a >> b;
1198 int t = (b - a + 24) % 24;
1199 if(t == 0) {
1200 t = 24;
1201 }
1202 cout << "O JOGO DUROU " << t << " HORA(S)";
1203 return 0;
1204 }
1205
1206 int acwing668::main(istream &cin, ostream &cout) {
1207 unsigned int a;
1208 unsigned int b;
1209 unsigned int c;
1210 unsigned int d;
1211 cin >> a >> b >> c >> d;
1212 unsigned int t = (c * 60 + d - (a * 60 + b) + 24 * 60) % (24 * 60);
1213 if(t == 0) {
1214 t = 24 * 60;
1215 }
1216 cout << "O JOGO DUROU " << t / 60 << " HORA(S) E " << t % 60 << " MINUTO(S)";
1217 return 0;
1218 }
1219
1220 int acwing1952::main(istream &cin, ostream &cout) {
1221 unsigned short n;
1222 unsigned short x;
1223 unsigned short y;
1224 unsigned short z;
1225 cin >> n >> x >> y >> z;
1226 auto as = unordered_map<unsigned int, unsigned int>();
1227 auto bs = unordered_map<unsigned int, unsigned int>();
1228 auto edges = set<unsigned int>();
1229 for(unsigned short i = 0; i < n; i++) {
1230 unsigned int a;
1231 unsigned int b;
1232 cin >> a >> b;
1233 if(!as.contains(a)) {
1234 as.insert(pair<unsigned int, unsigned int>(a, 1));
1235 edges.insert(a);
1236 } else {
1237 as[a]++;
1238 }
1239 if(!bs.contains(b)) {
1240 bs.insert(pair<unsigned int, unsigned int>(b, 1));
1241 edges.insert(b);
1242 } else {
1243 bs[b]++;
1244 }
1245 }
1246 unsigned int count = x * n;
1247 unsigned int max = count;
1248 for(unsigned int edge: edges) {
1249 if(as.contains(edge)) {
1250 count += (y - x) * as[edge];
1251 }
1252 if(max < count) {
1253 max = count;
1254 }
1255 if(bs.contains(edge)) {
1256 count -= (y - z) * bs[edge];
1257 }
1258 }
1259 cout << max;
1260 return 0;
1261 }
1262
1263 int acwing669::main(istream &cin, ostream &cout) {
1264 double salary;
1265 cin >> salary;
1266 unsigned short percentual = 0;
1267 if(salary <= 400) {
1268 percentual = 15;
1269 } else if(salary <= 800) {
1270 percentual = 12;
1271 } else if(salary <= 1200) {
1272 percentual = 10;
1273 } else if(salary <= 2000) {
1274 percentual = 7;
1275 } else {
1276 percentual = 4;
1277 }
1278 const double new_salary = salary * (100 + percentual) / 100;
1279 cout << setiosflags(ios::fixed) << setprecision(2);
1280 cout << "Novo salario: " << new_salary << endl;
1281 cout << "Reajuste ganho: " << new_salary - salary << endl;
1282 cout << "Em percentual: " << percentual << " %";
1283 return 0;
1284 }
1285
1286 int acwing672::main(istream &cin, ostream &cout) {
1287 double income;
1288 cin >> income;
1289 double tax = 0;
1290 if(income <= 2000) {
1291 tax = 0;
1292 } else if(2000 < income && income <= 3000) {
1293 income -= 2000;
1294 tax += income * 0.08;
1295 } else if(income <= 4500) {
1296 tax = 80;
1297 income -= 3000;
1298 tax += income * 0.18;
1299 } else {
1300 tax = 350;
1301 income -= 4500;
1302 tax += income * 0.28;
1303 }
1304 if(tax == 0) {
1305 cout << "Isento";
1306 } else {
1307 cout << setiosflags(ios::fixed) << setprecision(2) << "R$ " << tax;
1308 }
1309 return 0;
1310 }
1311
1312 int acwing1945::main(istream &cin, ostream &cout) {
1313 unsigned int count = 0;
1314 unsigned short n;
1315 cin >> n;
1316 auto cows = vector<unsigned int>();
1317 cows.resize(n);
1318 for(int i = 0; i < n; i++) {
1319 unsigned int cow;
1320 cin >> cow;
1321 cows[i] = cow;
1322 }
1323 sort(cows.begin(), cows.end());
1324 for(auto i = cows.begin(); i != cows.end(); ++i) {
1325 for(auto j = i + 1; j != cows.end(); ++j) {
1326 const unsigned int xy = *j - *i;
1327 auto min = lower_bound(j, cows.end(), *j + xy);
1328 auto max = upper_bound(j, cows.end(), *j + 2 * xy);
1329 count += max - min;
1330 }
1331 }
1332 cout << count;
1333 return 0;
1334 }
1335
1336 int acwing4209::main(istream &cin, ostream &cout) {
1337 unsigned int n;
1338 cin >> n;
1339 int x = 0;
1340 int y = 0;
1341 int z = 0;
1342 for(int i = 0; i < n; i++) {
1343 int xi;
1344 int yi;
1345 int zi;
1346 cin >> xi >> yi >> zi;
1347 x += xi;
1348 y += yi;
1349 z += zi;
1350 }
1351 if(x == 0 && y == 0 && z == 0) {
1352 cout << "YES";
1353 } else {
1354 cout << "NO";
1355 }
1356 return 0;
1357 }
1358
1359 int acwing4210::main(istream &cin, ostream &cout) {
1360 unsigned short a;
1361 cin >> a;
1362 unsigned int count = 0;
1363 for(int i = 2; i <= a - 1; i++) {
1364 unsigned short cpy = a;
1365 while(cpy != 0) {
1366 count += cpy % i;
1367 cpy /= i;
1368 }
1369 }
1370 unsigned int denominator = a - 2;
1371 unsigned int molecular = count;
1372 while(denominator % molecular != 0) {
1373 const unsigned int temp = denominator;
1374 denominator = molecular;
1375 molecular = temp % molecular;
1376 }
1377 cout << count / molecular << "/" << (a - 2) / molecular;
1378 return 0;
1379 }
1380
1381 int acwing4211::main(istream &cin, ostream &cout) {
1382 unsigned short n;
1383 cin >> n;
1384 auto vec = vector<unsigned long long>();
1385 for(unsigned short i = 0; i < n; i++) {
1386 unsigned long long a;
1387 cin >> a;
1388 vec.push_back(a);
1389 }
1390 sort(vec.begin(), vec.end(), cmp);
1391 for(const auto i: vec) {
1392 cout << i << " ";
1393 }
1394 return 0;
1395 }
1396
1397 unsigned int acwing4211::no2(unsigned long long a) {
1398 unsigned int count = 0;
1399 while(a % 2 == 0) {
1400 count++;
1401 a /= 2;
1402 }
1403 return count;
1404 }
1405
1406 unsigned int acwing4211::no3(unsigned long long a) {
1407 unsigned int count = 0;
1408 while(a % 3 == 0) {
1409 count++;
1410 a /= 3;
1411 }
1412 return count;
1413 }
1414
1415 bool acwing4211::cmp(unsigned long long a, unsigned long long b) {
1416 const unsigned a3 = no3(a);
1417 const unsigned b3 = no3(b);
1418 if(a3 == b3) {
1419 const unsigned a2 = no2(a);
1420 const unsigned b2 = no2(b);
1421 return a2 < b2;
1422 }
1423 return a3 > b3;
1424 }
1425
1426 int acwing670::main(istream &cin, ostream &cout) {
1427 string str1;
1428 string str2;
1429 string str3;
1430 cin >> str1 >> str2 >> str3;
1431 if(str1 == "vertebrado") {
1432 if(str2 == "ave") {
1433 if(str3 == "carnivoro") {
1434 cout << "aguia";
1435 } else {
1436 cout << "pomba";
1437 }
1438 } else {
1439 if(str3 == "onivoro") {
1440 cout << "homem";
1441 } else {
1442 cout << "vaca";
1443 }
1444 }
1445 } else {
1446 if(str2 == "inseto") {
1447 if(str3 == "hematofago") {
1448 cout << "pulga";
1449 } else {
1450 cout << "lagarta";
1451 }
1452 } else {
1453 if(str3 == "hematofago") {
1454 cout << "sanguessuga";
1455 } else {
1456 cout << "minhoca";
1457 }
1458 }
1459 }
1460 return 0;
1461 }
1462
1463 int acwing633::main(istream &cin, ostream &cout) {
1464 auto vec = vector<short>();
1465 vec.resize(3);
1466 cin >> vec[0];
1467 cin >> vec[1];
1468 cin >> vec[2];
1469 auto sorted = vector(vec);
1470 sort(sorted.begin(), sorted.end());
1471 for(const auto num: sorted) {
1472 cout << num << endl;
1473 }
1474 cout << endl;
1475 for(const auto num: vec) {
1476 cout << num << endl;
1477 }
1478 return 0;
1479 }
1480
1481 int acwing1934::main(istream &cin, ostream &cout) {
1482 int n;
1483 cin >> n;
1484 auto t = vector<int>();
1485 auto d = vector<int>();
1486 for(int i = 0; i < n; i++) {
1487 char op;
1488 int x;
1489 cin >> op >> x;
1490 if(op == 'T') {
1491 t.push_back(x);
1492 } else {
1493 d.push_back(x);
1494 }
1495 }
1496 sort(t.begin(), t.end());
1497 sort(d.begin(), d.end());
1498 double current_d = 0;
1499 double current_t = 0;
1500 double decelerations = 1;
1501 auto it_d = d.begin();
1502 auto it_t = t.begin();
1503 while(true) {
1504 int next_d = 1000;
1505 if(it_d != d.end()) {
1506 next_d = *it_d;
1507 }
1508 const auto t_for_next_d = (next_d - current_d) * decelerations;//到下一个D的时间
1509 bool next_is_d = true;
1510 if(it_t != t.end()) {
1511 next_is_d = t_for_next_d < *it_t - current_t;
1512 }
1513 if(next_is_d) {
1514 //先到D
1515 current_d = next_d;
1516 ++it_d;
1517 current_t += t_for_next_d;
1518 } else if(it_t != t.end()) {
1519 //先到T
1520 current_d += (*it_t - current_t) * (1.0 / decelerations);
1521 current_t = *it_t;
1522 ++it_t;
1523 }
1524 decelerations++;
1525 if(it_d == d.end() && it_t == t.end()) {
1526 current_t += (1000 - current_d) * decelerations;
1527 break;
1528 }
1529 }
1530 cout << lround(current_t);
1531 return 0;
1532 }
1533
1534 int acwing658::main(istream &cin, ostream &cout) {
1535 double a;
1536 double b;
1537 double c;
1538 cin >> a >> b >> c;
1539 if(b * b - 4 * a * c < 0 || a == 0) {
1540 cout << "Impossivel calcular";
1541 return 0;
1542 }
1543 const auto r1 = (-b + sqrt(b * b - 4 * a * c)) / (2 * a);
1544 const auto r2 = (-b - sqrt(b * b - 4 * a * c)) / (2 * a);
1545 cout << setiosflags(ios::fixed) << setprecision(5)
1546 << "R1 = " << r1 << endl
1547 << "R2 = " << r2;
1548 return 0;
1549 }
1550
1551 int acwing661::main(istream &cin, ostream &cout) {
1552 double n1;
1553 double n2;
1554 double n3;
1555 double n4;
1556 cin >> n1 >> n2 >> n3 >> n4;
1557 const double x = (2 * n1 + 3 * n2 + 4 * n3 + n4) / 10;
1558 cout << setiosflags(ios::fixed) << setprecision(1);
1559 cout << "Media: " << x << endl;
1560 if(x >= 7.0) {
1561 cout << "Aluno aprovado.";
1562 } else if(x <= 5.0) {
1563 cout << "Aluno reprovado.";
1564 } else {
1565 cout << "Aluno em exame." << endl;
1566 double y;
1567 cin >> y;
1568 cout << "Nota do exame: " << y << endl;
1569 const double z = (x + y) / 2;
1570 if(z >= 5.0) {
1571 cout << "Aluno aprovado." << endl;
1572 } else {
1573 cout << "Aluno reprovado." << endl;
1574 }
1575 cout << "Media final: " << z;
1576 }
1577 return 0;
1578 }
1579
1580 namespace acwing1929 {
1581 int Solution::main(istream &cin, ostream &cout) {
1582 cin >> n >> m;
1583 for(unsigned short i = 0; i < n; i++) {
1584 for(unsigned short j = 0; j < m; j++) {
1585 cin >> mirrors[i][j];
1586 }
1587 }
1588 int maximum = -1;
1589 for(unsigned short j = 0; j < m; j++) {
1590 maximum = max(maximum, static_cast<int>(count_reflect(down, 0, j)));
1591 }
1592 for(unsigned short j = 0; j < m; j++) {
1593 maximum = max(maximum, static_cast<int>(count_reflect(up, n - 1, j)));
1594 }
1595 for(unsigned short i = 0; i < n; i++) {
1596 maximum = max(maximum, static_cast<int>(count_reflect(right, i, 0)));
1597 }
1598 for(unsigned short i = 0; i < n; i++) {
1599 maximum = max(maximum, static_cast<int>(count_reflect(left, i, m - 1)));
1600 }
1601 cout << maximum;
1602 return 0;
1603 }
1604
1605 unsigned int Solution::count_reflect(direction d, unsigned int x, unsigned int y) {
1606 if(x == 0 || y == 0 || x == n - 1 || y == m - 1) {
1607 unsigned int count = 0;
1608 int current_x = x;
1609 int current_y = y;
1610 direction current_d = d;
1611 auto path = unordered_set<step, step_hash, step_equal>();
1612 while(0 <= current_x && current_x < n && 0 <= current_y && current_y < m) {
1613 auto s = step(current_d, current_x, current_y);
1614 if(!path.contains(s)) {
1615 path.insert(s);
1616 } else {
1617 return -1;
1618 }
1619
1620 const auto *record = get_record(d);
1621 if((*record)[x][y] != 0) {
1622 return count + (*record)[x][y];
1623 }
1624 current_d = reflect(current_d, mirrors[current_x][current_y]);
1625 count++;
1626 (*get_record(!current_d))[current_x][current_y] = count;
1627 switch(current_d) {
1628 case left: {
1629 current_y--;
1630 break;
1631 }
1632 case right: {
1633 current_y++;
1634 break;
1635 }
1636 case up: {
1637 current_x--;
1638 break;
1639 }
1640 case down: {
1641 current_x++;
1642 break;
1643 }
1644 }
1645 }
1646 return count;
1647 }
1648 return -1;
1649 }
1650
1651 unsigned int (*Solution::get_record(direction d))[1000][1000] {
1652 switch(d) {
1653 case left: {
1654 return &left_map;
1655 }
1656 case right: {
1657 return &right_map;
1658 }
1659 case up: {
1660 return &up_map;
1661 }
1662 case down: {
1663 return &down_map;
1664 }
1665 }
1666 return nullptr;
1667 }
1668
1669 direction reflect(direction d, char mirror) {
1670 switch(d) {
1671 case left: {
1672 if(mirror == '/') {
1673 return down;
1674 }
1675 if(mirror == '\\') {
1676 return up;
1677 }
1678 break;
1679 }
1680 case right: {
1681 if(mirror == '/') {
1682 return up;
1683 }
1684 if(mirror == '\\') {
1685 return down;
1686 }
1687 break;
1688 }
1689 case up: {
1690 if(mirror == '/') {
1691 return right;
1692 }
1693 if(mirror == '\\') {
1694 return left;
1695 }
1696 break;
1697 }
1698 case down: {
1699 if(mirror == '/') {
1700 return left;
1701 }
1702 if(mirror == '\\') {
1703 return right;
1704 }
1705 break;
1706 }
1707 }
1708 return {};
1709 }
1710
1712 switch(d) {
1713 case left: {
1714 return right;
1715 }
1716 case right: {
1717 return left;
1718 }
1719 case up: {
1720 return down;
1721 }
1722 case down: {
1723 return up;
1724 }
1725 }
1726 return {};
1727 }
1728
1729 unsigned long step_hash::operator()(const step &s) const { return s.d * 1000 * 1000 + s.x * 1000 + s.y; }
1730
1731 bool step_equal::operator()(const step &s1, const step &s2) const { return s1.d == s2.d && s1.x == s2.x && s1.y == s2.y; }
1732 }// namespace acwing1929
1733
1734 int acwing708::main(istream & /*cin*/, ostream &cout) {
1735 for(int i = 1; i <= 100; i++) {
1736 if(i % 2 == 0) {
1737 cout << i << endl;
1738 }
1739 }
1740 return 0;
1741 }
1742
1743 int acwing715::main(istream &cin, ostream &cout) {
1744 int n;
1745 cin >> n;
1746 for(int i = 2; i < 10000; i += n) {
1747 cout << i << endl;
1748 }
1749 return 0;
1750 }
1751
1752 int acwing1922::main(istream &cin, ostream &cout) {
1753 unsigned int n;
1754 unsigned int k;
1755 cin >> n >> k;
1756 auto um = unordered_map<unsigned int, unsigned int>();
1757 unsigned int max_x = 0;
1758 for(unsigned int i = 0; i < n; i++) {
1759 unsigned int g;
1760 unsigned int x;
1761 cin >> g >> x;
1762 max_x = max(max_x, x);
1763 um.insert(pair(x, g));
1764 }
1765 unsigned int count = 0;
1766 for(int i = 0; i < 2 * k; i++) {
1767 if(um.contains(i)) {
1768 count += um[i];
1769 }
1770 }
1771 unsigned int maximum = count;
1772 for(int i = 1; i + 2 * k <= max_x; i++) {
1773 if(um.contains(i - 1)) {
1774 count -= um[i - 1];
1775 }
1776 if(um.contains(i + 2 * k)) {
1777 count += um[i + 2 * k];
1778 }
1779 maximum = max(maximum, count);
1780 }
1781 cout << maximum;
1782 return 0;
1783 }
1784
1785 int acwing709::main(istream &cin, ostream &cout) {
1786 int x;
1787 cin >> x;
1788 for(int i = 1; i <= x; i += 2) {
1789 cout << i << endl;
1790 }
1791 return 0;
1792 }
1793
1794 int acwing710::main(istream &cin, ostream &cout) {
1795 int x;
1796 cin >> x;
1797 if(x % 2 == 0) {
1798 x++;
1799 }
1800 for(int i = 0; i < 6; i++) {
1801 cout << x + i * 2 << endl;
1802 }
1803 return 0;
1804 }
1805
1806 int acwing1913::main(istream &cin, ostream &cout) {
1807 unsigned int n;
1808 cin >> n;
1809 auto cows = map<unsigned int, int>();
1810 auto indexes = vector<unsigned int>();
1811 auto sum = unordered_map<int, set<unsigned int>>();
1812 for(unsigned int i = 0; i < n; i++) {
1813 unsigned int x;
1814 char b;
1815 cin >> x >> b;
1816 indexes.push_back(x);
1817 if(b == 'G') {
1818 cows.insert(pair(x, 1));
1819 } else {
1820 cows.insert(pair(x, -1));
1821 }
1822 }
1823 sort(indexes.begin(), indexes.end());
1824
1825 unsigned int g_count = 0;
1826 unsigned int h_count = 0;
1827 unsigned int g_max = 0;
1828 unsigned int h_max = 0;
1829 int g_start = -1;
1830 int h_start = -1;
1831 int count = 0;
1832 for(auto &cow: cows) {
1833 if(cow.second == 1) {
1834 //G
1835 h_count = 0;
1836 h_start = -1;
1837 if(g_start == -1) {
1838 g_start = cow.first;
1839 } else {
1840 g_count = cow.first - g_start;
1841 }
1842 g_max = max(g_max, g_count);
1843 } else {
1844 //H
1845 g_count = 0;
1846 g_start = -1;
1847 if(h_start == -1) {
1848 h_start = cow.first;
1849 } else {
1850 h_count = cow.first - h_start;
1851 }
1852 h_max = max(h_max, h_count);
1853 }
1854 count += cow.second;
1855 cow.second = count;
1856 if(!sum.contains(cow.second)) {
1857 auto s = set<unsigned int>();
1858 s.insert(cow.first);
1859 sum.insert(pair(cow.second, s));
1860 } else {
1861 sum[cow.second].insert(cow.first);
1862 }
1863 }
1864 unsigned int maximum = 0;
1865 for(const auto &i: sum) {
1866 if(i.first == 0) {
1867 maximum = max(maximum, *i.second.rbegin() - indexes[0]);
1868 } else if(i.second.size() >= 2) {
1869 maximum = max(maximum, *i.second.rbegin() - *upper_bound(indexes.begin(), indexes.end(), *i.second.begin()));
1870 }
1871 }
1872 cout << max(maximum, max(g_max, h_max));
1873 return 0;
1874 }
1875
1876 int acwing712::main(istream &cin, ostream &cout) {
1877 int count = 0;
1878 for(int i = 0; i < 6; i++) {
1879 double x;
1880 cin >> x;
1881 if(x > 0) {
1882 count++;
1883 }
1884 }
1885 cout << count << " positive numbers";
1886 return 0;
1887 }
1888
1889 int acwing711::main(istream &cin, ostream &cout) {
1890 int n;
1891 cin >> n;
1892 for(int i = 1; i <= 10; i++) {
1893 cout << i << " x " << n << " = " << i * n << endl;
1894 }
1895 return 0;
1896 }
1897
1898 int acwing1904::main(istream &cin, ostream &cout) {
1899 unsigned int n;
1900 cin >> n;
1901 auto speeds = map<unsigned int, unsigned int>();
1902 for(unsigned int i = 0; i < n; i++) {
1903 unsigned int pos;
1904 unsigned int speed;
1905 cin >> pos >> speed;
1906 speeds.insert(pair(pos, speed));
1907 }
1908 unsigned int current_min = 1000000000;
1909 unsigned int count = 0;
1910 for(auto i = speeds.rbegin(); i != speeds.rend(); ++i) {
1911 if((*i).second <= current_min) {
1912 current_min = (*i).second;
1913 count++;
1914 }
1915 }
1916 cout << count;
1917 return 0;
1918 }
1919
1920 int acwing714::main(istream &cin, ostream &cout) {
1921 short x;
1922 short y;
1923 cin >> x >> y;
1924 if(y < x) {
1925 const auto temp = x;
1926 x = y;
1927 y = temp;
1928 }
1929 int count = 0;
1930 for(int i = x + 1; i < y; i++) {
1931 if(i % 2 != 0) {
1932 count += i;
1933 }
1934 }
1935 cout << count;
1936 return 0;
1937 }
1938
1939 int acwing718::main(istream &cin, ostream &cout) {
1940 unsigned short n;
1941 cin >> n;
1942 unsigned int c_count = 0;
1943 unsigned int r_count = 0;
1944 unsigned int f_count = 0;
1945 for(unsigned short i = 0; i < n; i++) {
1946 unsigned short a;
1947 char t;
1948 cin >> a >> t;
1949 switch(t) {
1950 case 'C':
1951 c_count += a;
1952 break;
1953 case 'R':
1954 r_count += a;
1955 break;
1956 case 'F':
1957 f_count += a;
1958 break;
1959 }
1960 }
1961 const unsigned int count = c_count + r_count + f_count;
1962 cout << setiosflags(ios::fixed) << setprecision(2) << "Total: " << count << " animals" << endl
1963 << "Total coneys: " << c_count << endl
1964 << "Total rats: " << r_count << endl
1965 << "Total frogs: " << f_count << endl
1966 << "Percentage of coneys: " << static_cast<double>(c_count) / static_cast<double>(count) * 100
1967 << " %" << endl
1968 << "Percentage of rats: " << static_cast<double>(r_count) / static_cast<double>(count) * 100
1969 << " %" << endl
1970 << "Percentage of frogs: " << static_cast<double>(f_count) / static_cast<double>(count) * 100
1971 << " %";
1972 return 0;
1973 }
1974
1975 int acwing1884::main(istream &cin, ostream &cout) {
1976 int n;
1977 cin >> n;
1978 auto *cow = new char[n];
1979 auto *c = new int[n];//当前项左边有多少个C
1980 auto *w = new int[n];//当前项右边有多少个W
1981 c[0] = 0;
1982 w[n - 1] = 0;
1983 for(int i = 0; i < n; i++) {
1984 cin >> cow[i];
1985 if(i >= 1) {
1986 c[i] = c[i - 1];
1987 if(cow[i - 1] == 'C') {
1988 c[i]++;
1989 }
1990 }
1991 }
1992 for(int i = n - 2; i >= 0; i--) {
1993 w[i] = w[i + 1];
1994 if(cow[i + 1] == 'W') {
1995 w[i]++;
1996 }
1997 }
1998 unsigned long count = 0;
1999 for(int i = 0; i < n; i++) {
2000 if(cow[i] == 'O') {
2001 count += c[i] * w[i];
2002 }
2003 }
2004 cout << count;
2005 delete[] w;
2006 delete[] c;
2007 delete[] cow;
2008 return 0;
2009 }
2010
2011 int acwing4212::main(istream &cin, ostream &cout) {
2012 string a;
2013 string b;
2014 cin >> a >> b;
2015 auto ossa = ostringstream();
2016 auto ossb = ostringstream();
2017 for(char ch: a) {
2018 if(isupper(ch) != 0) {
2019 ch = tolower(ch);
2020 }
2021 ossa << ch;
2022 }
2023 for(char ch: b) {
2024 if(isupper(ch) != 0) {
2025 ch = tolower(ch);
2026 }
2027 ossb << ch;
2028 }
2029 a = ossa.str();
2030 b = ossb.str();
2031 if(a > b) {
2032 cout << 1;
2033 } else if(a < b) {
2034 cout << -1;
2035 } else {
2036 cout << 0;
2037 }
2038 return 0;
2039 }
2040
2041 int acwing4213::main(istream &cin, ostream &cout) {
2042 unsigned int num[4];
2043 cin >> num[0] >> num[1] >> num[2] >> num[3];
2044 vector<char> ops;
2045 char op;
2046 for(int i = 0; i < 3; i++) {
2047 cin >> op;
2048 ops.push_back(op);
2049 }
2050 cout << get_min(ops, vector<unsigned long long>(begin(num), end(num)));
2051 return 0;
2052 }
2053
2054 unsigned long long acwing4213::get_min(vector<char> ops, vector<unsigned long long> vec) {
2055 const char op = ops[0];
2056 if(vec.size() == 2) {
2057 if(op == '+') {
2058 return vec[0] + vec[1];
2059 }
2060 return vec[0] * vec[1];
2061 }
2062 const auto next_ops = vector(ops.begin() + 1, ops.end());
2063 unsigned long long minimum = 1000000000000;
2064 for(int i = 0; i < vec.size() - 1; i++) {
2065 for(int j = i + 1; j < vec.size(); j++) {
2066 unsigned long long new_num;
2067 if(op == '+') {
2068 new_num = vec[i] + vec[j];
2069 } else {
2070 new_num = vec[i] * vec[j];
2071 }
2072 auto new_vec = vector<unsigned long long>();
2073 new_vec.push_back(new_num);
2074 for(int k = 0; k < vec.size(); k++) {
2075 if(k != i && k != j) {
2076 new_vec.push_back(vec[k]);
2077 }
2078 }
2079 const auto ret = get_min(next_ops, new_vec);
2080 if(minimum > ret) {
2081 minimum = ret;
2082 }
2083 }
2084 }
2085 return minimum;
2086 }
2087
2088 int acwing4214::main(istream &cin, ostream &cout) {
2089 unsigned short n;
2090 cin >> n;
2091 auto *s = new unsigned int[n];
2092 auto *c = new unsigned int[n];
2093 for(unsigned short i = 0; i < n; i++) {
2094 cin >> s[i];
2095 }
2096 for(unsigned short i = 0; i < n; i++) {
2097 cin >> c[i];
2098 }
2099 unsigned int minimum = 300000001;
2100 for(int j = 1; j < n - 1; j++) {
2101 unsigned int min_left = 100000001;
2102 unsigned int min_right = 100000001;
2103 for(int i = 0; i < j; i++) {
2104 if(s[i] < s[j]) {
2105 if(c[i] < min_left) {
2106 min_left = c[i];
2107 }
2108 }
2109 }
2110 for(int k = j + 1; k < n; k++) {
2111 if(s[j] < s[k]) {
2112 if(c[k] < min_right) {
2113 min_right = c[k];
2114 }
2115 }
2116 }
2117 if(min_left != 100000001 && min_right != 100000001 && minimum > min_left + c[j] + min_right) {
2118 minimum = min_left + c[j] + min_right;
2119 }
2120 }
2121 if(minimum != 300000001) {
2122 cout << minimum;
2123 } else {
2124 cout << -1;
2125 }
2126 return 0;
2127 }
2128
2129 int acwing716::main(istream &cin, ostream &cout) {
2130 int maximum = 0;
2131 int max_i = 0;
2132 for(int i = 1; i <= 100; i++) {
2133 int num;
2134 cin >> num;
2135 if(num > maximum) {
2136 maximum = num;
2137 max_i = i;
2138 }
2139 }
2140 cout << maximum << endl
2141 << max_i;
2142 return 0;
2143 }
2144
2145 int acwing713::main(istream &cin, ostream &cout) {
2146 int n;
2147 unsigned int in = 0;
2148 unsigned int out = 0;
2149 cin >> n;
2150 for(int i = 0; i < n; i++) {
2151 int num;
2152 cin >> num;
2153 if(10 <= num && num <= 20) {
2154 in++;
2155 } else {
2156 out++;
2157 }
2158 }
2159 cout << in << " in" << endl
2160 << out << " out";
2161 return 0;
2162 }
2163
2164 int acwing721::main(istream &cin, ostream &cout) {
2165 unsigned short x;
2166 while(cin >> x) {
2167 if(x == 0) {
2168 return 0;
2169 }
2170 for(int i = 1; i <= x; i++) {
2171 cout << i << " ";
2172 }
2173 cout << endl;
2174 }
2175 return 0;
2176 }
2177
2178 int acwing719::main(istream &cin, ostream &cout) {
2179 unsigned short n;
2180 cin >> n;
2181 for(unsigned short i = 0; i < n; i++) {
2182 int count = 0;
2183 int x;
2184 int y;
2185 cin >> x >> y;
2186 if(x > y) {
2187 const int temp = y;
2188 y = x;
2189 x = temp;
2190 }
2191 if(x % 2 == 0) {
2192 x++;
2193 } else {
2194 x += 2;
2195 }
2196 for(int j = x; j < y; j += 2) {
2197 count += j;
2198 }
2199 cout << count << endl;
2200 }
2201 return 0;
2202 }
2203
2204 int acwing1875::main(istream &cin, ostream &cout) {
2205 auto b = vector<int>();
2206 auto e = vector<int>();
2207 auto s = vector<int>();
2208 auto i = vector<int>();
2209 auto g = vector<int>();
2210 auto o = vector<int>();
2211 auto m = vector<int>();
2212 unsigned short n;
2213 cin >> n;
2214 for(unsigned short j = 0; j < n; j++) {
2215 char ch;
2216 int val;
2217 cin >> ch >> val;
2218 switch(ch) {
2219 case 'B':
2220 b.push_back(val);
2221 break;
2222 case 'E':
2223 e.push_back(val);
2224 break;
2225 case 'S':
2226 s.push_back(val);
2227 break;
2228 case 'I':
2229 i.push_back(val);
2230 break;
2231 case 'G':
2232 g.push_back(val);
2233 break;
2234 case 'O':
2235 o.push_back(val);
2236 break;
2237 case 'M':
2238 m.push_back(val);
2239 break;
2240 default: return 1;
2241 }
2242 }
2243 unsigned int count_a = 0;
2244 for(const auto ms: m) {
2245 if(ms % 2 != 0) {
2246 count_a++;
2247 }
2248 }
2249 unsigned int count_b = 0;
2250 for(const auto bs: b) {
2251 for(const auto is: i) {
2252 if((bs + is) % 2 != 0) {
2253 count_b++;
2254 }
2255 }
2256 }
2257 unsigned int count_c = 0;
2258 for(const auto gs: g) {
2259 for(const auto os: o) {
2260 for(const auto es: e) {
2261 for(const auto ss: s) {
2262 if((gs + os + es + ss) % 2 != 0) {
2263 count_c++;
2264 }
2265 }
2266 }
2267 }
2268 }
2269 const unsigned long long count = b.size() * e.size() * s.size() * i.size() * g.size() * o.size() * m.size();
2270 cout << count - count_a * count_b * count_c;
2271 return 0;
2272 }
2273
2274 int acwing720::main(istream &cin, ostream &cout) {
2275 int a;
2276 int count = 0;
2277 cin >> a;
2278 int n;
2279 do {
2280 cin >> n;
2281 } while(n <= 0);
2282 for(int i = 0; i < n; i++) {
2283 count += a + i;
2284 }
2285 cout << count;
2286 return 0;
2287 }
2288
2289 int acwing717::main(istream &cin, ostream &cout) {
2290 unsigned short n;
2291 cin >> n;
2292 auto fibb = vector<unsigned int>();
2293 fibb.resize(n);
2294 fibb[0] = 0;
2295 fibb[1] = 1;
2296 for(unsigned short i = 2; i < n; i++) {
2297 fibb[i] = fibb[i - 1] + fibb[i - 2];
2298 }
2299 for(const auto num: fibb) {
2300 cout << num << " ";
2301 }
2302 return 0;
2303 }
2304
2305 int acwing1855::main(istream &cin, ostream &cout) {
2306 unsigned short n;
2307 cin >> n;
2308 auto hay = vector<unsigned int>();
2309 for(unsigned short i = 0; i < n; i++) {
2310 unsigned int x;
2311 cin >> x;
2312 hay.push_back(x);
2313 }
2314 sort(hay.begin(), hay.end());
2315 unsigned int maximum = 0;
2316 for(auto start = hay.begin(); start != hay.end(); ++start) {
2317 bool left_end = false;
2318 bool right_end = false;
2319 auto left = start;
2320 auto right = start;
2321 for(int i = 1;; i++) {
2322 if(!left_end) {
2323 auto l = lower_bound(hay.begin(), hay.end(), *left - i);
2324 if(l == hay.end() || l == left) {
2325 left_end = true;
2326 } else {
2327 left = l;
2328 }
2329 }
2330 if(!right_end) {
2331 auto r = upper_bound(hay.begin(), hay.end(), *right + i) - 1;
2332 if(r == hay.end() || r == right) {
2333 right_end = true;
2334 } else {
2335 right = r;
2336 }
2337 }
2338 if(left_end && right_end) {
2339 maximum = max(maximum, static_cast<unsigned int>(right - left) + 1);
2340 break;
2341 }
2342 }
2343 }
2344 cout << maximum;
2345 return 0;
2346 }
2347
2348 int acwing724::main(istream &cin, ostream &cout) {
2349 unsigned short n;
2350 cin >> n;
2351 cout << 1 << endl;
2352 for(unsigned short i = 2; i < n; i++) {
2353 if(n % i == 0) {
2354 cout << i << endl;
2355 }
2356 }
2357 if(n != 1) {
2358 cout << n;
2359 }
2360 return 0;
2361 }
2362
2363 int acwing722::main(istream &cin, ostream &cout) {
2364 int count = 0;
2365 int m;
2366 int n;
2367 cin >> m >> n;
2368 while(n > 0 && m > 0) {
2369 if(m > n) {
2370 swap(m, n);
2371 }
2372 for(int i = m; i <= n; i++) {
2373 cout << i << " ";
2374 }
2375 count += 2 * (m + n);
2376 cout << "Sum=" << (n - m + 1) * (m + n) / 2 << endl;
2377 cin >> m >> n;
2378 }
2379 return 0;
2380 }
2381
2382 int acwing1843::main(istream &cin, ostream &cout) {
2383 unsigned short n;
2384 unsigned int min = 0;
2385 cin >> n;
2386 auto *r = new unsigned short[n];
2387 for(unsigned short i = 0; i < n; i++) {
2388 cin >> r[i];
2389 }
2390 for(unsigned short i = 0; i < n; i++) {
2391 unsigned int count = 0;
2392 for(unsigned short j = 0; j < n - 1; j++) {
2393 count += r[(i - j + n) % n] * (n - j - 1);
2394 }
2395 if(min == 0 || min > count) {
2396 min = count;
2397 }
2398 }
2399 cout << min;
2400 delete[] r;
2401 return 0;
2402 }
2403
2404 int acwing723::main(istream &cin, ostream &cout) {
2405 unsigned short n;
2406 unsigned short m;
2407 cin >> n >> m;
2408 for(int i = 0; i < n; i++) {
2409 for(int j = 0; j < m; j++) {
2410 if(j != m - 1) {
2411 cout << i * m + j + 1 << " ";
2412 } else {
2413 cout << "PUM" << endl;
2414 }
2415 }
2416 }
2417 return 0;
2418 }
2419
2420 int acwing725::main(istream &cin, ostream &cout) {
2421 unsigned short n;
2422 cin >> n;
2423 unsigned int x;
2424 for(unsigned short i = 0; i < n; i++) {
2425 cin >> x;
2426 unsigned int count = 1;
2427 const auto max = static_cast<unsigned int>(sqrt(static_cast<double>(x)));
2428 for(unsigned int j = 2; j <= max; j++) {
2429 if(x % j == 0) {
2430 count += j;
2431 count += x / j;
2432 if(j == x / j) {
2433 count -= j;
2434 }
2435 }
2436 }
2437 cout << x;
2438 if(x == 1 || count != x) {
2439 cout << " is not perfect";
2440 } else {
2441 cout << " is perfect";
2442 }
2443 cout << endl;
2444 }
2445 return 0;
2446 }
2447
2448 namespace acwing1826 {
2449 int acwing1826::main(istream &cin, ostream &cout) {
2450 unsigned int n;
2451 unsigned int x;
2452 unsigned int y;
2453 cin >> n;
2454 multiset<pair<unsigned int, unsigned int>, cmprow> row;
2455 multiset<pair<unsigned int, unsigned int>, cmpcol> col;
2456 for(unsigned int i = 0; i < n; i++) {
2457 cin >> x >> y;
2458 row.insert(pair(x, y));
2459 col.insert(pair(x, y));
2460 }
2461 unsigned int minimum = ((*row.rbegin()).first - (*row.begin()).first) * ((*col.rbegin()).second - (*col.begin()).second);
2462
2463 auto row_cpy = multiset(row);
2464 auto col_cpy = multiset(col);
2465 auto r_pair = *row_cpy.begin();
2466 row_cpy.erase(row_cpy.find(r_pair));
2467 col_cpy.erase(col_cpy.find(r_pair));
2468 minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
2469
2470 row_cpy = multiset(row);
2471 col_cpy = multiset(col);
2472 r_pair = *row_cpy.rbegin();
2473 row_cpy.erase(row_cpy.find(r_pair));
2474 col_cpy.erase(col_cpy.find(r_pair));
2475 minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
2476
2477 row_cpy = multiset(row);
2478 col_cpy = multiset(col);
2479 auto c_pair = *col_cpy.begin();
2480 row_cpy.erase(row_cpy.find(c_pair));
2481 col_cpy.erase(col_cpy.find(c_pair));
2482 minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
2483
2484 row_cpy = multiset(row);
2485 col_cpy = multiset(col);
2486 c_pair = *col_cpy.rbegin();
2487 row_cpy.erase(row_cpy.find(c_pair));
2488 col_cpy.erase(col_cpy.find(c_pair));
2489 minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
2490
2491 cout << minimum;
2492 return 0;
2493 }
2494
2495 bool cmprow::operator()(const pair<unsigned int, unsigned int> &left, const pair<unsigned int, unsigned int> &right) const { return left.first < right.first; }
2496
2497 bool cmpcol::operator()(const pair<unsigned int, unsigned int> &left, const pair<unsigned int, unsigned int> &right) const { return left.second < right.second; }
2498 }// namespace acwing1826
2499
2500 int acwing1813::main(istream &cin, ostream &cout) {
2501 int n;
2502 int charmap[26] = {};
2503 cin >> n;
2504 for(int i = 0; i < n; i++) {
2505 int charmap_a[26] = {};
2506 int charmap_b[26] = {};
2507 string a;
2508 string b;
2509 cin >> a >> b;
2510 for(const char ch: a) {
2511 charmap_a[ch - 'a']++;
2512 }
2513 for(const char ch: b) {
2514 charmap_b[ch - 'a']++;
2515 }
2516 for(int j = 0; j < 26; j++) {
2517 charmap[j] += max(charmap_a[j], charmap_b[j]);
2518 }
2519 }
2520 for(const int i: charmap) {
2521 cout << i << endl;
2522 }
2523 return 0;
2524 }
2525
2526 int acwing726::main(istream &cin, ostream &cout) {
2527 int n;
2528 int x;
2529 cin >> n;
2530 for(int i = 0; i < n; i++) {
2531 cin >> x;
2532 for(int j = 2; j <= sqrt(x); j++) {
2533 if(x % j == 0) {
2534 cout << x << " is not prime" << endl;
2535 goto next;
2536 }
2537 }
2538 cout << x << " is prime" << endl;
2539 next:;
2540 }
2541 return 0;
2542 }
2543
2544 int acwing727::main(istream &cin, ostream &cout) {
2545 int n;
2546 cin >> n;
2547 for(int i = 0; i <= n / 2; i++) {
2548 for(int j = 0; j < n / 2 - i; j++) {
2549 cout << ' ';
2550 }
2551 for(int k = 0; k < 1 + 2 * i; k++) {
2552 cout << '*';
2553 }
2554 cout << endl;
2555 }
2556 for(int i = n / 2 + 1; i < n; i++) {
2557 for(int j = 0; j < i - n / 2; j++) {
2558 cout << ' ';
2559 }
2560 for(int k = 0; k < 1 + 2 * (n - i - 1); k++) {
2561 cout << '*';
2562 }
2563 cout << endl;
2564 }
2565 return 0;
2566 }
2567
2568 int acwing737::main(istream &cin, ostream &cout) {
2569 short x;
2570 for(int i = 0; i < 10; i++) {
2571 cin >> x;
2572 if(x <= 0) {
2573 x = 1;
2574 }
2575 cout << "X[" << i << "] = " << x << endl;
2576 }
2577 return 0;
2578 }
2579
2580 int acwing740::main(istream &cin, ostream &cout) {
2581 short n[20];
2582 for(int i = 0; i < 20; i++) {
2583 cin >> n[20 - i - 1];
2584 }
2585 for(int i = 0; i < 20; i++) {
2586 cout << "N[" << i << "] = " << n[i] << endl;
2587 }
2588 return 0;
2589 }
2590
2591 int acwing1801::main(istream &cin, ostream &cout) {
2592 int n;
2593 cin >> n;
2594 int count_123 = 0;
2595 int count_132 = 0;
2596 int count_213 = 0;
2597 int count_231 = 0;
2598 int count_312 = 0;
2599 int count_321 = 0;
2600 for(int i = 0; i < n; i++) {
2601 int a;
2602 int b;
2603 cin >> a >> b;
2604 if(a == 1 && b == 2) {
2605 count_132++;
2606 count_213++;
2607 count_321++;
2608 } else if(a == 1 && b == 3) {
2609 count_123++;
2610 count_231++;
2611 count_312++;
2612 } else if(a == 2 && b == 1) {
2613 count_123++;
2614 count_231++;
2615 count_312++;
2616 } else if(a == 2 && b == 3) {
2617 count_132++;
2618 count_213++;
2619 count_321++;
2620 } else if(a == 3 && b == 1) {
2621 count_132++;
2622 count_213++;
2623 count_321++;
2624 } else if(a == 3 && b == 2) {
2625 count_123++;
2626 count_231++;
2627 count_312++;
2628 }
2629 }
2630 int maximum = count_123;
2631 maximum = max(maximum, count_132);
2632 maximum = max(maximum, count_213);
2633 maximum = max(maximum, count_231);
2634 maximum = max(maximum, count_312);
2635 maximum = max(maximum, count_321);
2636 cout << maximum;
2637 return 0;
2638 }
2639
2640 int acwing4215::main(istream &cin, ostream &cout) {
2641 char ch;
2642 while(cin >> ch) {
2643 if(isupper(ch) != 0) {
2644 ch = tolower(ch);
2645 }
2646 if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'y') {
2647 continue;
2648 }
2649 cout << '.' << ch;
2650 }
2651 return 0;
2652 }
2653
2654 int acwing4216::main(istream &cin, ostream &cout) {
2655 unsigned short n;
2656 unsigned short m;
2657 unsigned short a;
2658 unsigned short b;
2659 cin >> n >> m;
2660 auto flag = vector(n, false);
2661 auto edge = vector(n, unordered_set<unsigned short>());
2662 for(unsigned short i = 0; i < m; i++) {
2663 cin >> a >> b;
2664 edge[a - 1].insert(b - 1);
2665 edge[b - 1].insert(a - 1);
2666 }
2667 int circle = 0;
2668 auto que = queue<pair<unsigned short, unsigned short>>();
2669 que.push(pair(0, 0));
2670 flag[0] = true;
2671 while(!que.empty()) {
2672 auto [prev, current] = que.front();
2673 que.pop();
2674 for(auto next: edge[current]) {
2675 if(next != prev) {
2676 if(flag[next]) {
2677 if(circle == 2) {
2678 cout << "NO";
2679 return 0;
2680 }
2681 circle += 1;
2682 } else {
2683 que.push(pair(current, next));
2684 flag[next] = true;
2685 }
2686 }
2687 }
2688 }
2689 for(unsigned short i = 0; i < n; i++) {
2690 if(!flag[i]) {
2691 cout << "NO";
2692 return 0;
2693 }
2694 }
2695 if(circle != 2) {
2696 cout << "NO";
2697 return 0;
2698 }
2699 cout << "YES";
2700 return 0;
2701 }
2702
2703 int acwing4217::main(istream &cin, ostream &cout) {
2704 cin >> n;
2705 ops = vector<char>();
2706 forth = vector<pair<int, int>>();
2707 back = vector<pair<int, int>>();
2708 ops.resize(n);
2709 forth.emplace_back(0, 0);
2710 for(int i = 0; i < n; i++) {
2711 cin >> ops[i];
2712 switch(ops[i]) {
2713 case 'U': {
2714 forth.emplace_back(forth.back().first, forth.back().second + 1);
2715 break;
2716 }
2717 case 'D': {
2718 forth.emplace_back(forth.back().first, forth.back().second - 1);
2719 break;
2720 }
2721 case 'L': {
2722 forth.emplace_back(forth.back().first - 1, forth.back().second);
2723 break;
2724 }
2725 case 'R': {
2726 forth.emplace_back(forth.back().first + 1, forth.back().second);
2727 break;
2728 }
2729 }
2730 }
2731 cin >> a >> b;
2732 if(forth.back().first == a && forth.back().second == b) {
2733 cout << 0;
2734 return 0;
2735 }
2736 if(n < abs(a) + abs(b) || (n - (abs(a) + abs(b))) % 2 != 0) {
2737 cout << -1;
2738 return 0;
2739 }
2740 back.emplace_back(a, b);
2741 for(int i = n - 1; i >= 0; i--) {
2742 switch(ops[i]) {
2743 case 'U': {
2744 back.emplace_back(back.back().first, back.back().second - 1);
2745 break;
2746 }
2747 case 'D': {
2748 back.emplace_back(back.back().first, back.back().second + 1);
2749 break;
2750 }
2751 case 'L': {
2752 back.emplace_back(back.back().first + 1, back.back().second);
2753 break;
2754 }
2755 case 'R': {
2756 back.emplace_back(back.back().first - 1, back.back().second);
2757 break;
2758 }
2759 }
2760 }
2761 back = vector(back.rbegin(), back.rend());
2762 int l = 1;
2763 int r = n;
2764 while(l < r) {
2765 const int mid = (l + r) / 2;
2766 if(check(mid)) {
2767 r = mid;
2768 } else {
2769 l = mid + 1;
2770 }
2771 }
2772 cout << l;
2773 return 0;
2774 }
2775
2776 bool acwing4217::check(int len) const {
2777 for(int i = 0; i + len < n + 1; i++) {
2778 const auto s = forth[i];
2779 const auto e = back[i + len];
2780 const auto dist = abs(s.first - e.first) + abs(s.second - e.second);
2781 if(len - dist >= 0 && (len - dist) % 2 == 0) {
2782 return true;
2783 }
2784 }
2785 return false;
2786 }
2787
2788 int acwing738::main(istream &cin, ostream &cout) {
2789 unsigned int v;
2790 cin >> v;
2791 for(int i = 0; i < 10; i++) {
2792 cout << "N[" << i << "] = " << v * static_cast<unsigned int>(pow(2, i)) << endl;
2793 }
2794 return 0;
2795 }
2796
2797 int acwing741::main(istream &cin, ostream &cout) {
2798 unsigned int t;
2799 unsigned short n;
2800 cin >> t;
2801 unsigned int fib[60];
2802 fib[0] = 0;
2803 fib[1] = 1;
2804 for(int i = 2; i < 60; i++) {
2805 fib[i] = fib[i - 1] + fib[i - 2];
2806 }
2807 for(unsigned i = 0; i < t; i++) {
2808 cin >> n;
2809 cout << "Fib(" << n << ") = " << fib[n] << endl;
2810 }
2811 return 0;
2812 }
2813
2814 int acwing1789::main(istream &cin, ostream &cout) {
2815 char str[52];
2816 int count = 0;
2817 auto poses = vector(26, vector<int>());
2818 for(int i = 0; i < 52; i++) {
2819 char ch;
2820 cin >> ch;
2821 str[i] = ch;
2822 poses[ch - 'A'].push_back(i);
2823 }
2824 for(auto pos: poses) {
2825 auto um = unordered_map<int, int>();
2826 for(int i = pos[0] + 1; i < pos[1]; i++) {
2827 if(!um.contains(str[i])) {
2828 um.insert(pair(str[i], 1));
2829 } else {
2830 um[str[i]] = 0;
2831 }
2832 }
2833 for(const auto p: um) {
2834 if(p.second == 1) {
2835 count++;
2836 }
2837 }
2838 um = unordered_map<int, int>();
2839 for(int i = pos[1] + 1; i < pos[0] + 52; i++) {
2840 if(!um.contains(str[i % 52])) {
2841 um.insert(pair(str[i % 52], 1));
2842 } else {
2843 um[str[i % 52]] = 0;
2844 }
2845 }
2846 for(const auto p: um) {
2847 if(p.second == 1) {
2848 count++;
2849 }
2850 }
2851 }
2852 cout << count / 4;
2853 return 0;
2854 }
2855
2856 int acwing739::main(istream &cin, ostream &cout) {
2857 double a;
2858 cout << setiosflags(ios::fixed) << setprecision(1);
2859 for(int i = 0; i < 100; i++) {
2860 cin >> a;
2861 if(a <= 10) {
2862 cout << "A[" << i << "] = " << a << endl;
2863 }
2864 }
2865 return 0;
2866 }
2867
2868 int acwing742::main(istream &cin, ostream &cout) {
2869 unsigned short n;
2870 cin >> n;
2871 unsigned short minimum_i = 0;
2872 short minimum = 1000;
2873 short x;
2874 for(unsigned short i = 0; i < n; i++) {
2875 cin >> x;
2876 if(minimum > x) {
2877 minimum = x;
2878 minimum_i = i;
2879 }
2880 }
2881 cout << "Minimum value: " << minimum << endl
2882 << "Position: " << minimum_i;
2883 return 0;
2884 }
2885
2886 int acwing1776::main(istream &cin, ostream &cout) {
2887 int n;
2888 int m;
2889 cin >> n >> m;
2890 char ch;
2891 auto *dot = new int[m];
2892 memset(dot, 0, m * sizeof(int));
2893 auto *normal = new int[m];
2894 memset(normal, 0, m * sizeof(int));
2895 for(int i = 0; i < n; i++) {
2896 for(int j = 0; j < m; j++) {
2897 cin >> ch;
2898 dot[j] |= 1 << ch - 'A';
2899 }
2900 }
2901 for(int i = 0; i < n; i++) {
2902 for(int j = 0; j < m; j++) {
2903 cin >> ch;
2904 normal[j] |= 1 << ch - 'A';
2905 }
2906 }
2907 int count = 0;
2908 for(int i = 0; i < m; i++) {
2909 if((dot[i] & normal[i]) == 0) {
2910 count++;
2911 }
2912 }
2913 cout << count;
2914 delete[] normal;
2915 delete[] dot;
2916 return 0;
2917 }
2918
2919 int acwing743::main(istream &cin, ostream &cout) {
2920 int l;
2921 char op;
2922 double m[12][12];
2923 cin >> l >> op;
2924 for(auto &i: m) {
2925 for(auto &j: i) {
2926 cin >> j;
2927 }
2928 }
2929 double ans = 0;
2930 for(int j = 0; j < 12; j++) {
2931 ans += m[l][j];
2932 }
2933 if(op == 'M') {
2934 ans /= 12;
2935 }
2936 cout << fixed << setprecision(1) << ans;
2937 return 0;
2938 }
2939
2940 int acwing744::main(istream &cin, ostream &cout) {
2941 int l;
2942 char op;
2943 double m[12][12];
2944 cin >> l >> op;
2945 for(auto &i: m) {
2946 for(auto &j: i) {
2947 cin >> j;
2948 }
2949 }
2950 double ans = 0;
2951 for(const auto &j: m) {
2952 ans += j[l];
2953 }
2954 if(op == 'M') {
2955 ans /= 12;
2956 }
2957 cout << fixed << setprecision(1) << ans;
2958 return 0;
2959 }
2960
2961 int acwing745::main(istream &cin, ostream &cout) {
2962 char op;
2963 cin >> op;
2964 double sum = 0;
2965 int count = 0;
2966 double m[12][12];
2967 for(int i = 0; i < 12; i++) {
2968 for(int j = 0; j < 12; j++) {
2969 cin >> m[i][j];
2970 if(j > i) {
2971 sum += m[i][j];
2972 count++;
2973 }
2974 }
2975 }
2976 if(op == 'M') {
2977 sum /= count;
2978 }
2979 cout << fixed << setprecision(1) << sum;
2980 return 0;
2981 }
2982
2983 int acwing748::main(istream &cin, ostream &cout) {
2984 char op;
2985 cin >> op;
2986 double sum = 0;
2987 int count = 0;
2988 double m[12][12];
2989 for(int i = 0; i < 12; i++) {
2990 for(int j = 0; j < 12; j++) {
2991 cin >> m[i][j];
2992 if(i + j >= 12) {
2993 sum += m[i][j];
2994 count++;
2995 }
2996 }
2997 }
2998 if(op == 'M') {
2999 sum /= count;
3000 }
3001 cout << fixed << setprecision(1) << sum;
3002 return 0;
3003 }
3004
3005 int acwing1762::main(istream &cin, ostream &cout) {
3006 int n;
3007 cin >> n;
3008 auto *a = new int[n + 1];
3009 auto *id = new string[n + 1];
3010 for(int i = 1; i <= n; i++) {
3011 cin >> a[i];
3012 }
3013 for(int i = 1; i <= n; i++) {
3014 cin >> id[i];
3015 }
3016 for(int i = 1; i <= n; i++) {
3017 cout << id[a[a[a[i]]]] << endl;
3018 }
3019 delete[] a;
3020 delete[] id;
3021 return 0;
3022 }
3023
3024 int acwing1750::main(istream &cin, ostream &cout) {
3025 int n;
3026 cin >> n;
3027 auto start = unordered_set<int>();
3028 auto end = unordered_set<int>();
3029 auto t = vector<pair<int, int>>();
3030 auto levels = vector<int>();
3031 levels.resize(1000);
3032 for(int i = 0; i < n; i++) {
3033 int t1;
3034 int t2;
3035 cin >> t1 >> t2;
3036 start.insert(t1);
3037 end.insert(t2);
3038 t.emplace_back(make_pair(t1, t2));
3039 }
3040 int level = 0;
3041 int maximum = 0;
3042 for(int i = 0; i < 1000; i++) {
3043 if(start.count(i) == 1) {
3044 level++;
3045 }
3046 if(end.count(i) == 1) {
3047 level--;
3048 }
3049 levels[i] = level;
3050 if(level > 0) {
3051 maximum++;
3052 }
3053 }
3054 int ans = 0;
3055 for(auto [t1, t2]: t) {
3056 int len = maximum;
3057 for(int i = t1; i < t2; i++) {
3058 if(levels[i] == 1) {
3059 len--;
3060 }
3061 }
3062 ans = max(ans, len);
3063 }
3064 cout << ans;
3065 return 0;
3066 }
3067
3068 int acwing747::main(istream &cin, ostream &cout) {
3069 char op;
3070 cin >> op;
3071 double sum = 0;
3072 int count = 0;
3073 double m[12][12];
3074 for(int i = 0; i < 12; i++) {
3075 for(int j = 0; j < 12; j++) {
3076 cin >> m[i][j];
3077 if(i + j < 11) {
3078 sum += m[i][j];
3079 count++;
3080 }
3081 }
3082 }
3083 if(op == 'M') {
3084 sum /= count;
3085 }
3086 cout << fixed << setprecision(1) << sum;
3087 return 0;
3088 }
3089
3090 int acwing746::main(istream &cin, ostream &cout) {
3091 char op;
3092 cin >> op;
3093 double sum = 0;
3094 int count = 0;
3095 double m[12][12];
3096 for(int i = 0; i < 12; i++) {
3097 for(int j = 0; j < 12; j++) {
3098 cin >> m[i][j];
3099 if(j < i) {
3100 sum += m[i][j];
3101 count++;
3102 }
3103 }
3104 }
3105 if(op == 'M') {
3106 sum /= count;
3107 }
3108 cout << fixed << setprecision(1) << sum;
3109 return 0;
3110 }
3111
3112 int acwing1738::main(istream &cin, ostream &cout) {
3113 int n;
3114 cin >> n;
3115 if(n == 1 || n == 2) {
3116 cout << 1;
3117 return 0;
3118 }
3119 auto *x = new int[n];
3120 auto *jmp = new int[n];
3121 auto *in = new int[n];
3122 memset(in, 0, n * sizeof(int));
3123 for(int i = 0; i < n; i++) {
3124 cin >> x[i];
3125 }
3126 sort(x, x + n);
3127 in[1] = 1;
3128 in[n - 2] = 1;
3129 jmp[0] = 1;
3130 jmp[n - 1] = n - 2;
3131 for(int i = 1; i < n - 1; i++) {
3132 if(x[i + 1] - x[i] < x[i] - x[i - 1]) {
3133 in[i + 1]++;
3134 jmp[i] = i + 1;
3135 } else {
3136 in[i - 1]++;
3137 jmp[i] = i - 1;
3138 }
3139 }
3140 int circle_count = 0;
3141 int ans = 0;
3142 for(int i = 0; i < n; i++) {
3143 if(in[i] == 0) {
3144 ans++;
3145 }
3146 if(jmp[jmp[i]] == i && in[i] == 1 && in[jmp[i]] == 1) {
3147 circle_count++;
3148 }
3149 }
3150 circle_count /= 2;
3151 cout << ans + circle_count;
3152 delete[] x;
3153 delete[] in;
3154 delete[] jmp;
3155 return 0;
3156 }
3157
3158 int acwing4296::main(istream &cin, ostream &cout) {
3159 int n;
3160 int a;
3161 int b;
3162 cin >> n >> a >> b;
3163 for(int i = 0; a * i <= n; i++) {
3164 for(int j = 0; a * i + b * j <= n; j++) {
3165 if(a * i + b * j == n) {
3166 cout << "YES" << endl
3167 << i << endl
3168 << j;
3169 return 0;
3170 }
3171 }
3172 }
3173 cout << "NO";
3174 return 0;
3175 }
3176
3177 int acwing4297::main(istream &cin, ostream &cout) {
3178 int n;
3179 cin >> n;
3180 unsigned int d[200000];
3181 unsigned long long left[200001];
3182 unsigned long long right[200001];
3183 for(int i = 0; i < n; i++) {
3184 cin >> d[i];
3185 }
3186 left[0] = 0;
3187 auto us = unordered_map<unsigned long long, unsigned int>();
3188 us.insert(make_pair(0, 0));
3189 for(int i = 1; i <= n; i++) {
3190 left[i] = left[i - 1] + d[i - 1];
3191 us.insert(make_pair(left[i], i));
3192 }
3193 right[n] = 0;
3194 unsigned long long ans = 0;
3195 for(int i = n - 1; i >= 0; i--) {
3196 right[i] = right[i + 1] + d[i];
3197 if(us.count(right[i]) == 1) {
3198 if(us[right[i]] <= i) {
3199 ans = max(ans, right[i]);
3200 }
3201 }
3202 }
3203 cout << ans;
3204 return 0;
3205 }
3206
3207 int acwing4298::main(istream &cin, ostream &cout) {
3208 cin >> n;
3209 a = new int[n];
3210 memset(a, 0, n * sizeof(int));
3211 for(int i = 0; i < n; i++) {
3212 cin >> a[i];
3213 }
3214 cin >> m;
3215 b = new int[m];
3216 found = new bool[m];
3217 match = new int[m];
3218 memset(b, 0, m * sizeof(int));
3219 memset(found, 0, m * sizeof(bool));
3220 memset(match, -1, m * sizeof(int));
3221 for(int i = 0; i < m; i++) {
3222 cin >> b[i];
3223 }
3224 connected = new bool *[n];
3225 for(int i = 0; i < n; i++) {
3226 connected[i] = new bool[m];
3227 for(int j = 0; j < m; j++) {
3228 if(abs(a[i] - b[j]) <= 1) {
3229 connected[i][j] = true;
3230 } else {
3231 connected[i][j] = false;
3232 }
3233 }
3234 }
3235
3236 int ans = 0;
3237 for(int i = 0; i < n; i++) {
3238 memset(found, 0, m * sizeof(bool));
3239 if(find(i)) {
3240 ans++;
3241 }
3242 }
3243 cout << ans;
3244 for(int i = 0; i < n; i++) {
3245 delete[] connected[i];
3246 }
3247 delete[] connected;
3248 delete[] a;
3249 delete[] b;
3250 delete[] found;
3251 delete[] match;
3252 return 0;
3253 }
3254
3255 bool acwing4298::find(int i) {
3256 for(int j = 0; j < m; j++) {
3257 if(connected[i][j] && !found[j]) {
3258 //可以配对且女孩未被找到
3259 found[j] = true;
3260 if(match[j] == -1 || find(match[j])) {
3261 //女孩没有配对的对象或女孩配对的对象可以找到其他对象去配对
3262 match[j] = i;//设置女孩j和男孩i配对
3263 return true;
3264 }
3265 }
3266 }
3267 return false;
3268 }
3269
3270 int acwing749::main(istream &cin, ostream &cout) {
3271 char op;
3272 cin >> op;
3273 double sum = 0;
3274 int count = 0;
3275 double m[12][12];
3276 for(int i = 0; i < 12; i++) {
3277 for(int j = 0; j < 12; j++) {
3278 cin >> m[i][j];
3279 if(j > i && i + j < 11) {
3280 sum += m[i][j];
3281 count++;
3282 }
3283 }
3284 }
3285 if(op == 'M') {
3286 sum /= count;
3287 }
3288 cout << fixed << setprecision(1) << sum;
3289 return 0;
3290 }
3291
3292 int acwing750::main(istream &cin, ostream &cout) {
3293 char op;
3294 cin >> op;
3295 double sum = 0;
3296 int count = 0;
3297 double m[12][12];
3298 for(int i = 0; i < 12; i++) {
3299 for(int j = 0; j < 12; j++) {
3300 cin >> m[i][j];
3301 if(i + j > 11 && i > j) {
3302 sum += m[i][j];
3303 count++;
3304 }
3305 }
3306 }
3307 if(op == 'M') {
3308 sum /= count;
3309 }
3310 cout << fixed << setprecision(1) << sum;
3311 return 0;
3312 }
3313
3314 int acwing751::main(istream &cin, ostream &cout) {
3315 char op;
3316 cin >> op;
3317 double sum = 0;
3318 int count = 0;
3319 double m[12][12];
3320 for(int i = 0; i < 12; i++) {
3321 for(int j = 0; j < 12; j++) {
3322 cin >> m[i][j];
3323 if(i + j < 11 && i > j) {
3324 sum += m[i][j];
3325 count++;
3326 }
3327 }
3328 }
3329 if(op == 'M') {
3330 sum /= count;
3331 }
3332 cout << fixed << setprecision(1) << sum;
3333 return 0;
3334 }
3335
3336 int acwing752::main(istream &cin, ostream &cout) {
3337 char op;
3338 cin >> op;
3339 double sum = 0;
3340 int count = 0;
3341 double m[12][12];
3342 for(int i = 0; i < 12; i++) {
3343 for(int j = 0; j < 12; j++) {
3344 cin >> m[i][j];
3345 if(i + j > 11 && i < j) {
3346 sum += m[i][j];
3347 count++;
3348 }
3349 }
3350 }
3351 if(op == 'M') {
3352 sum /= count;
3353 }
3354 cout << fixed << setprecision(1) << sum;
3355 return 0;
3356 }
3357
3358 int acwing1726::main(istream &cin, ostream &cout) {
3359 int N;
3360 int M;
3361 int K;
3362 cin >> N >> M >> K;
3363 unordered_set<int> ms;
3364 auto *const m = new int[M];
3365 auto *const n = new int[N + 1];
3366 memset(n, -1, (N + 1) * sizeof(int));
3367 for(int i = 0; i < M; i++) {
3368 cin >> m[i];
3369 ms.insert(m[i]);
3370 }
3371 auto cp = unordered_map<int, int>();
3372 for(int i = 0; i < K; i++) {
3373 int c;
3374 int p;
3375 cin >> c >> p;
3376 n[p] = c;
3377 cp.insert(make_pair(c, p));
3378 }
3379 if(cp.contains(1)) {
3380 //固定
3381 cout << cp[1];
3382 delete[] n;
3383 delete[] m;
3384 return 0;
3385 }
3386 if(ms.contains(1)) {
3387 //在阶级中
3388 int current = 1;
3389 for(int i = 0; i < M; i++) {
3390 //对所有阶级
3391 if(cp.contains(m[i])) {
3392 //是固定的
3393 current = cp[m[i]];
3394 continue;
3395 }
3396 //不是固定的
3397 while(n[current] != -1) {
3398 current++;
3399 }
3400 n[current] = m[i];
3401 if(m[i] == 1) {
3402 cout << current;
3403 delete[] n;
3404 delete[] m;
3405 return 0;
3406 }
3407 }
3408 }
3409 //不在阶级中
3410 int current = N;
3411 for(int i = M - 1; i >= 0; i--) {
3412 if(cp.contains(m[i])) {
3413 //是固定的
3414 current = cp[m[i]];
3415 continue;
3416 }
3417 //不是固定的
3418 while(n[current] != -1) {
3419 current--;
3420 }
3421 n[current] = m[i];
3422 }
3423 for(int i = 1; i <= N; i++) {
3424 if(n[i] == -1) {
3425 cout << i;
3426 break;
3427 }
3428 }
3429 delete[] n;
3430 delete[] m;
3431 return 0;
3432 }
3433
3434 int acwing753::main(istream &cin, ostream &cout) {
3435 int n;
3436 while(true) {
3437 cin >> n;
3438 if(n == 0) {
3439 break;
3440 }
3441 for(int i = 0; i < n; i++) {
3442 for(int j = 0; j < n; j++) {
3443 cout << min(min(i, j), min(n - i - 1, n - j - 1)) + 1 << " ";
3444 }
3445 cout << endl;
3446 }
3447 cout << endl;
3448 }
3449 return 0;
3450 }
3451
3452 int acwing754::main(istream &cin, ostream &cout) {
3453 int n;
3454 while(true) {
3455 cin >> n;
3456 if(n == 0) {
3457 break;
3458 }
3459 for(int i = 0; i < n; i++) {
3460 for(int j = 0; j < n; j++) {
3461 cout << abs(j - i) + 1 << " ";
3462 }
3463 cout << endl;
3464 }
3465 cout << endl;
3466 }
3467 return 0;
3468 }
3469
3470 int acwing1715::main(istream &cin, ostream &cout) {
3471 int n;
3472 cin >> n;
3473 auto sb = unordered_map<int, int>();
3474 auto tb = unordered_map<int, int>();
3475 for(int i = 0; i < n; i++) {
3476 int s;
3477 int t;
3478 int b;
3479 cin >> s >> t >> b;
3480 sb.insert(make_pair(s, b));
3481 tb.insert(make_pair(t, b));
3482 }
3483 int ans = 0;
3484 int current = 0;
3485 for(int i = 1; i <= 1000; i++) {
3486 if(sb.count(i) == 1) {
3487 current += sb[i];
3488 } else if(tb.count(i) == 1) {
3489 current -= tb[i];
3490 }
3491 ans = max(ans, current);
3492 }
3493 cout << ans;
3494 return 0;
3495 }
3496
3497 int acwing755::main(istream &cin, ostream &cout) {
3498 int n;
3499 while(true) {
3500 cin >> n;
3501 if(n == 0) {
3502 break;
3503 }
3504 for(int i = 0; i < n; i++) {
3505 for(int j = 0; j < n; j++) {
3506 cout << static_cast<int>(pow(2, i + j)) << " ";
3507 }
3508 cout << endl;
3509 }
3510 cout << endl;
3511 }
3512 return 0;
3513 }
3514
3515 int acwing756::main(istream &cin, ostream &cout) {
3516 int n;
3517 int m;
3518 int arr[100][100] = {};
3519 int x = 0;
3520 int y = 0;
3521 int v = 1;
3522 int dir = 1;//0 上 1 右 2 下 3 左
3523 cin >> n >> m;
3524 while(v <= n * m) {
3525 arr[x][y] = v++;
3526 move:;
3527 if(v > m * n) {
3528 break;
3529 }
3530 switch(dir) {
3531 case 3://左
3532 {
3533 const int next_y = y - 1;
3534 if(arr[x][next_y] != 0 || next_y < 0) {
3535 //不能向上
3536 dir = (dir + 1) % 4;
3537 goto move;
3538 }
3539 y--;
3540 break;
3541 }
3542 case 2://下
3543 {
3544 const int next_x = x + 1;
3545 if(arr[next_x][y] != 0 || next_x >= n) {
3546 dir = (dir + 1) % 4;
3547 goto move;
3548 }
3549 x++;
3550 break;
3551 }
3552 case 1://右
3553 {
3554 const int next_y = y + 1;
3555 if(arr[x][next_y] != 0 || next_y >= m) {
3556 dir = (dir + 1) % 4;
3557 goto move;
3558 }
3559 y++;
3560 break;
3561 }
3562 case 0://上
3563 {
3564 const int next_x = x - 1;
3565 if(arr[next_x][y] != 0 || next_x < 0) {
3566 dir = (dir + 1) % 4;
3567 goto move;
3568 }
3569 x--;
3570 break;
3571 }
3572 }
3573 }
3574 for(int i = 0; i < n; i++) {
3575 for(int j = 0; j < m; j++) {
3576 cout << arr[i][j] << " ";
3577 }
3578 cout << endl;
3579 }
3580 return 0;
3581 }
3582
3583 int acwing1696::main(istream &cin, ostream &cout) {
3584 int n;
3585 cin >> n;
3586 auto *const p = new int[n];
3587 for(int i = 0; i < n; i++) {
3588 cin >> p[i];
3589 }
3590 int i = n - 1;
3591 for(int j = i - 1; j >= 0 && p[j] < p[i]; i--, j--) {}
3592 cout << i;
3593 delete[] p;
3594 return 0;
3595 }
3596
3597 int acwing760::main(istream &cin, ostream &cout) {
3598 auto *str = new char[101];
3599 cin.getline(str, 101);
3600 for(int i = 0; i < 101; i++) {
3601 if(str[i] == '\0') {
3602 cout << i;
3603 break;
3604 }
3605 }
3606 return 0;
3607 }
3608
3609 int acwing762::main(istream &cin, ostream &cout) {
3610 double k;
3611 string a;
3612 string b;
3613 int match = 0;
3614 cin >> k >> a >> b;
3615 for(int i = 0; i < a.length(); i++) {
3616 if(a[i] == b[i]) {
3617 match++;
3618 }
3619 }
3620 cout << (match >= k * a.length() ? "yes" : "no");
3621 return 0;
3622 }
3623
3624 int acwing1684::main(istream &cin, ostream &cout) {
3625 int n;
3626 int m;
3627 cin >> n >> m;
3628 bitset<151> ns[101] = {};
3629 bitset<151> ans[4] = {};
3630 for(int i = 1; i <= m; i++) {
3631 int m1;
3632 int m2;
3633 cin >> m1 >> m2;
3634 ns[m1].set(i);
3635 ns[m2].set(i);
3636 }
3637 for(int i = 1; i <= n; i++) {
3638 for(int j = 0; j < 4; j++) {
3639 if((ns[i] & ans[j]) == 0) {
3640 cout << j + 1;
3641 ans[j] |= ns[i];
3642 break;
3643 }
3644 }
3645 }
3646 return 0;
3647 }
3648
3649 int acwing761::main(istream &cin, ostream &cout) {
3650 auto *str = new char[101];
3651 cin.getline(str, 101);
3652 unsigned short ans = 0;
3653 for(unsigned short i = 0; str[i] != '\0'; i++) {
3654 if(isdigit(str[i]) != 0) {
3655 ans++;
3656 }
3657 }
3658 cout << ans;
3659 delete[] str;
3660 return 0;
3661 }
3662
3663 int acwing768::main(istream &cin, ostream &cout) {
3664 auto *a = new char[81];
3665 auto *b = new char[81];
3666 cin.getline(a, 81);
3667 cin.getline(b, 81);
3668 for(int i = 0;; i++) {
3669 if(isupper(a[i]) != 0) {
3670 a[i] = tolower(a[i]);
3671 }
3672 if(isupper(b[i]) != 0) {
3673 b[i] = tolower(b[i]);
3674 }
3675 if(a[i] == '\0' && b[i] == '\0') {
3676 cout << '=';
3677 break;
3678 }
3679 if(a[i] < b[i]) {
3680 cout << '<';
3681 break;
3682 }
3683 if(a[i] > b[i]) {
3684 cout << '>';
3685 break;
3686 }
3687 }
3688 delete[] a;
3689 delete[] b;
3690 return 0;
3691 }
3692
3693 int acwing1471::main(istream &cin, ostream &cout) {
3694 int n;
3695 cin >> n;
3696 auto *in = new int[n];
3697 auto *out = new int[n];
3698 memset(in, 0, n * sizeof(int));
3699 memset(out, 0, n * sizeof(int));
3700 int a;
3701 int b;
3702 for(int i = 0; i < n - 1; i++) {
3703 cin >> a >> b;
3704 out[a - 1]++;
3705 in[b - 1]++;
3706 }
3707 bool ok = true;
3708 int ans = -1;
3709 for(int i = 0; i < n; i++) {
3710 if(in[i] > 0 && out[i] == 0) {
3711 if(ans != -1) {
3712 ok = false;
3713 break;
3714 }
3715 ans = i;
3716 }
3717 if(in[i] == 0 && out[i] > 1) {
3718 ok = false;
3719 break;
3720 }
3721 }
3722 if(ok) {
3723 cout << ans + 1;
3724 } else {
3725 cout << -1;
3726 }
3727 delete[] in;
3728 delete[] out;
3729 return 0;
3730 }
3731
3732 int acwing763::main(istream &cin, ostream &cout) {
3733 int t;
3734 cin >> t;
3735 for(int i = 0; i < t; i++) {
3736 string str1;
3737 string str2;
3738 cin >> str1 >> str2;
3739 if(str1 == str2) {
3740 cout << "Tie";
3741 } else if(str1 == "Hunter" && str2 == "Gun" || str1 == "Gun" && str2 == "Bear" || str1 == "Bear" && str2 == "Hunter") {
3742 cout << "Player1";
3743 } else {
3744 cout << "Player2";
3745 }
3746 cout << endl;
3747 }
3748 return 0;
3749 }
3750
3751 int acwing766::main(istream &cin, ostream &cout) {
3752 auto *str = new char[201];
3753 cin.getline(str, 201);
3754 bool flag = false;
3755 for(int i = 0; str[i] != '\0'; i++) {
3756 if(str[i] != ' ') {
3757 cout << str[i];
3758 flag = false;
3759 } else if(!flag) {
3760 cout << ' ';
3761 flag = true;
3762 }
3763 }
3764 return 0;
3765 }
3766
3767 int acwing1460::main(istream &cin, ostream &cout) {
3768 int n;
3769 cin >> n;
3770 string str;
3771 cin >> str;
3772 for(int k = 1; k <= n; k++) {
3773 auto us = unordered_set<string>();
3774 bool ok = true;
3775 for(int i = 0; i + k <= n; i++) {
3776 string nstr = str.substr(i, k);
3777 if(!us.contains(nstr)) {
3778 us.insert(nstr);
3779 } else {
3780 ok = false;
3781 break;
3782 }
3783 }
3784 if(ok) {
3785 cout << k;
3786 break;
3787 }
3788 }
3789 return 0;
3790 }
3791
3792 int acwing4299::main(istream &cin, ostream &cout) {
3793 int n;
3794 cin >> n;
3795 int pos = 0;
3796 int neg = 0;
3797 for(int i = 0; i < n; i++) {
3798 int x;
3799 int y;
3800 cin >> x >> y;
3801 if(x > 0) {
3802 pos++;
3803 } else {
3804 neg++;
3805 }
3806 }
3807 if(pos <= 1 || neg <= 1) {
3808 cout << "Yes";
3809 } else {
3810 cout << "No";
3811 }
3812 return 0;
3813 }
3814
3815 int acwing4300::main(istream &cin, ostream &cout) {
3816 int n;
3817 int m;
3818 cin >> n >> m;
3819 auto um = unordered_set<int>();
3820 auto que = queue<pair<int, int>>();
3821 que.push(make_pair(n, 0));
3822 um.insert(n);
3823 while(!que.empty()) {
3824 auto [current, step] = que.front();
3825 que.pop();
3826 if(current == m) {
3827 cout << step;
3828 return 0;
3829 }
3830 int k = 1;
3831 const int nexts[2] = {current - 1, current * 2};
3832 if(current < m) {
3833 k = 2;
3834 }
3835 for(int i = 0; i < k; i++) {
3836 auto next = nexts[i];
3837 if(next == m) {
3838 cout << step + 1;
3839 return 0;
3840 }
3841 if(next > 0 && !um.contains(next)) {
3842 que.push(make_pair(next, step + 1));
3843 um.insert(next);
3844 }
3845 }
3846 }
3847 return 0;
3848 }
3849
3850 int acwing4301::main(istream &cin, ostream &cout) {
3851 int n;
3852 cin >> n;
3853 auto vec = vector<int>();
3854 auto targets = unordered_set<int>();
3855 int sum = 0;
3856 int maximum = 0;
3857 char ch;
3858 vec.resize(n);
3859 for(int i = 0; i < n; i++) {
3860 cin >> ch;
3861 int a = ch - '0';
3862 vec[i] = a;
3863 sum += a;
3864 maximum = max(maximum, a);
3865 }
3866 if(sum == 0) {
3867 cout << "YES";
3868 return 0;
3869 }
3870 for(int i = maximum; i <= sum / 2; i++) {
3871 if(sum % i == 0) {
3872 targets.insert(i);
3873 }
3874 }
3875 for(const auto target: targets) {
3876 int current = 0;
3877 bool ok = true;
3878 for(int i = 0; i < n; i++) {
3879 current += vec[i];
3880 if(current == target) {
3881 current = 0;
3882 } else if(current > target) {
3883 ok = false;
3884 break;
3885 }
3886 }
3887 if(ok && current == 0) {
3888 cout << "YES";
3889 return 0;
3890 }
3891 }
3892 cout << "NO";
3893 return 0;
3894 }
3895
3896 int acwing765::main(istream &cin, ostream &cout) {
3897 auto *str = new char[101];
3898 cin.getline(str, 101);
3899 for(int i = 0; str[i] != '\0'; i++) {
3900 cout << str[i] << " ";
3901 }
3902 delete[] str;
3903 return 0;
3904 }
3905
3906 int acwing767::main(istream &cin, ostream &cout) {
3907 auto *str = new char[101];
3908 cin.getline(str, 101);
3909 for(int i = 0; str[i] != '\0'; i++) {
3910 if(isupper(str[i]) != 0) {
3911 str[i] = (str[i] - 'A' + 1) % 26 + 'A';
3912 } else if(islower(str[i]) != 0) {
3913 str[i] = (str[i] - 'a' + 1) % 26 + 'a';
3914 }
3915 cout << str[i];
3916 }
3917 delete[] str;
3918 return 0;
3919 }
3920
3921 int acwing769::main(istream &cin, ostream &cout) {
3922 string str;
3923 cin >> str;
3924 char ch;
3925 cin >> ch;
3926 for(char c: str) {
3927 if(c == ch) {
3928 c = '#';
3929 }
3930 cout << c;
3931 }
3932 return 0;
3933 }
3934
3935 int acwing764::main(istream &cin, ostream &cout) {
3936 auto *a = new char[101];
3937 cin.getline(a, 101);
3938 const int len = strlen(a);
3939 for(int i = 1; i <= len; i++) {
3940 cout << static_cast<char>(a[(i - 1) % len] + a[i % len]);
3941 }
3942 delete[] a;
3943 return 0;
3944 }
3945
3946 int acwing1443::main(istream &cin, ostream &cout) {
3947 int n;
3948 cin >> n;
3949 auto *a = new int[n];
3950 auto *b = new int[n - 1];
3951 for(int i = 0; i < n - 1; i++) {
3952 cin >> b[i];
3953 }
3954 for(int i = 1; i <= n; i++) {
3955 auto us = unordered_set<int>();
3956 bool flag = true;
3957 a[0] = i;
3958 for(int j = 1; j < n; j++) {
3959 a[j] = b[j - 1] - a[j - 1];
3960 if(us.contains(a[j]) || a[j] <= 0) {
3961 flag = false;
3962 break;
3963 }
3964 us.insert(a[j]);
3965
3966 us.insert(a[j]);
3967 }
3968 if(flag) {
3969 for(int j = 0; j < n; j++) {
3970 cout << a[j] << " ";
3971 }
3972 break;
3973 }
3974 }
3975 delete[] b;
3976 delete[] a;
3977 return 0;
3978 }
3979
3980 int acwing773::main(istream &cin, ostream &cout) {
3981 string str;
3982 string substr;
3983 while(cin >> str) {
3984 cin >> substr;
3985 auto oss = ostringstream();
3986 int max_i = 0;
3987 for(int i = 0; i < str.length(); i++) {
3988 if(str[i] > str[max_i]) {
3989 max_i = i;
3990 }
3991 }
3992 oss << str.substr(0, max_i + 1);
3993 oss << substr;
3994 oss << str.substr(max_i + 1);
3995 cout << oss.str() << endl;
3996 }
3997 return 0;
3998 }
3999
4000 int acwing770::main(istream &cin, ostream &cout) {
4001 auto *str = new char[101];
4002 auto *to_be_replaced = new char[101];
4003 auto *replacement = new char[101];
4004 cin.getline(str, 101);
4005 cin.getline(to_be_replaced, 101);
4006 cin.getline(replacement, 101);
4007 for(const char *word = strtok(str, " "); word != nullptr; word = strtok(nullptr, " ")) {
4008 if(strcmp(word, to_be_replaced) == 0) {
4009 cout.write(replacement, strlen(replacement));
4010 } else {
4011 cout.write(word, strlen(word));
4012 }
4013 cout << " ";
4014 }
4015 delete[] str;
4016 delete[] to_be_replaced;
4017 delete[] replacement;
4018 return 0;
4019 }
4020
4021 int acwing1672::main(istream &cin, ostream &cout) {
4022 int n;
4023 cin >> n;
4024 string a;
4025 string b;
4026 cin >> a >> b;
4027 bool prev_eq = true;
4028 int ans = 0;
4029 for(int i = 0; i < n; i++) {
4030 if(a[i] == b[i]) {
4031 if(!prev_eq) {
4032 ans++;
4033 }
4034 prev_eq = true;
4035 } else {
4036 prev_eq = false;
4037 }
4038 }
4039 if(!prev_eq) {
4040 ans++;
4041 }
4042 cout << ans;
4043 return 0;
4044 }
4045
4046 int acwing772::main(istream &cin, ostream &cout) {
4047 string str;
4048 cin >> str;
4049 int charset[26] = {};
4050 for(const char ch: str) {
4051 charset[ch - 'a']++;
4052 }
4053 for(const char ch: str) {
4054 if(charset[ch - 'a'] == 1) {
4055 cout << ch;
4056 return 0;
4057 }
4058 }
4059 cout << "no";
4060 return 0;
4061 }
4062
4063 int acwing771::main(istream &cin, ostream &cout) {
4064 int n;
4065 cin >> n;
4066 for(int i = 0; i < n; i++) {
4067 string str;
4068 cin >> str;
4069 char ch_max = str[0];
4070 int count_max = 1;
4071 char ch = str[0];
4072 int count = 1;
4073 for(int j = 1; j < str.length(); j++) {
4074 if(str[j] == str[j - 1]) {
4075 count++;
4076 } else {
4077 if(count > count_max) {
4078 count_max = count;
4079 ch_max = ch;
4080 }
4081 ch = str[j];
4082 count = 1;
4083 }
4084 }
4085 if(count > count_max) {
4086 count_max = count;
4087 ch_max = ch;
4088 }
4089 cout << ch_max << " " << count_max << endl;
4090 }
4091 return 0;
4092 }
4093
4094 namespace acwing1660 {
4095 int acwing1660::main(istream &cin, ostream &cout) {
4096 int n;
4097 cin >> n;
4098 auto cows = vector<cow>();
4099 for(int i = 0; i < n; i++) {
4100 int x;
4101 bool infected;
4102 cin >> x >> infected;
4103 cows.push_back(cow{x, infected});
4104 }
4105 sort(cows.begin(), cows.end());
4106 int r = 1000000;
4107 for(int i = 0; i < n; i++) {
4108 if(i - 1 >= 0 && cows[i].infected != cows[i - 1].infected) {
4109 r = min(r, abs(cows[i].x - cows[i - 1].x));
4110 }
4111 if(i + 1 < n && cows[i].infected != cows[i + 1].infected) {
4112 r = min(r, abs(cows[i].x - cows[i + 1].x));
4113 }
4114 }
4115 for(int i = 0; i + 1 < n; i++) {
4116 if(cows[i].infected && cows[i + 1].infected && abs(cows[i].x - cows[i + 1].x) < r) {
4117 cows[i].infected = false;
4118 }
4119 }
4120 int ans = 0;
4121 for(int i = 0; i < n; i++) {
4122 if(cows[i].infected) {
4123 ans++;
4124 }
4125 }
4126 cout << ans;
4127 return 0;
4128 }
4129
4130 bool cow::operator<(const cow &c) const { return this->x < c.x; }
4131 }// namespace acwing1660
4132
4133 int acwing774::main(istream &cin, ostream &cout) {
4134 auto *str = new char[501];
4135 cin.getline(str, 501);
4136 str[strlen(str) - 1] = '\0';
4137 const char *longest_word = nullptr;
4138 int max_len = 0;
4139 for(const char *word = strtok(str, " "); word != nullptr; word = strtok(nullptr, " ")) {
4140 if(max_len < strlen(word)) {
4141 max_len = strlen(word);
4142 longest_word = word;
4143 }
4144 }
4145 cout << longest_word;
4146 delete[] str;
4147 return 0;
4148 }
4149
4150 int acwing775::main(istream &cin, ostream &cout) {
4151 auto *str = new char[101];
4152 auto *str_rev = new char *[101];
4153 int i = 0;
4154 cin.getline(str, 101);
4155 for(char *word = strtok(str, " "); word != nullptr; word = strtok(nullptr, " ")) {
4156 str_rev[i++] = word;
4157 }
4158 for(int j = i - 1; j >= 0; j--) {
4159 cout << str_rev[j] << " ";
4160 }
4161 delete[] str;
4162 delete[] str_rev;
4163 return 0;
4164 }
4165
4166 int acwing3347::main(istream &cin, ostream &cout) {
4167 int n;
4168 cin >> n;
4169 auto *flowers = new int[n];
4170 auto *prefix_sum = new int[n];
4171 auto location = unordered_map<int, unordered_set<int>>();
4172 int sum = 0;
4173 for(int i = 0; i < n; i++) {
4174 cin >> flowers[i];
4175 sum += flowers[i];
4176 prefix_sum[i] = sum;
4177 location[flowers[i]].insert(i);
4178 }
4179 int ans = 0;
4180 for(int i = 0; i < n; i++) {
4181 for(int j = i; j < n; j++) {
4182 const int len = j - i + 1;
4183 sum = prefix_sum[j] - (i - 1 >= 0 ? prefix_sum[i - 1] : 0);
4184 if(sum % len == 0) {
4185 int avg = sum / len;
4186 for(const auto flower: location[avg]) {
4187 if(i <= flower && flower <= j) {
4188 ans++;
4189 break;
4190 }
4191 }
4192 }
4193 }
4194 }
4195 cout << ans;
4196 delete[] flowers;
4197 delete[] prefix_sum;
4198 return 0;
4199 }
4200
4201 int acwing777::main(istream &cin, ostream &cout) {
4202 string str;
4203 cin >> str;
4204 while(str != ".") {
4205 for(int i = 1; i <= str.length(); i++) {
4206 if(str.length() % i == 0) {
4207 bool ok = true;
4208 string substr = str.substr(0, i);
4209 for(int j = i; j < str.length(); j += i) {
4210 if(str.substr(j, i) != substr) {
4211 ok = false;
4212 break;
4213 }
4214 }
4215 if(ok) {
4216 cout << str.length() / i << endl;
4217 break;
4218 }
4219 }
4220 }
4221 cin >> str;
4222 }
4223 return 0;
4224 }
4225
4226 int acwing776::main(istream &cin, ostream &cout) {
4227 string s1;
4228 string s2;
4229 cin >> s1 >> s2;
4230 const string s11 = s1 + s1;
4231 const string s22 = s2 + s2;
4232 cout << boolalpha << (s11.find(s2) != string::npos || s22.find(s1) != string::npos);
4233 return 0;
4234 }
4235
4236 int acwing4302::main(istream &cin, ostream &cout) {
4237 int sum_b = 0;
4238 int sum_c = 0;
4239 int n;
4240 cin >> n;
4241 for(int i = 0; i < n; i++) {
4242 int a;
4243 cin >> a;
4244 if(a > 0) {
4245 sum_b += a;
4246 } else {
4247 sum_c -= a;
4248 }
4249 }
4250 cout << sum_b + sum_c;
4251 return 0;
4252 }
4253
4254 int acwing4303::main(istream &cin, ostream &cout) {
4255 int q;
4256 cin >> q;
4257 auto um = unordered_map<string, vector<string> *>();
4258 for(int i = 0; i < q; i++) {
4259 string str1;
4260 string str2;
4261 cin >> str1 >> str2;
4262 if(!um.contains(str1)) {
4263 auto *vec = new vector<string>();
4264 vec->push_back(str1);
4265 vec->push_back(str2);
4266 um.insert(make_pair(str2, vec));
4267 } else {
4268 um[str1]->push_back(str2);
4269 um[str2] = um[str1];
4270 um[str1] = nullptr;
4271 }
4272 }
4273 int count = 0;
4274 for(auto [k, v]: um) {
4275 if(v != nullptr) {
4276 count++;
4277 }
4278 }
4279 cout << count << endl;
4280 for(auto [k, v]: um) {
4281 if(v != nullptr) {
4282 cout << *v->begin() << " " << k << endl;
4283 delete v;
4284 }
4285 }
4286 return 0;
4287 }
4288
4289 int acwing4304::main(istream &cin, ostream &cout) {
4290 int n;
4291 cin >> n;
4292 auto vec = vector<unsigned int>();
4293 for(int i = 0; i < n; i++) {
4294 string str;
4295 cin >> str;
4296 auto ui = str2int(str);
4297 bool flag = false;
4298 for(int j = 0; j < vec.size(); j++) {
4299 if((vec[j] & ui) != 0) {
4300 vec[j] |= ui;
4301 flag = true;
4302 }
4303 }
4304 if(!flag) {
4305 vec.push_back(ui);
4306 }
4307 }
4308 bool ok = true;
4309 while(ok) {
4310 ok = false;
4311 for(int i = 0; i + 1 < vec.size(); i++) {
4312 for(int j = i + 1; j < vec.size(); j++) {
4313 if((vec[i] & vec[j]) != 0) {
4314 vec[i] |= vec[j];
4315 vec.erase(vec.begin() + j);
4316 ok = true;
4317 }
4318 }
4319 }
4320 }
4321 cout << vec.size();
4322 return 0;
4323 }
4324
4325 unsigned int acwing4304::str2int(const string &str) {
4326 unsigned int ans = 0;
4327 for(const char ch: str) {
4328 ans |= 1 << ch - 'a';
4329 }
4330 return ans;
4331 }
4332
4333 int acwing778::main(istream &cin, ostream &cout) {
4334 auto *input = new char[323];
4335 auto strs = vector<string>();
4336 cin.getline(input, 323);
4337 for(char *str = strtok(input, ","); str != nullptr; str = strtok(nullptr, ",")) {
4338 strs.emplace_back(str);
4339 }
4340 auto l = strs[0].find(strs[1]);
4341 const auto r = strs[0].rfind(strs[2]);
4342 if(l == string::npos || r == string::npos) {
4343 cout << -1;
4344 return 0;
4345 }
4346 l += strs[1].length();
4347 cout << (static_cast<int>(r) < static_cast<int>(l) ? -1 : static_cast<int>(r) - static_cast<int>(l));
4348 return 0;
4349 }
4350
4351 int acwing779::main(istream &cin, ostream &cout) {
4352 while(true) {
4353 int n;
4354 cin >> n;
4355 if(n == 0) {
4356 break;
4357 }
4358 string suffix;
4359 cin >> suffix;
4360 for(int i = 1; i < n; i++) {
4361 string str;
4362 cin >> str;
4363 if(!suffix.empty()) {
4364 auto ss = stringstream();
4365 for(int j = 0; j < min(str.length(), suffix.length()) && suffix[suffix.length() - 1 - j] == str[str.length() - 1 - j]; j++) {
4366 ss << suffix[suffix.length() - 1 - j];
4367 }
4368 string s = ss.str();
4369 suffix = string(s.rbegin(), s.rend());
4370 }
4371 }
4372 cout << suffix << endl;
4373 }
4374 return 0;
4375 }
4376
4377 int acwing804::fact(int n) {
4378 if(n == 1) {
4379 return 1;
4380 }
4381 return n * fact(n - 1);
4382 }
4383
4384 int acwing804::main(istream &cin, ostream &cout) {
4385 int n;
4386 cin >> n;
4387 cout << fact(n);
4388 return 0;
4389 }
4390
4391 int acwing810::abs(int n) { return n > 0 ? n : -n; }
4392
4393 int acwing810::main(istream &cin, ostream &cout) {
4394 int x;
4395 cin >> x;
4396 cout << abs(x);
4397 return 0;
4398 }
4399
4400 int acwing805::main(istream &cin, ostream &cout) {
4401 int x;
4402 int y;
4403 cin >> x >> y;
4404 cout << max(x, y);
4405 return 0;
4406 }
4407
4408 int acwing805::max(int x, int y) { return x > y ? x : y; }
4409
4410 int acwing806::main(istream &cin, ostream &cout) {
4411 double x;
4412 double y;
4413 cin >> x >> y;
4414 cout << fixed << setprecision(2) << add(x, y);
4415 return 0;
4416 }
4417
4418 double acwing806::add(double x, double y) { return x + y; }
4419
4420 int acwing808::main(istream &cin, ostream &cout) {
4421 int a;
4422 int b;
4423 cin >> a >> b;
4424 cout << gcd(a, b);
4425 return 0;
4426 }
4427
4428 int acwing808::gcd(int a, int b) {
4429 while(b != 0) {
4430 const int t = a % b;
4431 a = b;
4432 b = t;
4433 }
4434 return a;
4435 }
4436
4437 int acwing807::main(istream &cin, ostream &cout) {
4438 int l;
4439 int r;
4440 cin >> l >> r;
4441 cout << sum(l, r);
4442 return 0;
4443 }
4444
4445 int acwing807::sum(int l, int r) {
4446 int sum = (l + r) * ((r - l + 1) / 2);
4447 if((r - l + 1) % 2 == 1) {
4448 sum += (r + l) / 2;
4449 }
4450 return sum;
4451 }
4452
4453 int acwing811::main(istream &cin, ostream &cout) {
4454 int x;
4455 int y;
4456 cin >> x >> y;
4457 swap(x, y);
4458 cout << x << " " << y;
4459 return 0;
4460 }
4461
4462 void acwing811::swap(int &x, int &y) {
4463 const int temp = x;
4464 x = y;
4465 y = temp;
4466 }
4467
4468 int acwing809::main(istream &cin, ostream &cout) {
4469 int a;
4470 int b;
4471 cin >> a >> b;
4472 cout << lcm(a, b);
4473 return 0;
4474 }
4475
4476 int acwing809::lcm(int a, int b) {
4477 const int f = acwing808::gcd(a, b);
4478 return a * b / f;
4479 }
4480
4481 int acwing812::main(istream &cin, ostream &cout) {
4482 int n;
4483 int size;
4484 cin >> n >> size;
4485 auto *a = new int[n];
4486 for(int i = 0; i < n; i++) {
4487 cin >> a[i];
4488 }
4489 print(a, size, cout);
4490 delete[] a;
4491 return 0;
4492 }
4493
4494 void acwing812::print(int *a, int size, ostream &cout) {
4495 for(int i = 0; i < size; i++) {
4496 cout << a[i] << " ";
4497 }
4498 }
4499
4500 int acwing814::main(istream &cin, ostream &cout) {
4501 int n;
4502 int m;
4503 int size;
4504 cin >> n >> m >> size;
4505 auto *a = new int[n];
4506 auto *b = new int[m];
4507 for(int i = 0; i < n; i++) {
4508 cin >> a[i];
4509 }
4510 for(int i = 0; i < m; i++) {
4511 cin >> b[i];
4512 }
4513 copy(a, b, size);
4514 for(int i = 0; i < m; i++) {
4515 cout << b[i] << " ";
4516 }
4517 return 0;
4518 }
4519
4520 void acwing814::copy(const int *a, int *b, int size) {
4521 for(int i = 0; i < size; i++) {
4522 b[i] = a[i];
4523 }
4524 }
4525
4526 void acwing813::print2D(int a[][100], int row, int col, ostream &cout) {
4527 for(int i = 0; i < row; i++) {
4528 for(int j = 0; j < col; j++) {
4529 cout << a[i][j] << " ";
4530 }
4531 cout << endl;
4532 }
4533 }
4534
4535 int acwing813::main(istream &cin, ostream &cout) {
4536 int row;
4537 int col;
4538 cin >> row >> col;
4539 int arr[100][100];
4540 for(int i = 0; i < row; i++) {
4541 for(int j = 0; j < col; j++) {
4542 cin >> arr[i][j];
4543 }
4544 }
4545 print2D(arr, row, col, cout);
4546 return 0;
4547 }
4548
4549 int acwing815::main(istream &cin, ostream &cout) {
4550 auto *str = new char[101];
4551 cin.getline(str, 101);
4552 print(str, cout);
4553 return 0;
4554 }
4555
4556 void acwing815::print(char *str, ostream &cout) {
4557 for(int i = 0; str[i] != '\0'; i++) {
4558 cout << str[i];
4559 }
4560 }
4561
4562 int acwing4305::main(istream &cin, ostream &cout) {
4563 int n;
4564 cin >> n;
4565 char fibb[1001] = {};
4566 memset(fibb, 'o', sizeof fibb);
4567 fibb[1] = 'O';
4568 unsigned int a = 1;
4569 unsigned int b = 1;
4570 unsigned int next = a + b;
4571 while(next <= n) {
4572 fibb[next] = 'O';
4573 a = b;
4574 b = next;
4575 next = a + b;
4576 }
4577 for(int i = 1; i <= n; i++) {
4578 cout << fibb[i];
4579 }
4580 return 0;
4581 }
4582
4583 int acwing4306::main(istream &cin, ostream &cout) {
4584 int n;
4585 cin >> n;
4586 vector<int> a(n);
4587 for(int i = 0; i < n; i++) {
4588 cin >> a[i];
4589 }
4590 sort(a.begin(), a.end());
4591 int sum = 0;
4592 int addition = 0;
4593 for(int i = 1; i <= n; i++) {
4594 if(i + addition < a[i - 1]) {
4595 addition = a[i - 1] - i;
4596 }
4597 sum += i + addition - a[i - 1];
4598 }
4599 cout << sum;
4600 return 0;
4601 }
4602
4603 int acwing4307::main(istream &cin, ostream &cout) {
4604 string a;
4605 string b;
4606 cin >> a >> b;
4607 auto a_count = unordered_map<int, int>();
4608 for(const char ch: a) {
4609 a_count[ch - '0']++;
4610 }
4611 if(a.length() == b.length()) {
4612 cout << dfs(0, false, a_count, b);
4613 } else {
4614 for(int i = 9; i >= 0; i--) {
4615 while(a_count[i] > 0) {
4616 cout << i;
4617 a_count[i]--;
4618 }
4619 }
4620 }
4621 return 0;
4622 }
4623
4624 string acwing4307::dfs(int i, bool free, unordered_map<int, int> um, string &b) {
4625 auto oss = ostringstream();
4626 int j = b[i] - '0';
4627 if(free) {
4628 goto B;
4629 }
4630 if(um[j] > 0) {
4631 auto um_cpy = unordered_map(um);
4632 um_cpy[j]--;
4633 if(i == b.length() - 1) {
4634 oss << j;
4635 return oss.str();
4636 }
4637 string ans = dfs(i + 1, false, um_cpy, b);
4638 if(!ans.empty()) {
4639 oss << j << ans;
4640 } else {
4641 //不可行
4642 goto B;
4643 }
4644 } else {
4645 B:;
4646 int k = b[i] - '0' - 1;
4647 if(free) {
4648 k = 9;
4649 }
4650 for(; k >= 0; k--) {
4651 if(um[k] > 0) {
4652 auto um_cpy = unordered_map(um);
4653 um_cpy[k]--;
4654 if(i == b.length() - 1) {
4655 oss << k;
4656 break;
4657 }
4658 string ans = dfs(i + 1, true, um_cpy, b);
4659 if(!ans.empty()) {
4660 oss << k << ans;
4661 break;
4662 }
4663 }
4664 }
4665 }
4666
4667 return oss.str();
4668 }
4669
4670 int acwing819::main(istream &cin, ostream &cout) {
4671 int n;
4672 cin >> n;
4673 cout << factorial(n);
4674 return 0;
4675 }
4676
4678 if(n == 1) {
4679 return 1;
4680 }
4681 return n * factorial(n - 1);
4682 }
4683
4684 int acwing816::main(istream &cin, ostream &cout) {
4685 int n;
4686 int size;
4687 cin >> n >> size;
4688 auto *a = new int[n];
4689 for(int i = 0; i < n; i++) {
4690 cin >> a[i];
4691 }
4692 reverse(a, size);
4693 for(int i = 0; i < n; i++) {
4694 cout << a[i] << " ";
4695 }
4696 delete[] a;
4697 return 0;
4698 }
4699
4700 void acwing816::reverse(int a[], int size) {
4701 for(int i = 0; i < size - 1 - i; i++) {
4702 const int tmp = a[i];
4703 a[i] = a[size - 1 - i];
4704 a[size - 1 - i] = tmp;
4705 }
4706 }
4707
4708 int acwing820::main(istream &cin, ostream &cout) {
4709 int n;
4710 cin >> n;
4711 cout << fibb(n);
4712 return 0;
4713 }
4714
4715 int acwing820::fibb(int n) {
4716 if(n <= 2) {
4717 return 1;
4718 }
4719 return fibb(n - 1) + fibb(n - 2);
4720 }
4721
4722 int acwing817::main(istream &cin, ostream &cout) {
4723 int n;
4724 cin >> n;
4725 auto *a = new int[n];
4726 for(int i = 0; i < n; i++) {
4727 cin >> a[i];
4728 }
4729 cout << get_unique_count(a, n);
4730 delete[] a;
4731 return 0;
4732 }
4733
4734 int acwing817::get_unique_count(int *a, int n) {
4735 unordered_set<int> um;
4736 for(int i = 0; i < n; i++) {
4737 um.insert(a[i]);
4738 }
4739 return um.size();
4740 }
4741
4742 int acwing818::main(istream &cin, ostream &cout) {
4743 int n;
4744 int l;
4745 int r;
4746 cin >> n >> l >> r;
4747 auto *a = new int[n];
4748 for(int i = 0; i < n; i++) {
4749 cin >> a[i];
4750 }
4751 sort(a, l, r);
4752 for(int i = 0; i < n; i++) {
4753 cout << a[i] << " ";
4754 }
4755 delete[] a;
4756 return 0;
4757 }
4758
4759 void acwing818::sort(int *a, int l, int r) {
4760 if(l == r) {
4761 return;
4762 }
4763 if(l + 1 == r) {
4764 if(a[l] < a[r]) {
4765 return;
4766 }
4767 const int tmp = a[l];
4768 a[l] = a[r];
4769 a[r] = tmp;
4770 }
4771 const int m = a[(l + r) / 2];
4772 deque<int> dq;
4773 int cursor = l;
4774 dq.push_back(m);
4775 for(int i = l; i <= r; i++) {
4776 if(i != (l + r) / 2) {
4777 if(a[i] <= m) {
4778 dq.push_front(a[i]);
4779 cursor++;
4780 } else {
4781 dq.push_back(a[i]);
4782 }
4783 }
4784 }
4785 for(int i = l; i <= r; i++) {
4786 a[i] = dq[i - l];
4787 }
4788 if(l <= cursor - 1) {
4789 sort(a, l, cursor - 1);
4790 }
4791 if(r >= cursor + 1) {
4792 sort(a, cursor + 1, r);
4793 }
4794 }
4795
4796 int acwing821::main(istream &cin, ostream &cout) {
4797 int n;
4798 cin >> n;
4799 auto *dp = new int[n + 1];
4800 memset(dp, 0, (n + 1) * sizeof(int));
4801 dp[1] = 1;
4802 dp[2] = 1;
4803 for(int i = 1; i <= n; i++) {
4804 if(i + 1 <= n) {
4805 dp[i + 1] += dp[i];
4806 }
4807 if(i + 2 <= n) {
4808 dp[i + 2] += dp[i];
4809 }
4810 }
4811 cout << dp[n];
4812 delete[] dp;
4813 return 0;
4814 }
4815
4816 int acwing822::main(istream &cin, ostream &cout) {
4817 int n;
4818 int m;
4819 cin >> n >> m;
4820 const int sum = n + m;
4821 auto *factorial = new unsigned long long[sum + 1];
4822 factorial[1] = 1;
4823 for(int i = 2; i <= sum; i++) {
4824 factorial[i] = i * factorial[i - 1];
4825 }
4826 cout << factorial[sum] / (factorial[n] * factorial[m]);
4827 delete[] factorial;
4828 return 0;
4829 }
4830
4831 int acwing823::main(istream &cin, ostream &cout) {
4832 int n;
4833 cin >> n;
4834 set<int> s;
4835 for(int i = 1; i <= n; i++) {
4836 s.insert(i);
4837 }
4838 vector<int> vec;
4839 dfs(vec, s, cout);
4840 return 0;
4841 }
4842
4843 void acwing823::dfs(vector<int> &vec, set<int> &s, ostream &cout) {
4844 if(s.empty()) {
4845 for(const int i: vec) {
4846 cout << i << " ";
4847 }
4848 cout << endl;
4849 } else {
4850 for(auto i: s) {
4851 vector vec_cpy = vec;
4852 set<int> s_cpy = s;
4853 vec_cpy.push_back(i);
4854 s_cpy.erase(i);
4855 dfs(vec_cpy, s_cpy, cout);
4856 }
4857 }
4858 }
4859
4861 auto *fibb = new int[n];
4862 fibb[0] = 1;
4863 fibb[1] = 1;
4864 for(int i = 2; i < n; i++) {
4865 fibb[i] = fibb[i - 1] + fibb[i - 2];
4866 }
4867 const int ans = fibb[n - 1];
4868 delete[] fibb;
4869 return ans;
4870 }
4871
4872 namespace acwing78 {
4873 string Solution::leftRotateString(string str, int n) {
4874 ostringstream oss;
4875 for(int i = 0; i < str.length(); i++) {
4876 oss << str[(n + i) % str.length()];
4877 }
4878 return oss.str();
4879 }
4880 }// namespace acwing78
4881
4882 namespace acwing16 {
4883 string Solution::replaceSpaces(string &str) {
4884 ostringstream oss;
4885 for(const char ch: str) {
4886 if(ch != ' ') {
4887 oss << ch;
4888 } else {
4889 oss << "%20";
4890 }
4891 }
4892 return oss.str();
4893 }
4894 }// namespace acwing16
4895
4896 namespace acwing87 {
4897 int Solution::strToInt(string str) {
4898 for(int i = 0; i < str.length(); i++) {
4899 if(str[i] != ' ') {
4900 str = str.substr(i);
4901 break;
4902 }
4903 }
4904 bool pos = true;
4905 if(str[0] == '+' || str[0] == '-') {
4906 pos = str[0] == '+';
4907 str = str.substr(1);
4908 }
4909 unsigned long long ans = 0;
4910 for(const char ch: str) {
4911 if(isdigit(ch) != 0) {
4912 ans *= 10;
4913 ans += ch - '0';
4914 } else {
4915 break;
4916 }
4917 }
4918 return ans > INT_MAX
4919 ? (pos ? INT_MAX : INT_MIN)
4920 : pos
4921 ? ans
4922 : -ans;
4923 }
4924 }// namespace acwing87
4925
4926 int acwing4308::main(istream &cin, ostream &cout) {
4927 string s1;
4928 string s2;
4929 cin >> s1 >> s2;
4930 bool flag = true;
4931 cout << s1[0];
4932 for(int i = 1; i < s1.length(); i++) {
4933 const char ch = s1[i];
4934 if(ch < s2[0]) {
4935 cout << ch;
4936 } else {
4937 break;
4938 }
4939 }
4940 cout << s2[0];
4941 return 0;
4942 }
4943
4944 int acwing4309::main(istream &cin, ostream &cout) {
4945 int n;
4946 int x0;
4947 int y0;
4948 cin >> n >> x0 >> y0;
4949 bool flag = false;
4950 unordered_set<double> slopes;
4951 for(int i = 0; i < n; i++) {
4952 int xi;
4953 int yi;
4954 cin >> xi >> yi;
4955 if(xi != x0) {
4956 double slope = static_cast<double>(y0 - yi) / (x0 - xi);
4957 slopes.insert(slope);
4958 } else {
4959 flag = true;
4960 }
4961 }
4962 cout << slopes.size() + (flag ? 1 : 0);
4963 return 0;
4964 }
4965
4966 namespace acwing4310 {
4967 int acwing4310::main(istream &cin, ostream &cout) {
4968 int n;
4969 int q;
4970 cin >> n >> q;
4971 vector<int> vec;
4972 for(int i = 1; i <= n; i++) {
4973 um[i] = new TreeNode(i);
4974 }
4975 for(int i = 2; i <= n; i++) {
4976 int parent;
4977 cin >> parent;
4978 um[parent]->nexts[i] = um[i];
4979 }
4980 dfs(&vec, um[1]);
4981 for(int i = 0; i < vec.size(); i++) {
4982 position[vec[i]] = i;
4983 }
4984 for(int i = 0; i < q; i++) {
4985 int u;
4986 int k;
4987 cin >> u >> k;
4988 if(k > size_tree[u]) {
4989 cout << -1;
4990 } else {
4991 cout << vec[position[u] + k - 1];
4992 }
4993 cout << endl;
4994 }
4995 for(auto [i, v]: um) {
4996 delete v;
4997 }
4998 return 0;
4999 }
5000
5001 int acwing4310::dfs(vector<int> *vec, TreeNode *node) {
5002 int sum = 1;
5003 vec->push_back(node->val);
5004 for(auto [i, next]: node->nexts) {
5005 if(next != nullptr) {
5006 sum += dfs(vec, next);
5007 }
5008 }
5009 size_tree[node->val] = sum;
5010 return sum;
5011 }
5012 }// namespace acwing4310
5013
5014 namespace acwing84 {
5015 int Solution::getSum(int n) {
5016 int ans = (1 + n) * (n / 2);
5017 if(n % 2 != 0) {
5018 ans += n / 2;
5019 }
5020 return ans;
5021 }
5022 }// namespace acwing84
5023
5024 namespace acwing35 {
5026 if(head == nullptr) {
5027 return head;
5028 }
5029 auto *prev = head;
5030 auto *current = head->next;
5031 while(current != nullptr) {
5032 auto *next = current->next;
5033 current->next = prev;
5034 prev = current;
5035 current = next;
5036 }
5037 head->next = nullptr;
5038 return prev;
5039 }
5040 }// namespace acwing35
5041
5042 namespace acwing28 {
5044 node->val = node->next->val;
5045 const auto *next = node->next;
5046 delete next;
5047 node->next = node->next->next;
5048 }
5049 }// namespace acwing28
5050
5051 namespace acwing66 {
5053 unordered_set<ListNode *> nodes;
5054 for(auto *current = headA; current != nullptr; current = current->next) {
5055 nodes.insert(current);
5056 }
5057 for(auto *current = headB; current != nullptr; current = current->next) {
5058 if(nodes.contains(current)) {
5059 return current;
5060 }
5061 }
5062 return nullptr;
5063 }
5064 }// namespace acwing66
5065
5066 namespace acwing36 {
5068 auto *current = new ListNode(0);
5069 const ListNode *head = current;
5070 while(l1 != nullptr && l2 != nullptr) {
5071 if(l1->val < l2->val) {
5072 current->next = l1;
5073 l1 = l1->next;
5074 } else {
5075 current->next = l2;
5076 l2 = l2->next;
5077 }
5078 current = current->next;
5079 }
5080 if(l1 == nullptr) {
5081 current->next = l2;
5082 } else {
5083 current->next = l1;
5084 }
5085 return head->next;
5086 }
5087 }// namespace acwing36
5088
5089 namespace acwing29 {
5091 if(head == nullptr) {
5092 return head;
5093 }
5094 while(head != nullptr && head->next != nullptr && head->val == head->next->val) {
5095 const int val = head->val;
5096 while(head != nullptr && head->val == val) {
5097 head = head->next;
5098 }
5099 }
5100 ListNode *ans = head;
5101 while(head != nullptr) {
5102 while(head->next != nullptr && head->next->next != nullptr && head->next->val == head->next->next->val) {
5103 const int val = head->next->val;
5104 ListNode *cursor = head->next;
5105 while(cursor != nullptr && cursor->val == val) {
5106 cursor = cursor->next;
5107 }
5108 head->next = cursor;
5109 }
5110 head = head->next;
5111 }
5112 return ans;
5113 }
5114 }// namespace acwing29
5115
5116 namespace acwing67 {
5117 int Solution::getNumberOfK(vector<int> &nums, int k) {
5118 int ans = 0;
5119 bool flag = false;
5120 for(const auto num: nums) {
5121 if(num == k) {
5122 ans++;
5123 flag = true;
5124 } else if(flag) {
5125 break;
5126 }
5127 }
5128 return ans;
5129 }
5130 }// namespace acwing67
5131
5132 namespace acwing53 {
5133 vector<int> Solution::getLeastNumbers_Solution(vector<int> input, int k) {
5134 sort(input.begin(), input.end());
5135 return vector(input.begin(), input.begin() + k);
5136 }
5137 }// namespace acwing53
5138
5140 namespace acwing68 {
5141 int Solution::getMissingNumber(vector<int> &nums) {
5142 if(nums.empty()) {
5143 return 0;
5144 }
5145 int i = 0;
5146 while(nums[i] == i) {
5147 i++;
5148 }
5149 return i;
5150 }
5151 }// namespace acwing68
5152
5153 namespace acwing75 {
5154 vector<int> Solution::findNumbersWithSum(vector<int> &nums, int target) {
5155 vector<int> ans(2);
5156 set nms(nums.begin(), nums.end());
5157 for(auto num = nms.begin(); *num <= target / 2 && num != nms.end(); ++num) {
5158 if(nms.contains(target - *num)) {
5159 ans[0] = *num;
5160 ans[1] = target - *num;
5161 return ans;
5162 }
5163 }
5164 return ans;
5165 }
5166 }// namespace acwing75
5167
5168 namespace acwing32 {
5169 void Solution::reOrderArray(vector<int> &array) {
5170 int l = 0;
5171 int r = array.size() - 1;
5172 while(l < r) {
5173 while(l < r && array[l] % 2 == 1) {
5174 l++;
5175 }
5176 while(l < r && array[r] % 2 == 0) {
5177 r--;
5178 }
5179 if(l < r) {
5180 swap(array[l], array[r]);
5181 }
5182 }
5183 }
5184 }// namespace acwing32
5185
5186 namespace acwing51 {
5187 vector<vector<int>> Solution::permutation(vector<int> &nums) {
5188 auto ans = vector<vector<int>>();
5189 set<vector<int>> s;
5190 dfs(vector<int>(), nums, s);
5191 for(const auto &vec: s) {
5192 ans.push_back(vec);
5193 }
5194 return ans;
5195 }
5196
5197 void Solution::dfs(const vector<int> &vec, vector<int> nums, set<vector<int>> &s) {
5198 if(nums.empty()) {
5199 s.insert(vec);
5200 }
5201 for(int i = 0; i < nums.size(); i++) {
5202 auto nums_cpy = vector(nums);
5203 auto vec_cpy = vector(vec);
5204 nums_cpy.erase(nums_cpy.begin() + i);
5205 vec_cpy.push_back(nums[i]);
5206 dfs(vec_cpy, nums_cpy, s);
5207 }
5208 }
5209 }// namespace acwing51
5210
5211 namespace acwing17 {
5213 deque<int> deq;
5214 for(const auto *current = head; current != nullptr; current = current->next) {
5215 deq.push_front(current->val);
5216 }
5217 return vector(deq.begin(), deq.end());
5218 }
5219 }// namespace acwing17
5220
5221 namespace acwing26 {
5223 int ans = 0;
5224 unsigned int un = n;
5225 while(un != 0U) {
5226 ans += un & 1;
5227 un >>= 1;
5228 }
5229 return ans;
5230 }
5231 }// namespace acwing26
5232
5233 namespace acwing20 {
5235 main = vector<int>();
5236 tmp = vector<int>();
5237 }
5238
5239 void MyQueue::push(int x) { main.push_back(x); }
5240
5242 while(main.size() != 1) {
5243 tmp.push_back(main.back());
5244 main.pop_back();
5245 }
5246 const auto ret = main.back();
5247 main.pop_back();
5248 while(!tmp.empty()) {
5249 main.push_back(tmp.back());
5250 tmp.pop_back();
5251 }
5252 return ret;
5253 }
5254
5256 while(main.size() != 1) {
5257 tmp.push_back(main.back());
5258 main.pop_back();
5259 }
5260 const auto ret = main.back();
5261 while(!tmp.empty()) {
5262 main.push_back(tmp.back());
5263 tmp.pop_back();
5264 }
5265 return ret;
5266 }
5267
5268 bool MyQueue::empty() const { return main.empty(); }
5269 }// namespace acwing20
5270
5271 int acwing862::main(istream &cin, ostream &cout) {
5272 int n;
5273 cin >> n;
5274 auto comp = [](tuple<int, float, string> a, tuple<int, float, string> b) {
5275 auto [ax, ay, az] = std::move(a);
5276 auto [bx, by, bz] = std::move(b);
5277 return ax < bx;
5278 };
5279 set<tuple<int, float, string>, decltype(comp)> s(comp);
5280 for(int i = 0; i < n; i++) {
5281 int x;
5282 float y;
5283 string z;
5284 cin >> x >> y >> z;
5285 s.insert(make_tuple(x, y, z));
5286 }
5287 for(const auto &t: s) {
5288 auto [x, y, z] = t;
5289 cout << x << ' ' << fixed << setprecision(2) << y << ' ' << z << endl;
5290 }
5291 return 0;
5292 }
5293
5294 int acwing4311::main(istream &cin, ostream &cout) {
5295 int n;
5296 int m;
5297 cin >> n >> m;
5298 double maximum = 0;
5299 for(int i = 0; i < n; i++) {
5300 int a;
5301 int b;
5302 cin >> a >> b;
5303 maximum = max(maximum, m * a / static_cast<double>(b));
5304 }
5305 cout << fixed << setprecision(6) << maximum;
5306 return 0;
5307 }
5308
5309 int acwing3412::main(istream &cin, ostream &cout) {
5310 int n;
5311 int m;
5312 int q;
5313 cin >> n >> m >> q;
5314 if(m > n) {
5315 for(int i = 0; i < q; i++) {
5316 cout << 0 << endl;
5317 }
5318 return 0;
5319 }
5320 string s;
5321 string t;
5322 cin >> s >> t;
5323 set<int> sub_end;
5324 set<int> sub_start;
5325 int sub_count = 0;
5326 for(int i = 0; i + m <= n; i++) {
5327 string str = s.substr(i, m);
5328 if(str == t) {
5329 sub_count++;
5330 sub_start.insert(i);
5331 sub_end.insert(i + m - 1);
5332 }
5333 }
5334 vector sub_end_count(n + 1, 0);
5335 vector sub_start_count(n + 1, 0);
5336 int current = 0;
5337 for(int i = 0; i < n + 1; i++) {
5338 if(sub_end.contains(i)) {
5339 current++;
5340 }
5341 sub_end_count[i] = current;
5342 }
5343 current = 0;
5344 for(int i = n; i >= 0; i--) {
5345 if(sub_start.contains(i)) {
5346 current++;
5347 }
5348 sub_start_count[i] = current;
5349 }
5350 for(int i = 0; i < q; i++) {
5351 int l;
5352 int r;
5353 cin >> l >> r;
5354 int ans = sub_end_count[r - 1] - (sub_count - sub_start_count[l - 1]);
5355 cout << max(ans, 0) << endl;
5356 }
5357 return 0;
5358 }
5359
5360 int acwing3346::main(istream &cin, ostream &cout) {
5361 vector<int> nums(7);
5362 vector<int> abc(3);
5363 for(int i = 0; i < 7; i++) {
5364 cin >> nums[i];
5365 }
5366 sort(nums.begin(), nums.end());
5367 abc[0] = nums[0];
5368 abc[1] = nums[1];
5369 abc[2] = nums[6] - abc[0] - abc[1];
5370 sort(abc.begin(), abc.end());
5371 cout << abc[0] << ' ' << abc[1] << ' ' << abc[2];
5372 return 0;
5373 }
5374
5375 namespace acwing3358 {
5376 int main(istream &cin, ostream &cout) {
5377 int char_pos[26] = {};
5378 char ch;
5379 for(int i = 0; i < 26; i++) {
5380 cin >> ch;
5381 char_pos[ch - 'a'] = i;
5382 }
5383 int ans = 1;
5384 int current = -1;
5385 while(cin >> ch) {
5386 if(char_pos[ch - 'a'] <= current) {
5387 ans++;
5388 }
5389 current = char_pos[ch - 'a'];
5390 }
5391 cout << ans;
5392 return 0;
5393 }
5394 };// namespace acwing3358
5395
5396 namespace acwing3370 {
5397 int main(istream &cin, ostream &cout) {
5398 int n;
5399 cin >> n;
5400 unordered_map<string, int> zodiacs;
5401 unordered_map<string, cow *> cows;
5402 zodiacs["Ox"] = 0;
5403 zodiacs["Tiger"] = 1;
5404 zodiacs["Rabbit"] = 2;
5405 zodiacs["Dragon"] = 3;
5406 zodiacs["Snake"] = 4;
5407 zodiacs["Horse"] = 5;
5408 zodiacs["Goat"] = 6;
5409 zodiacs["Monkey"] = 7;
5410 zodiacs["Rooster"] = 8;
5411 zodiacs["Dog"] = 9;
5412 zodiacs["Pig"] = 10;
5413 zodiacs["Rat"] = 11;
5414 cows["Bessie"] = new cow("Bessie", 0, zodiacs["Ox"]);
5415 for(int i = 0; i < n; i++) {
5416 string str;
5417 string name1;
5418 string name2;
5419 cin >> name1 >> str >> str >> str;
5420 const bool previous = str == "previous";
5421 cin >> str;
5422 const int zodiac = zodiacs[str];
5423 cin >> str >> str >> name2;
5424 cow *cow1;
5425 cow *cow2;
5426 if(!cows.contains(name1)) {
5427 cow1 = new cow(name1, -1, zodiac);
5428 cows[name1] = cow1;
5429 } else {
5430 cow1 = cows[name1];
5431 cow1->zodiac = zodiac;
5432 }
5433 if(!cows.contains(name2)) {
5434 cow2 = new cow(name2, -1, -1);
5435 cows[name2] = cow2;
5436 } else {
5437 cow2 = cows[name2];
5438 }
5439 if(previous) {
5440 cow2->previous.push_back(cow1);
5441 cow1->next.push_back(cow2);
5442 } else {
5443 cow2->next.push_back(cow1);
5444 cow1->previous.push_back(cow2);
5445 }
5446 }
5447 cout << abs(dfs(cows["Bessie"]));
5448 return 0;
5449 }
5450
5451 int dfs(cow *c) {
5452 if(c->name == "Elsie") {
5453 return c->val;
5454 }
5455 for(auto *prev: c->previous) {
5456 if(prev->val == -1) {
5457 if(c->zodiac == prev->zodiac) {
5458 prev->val = c->val - 12;
5459 } else {
5460 prev->val = c->val - (c->zodiac + 12 - prev->zodiac) % 12;
5461 }
5462 const int ret = dfs(prev);
5463 if(ret != -1) {
5464 return ret;
5465 }
5466 }
5467 }
5468 for(auto *nxt: c->next) {
5469 if(nxt->val == -1) {
5470 if(c->zodiac == nxt->zodiac) {
5471 nxt->val = c->val + 12;
5472 } else {
5473 nxt->val = c->val + (nxt->zodiac + 12 - c->zodiac) % 12;
5474 }
5475 const int ret = dfs(nxt);
5476 if(ret != -1) {
5477 return ret;
5478 }
5479 }
5480 }
5481 return -1;
5482 }
5483
5484 cow::cow(string name, int val, int zodiac) {
5485 this->name = std::move(name);
5486 this->val = val;
5487 this->zodiac = zodiac;
5488 this->previous = vector<cow *>();
5489 this->next = vector<cow *>();
5490 }
5491 }// namespace acwing3370
5492
5493 namespace acwing3745 {
5494 int main(istream &cin, ostream &cout) {
5495 int n;
5496 int l;
5497 cin >> n >> l;
5498 vector<int> c(n);
5499 unordered_map<int, int> count;
5500 for(int i = 0; i < n; i++) {
5501 cin >> c[i];
5502 count[c[i]]++;
5503 }
5504 sort(c.rbegin(), c.rend());
5505 if(*c.begin() == 0) {
5506 if(l != 0) {
5507 *c.begin() = 1;
5508 l--;
5509 } else {
5510 cout << 0;
5511 return 0;
5512 }
5513 }
5514 int h = 0;
5515 while(h < n && c[h] >= h + 1) {
5516 h++;
5517 }
5518 if(l == 0) {
5519 cout << h;
5520 return 0;
5521 }
5522 int k = 0;
5523 for(int i = h - 1; i >= 0 && c[i] == h; i--) {
5524 k++;
5525 }
5526 if(l >= k + 1 && c[h] == h) {
5527 cout << h + 1;
5528 } else {
5529 cout << h;
5530 }
5531 return 0;
5532 }
5533 }// namespace acwing3745
5534
5535 namespace acwing1459 {
5536 int main(istream &cin, ostream &cout) {
5537 int k;
5538 int n;
5539 cin >> k >> n;
5540 auto hash = [](const pair<int, int> p) -> int { return p.first * 20 + p.second; };
5541 unordered_set<pair<int, int>, decltype(hash)> pairs;
5542 for(int i = 1; i <= n; i++) {
5543 for(int j = 1; j <= n; j++) {
5544 if(i != j) {
5545 pairs.insert(make_pair(i, j));
5546 }
5547 }
5548 }
5549 for(int i = 0; i < k; i++) {
5550 vector<int> vec(n);
5551 for(int j = 0; j < n; j++) {
5552 cin >> vec[j];
5553 }
5554 for(int j = 0; j + 1 < n; j++) {
5555 for(int l = j + 1; l < n; l++) {
5556 pairs.erase(make_pair(vec[j], vec[l]));
5557 }
5558 }
5559 }
5560 cout << pairs.size();
5561 return 0;
5562 }
5563 }// namespace acwing1459
5564
5565 namespace acwing1442 {
5566 int main(istream &cin, ostream &cout) {
5567 int n;
5568 int k;
5569 cin >> n >> k;
5570 vector<string> vec(n);
5571 for(int i = 0; i < n; i++) {
5572 cin >> vec[i];
5573 }
5574 ostringstream oss;
5575 oss << vec[0];
5576 int current = vec[0].length();
5577 for(int i = 1; i < n; i++) {
5578 if(current + vec[i].length() > k) {
5579 cout << oss.str() << endl;
5580 oss = ostringstream();
5581 oss << vec[i];
5582 current = vec[i].length();
5583 } else {
5584 oss << ' ';
5585 oss << vec[i];
5586 current += vec[i].length();
5587 }
5588 }
5589 cout << oss.str();
5590 return 0;
5591 }
5592 }// namespace acwing1442
5593
5594 namespace acwing4314 {
5595 int main(istream &cin, ostream &cout) {
5596 int n;
5597 cin >> n;
5598 int ans = 0;
5599 for(int a = 1; a <= n; a++) {
5600 for(int b = a; b <= n; b++) {
5601 const int c = a ^ b ^ 0;
5602 if(n >= c && c >= b && c < a + b) {
5603 ans++;
5604 }
5605 }
5606 }
5607 cout << ans;
5608 return 0;
5609 }
5610 }// namespace acwing4314
5611
5612 namespace acwing4315 {
5613 int main(istream &cin, ostream &cout) {
5614 long long n;
5615 long long s;
5616 cin >> n >> s;
5617 vector<long long> a(n);
5618 long long a_sum = 0;
5619 for(int i = 0; i < n; i++) {
5620 cin >> a[i];
5621 a_sum += a[i];
5622 }
5623 for(int i = 0; i < n; i++) {
5624 const long long low = max(static_cast<long long>(1), s - (a_sum - a[i]));
5625 const long long high = min(a[i], s - (n - 1));
5626 if(low <= high) {
5627 cout << a[i] - (high - low + 1) << ' ';
5628 }
5629 }
5630 return 0;
5631 }
5632 }// namespace acwing4315
5633
5634 namespace acwing1671 {
5635 int main(istream &cin, ostream &cout) {
5636 int ans = 0;
5637 unordered_map<int, set<int>> col;
5638 unordered_map<int, set<int>> row;
5639 set<pair<int, int>> us;
5640 int n;
5641 cin >> n;
5642 for(int i = 0; i < n; i++) {
5643 int x;
5644 int y;
5645 cin >> x >> y;
5646 us.insert(make_pair(x, y));
5647 row[x].insert(y);
5648 col[y].insert(x);
5649 }
5650 for(auto [x, y]: us) {
5651 const int max_width = max(abs(*row[x].begin() - y), abs(*row[x].rbegin() - y));
5652 const int max_height = max(abs(*col[y].begin() - x), abs(*col[y].rbegin() - x));
5653 ans = max(ans, max_width * max_height);
5654 }
5655 cout << ans;
5656 return 0;
5657 }
5658 }// namespace acwing1671
5659
5660 namespace acwing1659 {
5661 int main(istream &cin, ostream &cout) {
5662 int n;
5663 cin >> n;
5664 vector<bool> pen(n);
5665 string str;
5666 cin >> str;
5667 bool has1 = false;
5668 for(int i = 0; i < n; i++) {
5669 pen[i] = str[i] == '1';
5670 if(pen[i]) {
5671 has1 = true;
5672 }
5673 }
5674 if(!has1) {
5675 cout << n - 1;
5676 return 0;
5677 }
5678 vector<int> spaces2;
5679 vector<int> spaces1;
5680 int current = 0;
5681 int left = 0;
5682 int right = n - 1;
5683 while(!pen[left]) {
5684 left++;
5685 }
5686 if(left > 0) {
5687 spaces1.push_back(left);
5688 }
5689 left++;
5690 while(!pen[right]) {
5691 right--;
5692 }
5693 if(right < n - 1) {
5694 spaces1.push_back(n - 1 - right);
5695 }
5696 for(; left <= right; left++) {
5697 if(!pen[left]) {
5698 current++;
5699 } else {
5700 spaces2.push_back(current);
5701 current = 0;
5702 }
5703 }
5704 int minimum = 0;
5705 int limit = n;
5706 sort(spaces2.begin(), spaces2.end());
5707 sort(spaces1.begin(), spaces1.end());
5708 if(!spaces2.empty()) {
5709 limit = *spaces2.begin();
5710 //两个都在2
5711 //两个都在2的最大
5712 const int a = (*spaces2.rbegin() - 2) / 3;
5713 minimum = max(minimum, a);
5714 //两个分别在2的最大和第二大
5715 if(spaces2.size() > 1) {
5716 const int b = (spaces2[spaces2.size() - 2] - 1) / 2;
5717 minimum = max(minimum, b);
5718 }
5719 //两个分别在2的最大和1的最大
5720 if(!spaces1.empty()) {
5721 const int a = (*spaces2.rbegin() - 1) / 2;
5722 int b = *spaces1.rbegin() - 1;
5723 minimum = max(minimum, min(a, b));
5724 //两个都在1的最大
5725 b = (*spaces1.rbegin() - 2) / 2;
5726 minimum = max(minimum, b);
5727 //两个分别在1的最大和第二大
5728 if(spaces1.size() > 1) {
5729 const int a = *spaces1.begin() - 1;
5730 minimum = max(minimum, a);
5731 }
5732 }
5733 } else {
5734 //两个分别在1的最大和第二大
5735 if(spaces1.size() > 1) {
5736 const int a = *spaces1.begin() - 1;
5737 minimum = max(minimum, a);
5738 }
5739 //两个都在1的最大
5740 const int b = (*spaces1.rbegin() - 2) / 2;
5741 minimum = max(minimum, b);
5742 }
5743 minimum = min(limit, minimum);
5744 cout << minimum + 1;
5745 return 0;
5746 }
5747 }// namespace acwing1659
5748
5749 namespace acwing1714 {
5750 int main(istream &cin, ostream &cout) {
5751 unsigned int c[3];
5752 unsigned int m[3];
5753 for(int i = 0; i < 3; i++) {
5754 cin >> c[i] >> m[i];
5755 }
5756 for(int i = 0; i < 100; i++) {
5757 const int a = i % 3;
5758 const int b = (i + 1) % 3;
5759 if(m[a] + m[b] <= c[b]) {
5760 m[b] += m[a];
5761 m[a] = 0;
5762 } else {
5763 m[a] -= c[b] - m[b];
5764 m[b] = c[b];
5765 }
5766 }
5767 for(int i = 0; i < 3; i++) {
5768 cout << m[i] << endl;
5769 }
5770 return 0;
5771 }
5772 }// namespace acwing1714
5773
5774 namespace acwing1695 {
5775 int main(istream &cin, ostream &cout) {
5776 bool nuts[3][3] = {{true, false, false},
5777 {false, true, false},
5778 {false, false, true}};
5779 unsigned short score[3] = {0, 0, 0};
5780 unsigned short ans = 0;
5781 unsigned short n;
5782 cin >> n;
5783 unsigned short a;
5784 unsigned short b;
5785 unsigned short g;
5786 for(unsigned short i = 0; i < n; i++) {
5787 cin >> a >> b >> g;
5788 a--;
5789 b--;
5790 g--;
5791 for(unsigned short j = 0; j < 3; j++) {
5792 swap(nuts[j][a], nuts[j][b]);
5793 if(nuts[j][g]) {
5794 score[j]++;
5795 }
5796 }
5797 }
5798 for(unsigned short i = 0; i < 3; i++) {
5799 ans = max(ans, score[i]);
5800 }
5801 cout << ans;
5802 return 0;
5803 }
5804 }// namespace acwing1695
5805
5806 namespace acwing1683 {
5807 int main(istream &cin, ostream &cout) {
5808 int pos[3];
5809 int ans1;
5810 cin >> pos[0] >> pos[1] >> pos[2];
5811 sort(pos, pos + 3);
5812 const int g1 = pos[1] - pos[0];
5813 const int g2 = pos[2] - pos[1];
5814 if(g1 == 2 || g2 == 2) {
5815 ans1 = 1;
5816 } else {
5817 ans1 = 2;
5818 }
5819 int ans2 = max(g1, g2);
5820 ans2--;
5821 cout << ans1 << endl
5822 << ans2;
5823 return 0;
5824 }
5825 }// namespace acwing1683
5826
5827 namespace acwing4318 {
5828 int main(istream &cin, ostream &cout) {
5829 int x = 0;
5830 int y = 0;
5831 char op;
5832 int step = 0;
5833 set<pair<int, int>> s;
5834 s.insert(make_pair(0, 0));
5835 while(cin >> op) {
5836 step++;
5837 switch(op) {
5838 case 'U':
5839 x--;
5840 if(s.contains(make_pair(x, y)) ||
5841 s.contains(make_pair(x - 1, y)) ||
5842 s.contains(make_pair(x, y + 1)) ||
5843 s.contains(make_pair(x, y - 1))) {
5844 cout << "NO";
5845 return 0;
5846 }
5847 break;
5848 case 'D':
5849 x++;
5850 if(s.contains(make_pair(x, y)) ||
5851 s.contains(make_pair(x + 1, y)) ||
5852 s.contains(make_pair(x, y + 1)) ||
5853 s.contains(make_pair(x, y - 1))) {
5854 cout << "NO";
5855 return 0;
5856 }
5857 break;
5858 case 'L':
5859 y--;
5860 if(s.contains(make_pair(x, y)) ||
5861 s.contains(make_pair(x, y - 1)) ||
5862 s.contains(make_pair(x + 1, y)) ||
5863 s.contains(make_pair(x - 1, y))) {
5864 cout << "NO";
5865 return 0;
5866 }
5867 break;
5868 case 'R':
5869 y++;
5870 if(s.contains(make_pair(x, y)) ||
5871 s.contains(make_pair(x, y + 1)) ||
5872 s.contains(make_pair(x + 1, y)) ||
5873 s.contains(make_pair(x - 1, y))) {
5874 cout << "NO";
5875 return 0;
5876 }
5877 break;
5878 default:
5879 step--;
5880 break;
5881 }
5882 s.insert(make_pair(x, y));
5883 }
5884 if(step == 1) {
5885 cout << "YES";
5886 return 0;
5887 }
5888 if(abs(x) <= 1 && y == 0 || x == 0 && abs(y) <= 1) {
5889 cout << "NO";
5890 } else {
5891 cout << "YES";
5892 }
5893 return 0;
5894 }
5895 }// namespace acwing4318
5896
5897 namespace acwing4319 {
5898 int main(istream &cin, ostream &cout) {
5899 unsigned int n;
5900 unsigned int k;
5901 cin >> n >> k;
5902 vector<unsigned int> a(n);
5903 vector<vector<pair<unsigned int, unsigned int>>> factors(n);
5904 map<vector<pair<unsigned int, unsigned int>>, unsigned int> factor_status_count;
5905 for(int i = 0; i < n; i++) {
5906 cin >> a[i];
5907 for(unsigned int factor = 2; factor * factor <= a[i]; factor++) {
5908 if(a[i] % factor != 0U) {
5909 continue;
5910 }
5911 unsigned int count = 0;
5912 while(a[i] % factor == 0) {
5913 a[i] /= factor;
5914 ++count;
5915 }
5916 count %= k;
5917 if(count != 0) {
5918 factors[i].emplace_back(factor, count);
5919 }
5920 }
5921 if(a[i] != 1) {
5922 factors[i].emplace_back(a[i], 1);
5923 }
5924 }
5925 unsigned long long ans = 0;
5926 for(unsigned int i = 0; i < n; i++) {
5927 vector<pair<unsigned int, unsigned int>> factor_status;
5928 for(auto [factor, count]: factors[i]) {
5929 factor_status.emplace_back(factor, k - count);
5930 }
5931 ans += factor_status_count[factor_status];
5932 ++factor_status_count[factors[i]];
5933 }
5934 cout << ans;
5935 return 0;
5936 }
5937 }// namespace acwing4319
5938
5939 namespace acwing1470 {
5940 int main(istream &cin, ostream &cout) {
5941 char farm[10][10] = {};
5942 pair<int, int> b;
5943 pair<int, int> l;
5944 for(int i = 0; i < 10; i++) {
5945 for(int j = 0; j < 10; j++) {
5946 cin >> farm[i][j];
5947 if(farm[i][j] == 'B') {
5948 b = make_pair(i, j);
5949 } else if(farm[i][j] == 'L') {
5950 l = make_pair(i, j);
5951 }
5952 }
5953 }
5954 priority_queue<status> pq;
5955 pq.push(status(0, l, b));
5956 while(!pq.empty()) {
5957 status s = pq.top();
5958 pq.pop();
5959 if(s.current == b) {
5960 cout << s.len - 1;
5961 return 0;
5962 }
5963 pair<int, int> nexts[4] = {make_pair(s.current.first + 1, s.current.second),
5964 make_pair(s.current.first - 1, s.current.second),
5965 make_pair(s.current.first, s.current.second + 1),
5966 make_pair(s.current.first, s.current.second - 1)};
5967 for(const auto next: nexts) {
5968 if(0 <= next.first && next.first < 10 && 0 <= next.second && next.second < 10 && farm[next.first][next.second] != 'R') {
5969 pq.push(status(s.len + 1, next, b));
5970 }
5971 }
5972 }
5973 return 0;
5974 }
5975
5976 bool status::operator<(const status &s) const { return this->get_weight() > s.get_weight(); }
5977
5978 int status::get_weight() const { return len + abs(current.first - target.first) + abs(current.second - target.second); }
5979 }// namespace acwing1470
5980
5981 namespace acwing1761 {
5982 int main(istream &cin, ostream &cout) {
5983 int x1[3];
5984 int y1[3];
5985 int x2[3];
5986 int y2[3];
5987 for(int i = 0; i < 3; i++) {
5988 cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
5989 }
5990 unsigned int area = 0;
5991 for(int i = 0; i < 2; i++) {
5992 area += abs(x2[i] - x1[i]) * abs(y2[i] - y1[i]);
5993 int x_1 = x1[2];
5994 int x_2 = x2[2];
5995 int y_1 = y1[2];
5996 int y_2 = y2[2];
5997 x_1 = max(x_1, x1[i]);
5998 x_2 = max(x_2, x1[i]);
5999 x_1 = min(x_1, x2[i]);
6000 x_2 = min(x_2, x2[i]);
6001 y_1 = max(y_1, y1[i]);
6002 y_2 = max(y_2, y1[i]);
6003 y_1 = min(y_1, y2[i]);
6004 y_2 = min(y_2, y2[i]);
6005 area -= abs(x_2 - x_1) * abs(y_2 - y_1);
6006 }
6007 cout << area;
6008 return 0;
6009 }
6010 }// namespace acwing1761
6011
6012 namespace acwing1749 {
6013 int main(istream &cin, ostream &cout) {
6014 int x1[2];
6015 int x2[2];
6016 int y1[2];
6017 int y2[2];
6018 for(int i = 0; i < 2; i++) {
6019 cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
6020 }
6021 const unsigned int area = abs(x2[0] - x1[0]) * abs(y2[0] - y1[0]);
6022 int x_1 = x1[1];
6023 int x_2 = x2[1];
6024 int y_1 = y1[1];
6025 int y_2 = y2[1];
6026 x_1 = max(x_1, x1[0]);
6027 x_2 = max(x_2, x1[0]);
6028 x_1 = min(x_1, x2[0]);
6029 x_2 = min(x_2, x2[0]);
6030 y_1 = max(y_1, y1[0]);
6031 y_2 = max(y_2, y1[0]);
6032 y_1 = min(y_1, y2[0]);
6033 y_2 = min(y_2, y2[0]);
6034 if(x_2 == x_1 || y_2 == y_1) {
6035 //没有遮盖
6036 cout << area;
6037 return 0;
6038 }
6039 if(y_2 == y2[0] && y_1 == y1[0]) {
6040 //纵向填满
6041 cout << abs(abs(x2[0] - x1[0]) - abs(x_2 - x_1)) * abs(y_2 - y_1);
6042 return 0;
6043 }
6044 if(x_1 == x1[0] && x_2 == x2[0] && (y_1 == y1[0] || y_2 == y2[0])) {
6045 //横向填满
6046 cout << (x_2 - x_1) * max(y2[0] - y_2, y_1 - y1[0]);
6047 return 0;
6048 }
6049 cout << area;
6050 return 0;
6051 }
6052 }// namespace acwing1749
6053
6054 namespace acwing1737 {
6055 int main(istream &cin, ostream &cout) {
6056 int a;
6057 int b;
6058 int x;
6059 int y;
6060 cin >> a >> b >> x >> y;
6061 const int d1 = abs(b - a);
6062 const int d2 = abs(a - x) + abs(b - y);
6063 const int d3 = abs(a - y) + abs(b - x);
6064 cout << min(d1, min(d2, d3));
6065 return 0;
6066 }
6067 }// namespace acwing1737
6068
6069 namespace acwing1725 {
6070 int main(istream &cin, ostream &cout) {
6071 unordered_set<char> row[3];
6072 unordered_set<char> col[3];
6073 unordered_set<char> main_diagonal;
6074 unordered_set<char> leading_diagonal;
6075 unordered_set<char> win_1;
6076 auto hash = [](const pair<char, char> &p) {
6077 vector vec = {p.first, p.second};
6078 sort(vec.begin(), vec.end());
6079 unsigned int val = 0;
6080 for(auto &ch: vec) {
6081 ch -= 'A';
6082 val *= 26;
6083 val += ch;
6084 }
6085 return val;
6086 };
6087 unordered_set<pair<char, char>, decltype(hash)> win_2;
6088 char board[3][3];
6089 for(int i = 0; i < 3; i++) {
6090 for(int j = 0; j < 3; j++) {
6091 cin >> board[i][j];
6092 row[i].insert(board[i][j]);
6093 col[j].insert(board[i][j]);
6094 }
6095 }
6096 main_diagonal.insert(board[0][0]);
6097 main_diagonal.insert(board[1][1]);
6098 main_diagonal.insert(board[2][2]);
6099 leading_diagonal.insert(board[0][2]);
6100 leading_diagonal.insert(board[1][1]);
6101 leading_diagonal.insert(board[2][0]);
6102 for(int i = 0; i < 3; i++) {
6103 if(row[i].size() == 1) {
6104 win_1.insert(board[i][0]);
6105 } else if(row[i].size() == 2) {
6106 win_2.insert(make_pair(*row[i].begin(), *++row[i].begin()));
6107 }
6108 if(col[i].size() == 1) {
6109 win_1.insert(board[0][i]);
6110 } else if(col[i].size() == 2) {
6111 win_2.insert(make_pair(*col[i].begin(), *++col[i].begin()));
6112 }
6113 }
6114 if(main_diagonal.size() == 1) {
6115 win_1.insert(board[1][1]);
6116 } else if(main_diagonal.size() == 2) {
6117 win_2.insert(make_pair(*main_diagonal.begin(), *++main_diagonal.begin()));
6118 }
6119 if(leading_diagonal.size() == 1) {
6120 win_1.insert(board[1][1]);
6121 } else if(leading_diagonal.size() == 2) {
6122 win_2.insert(make_pair(*leading_diagonal.begin(), *++leading_diagonal.begin()));
6123 }
6124 cout << win_1.size() << endl
6125 << win_2.size();
6126 return 0;
6127 }
6128 }// namespace acwing1725
6129
6130 namespace acwing4394 {
6131 int main(istream &cin, ostream &cout) {
6132 unsigned n;
6133 unsigned k;
6134 cin >> n >> k;
6135 vector<unsigned> vec(n);
6136 for(unsigned i = 0; i < n; i++) {
6137 cin >> vec[i];
6138 }
6139 unsigned l = 0;
6140 unsigned r = 0;
6141 unsigned max_l = l;
6142 unsigned max_r = r;
6143 vector<unsigned> um(1000001, 0);
6144 unsigned size = 1;
6145 um[vec[0]]++;
6146 while(r < n) {
6147 while(size <= k) {
6148 r++;
6149 if(r < n) {
6150 if(um[vec[r]] == 0) {
6151 size++;
6152 }
6153 if(size > k) {
6154 r--;
6155 size--;
6156 break;
6157 }
6158 um[vec[r]]++;
6159 } else {
6160 cout << max_l + 1 << ' ' << max_r + 1;
6161 return 0;
6162 }
6163 max_r = r;
6164 }
6165
6166 um[vec[l]]--;
6167 if(um[vec[l]] == 0) {
6168 size--;
6169 }
6170 l++;
6171 r++;
6172 if(r < n) {
6173 if(um[vec[r]] == 0) {
6174 size++;
6175 }
6176 um[vec[r]]++;
6177 if(size <= k) {
6178 max_l = l;
6179 max_r = r;
6180 }
6181 } else {
6182 cout << max_l + 1 << ' ' << max_r + 1;
6183 return 0;
6184 }
6185 }
6186 cout << max_l + 1 << ' ' << max_r + 1;
6187 return 0;
6188 }
6189 }// namespace acwing4394
6190
6191 namespace acwing1812 {
6192 int main(istream &cin, ostream &cout) {
6193 int x[2][2];
6194 int y[2][2];
6195 for(int i = 0; i < 2; i++) {
6196 cin >> x[i][0] >> y[i][0] >> x[i][1] >> y[i][1];
6197 }
6198 const int x1 = min(x[0][0], x[1][0]);
6199 const int x2 = max(x[0][1], x[1][1]);
6200 const int y1 = min(y[0][0], y[1][0]);
6201 const int y2 = max(y[0][1], y[1][1]);
6202 const int edge = max(y2 - y1, x2 - x1);
6203 cout << edge * edge;
6204 return 0;
6205 }
6206 }// namespace acwing1812
6207
6208 namespace acwing1800 {
6209 int main(istream &cin, ostream &cout) {
6210 unordered_map<string, unsigned> um;
6211 um["Bessie"] = 0;
6212 um["Elsie"] = 0;
6213 um["Daisy"] = 0;
6214 um["Gertie"] = 0;
6215 um["Annabelle"] = 0;
6216 um["Maggie"] = 0;
6217 um["Henrietta"] = 0;
6218 unsigned short n;
6219 cin >> n;
6220 string name;
6221 unsigned amount;
6222 unsigned minimum = 0;
6223 while(n-- != 0U) {
6224 cin >> name >> amount;
6225 um[name] += amount;
6226 minimum = max(minimum, um[name]);
6227 }
6228 unsigned second_minimum = minimum;
6229 for(auto &[name, amount]: um) {
6230 minimum = min(minimum, amount);
6231 }
6232 for(auto &[name, amount]: um) {
6233 if(amount != minimum && amount < second_minimum) {
6234 second_minimum = amount;
6235 }
6236 }
6237 string ans;
6238 for(auto &[name, amount]: um) {
6239 if(second_minimum == amount) {
6240 if(ans.empty()) {
6241 ans = name;
6242 } else {
6243 cout << "Tie";
6244 return 0;
6245 }
6246 }
6247 }
6248 cout << ans;
6249 return 0;
6250 }
6251 }// namespace acwing1800
6252
6253 namespace acwing1788 {
6254 int main(istream &cin, ostream &cout) {
6255 int n;
6256 unordered_map<int, int> um;
6257 cin >> n;
6258 int ans = 0;
6259 while(n-- != 0) {
6260 int id;
6261 int side;
6262 cin >> id >> side;
6263 if(!um.contains(id)) {
6264 um[id] = side;
6265 } else if(um[id] != side) {
6266 ans++;
6267 um[id] = side;
6268 }
6269 }
6270 cout << ans;
6271 return 0;
6272 }
6273 }// namespace acwing1788
6274
6275 namespace acwing1775 {
6276 int main(istream &cin, ostream &cout) {
6277 int x;
6278 int y;
6279 cin >> x >> y;
6280 int step = 1;
6281 unsigned ans = 0;
6282 int current = x;
6283 while(current != y) {
6284 if((y - current) * (y - (x + step)) < 0) {
6285 ans += abs(y - current);
6286 cout << ans;
6287 return 0;
6288 }
6289 ans += abs(x + step - current);
6290 current = x + step;
6291 step *= -2;
6292 }
6293 cout << ans;
6294 return 0;
6295 }
6296 }// namespace acwing1775
6297
6298 namespace acwing785 {
6299 void qs(vector<int> &vec, int l, int r) {
6300 if(l >= r) {
6301 return;
6302 }
6303 const int x = vec[l + r >> 1];
6304 int lp = l - 1;
6305 int rp = r + 1;
6306 while(lp < rp) {
6307 while(vec[++lp] < x) {}
6308 while(vec[--rp] > x) {}
6309 if(lp < rp) {
6310 swap(vec[lp], vec[rp]);
6311 }
6312 }
6313 qs(vec, l, rp);
6314 qs(vec, rp + 1, r);
6315 }
6316
6317 int main(istream &cin, ostream &cout) {
6318 int n;
6319 cin >> n;
6320 vector<int> vec(n);
6321 for(int i = 0; i < n; i++) {
6322 cin >> vec[i];
6323 }
6324 qs(vec, 0, n - 1);
6325 for(int i = 0; i < n; i++) {
6326 cout << vec[i] << ' ';
6327 }
6328 return 0;
6329 }
6330 }// namespace acwing785
6331
6333 namespace acwing788 {
6334 void ms(vector<int> &arr, int l, int r, int *ans) {
6335 if(l >= r) {
6336 return;
6337 }
6338 const int m = l + r >> 1;
6339 ms(arr, l, m, ans);
6340 ms(arr, m + 1, r, ans);
6341 int i = l;
6342 int j = m + 1;
6343 int p = 0;
6344 vector<int> tmp(r - l + 1);
6345 while(i <= m && j <= r) {
6346 if(arr[i] <= arr[j]) {
6347 tmp[p++] = arr[i++];
6348 } else {
6349 tmp[p++] = arr[j++];
6350 *ans += m - i + 1;
6351 }
6352 }
6353 while(i <= m) {
6354 tmp[p++] = arr[i++];
6355 }
6356 while(j <= r) {
6357 tmp[p++] = arr[j++];
6358 }
6359 for(int i = 0; i < p; i++) {
6360 arr[l + i] = tmp[i];
6361 }
6362 }
6363
6364 int main(istream &cin, ostream &cout) {
6365 int n;
6366 cin >> n;
6367 vector<int> vec(n);
6368 for(int i = 0; i < n; i++) {
6369 cin >> vec[i];
6370 }
6371 int ans = 0;
6372 ms(vec, 0, n - 1, &ans);
6373 cout << ans;
6374 return 0;
6375 }
6376 }// namespace acwing788
6377
6378 namespace acwing789 {
6379
6380 long bfl(const vector<long> &vec, long target) {
6381 int l = 0;
6382 int r = vec.size() - 1;
6383 while(l < r) {
6384 const int m = (l + r + 1) / 2;
6385 if(vec[m] <= target) {
6386 l = m;
6387 } else {
6388 r = m - 1;
6389 }
6390 }
6391 if(vec[l] != target) {
6392 return -1;
6393 }
6394 return l;
6395 }
6396
6397 long bfr(const vector<long> &vec, long target) {
6398 int l = 0;
6399 int r = vec.size() - 1;
6400 while(l < r) {
6401 const int m = (l + r) / 2;
6402 if(vec[m] < target) {
6403 l = m + 1;
6404 } else {
6405 r = m;
6406 }
6407 }
6408 if(vec[l] != target) {
6409 return -1;
6410 }
6411 return l;
6412 }
6413
6414 int main(istream &cin, ostream &cout) {
6415 long n;
6416 long q;
6417 cin >> n >> q;
6418 vector<long> vec(n);
6419 for(long i = 0; i < n; i++) {
6420 cin >> vec[i];
6421 }
6422 for(long i = 0; i < q; i++) {
6423 long k;
6424 cin >> k;
6425 cout << bfr(vec, k) << ' ' << bfl(vec, k) << endl;
6426 }
6427 return 0;
6428 }
6429 }// namespace acwing789
6430
6431 namespace acwing1866 {
6432 int main(istream &cin, ostream &cout) {
6433 int a;
6434 int b;
6435 int c;
6436 int d;
6437 cin >> a >> b >> c >> d;
6438 const int ab = b - a;
6439 const int cd = d - c;
6440 const int dup_d = min(b, max(a, d));
6441 const int dup_c = min(b, max(a, c));
6442 const int sum = ab + cd - (dup_d - dup_c);
6443 cout << sum;
6444 return 0;
6445 }
6446 }// namespace acwing1866
6447
6448 namespace acwing1854 {
6449 int main(istream &cin, ostream &cout) {
6450 int b[4][2];
6451 for(int i = 0; i < 4; i++) {
6452 for(int j = 0; j < 2; j++) {
6453 cin >> b[i][j];
6454 }
6455 }
6456 int ans[3];
6457 ans[2] = b[3][1] - b[3][0];
6458 b[2][0] -= ans[2];
6459 ans[1] = b[2][1] - b[2][0];
6460 b[1][0] -= ans[1];
6461 ans[0] = b[1][1] - b[1][0];
6462 for(int i = 0; i < 3; i++) {
6463 cout << ans[i] << endl;
6464 }
6465 return 0;
6466 }
6467 }// namespace acwing1854
6468
6469 namespace acwing4397 {
6470 bool cmp(const pair<int, int> &a, const pair<int, int> &b) { return a.first > b.first; }
6471
6472 int main(istream &cin, ostream &cout) {
6473 int n;
6474 int k;
6475 cin >> n >> k;
6476 vector<int> a(n);
6477 vector<int> b(n);
6478 vector<pair<int, int>> a_b(n);
6479 for(int i = 0; i < n; i++) {
6480 cin >> a[i];
6481 }
6482 for(int i = 0; i < n; i++) {
6483 cin >> b[i];
6484 a_b[i] = make_pair(a[i] - b[i], i);
6485 }
6486 sort(a_b.begin(), a_b.end(), cmp);
6487 for(int i = 0; i < k; i++) {
6488 if(a_b[i].first > 0) {
6489 a[a_b[i].second] = b[a_b[i].second];
6490 } else {
6491 break;
6492 }
6493 }
6494 long long ans = 0;
6495 for(int i = 0; i < n; i++) {
6496 ans += a[i];
6497 }
6498 cout << ans;
6499 return 0;
6500 }
6501 }// namespace acwing4397
6502
6503 namespace acwing4398 {
6504 void TrieNode::insert(const string &str, int start, string *origin) {
6505 if(!this->nexts.contains(str[start])) {
6506 this->nexts[str[start]] = new TrieNode(str[start]);
6507 }
6508 if(origin != nullptr) {
6509 this->nexts[str[start]]->origin.insert(origin);
6510 }
6511 if(str.length() - start != 1) {
6512 this->nexts[str[start]]->insert(str, start + 1, origin);
6513 }
6514 }
6515
6516 TrieNode *TrieNode::search(const string &str, int start) {
6517 this->ch = this->ch;
6518 if(this->nexts.contains(str[start])) {
6519 if(start + 1 == str.length()) {
6520 return this->nexts[str[start]];
6521 }
6522 return this->nexts[str[start]]->search(str, start + 1);
6523 }
6524 return nullptr;
6525 }
6526
6528 for(const auto [k, v]: this->nexts) {
6529 delete v;
6530 }
6531 }
6532
6533 int main(istream &cin, ostream &cout) {
6534 int n;
6535 int q;
6536 cin >> n;
6537 TrieNode tn(0);
6538 vector<string> f(n);
6539 for(int i = 0; i < n; i++) {
6540 cin >> f[i];
6541 for(int j = 0; j < f[i].length(); ++j) {
6542 tn.insert(f[i], j, &f[i]);
6543 }
6544 }
6545 cin >> q;
6546 for(int i = 0; i < q; i++) {
6547 string s;
6548 cin >> s;
6549 const TrieNode *node = tn.search(s, 0);
6550 if(node == nullptr) {
6551 cout << "0 -" << endl;
6552 } else {
6553 cout << node->origin.size() << ' ' << **node->origin.begin() << endl;
6554 }
6555 }
6556 return 0;
6557 }
6558 }// namespace acwing4398
6559
6560 namespace acwing1842 {
6561 int main(istream &cin, ostream &cout) {
6562 int x;
6563 int y;
6564 int m;
6565 cin >> x >> y >> m;
6566 int ans = 0;
6567 for(int i = 0; y * i <= m; ++i) {
6568 int amount = y * i;
6569 amount += (m - amount) / x * x;
6570 ans = max(ans, amount);
6571 }
6572 cout << ans;
6573 return 0;
6574 }
6575 }// namespace acwing1842
6576
6577 namespace acwing1824 {
6578 int main(istream &cin, ostream &cout) {
6579 int n;
6580 int k;
6581 cin >> n >> k;
6582 vector vec(10010, 0);
6583 unsigned int size;
6584 for(int i = 0; i < n; i++) {
6585 cin >> size;
6586 vec[size]++;
6587 }
6588 vector sum(10010, 0);
6589 for(int i = 1; i < 10010; i++) {
6590 sum[i] = sum[i - 1] + vec[i];
6591 }
6592 int ans = 0;
6593 for(int i = 1; i + k < 10010; i++) {
6594 ans = max(ans, sum[i + k] - sum[i - 1]);
6595 }
6596 cout << ans;
6597 return 0;
6598 }
6599 }// namespace acwing1824
6600
6601 namespace acwing800 {
6602 int main(istream &cin, ostream &cout) {
6603 int n;
6604 int m;
6605 int x;
6606 cin >> n >> m >> x;
6607 vector<int> a(n);
6608 vector<int> b(m);
6609 for(int i = 0; i < n; i++) {
6610 cin >> a[i];
6611 }
6612 for(int i = 0; i < m; i++) {
6613 cin >> b[i];
6614 }
6615 int pa = 0;
6616 int pb = m - 1;
6617 while(a[pa] + b[pb] < x) {
6618 ++pa;
6619 }
6620 for(; pa < n; pa++) {
6621 if(a[pa] + b[pb] == x) {
6622 cout << pa << ' ' << pb;
6623 return 0;
6624 }
6625 while(a[pa] + b[pb] > x) {
6626 --pb;
6627 if(a[pa] + b[pb] == x) {
6628 cout << pa << ' ' << pb;
6629 return 0;
6630 }
6631 }
6632 }
6633 return 0;
6634 }
6635 }// namespace acwing800
6636
6637 namespace acwing2816 {
6638 int main(istream &cin, ostream &cout) {
6639 int n;
6640 int m;
6641 cin >> n >> m;
6642 vector<int> a(n);
6643 vector<int> b(m);
6644 for(int i = 0; i < n; i++) {
6645 cin >> a[i];
6646 }
6647 for(int i = 0; i < m; i++) {
6648 cin >> b[i];
6649 }
6650 int pa = 0;
6651 int pb = 0;
6652 for(; pa < n; ++pa) {
6653 while(pb < m && b[pb] != a[pa]) {
6654 ++pb;
6655 }
6656 if(pb == m) {
6657 cout << "No";
6658 return 0;
6659 }
6660 ++pb;
6661 }
6662 cout << "Yes";
6663 return 0;
6664 }
6665 }// namespace acwing2816
6666
6667 namespace acwing1902 {
6668 int main(istream &cin, ostream &cout) {
6669 int n;
6670 cin >> n;
6671 vector<pair<int, int>> checkpoints(n);
6672 vector<int> d(n - 1);
6673 for(int i = 0; i < n; i++) {
6674 int x;
6675 int y;
6676 cin >> x >> y;
6677 checkpoints[i] = make_pair(x, y);
6678 }
6679 int sum = 0;
6680 for(int i = 0; i < n - 1; i++) {
6681 const auto &[x1, y1] = checkpoints[i];
6682 const auto &[x2, y2] = checkpoints[i + 1];
6683 d[i] = abs(x2 - x1) + abs(y2 - y1);
6684 sum += d[i];
6685 }
6686 int max_diff = 0;
6687 for(int i = 1; i < n - 1; i++) {
6688 const auto &[x1, y1] = checkpoints[i - 1];
6689 const auto &[x2, y2] = checkpoints[i + 1];
6690 const int dist = abs(x2 - x1) + abs(y2 - y1);
6691 int diff = d[i - 1] + d[i] - dist;
6692 max_diff = max(max_diff, diff);
6693 }
6694 cout << sum - max_diff;
6695 return 0;
6696 }
6697 }// namespace acwing1902
6698
6699 namespace acwing3302 {
6700 int main(istream &cin, ostream &cout) {
6701 stack<int> nums;
6702 stack<char> ops;
6703 char ch;
6704 int num;
6705 while((ch = cin.peek()) > 0) {
6706 if(isdigit(ch) != 0) {
6707 cin >> num;
6708 if(!ops.empty() && ops.top() == '*') {
6709 num = nums.top() * num;
6710 nums.pop();
6711 nums.push(num);
6712 ops.pop();
6713 } else if(!ops.empty() && ops.top() == '/') {
6714 num = nums.top() / num;
6715 nums.pop();
6716 nums.push(num);
6717 ops.pop();
6718 } else {
6719 nums.push(num);
6720 }
6721 } else {
6722 cin >> ch;
6723 if(ch == ')') {
6724 vector<char> vec_op;
6725 vector<int> vec_num;
6726 vec_num.push_back(nums.top());
6727 nums.pop();
6728 while(ops.top() != '(') {
6729 vec_op.push_back(ops.top());
6730 vec_num.push_back(nums.top());
6731 ops.pop();
6732 nums.pop();
6733 }
6734 ops.pop();
6735 for(int i = vec_op.size() - 1; i >= 0; --i) {
6736 if(vec_op[i] == '+') {
6737 vec_num.back() += vec_num[i];
6738 } else if(vec_op[i] == '-') {
6739 vec_num.back() -= vec_num[i];
6740 } else {
6741 return 1;
6742 }
6743 }
6744 num = vec_num.back();
6745 if(!ops.empty() && ops.top() == '*') {
6746 num = nums.top() * num;
6747 nums.pop();
6748 nums.push(num);
6749 ops.pop();
6750 } else if(!ops.empty() && ops.top() == '/') {
6751 num = nums.top() / num;
6752 nums.pop();
6753 nums.push(num);
6754 ops.pop();
6755 } else {
6756 nums.push(num);
6757 }
6758 } else {
6759 ops.push(ch);
6760 }
6761 }
6762 }
6763 vector<char> vec_op;
6764 vector<int> vec_num;
6765 vec_num.push_back(nums.top());
6766 nums.pop();
6767 while(!ops.empty()) {
6768 vec_op.push_back(ops.top());
6769 vec_num.push_back(nums.top());
6770 ops.pop();
6771 nums.pop();
6772 }
6773 for(int i = vec_op.size() - 1; i >= 0; --i) {
6774 if(vec_op[i] == '+') {
6775 vec_num.back() += vec_num[i];
6776 } else if(vec_op[i] == '-') {
6777 vec_num.back() -= vec_num[i];
6778 } else {
6779 return 1;
6780 }
6781 }
6782 cout << vec_num.back();
6783 return 0;
6784 }
6785 }// namespace acwing3302
6786
6787 namespace acwing831 {
6788 int main(istream &cin, ostream &cout) {
6789 int n;
6790 int m;
6791 string p;
6792 string s;
6793 cin >> n >> p >> m >> s;
6794 const vector<int> next = get_next(p);
6795 int ip = 0;
6796 int is = 0;
6797 while(ip < n && is < m) {
6798 if(p[ip] == s[is]) {
6799 if(ip == n - 1) {
6800 //整串匹配成功
6801 cout << is - n + 1 << ' ';
6802 ip = next[ip - 1];
6803 } else {
6804 //当前匹配成功
6805 ip++;
6806 is++;
6807 }
6808 } else {
6809 if(ip == 0) {
6810 //开头就匹配失败
6811 is++;
6812 } else {
6813 //匹配失败,但不在开头
6814 ip = next[ip - 1];
6815 }
6816 }
6817 }
6818 return 0;
6819 }
6820
6821 vector<int> get_next(const string &str) {
6822 const int n = str.length();
6823 vector next(n, 0);
6824 int i = 1;
6825 int j = 0;
6826 while(i < n && j < n) {
6827 if(str[i] == str[j]) {
6828 //匹配成功
6829 next[i] = j + 1;
6830 j++;
6831 i++;
6832 } else {
6833 if(j == 0) {
6834 //开头就匹配失败
6835 i++;
6836 } else {
6837 //匹配失败,但不在开头
6838 j = next[j - 1];
6839 }
6840 }
6841 }
6842 return next;
6843 }
6844 }// namespace acwing831
6845
6846 namespace acwing1892 {
6847 int main(istream &cin, ostream &cout) {
6848 int a;
6849 int b;
6850 int n;
6851 cin >> a >> b >> n;
6852 int ans = 1001;
6853 for(int i = 0; i < n; i++) {
6854 int price;
6855 int num;
6856 bool flag = false;
6857 cin >> price >> num;
6858 int city;
6859 for(int j = 0; j < num; j++) {
6860 cin >> city;
6861 if(city == a) {
6862 flag = true;
6863 } else if(flag && city == b) {
6864 ans = min(ans, price);
6865 }
6866 }
6867 }
6868 if(ans == 1001) {
6869 cout << -1;
6870 } else {
6871 cout << ans;
6872 }
6873 return 0;
6874 }
6875 }// namespace acwing1892
6876
6877 namespace acwing1883 {
6878 int main(istream &cin, ostream &cout) {
6879 string s;
6880 string t;
6881 string res;
6882 cin >> s >> t;
6883 const int slen = s.length();
6884 const int tlen = t.length();
6885 //一边添加一边判断
6886 for(int i = 0; i < slen; i++) {
6887 res += s[i];
6888 //当添加到长度大于等于t字符串时,开始比较
6889 //每次从末尾向前匹配
6890 while(res.length() >= tlen && res.substr(res.length() - tlen, tlen) == t) {
6891 //存在t字符串,则删除
6892 res.erase(res.begin() + res.length() - tlen, res.end());
6893 }
6894 }
6895 cout << res;
6896 return 0;
6897 }
6898 }// namespace acwing1883
6899
6900 namespace acwing1995 {
6901 int main(istream &cin, ostream &cout) {
6902 int b;
6903 int e;
6904 cin >> b >> e;
6905 vector<int> pos_b;
6906 vector<int> pos_e;
6907 pos_b.push_back(0);
6908 pos_e.push_back(0);
6909 while(b-- != 0) {
6910 char dir;
6911 int dist;
6912 cin >> dist >> dir;
6913 if(dir == 'L') {
6914 for(int i = 0; i < dist; i++) {
6915 pos_b.push_back(pos_b.back() - 1);
6916 }
6917 } else {
6918 for(int i = 0; i < dist; i++) {
6919 pos_b.push_back(pos_b.back() + 1);
6920 }
6921 }
6922 }
6923 while(e-- != 0) {
6924 char dir;
6925 int dist;
6926 cin >> dist >> dir;
6927 if(dir == 'L') {
6928 for(int i = 0; i < dist; i++) {
6929 pos_e.push_back(pos_e.back() - 1);
6930 }
6931 } else {
6932 for(int i = 0; i < dist; i++) {
6933 pos_e.push_back(pos_e.back() + 1);
6934 }
6935 }
6936 }
6937 const int t = max(pos_e.size(), pos_b.size());
6938 int ans = 0;
6939 bool flag = true;
6940 for(int i = 0; i < t; i++) {
6941 const int pe = i < pos_e.size() ? pos_e[i] : pos_e.back();
6942 const int pb = i < pos_b.size() ? pos_b[i] : pos_b.back();
6943 if(pe == pb) {
6944 if(!flag) {
6945 ans++;
6946 }
6947 flag = true;
6948 } else {
6949 flag = false;
6950 }
6951 }
6952 cout << ans;
6953 return 0;
6954 }
6955 }// namespace acwing1995
6956
6957 namespace acwing143 {
6958 int main(istream &cin, ostream &cout) {
6959 int n;
6960 cin >> n;
6961 vector<string> vec(n);
6962 TrieNode tn;
6963 for(int j = 0; j < n; j++) {
6964 unsigned a;
6965 cin >> a;
6966 ostringstream oss;
6967 for(int i = 30; i >= 0; i--) {
6968 oss << ((a & 1 << i) != 0U ? '1' : '0');
6969 }
6970 string str = oss.str();
6971 vec[j] = str;
6972 tn.insert(str, 0);
6973 }
6974 unsigned maximum = 0;
6975 for(const auto &str: vec) {
6976 const TrieNode *current = &tn;
6977 unsigned ans = 0;
6978 for(int i = 0; i <= 30; i++) {
6979 ans <<= 1;
6980 if(current->next[str[i] - '0' == 0] != nullptr) {
6981 current = current->next[str[i] - '0' == 0];
6982 ans += 1;
6983 } else {
6984 current = current->next[str[i] - '0'];
6985 }
6986 }
6987 maximum = max(maximum, ans);
6988 }
6989 cout << maximum;
6990 return 0;
6991 }
6992
6993 void TrieNode::insert(const string &str, int i) {
6994 if(this->next[str[i] - '0'] == nullptr) {
6995 this->next[str[i] - '0'] = new TrieNode();
6996 this->next[str[i] - '0']->val = str[i] - '0';
6997 }
6998 if(i + 1 < str.length()) {
6999 this->next[str[i] - '0']->insert(str, i + 1);
7000 }
7001 }
7002 }// namespace acwing143
7003
7004 namespace acwing837 {
7005 int main(istream &cin, ostream &cout) {
7006 int n;
7007 int m;
7008 cin >> n >> m;
7009 UnionFind uf(n);
7010 while(m-- != 0) {
7011 string op;
7012 int a;
7013 int b;
7014 cin >> op;
7015 if(op == "C") {
7016 cin >> a >> b;
7017 uf.unite(a - 1, b - 1);
7018 } else if(op == "Q1") {
7019 cin >> a >> b;
7020 cout << (uf.same(a - 1, b - 1) ? "Yes" : "No") << endl;
7021 } else {
7022 cin >> a;
7023 cout << uf.get_size(a - 1) << endl;
7024 }
7025 }
7026 return 0;
7027 }
7028 }// namespace acwing837
7029
7030 namespace acwing240 {
7031 int main(istream &cin, ostream &cout) {
7032 int n;
7033 int k;
7034 cin >> n >> k;
7035 UnionFind uf(n);
7036 int ans = 0;
7037 while(k-- != 0) {
7038 char d;
7039 int x;
7040 int y;
7041 cin >> d >> x >> y;
7042 if(x > n || y > n) {
7043 ans++;
7044 continue;
7045 }
7046 x--;
7047 y--;
7048 const int px = uf.find(x);
7049 const int py = uf.find(y);
7050 if(d == '1') {
7051 if(px == py) {
7052 if((uf.dist[x] - uf.dist[y]) % 3 != 0) {
7053 ans++;
7054 }
7055 } else {
7056 uf.parent[px] = py;
7057 uf.dist[px] = uf.dist[y] - uf.dist[x];
7058 }
7059 } else {
7060 if(x == y) {
7061 ans++;
7062 continue;
7063 }
7064 if(px == py) {
7065 if((uf.dist[x] - uf.dist[y] - 1) % 3 != 0) {
7066 ans++;
7067 }
7068 } else {
7069 uf.parent[px] = py;
7070 uf.dist[px] = uf.dist[y] - uf.dist[x] + 1;
7071 }
7072 }
7073 }
7074 cout << ans;
7075 return 0;
7076 }
7077
7079 parent = vector<int>(n);
7080 dist = vector(n, 0);
7081 for(int i = 0; i < n; i++) {
7082 parent[i] = i;
7083 }
7084 }
7085
7086 int UnionFind::find(int x) {
7087 if(parent[x] != x) {
7088 const int tmp = find(parent[x]);
7089 dist[x] += dist[parent[x]];
7090 parent[x] = tmp;
7091 }
7092 return parent[x];
7093 }
7094 }// namespace acwing240
7095
7096 namespace acwing845 {
7097 int main(istream &cin, ostream &cout) {
7098 array<array<char, 3>, 3> target{};
7099 array<array<char, 3>, 3> grid{};
7100 unordered_set<array<array<char, 3>, 3>, hash> us;
7101 int start_x;
7102 int start_y;
7103 for(int i = 0; i < 9; i++) {
7104 cin >> grid[i / 3][i % 3];
7105 if(grid[i / 3][i % 3] == 'x') {
7106 start_x = i / 3;
7107 start_y = i % 3;
7108 }
7109 target[i / 3][i % 3] = i + '1';
7110 }
7111 target[2][2] = 'x';
7112 queue<tuple<array<array<char, 3>, 3>, int, int, int>> q;
7113 q.push(make_tuple(grid, 0, start_x, start_y));
7114 us.insert(grid);
7115 while(!q.empty()) {
7116 auto [g, step, x, y] = q.front();
7117 q.pop();
7118 if(g == target) {
7119 cout << step;
7120 return 0;
7121 }
7122 pair<int, int> nexts[4] = {
7123 make_pair(x, y + 1),
7124 make_pair(x, y - 1),
7125 make_pair(x + 1, y),
7126 make_pair(x - 1, y)};
7127 for(auto &[nx, ny]: nexts) {
7128 if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
7129 swap(g[nx][ny], g[x][y]);
7130 if(!us.contains(g)) {
7131 us.insert(g);
7132 q.push(make_tuple(g, step + 1, nx, ny));
7133 }
7134 swap(g[nx][ny], g[x][y]);
7135 }
7136 }
7137 }
7138 cout << -1;
7139 return 0;
7140 }
7141
7142 unsigned int hash::operator()(const array<array<char, 3>, 3> &g) const {
7143 unsigned int ret = 0;
7144 for(int i = 0; i < 9; i++) {
7145 char v = g[i / 3][i % 3];
7146 if(v == 'x') {
7147 v = '0';
7148 }
7149 ret *= 10;
7150 ret += v - '0';
7151 }
7152 return ret;
7153 }
7154 }// namespace acwing845
7155
7156 namespace acwing849 {
7157 bool comp::operator()(const pair<int, int> &p1, const pair<int, int> &p2) const { return p1.second > p2.second; }
7158
7159 int main(istream &cin, ostream &cout) {
7160 int n;
7161 int m;
7162 cin >> n >> m;
7163 vector<unordered_map<int, int>> vec(n + 1);
7164 unordered_set<int> ed;
7165 for(int i = 0; i < m; i++) {
7166 int x;
7167 int y;
7168 int z;
7169 cin >> x >> y >> z;
7170 if(vec[x][y] == 0) {
7171 vec[x][y] = z;
7172 } else {
7173 vec[x][y] = min(vec[x][y], z);
7174 }
7175 }
7176 priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
7177 pq.push(make_pair(1, 0));
7178 while(!pq.empty()) {
7179 auto [node, dist] = pq.top();
7180 pq.pop();
7181 if(ed.contains(node)) {
7182 continue;
7183 }
7184 ed.insert(node);
7185 if(node == n) {
7186 cout << dist;
7187 return 0;
7188 }
7189 for(auto [next_node, d]: vec[node]) {
7190 if(!ed.contains(next_node)) {
7191 pq.push(make_pair(next_node, dist + d));
7192 }
7193 }
7194 }
7195 cout << -1;
7196 return 0;
7197 }
7198 }// namespace acwing849
7199
7200 namespace acwing853 {
7201 int main(istream &cin, ostream &cout) {
7202 int n;
7203 int m;
7204 int k;
7205 cin >> n >> m >> k;
7206 vector<tuple<int, int, int>> vec(m);
7207 vector shortest(n + 1, 0x3f3f3f);
7208 shortest[1] = 0;
7209 for(int i = 0; i < m; i++) {
7210 int x;
7211 int y;
7212 int z;
7213 cin >> x >> y >> z;
7214 vec[i] = make_tuple(x, y, z);
7215 }
7216 for(int i = 0; i < k; i++) {
7217 vector<int> shortest_cpy = shortest;
7218 for(auto [x, y, z]: vec) {
7219 shortest[y] = min(shortest[y], shortest_cpy[x] + z);
7220 }
7221 }
7222 if(shortest[n] > 0x3f3f3f / 2) {
7223 cout << "impossible";
7224 } else {
7225 cout << shortest[n];
7226 }
7227 return 0;
7228 }
7229 }// namespace acwing853
7230
7231 namespace acwing851 {
7232 int main(istream &cin, ostream &cout) {
7233 int n;
7234 int m;
7235 cin >> n >> m;
7236 vector<unordered_map<int, int>> g(n + 1);
7237 vector reachable(n + 1, false);
7238 vector shortest(n + 1, 0x3f3f3f);
7239 for(int i = 0; i < m; i++) {
7240 int x;
7241 int y;
7242 int z;
7243 cin >> x >> y >> z;
7244 if(g[x][y] == 0) {
7245 g[x][y] = z;
7246 } else {
7247 g[x][y] = min(g[x][y], z);
7248 }
7249 }
7250 queue<int> q;
7251 unordered_set<int> us;
7252 us.insert(1);
7253 q.push(1);
7254 shortest[1] = 0;
7255 reachable[1] = true;
7256 while(!q.empty()) {
7257 int node = q.front();
7258 q.pop();
7259 us.erase(node);
7260 for(auto [next_node, d]: g[node]) {
7261 reachable[next_node] = true;
7262 if(shortest[next_node] > shortest[node] + d) {
7263 shortest[next_node] = shortest[node] + d;
7264 if(!us.contains(next_node)) {
7265 q.push(next_node);
7266 us.insert(next_node);
7267 }
7268 }
7269 }
7270 }
7271 if(!reachable[n]) {
7272 cout << "impossible";
7273 } else {
7274 cout << shortest[n];
7275 }
7276 return 0;
7277 }
7278 }// namespace acwing851
7279
7280 namespace acwing852 {
7281 int main(istream &cin, ostream &cout) {
7282 int n;
7283 int m;
7284 cin >> n >> m;
7285 vector<unordered_map<int, int>> g(n + 1);
7286 vector cnt(n + 1, 0);
7287 vector shortest(n + 1, 0x3f3f3f);
7288 for(int i = 0; i < m; i++) {
7289 int x;
7290 int y;
7291 int z;
7292 cin >> x >> y >> z;
7293 if(g[x][y] == 0) {
7294 g[x][y] = z;
7295 } else {
7296 g[x][y] = min(g[x][y], z);
7297 }
7298 }
7299 for(int i = 1; i <= n; i++) {
7300 g[0][i] = 0;
7301 }
7302 if(spfa(g, m, n)) {
7303 cout << "Yes";
7304 } else {
7305 cout << "No";
7306 }
7307 return 0;
7308 }
7309
7310 bool spfa(const vector<unordered_map<int, int>> &g, int /*m*/, int n) {
7311 vector cnt(n + 1, 0);
7312 vector shortest(n + 1, 0x3f3f3f);
7313 queue<int> q;
7314 unordered_set<int> us;
7315 q.push(0);
7316 us.insert(0);
7317 shortest[0] = 0;
7318 while(!q.empty()) {
7319 int node = q.front();
7320 q.pop();
7321 us.erase(node);
7322 for(auto [next_node, d]: g[node]) {
7323 if(shortest[next_node] > shortest[node] + d) {
7324 shortest[next_node] = shortest[node] + d;
7325 cnt[next_node] = cnt[node] + 1;
7326 if(cnt[next_node] >= n + 1) {
7327 return true;
7328 }
7329 if(!us.contains(next_node)) {
7330 q.push(next_node);
7331 us.insert(next_node);
7332 }
7333 }
7334 }
7335 }
7336 return false;
7337 }
7338 }// namespace acwing852
7339
7340 namespace acwing854 {
7341 int main(istream &cin, ostream &cout) {
7342 int n;
7343 int m;
7344 int k;
7345 cin >> n >> m >> k;
7346 vector g(n + 1, vector<int>(n + 1, 1e9));
7347 for(int i = 0; i < m; i++) {
7348 int x;
7349 int y;
7350 int z;
7351 cin >> x >> y >> z;
7352 g[x][y] = min(g[x][y], z);
7353 }
7354 for(int i = 1; i <= n; i++) {
7355 g[i][i] = 0;
7356 }
7357 for(int l = 1; l <= n; l++) {
7358 for(int i = 1; i <= n; i++) {
7359 for(int j = 1; j <= n; j++) {
7360 g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
7361 }
7362 }
7363 }
7364 for(int i = 0; i < k; i++) {
7365 int x;
7366 int y;
7367 cin >> x >> y;
7368 if(g[x][y] > 1e9 / 2) {
7369 cout << "impossible" << endl;
7370 } else {
7371 cout << g[x][y] << endl;
7372 }
7373 }
7374 return 0;
7375 }
7376 }// namespace acwing854
7377
7378 namespace acwing858 {
7379 int main(istream &cin, ostream &cout) {
7380 unsigned n;
7381 unsigned m;
7382 cin >> n >> m;
7383 vector g(n + 1, vector(n + 1, INT_MAX));
7384 vector dist(n + 1, INT_MAX);
7385 for(unsigned i = 0; i < m; i++) {
7386 int u;
7387 int v;
7388 int w;
7389 cin >> u >> v >> w;
7390 w = min(w, g[u][v]);
7391 w = min(w, g[v][u]);
7392 g[u][v] = w;
7393 g[v][u] = w;
7394 }
7395 unordered_set<int> us;
7396 int ans = 0;
7397 for(int i = 0; i < n; i++) {
7398 int t = -1;
7399 for(int j = 1; j <= n; j++) {
7400 if(!us.contains(j) && (t == -1 || dist[t] > dist[j])) {
7401 t = j;
7402 }
7403 }
7404 if(i > 0 && dist[t] == INT_MAX) {
7405 cout << "impossible";
7406 return 0;
7407 }
7408 if(i > 0) {
7409 ans += dist[t];
7410 }
7411 for(int j = 1; j <= n; j++) {
7412 dist[j] = min(dist[j], g[t][j]);
7413 }
7414 us.insert(t);
7415 }
7416 cout << ans;
7417 return 0;
7418 }
7419 }// namespace acwing858
7420
7421 namespace acwing859 {
7422 int main(istream &cin, ostream &cout) {
7423 int n;
7424 int m;
7425 cin >> n >> m;
7426 int ans = 0;
7427 int cnt = 1;
7428 vector<edge> edges(m);
7429 for(int i = 0; i < m; i++) {
7430 int u;
7431 int v;
7432 int n;
7433 cin >> edges[i].u >> edges[i].v >> edges[i].w;
7434 }
7435 sort(edges.begin(), edges.end());
7436 UnionFind uf(n + 1);
7437 for(const auto &edge: edges) {
7438 if(!uf.same(edge.u, edge.v)) {
7439 cnt++;
7440 uf.unite(edge.u, edge.v);
7441 ans += edge.w;
7442 }
7443 }
7444 if(cnt < n) {
7445 cout << "impossible";
7446 } else {
7447 cout << ans;
7448 }
7449 return 0;
7450 }
7451
7452 bool edge::operator<(const edge &e) const { return w < e.w; }
7453 }// namespace acwing859
7454
7455 namespace acwing860 {
7456 int main(istream &cin, ostream &cout) {
7457 int n;
7458 int m;
7459 cin >> n >> m;
7460 vector g(n + 1, unordered_set<int>());
7461 vector color(n + 1, 3);
7462 for(int i = 0; i < m; i++) {
7463 int u;
7464 int v;
7465 cin >> u >> v;
7466 g[u].insert(v);
7467 g[v].insert(u);
7468 }
7469 for(int i = 1; i <= n; i++) {
7470 if(color[i] == 3) {
7471 if(!dfs(g, i, color, 0)) {
7472 cout << "No";
7473 return 0;
7474 }
7475 }
7476 }
7477 cout << "Yes";
7478 return 0;
7479 }
7480
7481 bool dfs(vector<unordered_set<int>> &g, int node, vector<int> &color, int c) {
7482 color[node] = c;
7483 for(const auto sibling: g[node]) {
7484 if(color[sibling] == 3) {
7485 if(!dfs(g, sibling, color, c == 0)) {
7486 return false;
7487 }
7488 } else if(color[sibling] == c) {
7489 return false;
7490 }
7491 }
7492 return true;
7493 }
7494 }// namespace acwing860
7495
7496 namespace acwing861 {
7497 int main(istream &cin, ostream &cout) {
7498 int n1;
7499 int n2;
7500 int m;
7501 cin >> n1 >> n2 >> m;
7502 int ans = 0;
7503 vector<unordered_set<int>> g(n1 + 1);
7504 vector match(n2 + 1, 0);
7505 vector st(n2 + 1, false);
7506 for(int i = 0; i < m; i++) {
7507 int u;
7508 int v;
7509 cin >> u >> v;
7510 g[u].insert(v);
7511 }
7512 for(int i = 1; i <= n1; i++) {
7513 st = vector(n2 + 1, false);
7514 if(find(g, i, st, match)) {
7515 ans++;
7516 }
7517 }
7518 cout << ans;
7519 return 0;
7520 }
7521
7522 bool find(vector<unordered_set<int>> &g, int x, vector<bool> &st, vector<int> &match) {
7523 for(const auto y: g[x]) {
7524 if(!st[y]) {
7525 st[y] = true;
7526 if(match[y] == 0 || find(g, match[y], st, match)) {
7527 match[y] = x;
7528 return true;
7529 }
7530 }
7531 }
7532 return false;
7533 }
7534 }// namespace acwing861
7535
7536 namespace acwing3373 {
7537 int main(istream &cin, ostream &cout) {
7538 string input;
7539 while(cin >> input) {
7540 if(input == "0") {
7541 cout << 0 << endl;
7542 continue;
7543 }
7544 unsigned short promotion = 0;
7545 vector<unsigned short> result = vector<unsigned short>();
7546 vector<unsigned short> charvec = vector<unsigned short>(input.length());
7547 for(auto i = 0; i < input.length(); i++) {
7548 charvec[i] = input[i] - '0';
7549 }
7550 vector<unsigned short> next = vector<unsigned short>();
7551 while(!charvec.empty() && !(charvec.size() == 1 && charvec[0] == 0)) {
7552 for(unsigned short d: charvec) {
7553 unsigned short digit = promotion * 10 + d;
7554 if(digit / 2 > 0 || !next.empty()) {
7555 next.push_back(digit / 2);
7556 }
7557 promotion = digit % 2;
7558 }
7559 result.push_back(promotion);
7560 promotion = 0;
7561 charvec = next;
7562 next.clear();
7563 }
7564 for(auto i = result.rbegin(); i != result.rend(); i++) {
7565 cout << *i;
7566 }
7567 cout << endl;
7568 }
7569 return 0;
7570 }
7571 }// namespace acwing3373
7572}// namespace acwing
int main(int argc, char **argv)
定义 main.cpp:5
void flood(point first, bool occupy[55][55], unordered_set< point, pointhash, pointequal > *edge, char cowhide[55][55], int n, int m)
int bfs(point start, int **field, int max_x, int max_y)
AcWing 1929. 镜子田地
direction operator!(const direction &d)
取反方向
direction reflect(direction d, char mirror)
方向经过镜子反射后的变化
AcWing 78. 左旋转字符串
AcWing 16. 替换空格
AcWing 87. 把字符串转换成整数
AcWing 84. 求1+2+…+n
AcWing 35. 反转链表
AcWing 28. 在O(1)时间删除链表结点
AcWing 66. 两个链表的第一个公共结点
AcWing 36. 合并两个排序的链表
AcWing 29. 删除链表中重复的节点
AcWing 67. 数字在排序数组中出现的次数
AcWing 53. 最小的k个数
AcWing 68. 0到n-1中缺失的数字
AcWing 75. 和为S的两个数字
AcWing 32. 调整数组顺序使奇数位于偶数前面
AcWing 51. 数字排列
AcWing 17. 从尾到头打印链表
AcWing 26. 二进制中1的个数
AcWing 20. 用两个栈实现队列
AcWing 3358. 放养但没有完全放养
AcWing 3370. 牛年
AcWing 3745. 牛的学术圈 I
AcWing 1459. 奶牛体操
AcWing 1442. 单词处理器
AcWing 4314. 三元组
AcWing 4315. 两个数列
水桶传递队列
阻挡广告牌
阻挡广告牌 II
组队井字游戏
最长连续子序列
不做最后一个!
牛为什么过马路
void qs(vector< int > &vec, int l, int r)
逆序对的数量
void ms(vector< int > &arr, int l, int r, int *ans)
long bfl(const vector< long > &vec, long target)
long bfr(const vector< long > &vec, long target)
bool cmp(const pair< int, int > &a, const pair< int, int > &b)
查询字符串
钻石收藏家
数组元素的目标和
判断子序列
表达式求值
vector< int > get_next(const string &str)
见面与问候
最大异或对
连通块中点的数量
Dijkstra求最短路 I
有边数限制的最短路
spfa求最短路
spfa判断负环
bool spfa(const vector< unordered_map< int, int > > &g, int, int n)
Floyd求最短路
Prim算法求最小生成树
Kruskal算法求最小生成树
染色法判定二分图
bool dfs(vector< unordered_set< int > > &g, int node, vector< int > &color, int c)
二分图的最大匹配
bool find(vector< unordered_set< int > > &g, int x, vector< bool > &st, vector< int > &match)
ListNode * next
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
size_t operator()(const point &) const
bool operator()(const point &, const point &) const
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int dfs(bool stage, char horseshoes[5][5], const bool picked[5][5], int count, int level, int x, int y, int n)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
trie_node(int val, trie_node *father)
void insert(string str)
反向插入
trie_node * nexts[10]
子节点
static int main(istream &, ostream &)
static bool cmp(char x, char y)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
bool operator<(const path &p) const
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
bool * decompress(unsigned int status) const
unsigned int compress(const bool *) const
int main(istream &, ostream &)
unsigned int get_next(unsigned int status)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &, ostream &)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static unsigned int no2(unsigned long long a)
static unsigned int no3(unsigned long long a)
static bool cmp(unsigned long long a, unsigned long long b)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
unsigned int x
横坐标
unsigned int y
纵坐标
unsigned long operator()(const step &) const
bool operator()(const step &, const step &) const
unsigned int right_map[1000][1000]
在每格向右时可以被反射的次数
char mirrors[1000][1000]
镜子
unsigned int count_reflect(direction d, unsigned int x, unsigned int y)
获取反射的次数
unsigned short n
行数
int main(istream &cin, ostream &cout)
unsigned int down_map[1000][1000]
在每格向下时可以被反射的次数
unsigned int up_map[1000][1000]
在每格向上时可以被反射的次数
unsigned(* get_record(direction d))[1000]
获取记录类型
unsigned short m
列数
unsigned int left_map[1000][1000]
在每格向左时可以被反射的次数
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static unsigned long long get_min(vector< char > ops, vector< unsigned long long > vec)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
bool operator()(const pair< unsigned int, unsigned int > &left, const pair< unsigned int, unsigned int > &right) const
bool operator()(const pair< unsigned int, unsigned int > &left, const pair< unsigned int, unsigned int > &right) const
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
int main(istream &cin, ostream &cout)
vector< pair< int, int > > back
bool check(int len) const
vector< char > ops
vector< pair< int, int > > forth
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
int main(istream &cin, ostream &cout)
bool ** connected
邻接矩阵存图
int m
女孩数量
int * match
记录当前女孩所对应的男孩
bool * found
记录女孩是否已经被找到
int n
男孩数量
int * a
男孩魅力值
int * b
女孩魅力值
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
bool operator<(const cow &) const
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static unsigned int str2int(const string &str)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int fact(int n)
static int abs(int n)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int max(int x, int y)
static double add(double x, double y)
static int main(istream &cin, ostream &cout)
static int gcd(int a, int b)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int sum(int l, int r)
static int main(istream &cin, ostream &cout)
static void swap(int &x, int &y)
static int main(istream &cin, ostream &cout)
static int lcm(int a, int b)
static int main(istream &cin, ostream &cout)
static void print(int a[], int size, ostream &cout)
static void copy(const int a[], int b[], int size)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static void print2D(int a[][100], int row, int col, ostream &cout)
static int main(istream &cin, ostream &cout)
static void print(char str[], ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static string dfs(int i, bool free, unordered_map< int, int > um, string &b)
static int factorial(int n)
static int main(istream &cin, ostream &cout)
static void reverse(int a[], int size)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int fibb(int n)
static int main(istream &cin, ostream &cout)
static int get_unique_count(int a[], int n)
返回数组前n个数中的不同数的个数
static int main(istream &cin, ostream &cout)
static void sort(int a[], int l, int r)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static void dfs(vector< int > &vec, set< int > &s, ostream &cout)
static string leftRotateString(string str, int n)
static string replaceSpaces(string &str)
static int strToInt(string str)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
map< int, TreeNode * > nexts
unordered_map< int, int > position
int dfs(vector< int > *vec, TreeNode *node)
int main(istream &cin, ostream &cout)
unordered_map< int, TreeNode * > um
unordered_map< int, int > size_tree
static ListNode * reverseList(ListNode *head)
static void deleteNode(ListNode *node)
static ListNode * findFirstCommonNode(ListNode *headA, ListNode *headB)
static ListNode * merge(ListNode *l1, ListNode *l2)
static ListNode * deleteDuplication(ListNode *head)
static int getNumberOfK(vector< int > &nums, int k)
static vector< int > getLeastNumbers_Solution(vector< int > input, int k)
static int getMissingNumber(vector< int > &nums)
static vector< int > findNumbersWithSum(vector< int > &nums, int target)
static void reOrderArray(vector< int > &array)
static vector< vector< int > > permutation(vector< int > &nums)
static void dfs(const vector< int > &vec, vector< int > nums, set< vector< int > > &s)
static vector< int > printListReversingly(ListNode *head)
int pop()
Removes the element from in front of queue and returns that element
int peek()
Get the front element
bool empty() const
Returns whether the queue is empty
void push(int x)
Push element x to the back of queue
MyQueue()
Initialize your data structure here
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
static int main(istream &cin, ostream &cout)
vector< cow * > previous
cow(string name, int val, int zodiac)
status(int len, pair< int, int > current, pair< int, int > target)
bool operator<(const status &s) const
unordered_map< char, TrieNode * > nexts
TrieNode * search(const string &str, int start)
void insert(const string &str, int start, string *origin)
unordered_set< string * > origin
void insert(const string &str, int i)
unsigned int operator()(const array< array< char, 3 >, 3 > &g) const
bool operator()(const pair< int, int > &p1, const pair< int, int > &p2) const
bool operator<(const edge &e) const
void insert(const string &str)
并查集
void unite(int x, int y)
int get_size(int x)
bool same(int x, int y)
int find(int x)