codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1644.md (4221B)


      1 Source: https://codeforces.com/blog/entry/100227
      2 
      3 [1644A - Doors and Keys](/contest/1644/problem/A "Educational Codeforces Round 123 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	s = input()
     16 	for (d, k) in zip("RGB", "rgb"):
     17 		if s.find(d) < s.find(k):
     18 			print("NO")
     19 			break
     20 	else:
     21 		print("YES")
     22 ```
     23 
     24 [1644B - Anti-Fibonacci Permutation](/contest/1644/problem/B "Educational Codeforces Round 123 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (Neon)**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36 
     37 using namespace std;
     38 
     39 int main() {
     40 	int t;
     41 	cin >> t;
     42 	while (t--) {
     43 		int n;
     44 		cin >> n;
     45 		for (int i = 1; i <= n; ++i) {
     46 			cout << i;
     47 			for (int j = n; j > 0; --j) if (i != j)
     48 				cout << ' ' << j;
     49 			cout << '\n';
     50 		}
     51 	}
     52 }
     53 ```
     54 
     55 [1644C - Increase Subarray Sums](/contest/1644/problem/C "Educational Codeforces Round 123 (Rated for Div. 2)")
     56 
     57 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     58 
     59 **Tutorial**
     60 
     61 Tutorial is loading...
     62 
     63 **Solution (awoo)**
     64 
     65 ```
     66 INF = 10**9
     67 
     68 for _ in range(int(input())):
     69 	n, x = map(int, input().split())
     70 	a = list(map(int, input().split()))
     71 	mx = [-INF for i in range(n + 1)]
     72 	mx[0] = 0
     73 	for l in range(n):
     74 		s = 0
     75 		for r in range(l, n):
     76 			s += a[r]
     77 			mx[r - l + 1] = max(mx[r - l + 1], s)
     78 	ans = [0 for i in range(n + 1)]
     79 	for k in range(n + 1):
     80 		bst = 0
     81 		for i in range(n + 1):
     82 			bst = max(bst, mx[i] + min(k, i) * x)
     83 		ans[k] = bst
     84 	print(" ".join([str(x) for x in ans]))
     85 ```
     86 
     87 [1644D - Cross Coloring](/contest/1644/problem/D "Educational Codeforces Round 123 (Rated for Div. 2)")
     88 
     89 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution 1 (awoo)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 
    100 #define forn(i, n) for (int i = 0; i < int(n); i++)
    101 
    102 using namespace std;
    103 
    104 const int MOD = 998244353;
    105 
    106 int main() {
    107 	int t;
    108 	scanf("%d", &t);
    109 	forn(_, t){
    110 		int n, m, k, q;
    111 		scanf("%d%d%d%d", &n, &m, &k, &q);
    112 		vector<int> xs(q), ys(q);
    113 		forn(i, q) scanf("%d%d", &xs[i], &ys[i]);
    114 		int ans = 1;
    115 		set<int> ux, uy;
    116 		for (int i = q - 1; i >= 0; --i){
    117 			bool fl = false;
    118 			if (!ux.count(xs[i])){
    119 				ux.insert(xs[i]);
    120 				fl = true;
    121 			}
    122 			if (!uy.count(ys[i])){
    123 				uy.insert(ys[i]);
    124 				fl = true;
    125 			}
    126 			if (fl){
    127 				ans = ans * 1ll * k % MOD;
    128 			}
    129 			if (int(ux.size()) == n || int(uy.size()) == m){
    130 				break;
    131 			}
    132 		}
    133 		printf("%d\n", ans);
    134 	}
    135 	return 0;
    136 }
    137 ```
    138 
    139 **Solution 2 (awoo)**
    140 
    141 ```
    142 from sys import stdin, stdout
    143 
    144 MOD = 998244353
    145 
    146 ux = []
    147 uy = []
    148 for _ in range(int(stdin.readline())):
    149 	n, m, k, q = map(int, stdin.readline().split())
    150 	while len(ux) < n:
    151 		ux.append(False)
    152 	while len(uy) < m:
    153 		uy.append(False)
    154 	xs = [-1 for i in range(q)]
    155 	ys = [-1 for i in range(q)]
    156 	for i in range(q):
    157 		x, y = map(int, stdin.readline().split())
    158 		xs[i] = x - 1
    159 		ys[i] = y - 1
    160 	cx = 0
    161 	cy = 0
    162 	ans = 1
    163 	for i in range(q - 1, -1, -1):
    164 		fl = False
    165 		if not ux[xs[i]]:
    166 			ux[xs[i]] = True
    167 			cx += 1
    168 			fl = True
    169 		if not uy[ys[i]]:
    170 			uy[ys[i]] = True
    171 			cy += 1
    172 			fl = True
    173 		if fl:
    174 			ans = ans * k % MOD
    175 		if cx == n or cy == m:
    176 			break
    177 	for i in range(q):
    178 		ux[xs[i]] = False
    179 		uy[ys[i]] = False
    180 	stdout.write(str(ans) + "\n")
    181 ```
    182 
    183 [1644E - Expand the Path](/contest/1644/problem/E "Educational Codeforces Round 123 (Rated for Div. 2)")
    184 
    185 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    186 
    187 **Tutorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Solution (awoo)**
    192 
    193 ```
    194 def calc(s, n):
    195 	ld = s.find('R')
    196 	res = ld * (n - 1)
    197 	y = 0
    198 	for i in range(len(s) - 1, ld - 1, -1):
    199 		if s[i] == 'D':
    200 			res += y
    201 		else:
    202 			y += 1
    203 	return res
    204 
    205 for _ in range(int(input())):
    206 	n = int(input())
    207 	s = input()
    208 	if s.count(s[0]) == len(s):
    209 		print(n)
    210 		continue
    211 	ans = n * n
    212 	ans -= calc(s, n)
    213 	ans -= calc(''.join(['D' if c == 'R' else 'R' for c in s]), n)
    214 	print(ans)
    215 ```
    216 
    217 [1644F - Basis](/contest/1644/problem/F "Educational Codeforces Round 123 (Rated for Div. 2)")
    218 
    219 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    220 
    221 **Tutorial**
    222 
    223 Tutorial is loading...