codeforces-scrape

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

1766.md (7931B)


      1 Source: https://codeforces.com/blog/entry/110066
      2 
      3 [1766A - Extremely Round](/contest/1766/problem/A "Educational Codeforces Round 139 (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 def check(x):
     15     s = str(x)
     16     cnt = 0
     17     for c in s:
     18         if c != '0':
     19             cnt += 1
     20     return cnt == 1
     21 
     22 a = []
     23 for i in range(1, 1000000):
     24     if check(i):
     25         a.append(i)
     26 t = int(input())
     27 for i in range(t):
     28     n = int(input())
     29     ans = 0
     30     for x in a:
     31         if x <= n:
     32             ans += 1
     33     print(ans)
     34 ```
     35 
     36 [1766B - Notepad#](/contest/1766/problem/B "Educational Codeforces Round 139 (Rated for Div. 2)")
     37 
     38 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution (awoo)**
     45 
     46 ```
     47 for _ in range(int(input())):
     48 	n = int(input())
     49 	s = input()
     50 	cur = {}
     51 	for i in range(n - 1):
     52 		t = s[i:i+2]
     53 		if t in cur:
     54 			if cur[t] < i - 1:
     55 				print("YES")
     56 				break
     57 		else:
     58 			cur[t] = i
     59 	else:
     60 		print("NO")
     61 ```
     62 
     63 [1766C - Hamiltonian Wall](/contest/1766/problem/C "Educational Codeforces Round 139 (Rated for Div. 2)")
     64 
     65 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Solution (awoo)**
     72 
     73 ```
     74 for _ in range(int(input())):
     75 	n = int(input())
     76 	s = [input() for i in range(2)]
     77 	pos = -1
     78 	for i in range(n):
     79 		if s[0][i] != s[1][i]:
     80 			pos = i
     81 	if pos == -1:
     82 		print("YES")
     83 		continue
     84 	ok = True
     85 	cur = 0 if s[0][pos] == 'B' else 1
     86 	for i in range(pos + 1, n):
     87 		if s[cur][i] == 'W':
     88 			ok = False
     89 		if s[cur ^ 1][i] == 'B':
     90 			cur ^= 1
     91 	cur = 0 if s[0][pos] == 'B' else 1
     92 	for i in range(pos - 1, -1, -1):
     93 		if s[cur][i] == 'W':
     94 			ok = False
     95 		if s[cur ^ 1][i] == 'B':
     96 			cur ^= 1
     97 	print("YES" if ok else "NO")
     98 ```
     99 
    100 [1766D - Lucky Chains](/contest/1766/problem/D "Educational Codeforces Round 139 (Rated for Div. 2)")
    101 
    102 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Solution (adedalic)**
    109 
    110 ```
    111 #include<bits/stdc++.h>
    112 
    113 using namespace std;
    114 
    115 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    116 #define sz(a) int((a).size())
    117 
    118 typedef long long li;
    119 
    120 const int INF = int(1e9);
    121 const int N = int(1e7) + 5;
    122 
    123 int mind[N];
    124 
    125 void precalc() {
    126 	fore (i, 0, N)
    127 		mind[i] = i;
    128 	
    129 	for (int p = 2; p < N; p++) {
    130 		if (mind[p] != p)
    131 			continue;
    132 		for (int d = 2 * p; d < N; d += p)
    133 			mind[d] = min(mind[d], p);
    134 	}
    135 }
    136 
    137 int x, y;
    138 
    139 inline bool read() {
    140 	if(!(cin >> x >> y))
    141 		return false;
    142 	return true;
    143 }
    144 
    145 vector<int> getPrimes(int v) {
    146 	vector<int> ps;
    147 	while (v > 1) {
    148 		if (ps.empty() || ps.back() != mind[v])
    149 			ps.push_back(mind[v]);
    150 		v /= mind[v];
    151 	}
    152 	return ps;
    153 }
    154 
    155 inline void solve() {
    156 	int d = y - x;
    157 	if (d == 1) {
    158 		cout << -1 << '\n';
    159 		return;
    160 	}
    161 	
    162 	int r = INF;
    163 	for (int p : getPrimes(d))
    164 		r = min(r, ((x + p - 1) / p) * p);
    165 	cout << r - x << '\n';
    166 }
    167 
    168 int main() {
    169 #ifdef _DEBUG
    170 	freopen("input.txt", "r", stdin);
    171 	int tt = clock();
    172 #endif
    173 	ios_base::sync_with_stdio(false);
    174 	cin.tie(0), cout.tie(0);
    175 	cout << fixed << setprecision(15);
    176 	
    177 	precalc();
    178 	
    179 	int t; cin >> t;
    180 	while (t--) {
    181 		read();
    182 		solve();
    183 		
    184 #ifdef _DEBUG
    185 		cerr << "TIME = " << clock() - tt << endl;
    186 		tt = clock();
    187 #endif
    188 	}
    189 	return 0;
    190 }
    191 ```
    192 
    193 [1766E - Decomposition](/contest/1766/problem/E "Educational Codeforces Round 139 (Rated for Div. 2)")
    194 
    195 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    196 
    197 **Tutorial**
    198 
    199 Tutorial is loading...
    200 
    201 **Solution (BledDest)**
    202 
    203 ```
    204 #include<bits/stdc++.h>
    205 
    206 using namespace std;
    207 
    208 const int N = 300043;
    209 
    210 int n;
    211 int v[N];
    212 map<vector<int>, long long> dp[N];
    213 
    214 pair<int, vector<int>> go(vector<int> a, int x)
    215 {
    216     if(x == 0)
    217         return {1, a};
    218     else
    219     {
    220         bool f = false;
    221         for(int i = 0; i < a.size() && !f; i++)
    222             if((a[i] & x) > 0)
    223             {
    224                 f = true;
    225                 a[i] = x;
    226             }
    227         int c = 0;
    228         if(!f)
    229         {
    230             c = 1;
    231             a.push_back(x);
    232         }
    233         return {c, a};
    234     }
    235 }
    236 
    237 long long calc(int i, vector<int> a)
    238 {
    239     if(i == n) return 0ll;
    240     if(dp[i].count(a)) return dp[i][a];
    241     auto p = go(a, v[i]);
    242     return (dp[i][a] = p.first * 1ll * (n - i) + calc(i + 1, p.second));
    243 }
    244 
    245 int main()
    246 {
    247     scanf("%d", &n);
    248     for(int i = 0; i < n; i++) scanf("%d", &v[i]);
    249     long long ans = 0;
    250     for(int i = 0; i < n; i++)
    251         ans += calc(i, vector<int>(0));
    252     printf("%lld\n", ans);    
    253 }
    254 ```
    255 
    256 [1766F - MCF](/contest/1766/problem/F "Educational Codeforces Round 139 (Rated for Div. 2)")
    257 
    258 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    259 
    260 **Tutorial**
    261 
    262 Tutorial is loading...
    263 
    264 **Solution (BledDest)**
    265 
    266 ```
    267 #include <bits/stdc++.h>     
    268 
    269 using namespace std;
    270 
    271 const int N = 243;
    272 
    273 struct edge
    274 {
    275     int y, c, w, f;
    276     edge() {};
    277     edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
    278 };
    279 
    280 vector<edge> e;
    281 vector<int> g[N];
    282 
    283 int rem(int x)
    284 {
    285     return e[x].c - e[x].f;
    286 }
    287 
    288 void add_edge(int x, int y, int c, int w)
    289 {
    290     g[x].push_back(e.size());
    291     e.push_back(edge(y, c, w, 0));
    292     g[y].push_back(e.size());
    293     e.push_back(edge(x, 0, -w, 0));
    294 }
    295 
    296 int n, m, s, t, v;
    297 
    298 pair<int, long long> MCMF()
    299 {
    300     int flow = 0;
    301     long long cost = 0;
    302     while(true)
    303     {
    304         vector<long long> d(v, (long long)(1e18));
    305         vector<int> p(v, -1);
    306         vector<int> pe(v, -1);
    307         queue<int> q;
    308         vector<bool> inq(v);
    309         q.push(s);
    310         inq[s] = true;
    311         d[s] = 0;
    312         while(!q.empty())
    313         {
    314             int k = q.front();
    315             q.pop();
    316             inq[k] = false;
    317             for(auto ei : g[k])
    318             {
    319                 if(rem(ei) == 0) continue;
    320                 int to = e[ei].y;
    321                 int w = e[ei].w;
    322                 if(d[to] > d[k] + w)
    323                 {
    324                     d[to] = d[k] + w;
    325                     p[to] = k;
    326                     pe[to] = ei;
    327                     if(!inq[to])
    328                     {
    329                         inq[to] = true;
    330                         q.push(to);
    331                     }
    332                 }
    333             }
    334         }
    335         if(p[t] == -1 || d[t] >= 0) break;
    336         flow++;
    337         cost += d[t];
    338         int cur = t;
    339         while(cur != s)
    340         {
    341             e[pe[cur]].f++;
    342             e[pe[cur] ^ 1].f--;
    343             cur = p[cur];
    344         }
    345     }
    346     return make_pair(flow, cost);
    347 }
    348 
    349 void no_answer()
    350 {
    351     cout << "Impossible" << endl;
    352     exit(0);
    353 }
    354 
    355 int main()
    356 {                              
    357     cin >> n >> m;
    358     vector<int> excess_flow(n, 0);
    359     vector<int> orc(m);
    360     for(int i = 0; i < m; i++)
    361     {
    362         int x, y, c, w;
    363         cin >> x >> y >> c >> w;
    364         orc[i] = c;
    365         --x;
    366         --y;
    367         add_edge(x, y, c / 2, w);
    368         if(c % 2 == 1)
    369         {
    370             excess_flow[x]--;
    371             excess_flow[y]++;
    372         }
    373     }
    374     s = n;
    375     t = n + 1;
    376     v = n + 2;
    377     int total_excess = 0;
    378     if(excess_flow[0] % 2 == -1)
    379     {
    380         excess_flow[0]--;
    381         excess_flow[n - 1]++;
    382     }
    383     for(int i = 0; i < n; i++)
    384     {
    385         if(excess_flow[i] % 2 != 0)
    386             no_answer();
    387         int val = abs(excess_flow[i]) / 2;
    388         if(excess_flow[i] > 0)
    389         {
    390             total_excess += val;
    391             add_edge(s, i, val, -int(1e9));
    392         }
    393         if(excess_flow[i] < 0)
    394         {
    395             add_edge(i, t, val, -int(1e9));
    396         }
    397     }
    398     add_edge(s, 0, 100000, 0);
    399     add_edge(n - 1, t, 100000, 0);
    400     auto ans = MCMF();
    401     bool good_answer = true;
    402     for(int x = 0; x < e.size(); x++)
    403         if(e[x].w == -int(1e9) && rem(x) != 0)
    404             good_answer = false;
    405     if(!good_answer)
    406         no_answer();
    407     cout << "Possible" << endl;
    408     for(int i = 0; i < 2 * m; i += 2)
    409     {
    410         if(i) cout << " ";
    411         cout << e[i].f * 2 + orc[i / 2] % 2;
    412     }
    413     cout << endl;
    414 }
    415 ```