2043.md (7059B)
1 Source: https://codeforces.com/blog/entry/137801 2 3 [2043A - Coin Transformation](/contest/2043/problem/A "Educational Codeforces Round 173 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 ans = 1 18 while n > 3: 19 n //= 4 20 ans *= 2 21 print(ans) 22 ``` 23 24 [2043B - Digits](/contest/2043/problem/B "Educational Codeforces Round 173 (Rated for Div. 2)") 25 26 Idea: [AcidWrongGod](/profile/AcidWrongGod "International Master AcidWrongGod") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (BledDest)** 33 34 ``` 35 import sys 36 37 sys.set_int_max_str_digits(6000) 38 39 def fact(x): 40 if x == 0: 41 return 1 42 return x * fact(x - 1) 43 44 t = int(input()) 45 for i in range(t): 46 n, k = map(int, input().split()) 47 n = min(n, 7) 48 s = int(str(k) * fact(n)) 49 for i in range(1, 10, 2): 50 if s % i == 0: 51 print(i, end = ' ') 52 print() 53 ``` 54 55 [2043C - Sums on Segments](/contest/2043/problem/C "Educational Codeforces Round 173 (Rated for Div. 2)") 56 57 Idea: [Ferume](/profile/Ferume "Master Ferume") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution (awoo)** 64 65 ``` 66 for _ in range(int(input())): 67 n = int(input()) 68 a = list(map(int, input().split())) 69 l1, r1 = 0, 0 70 l2, r2 = 2*10**9, -2*10**9 71 72 pr = 0 73 mnl, mxl = 0, 0 74 mnr, mxr = 2*10**9, -2*10**9 75 for i in range(n): 76 pr += a[i] 77 if a[i] != -1 and a[i] != 1: 78 mnr, mxr = mnl, mxl 79 mnl, mxl = pr, pr 80 l1 = min(l1, pr - mxl) 81 r1 = max(r1, pr - mnl) 82 l2 = min(l2, pr - mxr) 83 r2 = max(r2, pr - mnr) 84 mnl = min(mnl, pr) 85 mxl = max(mxl, pr) 86 res = [] 87 if l2 > r1: 88 res = list(range(l1, r1 + 1)) + list(range(l2, r2 + 1)) 89 elif r2 < l1: 90 res = list(range(l2, r2 + 1)) + list(range(l1, r1 + 1)) 91 else: 92 res = list(range(min(l1, l2), max(r1, r2) + 1)) 93 print(len(res)) 94 print(*res) 95 ``` 96 97 [2043D - Problem about GCD](/contest/2043/problem/D "Educational Codeforces Round 173 (Rated for Div. 2)") 98 99 Idea: [Ferume](/profile/Ferume "Master Ferume") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (BledDest)** 106 107 ``` 108 #include<bits/stdc++.h> 109 110 using namespace std; 111 112 long long gcd(long long x, long long y) 113 { 114 if(x == 0) return y; 115 else return gcd(y % x, x); 116 } 117 118 void solve() 119 { 120 long long l, r, g; 121 scanf("%lld %lld %lld", &l, &r, &g); 122 long long L = l + (l % g == 0 ? 0 : g - (l % g)); 123 long long R = r - r % g; 124 for(int i = 0; i <= (R - L) / g; i++) 125 for(int j = 0; j <= i; j++) 126 if(gcd(L + j * g, R - (i - j) * g) == g) 127 { 128 printf("%lld %lld\n", L + j * g, R - (i - j) * g); 129 return; 130 } 131 puts("-1 -1"); 132 } 133 134 int main() 135 { 136 int t; 137 scanf("%d", &t); 138 for(int i = 0; i < t; i++) solve(); 139 } 140 ``` 141 142 [2043E - Matrix Transformation](/contest/2043/problem/E "Educational Codeforces Round 173 (Rated for Div. 2)") 143 144 Idea: [Ferume](/profile/Ferume "Master Ferume") 145 146 **Tutorial** 147 148 Tutorial is loading... 149 150 **Solution (BledDest)** 151 152 ``` 153 #include<bits/stdc++.h> 154 155 using namespace std; 156 157 struct graph 158 { 159 int V; 160 vector<vector<int>> g; 161 vector<int> color; 162 163 bool dfs(int v) 164 { 165 if(color[v] != 0) return false; 166 color[v] = 1; 167 bool res = false; 168 for(auto y : g[v]) 169 { 170 if(color[y] == 2) continue; 171 else if(color[y] == 0) 172 res |= dfs(y); 173 else res = true; 174 } 175 color[v] = 2; 176 return res; 177 } 178 179 void add_edge(int x, int y) 180 { 181 g[x].push_back(y); 182 } 183 184 graph(int V) 185 { 186 this->V = V; 187 this->g.resize(V); 188 this->color.resize(V); 189 }; 190 }; 191 192 int get_bit(int x, int y) 193 { 194 return (x >> y) & 1; 195 } 196 197 bool check(const vector<vector<int>>& a, const vector<vector<int>>& b, int k) 198 { 199 int n = a.size(); 200 int m = a[0].size(); 201 vector<bool> must_row(n); 202 vector<bool> must_col(m); 203 auto G = graph(n + m); 204 for(int i = 0; i < n; i++) 205 for(int j = 0; j < m; j++) 206 { 207 if(get_bit(a[i][j], k) != get_bit(b[i][j], k)) 208 { 209 if(get_bit(b[i][j], k) == 0) must_row[i] = true; 210 else must_col[j] = true; 211 } 212 if(get_bit(b[i][j], k) == 0) G.add_edge(j + n, i); 213 else G.add_edge(i, j + n); 214 } 215 for(int i = 0; i < n; i++) 216 if(must_row[i] && G.dfs(i)) 217 return false; 218 for(int j = 0; j < m; j++) 219 if(must_col[j] && G.dfs(j + n)) 220 return false; 221 return true; 222 } 223 224 void solve() 225 { 226 int n, m; 227 scanf("%d %d", &n, &m); 228 vector<vector<int>> a(n, vector<int>(m)); 229 auto b = a; 230 for(int i = 0; i < n; i++) 231 for(int j = 0; j < m; j++) 232 scanf("%d", &a[i][j]); 233 for(int i = 0; i < n; i++) 234 for(int j = 0; j < m; j++) 235 scanf("%d", &b[i][j]); 236 for(int i = 0; i < 30; i++) 237 { 238 if(!check(a, b, i)) 239 { 240 puts("No"); 241 return; 242 } 243 } 244 puts("Yes"); 245 } 246 247 int main() 248 { 249 int t; 250 scanf("%d", &t); 251 for(int i = 0; i < t; i++) solve(); 252 } 253 ``` 254 255 [2043F - Nim](/contest/2043/problem/F "Educational Codeforces Round 173 (Rated for Div. 2)") 256 257 Idea: [Ferume](/profile/Ferume "Master Ferume") 258 259 **Tutorial** 260 261 Tutorial is loading... 262 263 **Solution (awoo)** 264 265 ``` 266 #include <bits/stdc++.h> 267 268 using namespace std; 269 270 #define forn(i, n) for(int i = 0; i < int(n); i++) 271 272 const int MOD = 998244353; 273 274 int add(int a, int b){ 275 a += b; 276 if (a >= MOD) 277 a -= MOD; 278 return a; 279 } 280 281 int mul(int a, int b){ 282 return a * 1ll * b % MOD; 283 } 284 285 struct state{ 286 int mx, cnt; 287 }; 288 289 void merge(state &a, int mx, int cnt){ 290 if (a.mx > mx) return; 291 if (a.mx < mx) a.mx = mx, a.cnt = 0; 292 a.cnt = add(a.cnt, cnt); 293 } 294 295 state dp[52][64][2]; 296 297 int main(){ 298 cin.tie(0); 299 ios::sync_with_stdio(false); 300 int n, q; 301 cin >> n >> q; 302 vector<int> a(n); 303 forn(i, n) cin >> a[i]; 304 int mx = *max_element(a.begin(), a.end()); 305 vector<vector<int>> cnt(n + 1, vector<int>(mx + 1)); 306 forn(i, n){ 307 cnt[i + 1] = cnt[i]; 308 ++cnt[i + 1][a[i]]; 309 } 310 forn(_, q){ 311 int l, r; 312 cin >> l >> r; 313 --l; 314 memset(dp, -1, sizeof(dp)); 315 dp[0][0][0] = {0, 1}; 316 forn(i, mx + 1){ 317 int c = cnt[r][i] - cnt[l][i]; 318 int c2 = c * 1ll * (c - 1) / 2 % MOD; 319 forn(val, 64) forn(fl, 2) if (dp[i][val][fl].cnt >= 0){ 320 if (c > 0) 321 merge(dp[i + 1][val ^ i][true], dp[i][val][fl].mx + c - 1, mul(dp[i][val][fl].cnt, c)); 322 if (c > 1) 323 merge(dp[i + 1][val][true], dp[i][val][fl].mx + c - 2, mul(dp[i][val][fl].cnt, c2)); 324 merge(dp[i + 1][val][fl], dp[i][val][fl].mx + c, dp[i][val][fl].cnt); 325 } 326 } 327 auto ans = dp[mx + 1][0][1]; 328 if (ans.cnt == -1) 329 cout << -1 << '\n'; 330 else 331 cout << ans.mx << ' ' << ans.cnt << '\n'; 332 } 333 } 334 ``` 335 336 [2043G - Problem with Queries](/contest/2043/problem/G "Educational Codeforces Round 173 (Rated for Div. 2)") 337 338 Idea: [Ferume](/profile/Ferume "Master Ferume") 339 340 **Tutorial** 341 342 Tutorial is loading...