1838.md (5734B)
1 Source: https://codeforces.com/blog/entry/116995 2 3 [1838A - Blackboard List](/contest/1838/problem/A "Codeforces Round 877 (Div. 2)") 4 5 **Solution** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int main() { 16 17 int t; cin >> t; 18 for(int tc = 1; tc <= t; ++tc) { 19 20 int n; cin >> n; 21 int mn = INT_MAX, mx = INT_MIN; 22 23 for(int i = 0; i < n; ++i) { 24 int x; cin >> x; 25 mn = min(mn, x); 26 mx = max(mx, x); 27 } 28 29 if(mn < 0) cout << mn << '\n'; 30 else cout << mx << '\n'; 31 } 32 } 33 ``` 34 35 [1838B - Minimize Permutation Subarrays](/contest/1838/problem/B "Codeforces Round 877 (Div. 2)") 36 37 **Solution** 38 39 Tutorial is loading... 40 41 **Code** 42 43 ``` 44 #include <bits/stdc++.h> 45 using namespace std; 46 #define N 200010 47 48 int idx[N]; 49 50 int main() { 51 52 int t; cin >> t; 53 for(int tc = 1; tc <= t; ++tc) { 54 55 int n; cin >> n; 56 57 for(int i = 1; i <= n; ++i) { 58 int x; cin >> x; 59 idx[x] = i; 60 } 61 62 if(idx[n] < min(idx[1], idx[2])) { 63 cout << idx[n] << ' ' << min(idx[1], idx[2]) << '\n'; 64 } else if(idx[n] > max(idx[1], idx[2])) { 65 cout << idx[n] << ' ' << max(idx[1], idx[2]) << '\n'; 66 } else { 67 cout << idx[1] << ' ' << idx[2] << '\n'; 68 } 69 } 70 } 71 ``` 72 73 [1838C - No Prime Differences](/contest/1838/problem/C "Codeforces Round 877 (Div. 2)") 74 75 **Solution** 76 77 Tutorial is loading... 78 79 **Code** 80 81 ``` 82 #include <bits/stdc++.h> 83 using namespace std; 84 85 int main() { 86 87 int t; cin >> t; 88 for(int tc = 1; tc <= t; ++tc) { 89 90 int n, m; cin >> n >> m; 91 92 for(int i = 0; i < n; ++i) { 93 for(int j = 0; j < m; ++j) { 94 if(i % 2 == 0) cout << (n / 2 + i / 2) * m + j + 1 << ' '; 95 else cout << (i / 2) * m + j + 1 << ' '; 96 } 97 cout << '\n'; 98 } 99 } 100 } 101 ``` 102 103 [1838D - Bracket Walk](/contest/1838/problem/D "Codeforces Round 877 (Div. 2)") 104 105 **Solution** 106 107 Tutorial is loading... 108 109 **Code** 110 111 ``` 112 #include <bits/stdc++.h> 113 using namespace std; 114 115 int main() { 116 117 int n, q; string s; 118 cin >> n >> q >> s; 119 120 set<int> a; 121 122 for(int i = 1; i <= n; ++i) 123 if((i % 2) != (s[i - 1] == '(')) 124 a.insert(i); 125 126 while(q--) { 127 int i; cin >> i; 128 129 if(a.count(i)) a.erase(i); 130 else a.insert(i); 131 132 if(n % 2) cout << "NO\n"; 133 else if(a.size() && (*a.begin() % 2 || !(*a.rbegin() % 2))) cout << "NO\n"; 134 else cout << "YES\n"; 135 } 136 } 137 ``` 138 139 [1838E - Count Supersequences](/contest/1838/problem/E "Codeforces Round 877 (Div. 2)") 140 141 **Solution** 142 143 Tutorial is loading... 144 145 **Code** 146 147 ``` 148 #include <bits/stdc++.h> 149 using namespace std; 150 151 typedef long long int ll; 152 153 ll M = 1000000007; 154 155 ll pw(ll a, ll p) { return p ? pw(a * a % M, p / 2) * (p & 1 ? a : 1) % M : 1; } 156 157 ll inv(ll a) { return pw(a, M - 2); } 158 159 int main() { 160 161 ll t; cin >> t; 162 for(ll tc = 1; tc <= t; ++tc) { 163 164 ll n, m, k, ai; 165 cin >> n >> m >> k; 166 for(ll i = 0; i < n; ++i) cin >> ai; 167 168 ll ans = pw(k, m), mCi = 1; 169 170 for(ll i = 0; i < n; ++i) { 171 ans = (ans + M - mCi * pw(k - 1, m - i) % M) % M; 172 mCi = mCi * (m - i) % M * inv(i + 1) % M; 173 } 174 175 cout << ans << '\n'; 176 } 177 } 178 ``` 179 180 [1838F - Stuck Conveyor](/contest/1838/problem/F "Codeforces Round 877 (Div. 2)") 181 182 **Solution** 183 184 Tutorial is loading... 185 186 **Code** 187 188 ``` 189 #include <bits/stdc++.h> 190 using namespace std; 191 192 char grid[110][110]; 193 int n; 194 vector<pair<int, int>> snake; 195 map<pair<int, int>, char> getChar = { 196 {{1, 0}, 'v'}, 197 {{-1, 0}, '^'}, 198 {{0, 1}, '>'}, 199 {{0, -1}, '<'} 200 }; 201 202 pair<pair<int, int>, char> getBeltAndDir(pair<int, int> p) { 203 if(p.first == -1) return {p, 'X'}; 204 pair<int, int> q = p; 205 206 if(p.first == 0) q.first++; 207 if(p.second == 0) q.second++; 208 if(p.first > n) q.first--; 209 if(p.second > n) q.second--; 210 211 return {q, getChar[{p.first - q.first, p.second - q.second}]}; 212 } 213 214 pair<pair<int, int>, char> query(int idx) { 215 216 cout << "? " << snake[idx].first << ' ' << snake[idx].second << endl; 217 218 for(int i = 1; i <= n; ++i) { 219 for(int j = 1; j <= n; ++j) 220 cout << grid[i][j]; 221 cout << endl; 222 } 223 224 int i, j; cin >> i >> j; 225 226 return getBeltAndDir({i, j}); 227 } 228 229 void fillGrid() { 230 for(int i = 0; i < n * n; ++i) { 231 int dx = snake[i + 1].first - snake[i].first; 232 int dy = snake[i + 1].second - snake[i].second; 233 234 grid[snake[i].first][snake[i].second] = getChar[{dx, dy}]; 235 } 236 } 237 238 int main() { 239 cin >> n; 240 241 for(int i = 1; i <= n; ++i) 242 if(i % 2 == 0) 243 for(int j = n; j >= 1; --j) 244 snake.emplace_back(i, j); 245 else 246 for(int j = 1; j <= n; ++j) 247 snake.emplace_back(i, j); 248 249 snake.emplace_back(n + 1, (n % 2 ? n : 1)); 250 fillGrid(); 251 252 auto ans = query(0); 253 254 if(ans.second != 'X') { 255 256 snake.pop_back(); 257 reverse(snake.begin(), snake.end()); 258 snake.emplace_back(0, 1); 259 fillGrid(); 260 261 ans = query(0); 262 } 263 264 if(ans.second == 'X') { 265 266 int id = 0; 267 for(int j = 13; j >= 0; --j) 268 if(id + (1 << j) < n * n && query(id + (1 << j)).second == 'X') 269 id += (1 << j); 270 271 ans.first = snake[id]; 272 273 for(int i = 1; i <= n; ++i) 274 for(int j = 1; j <= n; ++j) 275 if(i < ans.first.first) grid[i][j] = '^'; 276 else if(i > ans.first.first) grid[i][j] = 'v'; 277 else grid[i][j] = j < ans.first.second ? '<' : '>'; 278 279 ans.second = query(id).second; 280 } 281 282 cout << "! " << ans.first.first << ' ' << ans.first.second << ' ' << ans.second << endl; 283 } 284 ```