codeforces-scrape

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

1790.md (7255B)


      1 Source: https://codeforces.com/blog/entry/111948
      2 
      3 [1790A - Polycarp and the Day of Pi](/contest/1790/problem/A "Codeforces Round 847 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 t = int(input())
     15 pi = '31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
     16 for _ in range(t):
     17     n = input() + '#'
     18     for i in range(len(n)):
     19         if pi[i] != n[i]:
     20             print(i)
     21             break
     22 ```
     23 
     24 [1790B - Taisia and Dice](/contest/1790/problem/B "Codeforces Round 847 (Div. 3)")
     25 
     26 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36 
     37 using namespace std;
     38 
     39 const int MAXN = 55;
     40 
     41 int n, s1, s2;
     42 vector<int> res;
     43 
     44 void solve() {
     45 	res.clear();
     46 	int d = s1 - s2;
     47 	for (; s2 >= d; s2 -= d)
     48 		res.push_back(d);
     49 	if (s2) res.push_back(s2);
     50 	for (int i = 0; i < res.size() && res.size() + 1 < n;) {
     51 		if (res[i] == 1) {
     52 		    ++i;
     53 		    continue;
     54 		}
     55 		--res[i];
     56 		res.push_back(1);
     57 	}
     58 	res.push_back(d);
     59 }
     60 
     61 int main() {
     62 	int t; cin >> t;
     63 	while (t--) {
     64 		cin >> n >> s1 >> s2;
     65 		solve();
     66 		sort(res.begin(), res.end());
     67 		for (int x: res)
     68 			cout << x << ' ';
     69 		cout << endl;
     70 	}
     71 }
     72 ```
     73 
     74 [1790C - Premutation](/contest/1790/problem/C "Codeforces Round 847 (Div. 3)")
     75 
     76 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution**
     83 
     84 ```
     85 #include "bits/stdc++.h"
     86 using namespace std;
     87 int n;
     88 
     89 void solve(){
     90     cin >> n;
     91     vector<vector<int>>perm(n, vector<int>(n - 1));
     92     vector<int>p(n, 0);
     93     vector<int>cnt(n + 1, 0);
     94     for(int i = 0; i < n; i++){
     95         p[i] = i + 1;
     96         for(int j = 0; j < n - 1; j++){
     97             cin >> perm[i][j];
     98             if(j == 0) cnt[perm[i][j]]++;
     99         }
    100     }
    101     for(int i = 1; i <= n; i++){
    102         if(cnt[i] == n - 1){
    103             p[0] = i;
    104             break;
    105         }
    106     }
    107     for(int i = 0; i < n; i++){
    108         if(perm[i][0] != p[0]){
    109             for(int j = 0; j < n - 1; j++){
    110                 p[j + 1] = perm[i][j];
    111             }
    112         }
    113     }
    114     for(int i = 0; i < n; i++) cout << p[i] << ' ';
    115     cout << endl;
    116 
    117 }
    118 
    119 int main(){
    120     int t;
    121     cin >> t;
    122     while(t--){
    123         solve();
    124     }
    125     return 0;
    126 }
    127 ```
    128 
    129 [1790D - Matryoshkas](/contest/1790/problem/D "Codeforces Round 847 (Div. 3)")
    130 
    131 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    132 
    133 **Tutorial**
    134 
    135 Tutorial is loading...
    136 
    137 **Solution**
    138 
    139 ```
    140 #include <iostream>
    141 #include <vector>
    142 #include <queue>
    143 #include <map>
    144 #include <set>
    145 
    146 using namespace std;
    147 
    148 void solve() {
    149     int n;
    150     cin >> n;
    151     vector<int> a(n);
    152     map<int, int> cnt;
    153     set<int> b;
    154     for (int i = 0; i < n; ++i) {
    155         cin >> a[i];
    156         cnt[a[i]]++;
    157         b.insert(a[i]);
    158         b.insert(a[i] + 1);
    159     }
    160     int last = 0;
    161     int res = 0;
    162     for (auto x: b) {
    163         int c = cnt[x];
    164         res += max(0, c - last);
    165         last = c;
    166     }
    167     cout << res << '\n';
    168 }
    169 
    170 int main(int argc, char* argv[]) {
    171     int t;
    172     cin >> t;
    173     for (int i = 0; i < t; ++i) {
    174         solve();
    175     }
    176 }
    177 ```
    178 
    179 [1790E - Vlad and a Pair of Numbers](/contest/1790/problem/E "Codeforces Round 847 (Div. 3)")
    180 
    181 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    182 
    183 **Tutorial**
    184 
    185 Tutorial is loading...
    186 
    187 **Solution**
    188 
    189 ```
    190 t = int(input())
    191 for _ in range(t):
    192     x = int(input())
    193     a = x
    194     b = 0
    195     for i in range(32, -1, -1):
    196         if x & (1 << i) > 0:
    197             continue
    198         if 2 * x - a - b >= (2 << i):
    199             a += 1 << i
    200             b += 1 << i
    201     if a + b == 2 * x and a ^ b == x:
    202         print(a, b)
    203     else:
    204         print(-1)
    205 ```
    206 
    207 [1790F - Timofey and Black-White Tree](/contest/1790/problem/F "Codeforces Round 847 (Div. 3)")
    208 
    209 Idea: [molney](/profile/molney "Candidate Master molney")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 using namespace std;
    220 
    221 const int MAXN = 200200;
    222 const int INF = 1e9;
    223 
    224 int n, ANS = INF;
    225 int crr[MAXN], dist[MAXN], res[MAXN];
    226 bool clr[MAXN];
    227 vector<int> gr[MAXN];
    228 
    229 void init() {
    230 	ANS = INF;
    231 	for (int v = 0; v < n; ++v)
    232 		gr[v].clear();
    233 	fill(dist, dist + n, INF);
    234 	memset(clr, 0, n);
    235 }
    236 
    237 void dfs(int v, int p) {
    238 	if (dist[v] >= ANS) return;
    239 	if (clr[v]) ANS = min(ANS, dist[v]);
    240 	for (int u: gr[v]) {
    241 		if (u == p) continue;
    242 		if (dist[v] + 1 < dist[u]) {
    243 			dist[u] = dist[v] + 1;
    244 			dfs(u, v);
    245 		} else ANS = min(ANS, dist[v] + 1 + dist[u]);
    246 	}
    247 }
    248 
    249 void solve() {
    250 	dist[*crr] = 0;
    251 	dfs(*crr, -1);
    252 	clr[*crr] = true;
    253 	for (int i = 1; i < n; ++i) {
    254 		dist[crr[i]] = 0;
    255 		dfs(crr[i], -1);
    256 		clr[crr[i]] = true;
    257 		res[i] = ANS;
    258 	}
    259 }
    260 
    261 int main() {
    262 	int gorilla; cin >> gorilla;
    263 	while (gorilla--) {
    264 		cin >> n >> *crr, --(*crr);
    265 		init();
    266 		for (int i = 1; i < n; ++i)
    267 			cin >> crr[i], --crr[i];
    268 		for (int i = 1; i < n; ++i) {
    269 			int v, u; cin >> v >> u, --v, --u;
    270 			gr[v].push_back(u);
    271 			gr[u].push_back(v);
    272 		}
    273 		solve();
    274 		for (int i = 1; i < n; ++i)
    275 			cout << res[i] << ' ';
    276 		cout << '\n';
    277 	}
    278 }
    279 ```
    280 
    281 [1790G - Tokens on Graph](/contest/1790/problem/G "Codeforces Round 847 (Div. 3)")
    282 
    283 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    284 
    285 **Tutorial**
    286 
    287 Tutorial is loading...
    288 
    289 **Solution**
    290 
    291 ```
    292 #include<bits/stdc++.h>
    293 
    294 using namespace std;
    295 
    296 void solve()
    297 {
    298     int n;
    299     cin >> n;
    300     vector<int> token(n), boni(n);
    301     vector<vector<int>> g(n);
    302     vector<int> good(n);
    303     int m;
    304     cin >> m;
    305     int p, b;
    306     cin >> p >> b;
    307     for(int i = 0; i < p; i++)
    308     {
    309         int x;
    310         cin >> x;
    311         --x;
    312         token[x] = 1;
    313     }
    314     for(int i = 0; i < b; i++)
    315     {
    316         int x;
    317         cin >> x;
    318         --x;
    319         boni[x] = 1;
    320     }
    321     for(int i = 0; i < m; i++)
    322     {
    323         int x, y;
    324         cin >> x >> y;
    325         --x;
    326         --y;
    327         g[x].push_back(y);
    328         g[y].push_back(x);
    329     }
    330     for(int i = 0; i < n; i++)
    331         for(auto x : g[i])
    332             if(boni[i] && boni[x]) good[i] = 1;
    333     set<int> good_tokens;
    334     set<int> not_so_good_tokens;
    335     for(int i = 0; i < n; i++)
    336         for(auto x : g[i])
    337         {
    338             if(token[i] && good[x]) good_tokens.insert(i);
    339             else if(token[i] && boni[x]) not_so_good_tokens.insert(i);
    340         }
    341     vector<int> d(n, int(1e9));
    342     queue<int> q;
    343     d[0] = 0;
    344     q.push(0);
    345     while(!q.empty())
    346     {
    347         int k = q.front();
    348         q.pop();
    349         for(auto x : g[k])
    350         {
    351             if(d[x] > d[k] + 1)
    352             {
    353                 d[x] = d[k] + 1;
    354                 if(boni[x]) q.push(x);
    355             }
    356         }
    357     }
    358     bool has_ans = false;
    359     for(int i = 0; i < n; i++)
    360     {
    361         if(!token[i] || d[i] > n) continue;
    362         has_ans |= (!good_tokens.empty() && (*good_tokens.begin() != i || *good_tokens.rbegin() != i));
    363         int cnt = not_so_good_tokens.size();
    364         if(not_so_good_tokens.count(i)) cnt--;
    365         has_ans |= d[i] <= 1 + cnt;
    366     }
    367     cout << (has_ans ? "YES" : "NO") << endl;
    368 }
    369 
    370 int main()
    371 {
    372     ios_base::sync_with_stdio(0);
    373     cin.tie(0);
    374 #ifdef _DEBUG
    375     freopen("input.txt", "r", stdin);
    376 #endif
    377     int tc = 1;
    378     cin >> tc;
    379     for(int i = 0; i < tc; i++)
    380     {
    381         solve();
    382     }
    383 }
    384 ```