1907.md (6472B)
1 Source: https://codeforces.com/blog/entry/123012 2 3 [1907A - Rook](/contest/1907/problem/A "Codeforces Round 913 (Div. 3)") 4 5 Idea: [pashka](/profile/pashka "International Grandmaster pashka") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 for _ in range(int(input())): 15 s = input() 16 for c in "abcdefgh": 17 if c != s[0]: 18 print(c + s[1], end=' ') 19 for c in "12345678": 20 if c != s[1]: 21 print(s[0] + c, end=' ') 22 print() 23 ``` 24 25 [1907B - YetnotherrokenKeoard](/contest/1907/problem/B "Codeforces Round 913 (Div. 3)") 26 27 Idea: [pashka](/profile/pashka "International Grandmaster pashka"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 28 29 **Tutorial** 30 31 Tutorial is loading... 32 33 **Solution** 34 35 ``` 36 for _ in range(int(input())): 37 s = list(input()) 38 n = len(s) 39 upper = [] 40 lower = [] 41 for i in range(n): 42 if s[i] == 'b': 43 s[i] = '' 44 if lower: 45 s[lower.pop()] = '' 46 continue 47 if s[i] == 'B': 48 s[i] = '' 49 if upper: 50 s[upper.pop()] = '' 51 continue 52 if 'a' <= s[i] <= 'z': 53 lower += [i] 54 else: 55 upper += [i] 56 print(''.join(s)) 57 ``` 58 59 [1907C - Removal of Unattractive Pairs](/contest/1907/problem/C "Codeforces Round 913 (Div. 3)") 60 61 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 62 63 **Tutorial** 64 65 Tutorial is loading... 66 67 **Solution** 68 69 ``` 70 orda = ord('a') 71 72 def solve(): 73 n = int(input()) 74 cnt = [0] * 26 75 for c in input(): 76 cnt[ord(c) - orda] += 1 77 mx = max(cnt) 78 print(max(n % 2, 2 * mx - n)) 79 80 for _ in range(int(input())): 81 solve() 82 ``` 83 84 [1907D - Jumping Through Segments](/contest/1907/problem/D "Codeforces Round 913 (Div. 3)") 85 86 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution** 93 94 ``` 95 def solve(): 96 n = int(input()) 97 seg = [list(map(int, input().split())) for x in range(n)] 98 99 def check(k): 100 ll, rr = 0, 0 101 for e in seg: 102 ll = max(ll - k, e[0]) 103 rr = min(rr + k, e[1]) 104 if ll > rr: 105 return False 106 return True 107 108 l, r = -1, 10 ** 9 109 while r - l > 1: 110 mid = (r + l) // 2 111 if check(mid): 112 r = mid 113 else: 114 l = mid 115 print(r) 116 117 for _ in range(int(input())): 118 solve() 119 ``` 120 121 [1907E - Good Triples](/contest/1907/problem/E "Codeforces Round 913 (Div. 3)") 122 123 Idea: [pashka](/profile/pashka "International Grandmaster pashka") 124 125 **Tutorial** 126 127 Tutorial is loading... 128 129 **Solution** 130 131 ``` 132 t = int(input()) 133 for _ in range(t): 134 n = int(input()) 135 cnt = 1 136 while n > 0: 137 d = n % 10 138 n //= 10 139 mul = 0 140 for i in range(d + 1): 141 for j in range(d + 1): 142 if d - i - j >= 0: 143 mul += 1 144 cnt *= mul 145 print(cnt) 146 ``` 147 148 [1907F - Shift and Reverse](/contest/1907/problem/F "Codeforces Round 913 (Div. 3)") 149 150 Idea: [pashka](/profile/pashka "International Grandmaster pashka") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution** 157 158 ``` 159 t = int(input()) 160 for _ in range(t): 161 n = int(input()) 162 a = list(map(int, input().split())) 163 a = list(reversed(a))*2 164 p = [0] 165 q = [0] 166 for i in range(n*2-1): 167 p.append(p[-1]+1 if a[i]>=a[i+1] else 0) 168 q.append(q[-1]+1 if a[i]<=a[i+1] else 0) 169 minn = 1000000 170 for i in range(n-1,len(p)): 171 if p[i] == n-1: 172 minn = min(minn, i-n+1, len(p)-i+1) 173 if q[i] == n-1: 174 minn = min(minn, len(p)-i, i-n+2) 175 print(-1 if minn == 1000000 else minn) 176 ``` 177 178 [1907G - Lights](/contest/1907/problem/G "Codeforces Round 913 (Div. 3)") 179 180 Idea: [pashka](/profile/pashka "International Grandmaster pashka") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 #define long long long int 192 #define DEBUG 193 using namespace std; 194 195 // @author: pashka 196 197 void solve(){ 198 int n; 199 cin >> n; 200 vector<bool> s(n); 201 { 202 string ss; 203 cin >> ss; 204 for (int i = 0; i < n; i++) { 205 s[i] = ss[i] == '1'; 206 } 207 } 208 vector<int> a(n); 209 for (int i = 0; i < n; i++) { 210 cin >> a[i]; 211 a[i]--; 212 } 213 214 vector<int> res; 215 vector<int> d(n); 216 for (int i = 0; i < n; i++) { 217 d[a[i]]++; 218 } 219 vector<int> z; 220 for (int i = 0; i < n; i++) { 221 if (d[i] == 0) z.push_back(i); 222 } 223 224 for (int i = 0; i < (int)z.size(); i++) { 225 int x = z[i]; 226 int y = a[x]; 227 if (s[x]) { 228 res.push_back(x); 229 s[x] = !s[x]; 230 s[y] = !s[y]; 231 } 232 d[y]--; 233 if (d[y] == 0) { 234 z.push_back(y); 235 } 236 } 237 238 vector<bool> u(n); 239 for (int i = 0; i < n; i++) { 240 if (s[i] && !u[i]) { 241 int x = i; 242 vector<int> p; 243 vector<bool> ps; 244 int c = 0; 245 while (!u[x]) { 246 p.push_back(x); 247 ps.push_back(s[x]); 248 c += s[x]; 249 u[x] = true; 250 x = a[x]; 251 } 252 int k = p.size(); 253 p.push_back(x); 254 ps.push_back(s[x]); 255 if (c % 2 == 1) { 256 cout << -1; 257 return; 258 } 259 vector<int> v1; 260 vector<bool> ps1 = ps; 261 for (int j = 0; j < k; j++) { 262 if (j == 0 || ps1[j]) { 263 v1.push_back(p[j]); 264 ps1[j] = !ps1[j]; 265 ps1[j + 1] = !ps1[j + 1]; 266 } 267 } 268 vector<int> v2; 269 vector<bool> ps2 = ps; 270 for (int j = 0; j < k; j++) { 271 if (j != 0 && ps2[j]) { 272 v2.push_back(p[j]); 273 ps2[j] = !ps2[j]; 274 ps2[j + 1] = !ps2[j + 1]; 275 } 276 } 277 if (v1.size() < v2.size()) { 278 for (auto x : v1) { 279 res.push_back(x); 280 } 281 } else { 282 for (auto x : v2) { 283 res.push_back(x); 284 } 285 } 286 } 287 } 288 cout << res.size() << "\n"; 289 for (auto x : res) cout << x + 1 << " "; 290 } 291 292 int main() { 293 int t; 294 cin >> t; 295 for(int _ = 0; _ < t; ++_){ 296 solve(); 297 cout << "\n"; 298 } 299 return 0; 300 } 301 ```