codeforces-scrape

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

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...