codeforces-scrape

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

2112.md (7469B)


      1 Source: https://codeforces.com/blog/entry/144148
      2 
      3 [2112A - Race](/contest/2112/problem/A "Educational Codeforces Round 180 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     int a, x, y;
     23     cin >> a >> x >> y;
     24     cout << ((a < x) == (a < y) ? "YES" : "NO") << '\n';
     25   }
     26 }
     27 ```
     28 
     29 [2112B - Shrinking Array](/contest/2112/problem/B "Educational Codeforces Round 180 (Rated for Div. 2)")
     30 
     31 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Solution (adedalic)**
     38 
     39 ```
     40 #include<bits/stdc++.h>
     41 
     42 using namespace std;
     43 
     44 void solve() {
     45 	int n;
     46 	cin >> n;
     47 	vector<int> a(n);
     48 	for (int i = 0; i < n; i++)
     49 		cin >> a[i];
     50 	
     51 	for (int i = 1; i < n; i++) {
     52 		if (abs(a[i - 1] - a[i]) <= 1) {
     53 			cout << 0 << endl;
     54 			return;
     55 		}
     56 	}
     57 	for (int i = 1; i + 1 < n; i++) {
     58 		if (a[i - 1] < a[i] && a[i] > a[i + 1]) {
     59 			cout << 1 << endl;
     60 			return;
     61 		}
     62 		if (a[i - 1] > a[i] && a[i] < a[i + 1]) {
     63 			cout << 1 << endl;
     64 			return;
     65 		}
     66 	}
     67 	cout << -1 << endl;
     68 }
     69 
     70 int main() {
     71 #ifdef _DEBUG
     72 	freopen("input.txt", "r", stdin);
     73 	int tt = clock();
     74 #endif
     75 	int t;
     76 	cin >> t;
     77 	while (t--) {
     78 		solve();
     79 	}
     80 	return 0;
     81 }
     82 ```
     83 
     84 [2112C - Coloring Game](/contest/2112/problem/C "Educational Codeforces Round 180 (Rated for Div. 2)")
     85 
     86 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution (Neon)**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96  
     97 using namespace std;
     98 
     99 int main() {
    100   int t;
    101   cin >> t;
    102   while (t--) {
    103     int n;
    104     cin >> n;
    105     vector<int> a(n);
    106     for (auto& x : a) cin >> x;
    107     long long ans = 0;
    108     for (int i = 0; i < n; ++i) {
    109       for (int j = 0; j < i; ++j) {
    110         int x = max(a[n - 1], 2 * a[i]) - a[i] - a[j];
    111         int k = upper_bound(a.begin(), a.begin() + j, x) - a.begin();
    112         ans += j - k;
    113       }
    114     }
    115     cout << ans << '\n';
    116   }
    117 }
    118 ```
    119 
    120 [2112D - Reachability and Tree](/contest/2112/problem/D "Educational Codeforces Round 180 (Rated for Div. 2)")
    121 
    122 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    123 
    124 **Tutorial**
    125 
    126 Tutorial is loading...
    127 
    128 **Solution (adedalic)**
    129 
    130 ```
    131 #include<bits/stdc++.h>
    132 
    133 using namespace std;
    134 
    135 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    136 #define sz(a) int((a).size())
    137 
    138 const int N = int(2e5) + 5;
    139 
    140 int n;
    141 vector<int> g[N];
    142 
    143 inline bool read() {
    144 	if(!(cin >> n))
    145 		return false;
    146 	fore (i, 0, n)
    147 		g[i].clear();
    148 	
    149 	fore (i, 0, n - 1) {
    150 		int u, v;
    151 		cin >> u >> v;
    152 		u--, v--;
    153 		g[u].push_back(v);
    154 		g[v].push_back(u);
    155 	}
    156 	return true;
    157 }
    158 
    159 vector<int> used;
    160 vector<pair<int, int>> ans;
    161 
    162 void dfs(int v, bool in) {
    163 	used[v] = 1;
    164 	for (int to : g[v]) {
    165 		if (used[to])
    166 			continue;
    167 		if (in)
    168 			ans.emplace_back(to, v);
    169 		else
    170 			ans.emplace_back(v, to);
    171 		dfs(to, !in);
    172 	}
    173 }
    174 
    175 inline void solve() {
    176 	int r = 0;
    177 	while (r < n && sz(g[r]) != 2)
    178 		r++;
    179 	if (r >= n) {
    180 		cout << "NO\n";
    181 		return;
    182 	}
    183 
    184 	used.assign(n, 0);
    185 	ans.clear();
    186 
    187 	ans.emplace_back(r, g[r][0]);
    188 	ans.emplace_back(g[r][1], r);
    189 	used[r] = 1;
    190 
    191 	dfs(g[r][0], true);
    192 	dfs(g[r][1], false);
    193 
    194 	cout << "YES\n";
    195 	sort(ans.begin(), ans.end());
    196 	for (auto [u, v] : ans)
    197 		cout << u + 1 << " " << v + 1 << '\n';
    198 }
    199 
    200 int main() {
    201 #ifdef _DEBUG
    202 	freopen("input.txt", "r", stdin);
    203 	int tt = clock();
    204 #endif
    205 	ios_base::sync_with_stdio(false);
    206 	cin.tie(0), cout.tie(0);
    207 	cout << fixed << setprecision(15);
    208 	
    209 	int t; cin >> t;
    210 	while (t--)  {
    211 		read();
    212 		solve();
    213 		
    214 #ifdef _DEBUG
    215 		cerr << "TIME = " << clock() - tt << endl;
    216 		tt = clock();
    217 #endif
    218 	}
    219 	return 0;
    220 }
    221 ```
    222 
    223 [2112E - Tree Colorings](/contest/2112/problem/E "Educational Codeforces Round 180 (Rated for Div. 2)")
    224 
    225 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution in M sqrt M (Neon)**
    232 
    233 ```
    234 #include <bits/stdc++.h>
    235  
    236 using namespace std;
    237 
    238 const int M = 5e5;
    239 const int INF = 1e9;
    240 
    241 int main() {
    242   vector<int> dp(M + 1, INF);
    243   dp[1] = 1;
    244   for (int m = 2; m <= M; ++m) {
    245     for (int i = 1; i * i <= m; ++i) {
    246       if (m % i != 0) continue;
    247       if (m / i > 2) dp[m] = min(dp[m], dp[i] + dp[m / i - 2]);
    248       if (i > 2) dp[m] = min(dp[m], dp[m / i] + dp[i - 2]);
    249     }
    250   }
    251   
    252   int q;
    253   cin >> q;
    254   while (q--) {
    255     int m;
    256     cin >> m;
    257     cout << (dp[m] == INF ? -1 : dp[m]) << '\n';
    258   }
    259 }
    260 ```
    261 
    262 **Solution in M log M (BledDest)**
    263 
    264 ```
    265 #include<bits/stdc++.h>
    266 
    267 using namespace std;
    268 
    269 const int N = 500043;
    270 
    271 vector<int> divisors[N];
    272 
    273 int dp[N], dp2[N];
    274 
    275 int calc(int x);
    276 
    277 int calc2(int x)
    278 {
    279     if(dp2[x] != -1) return dp2[x];
    280     if(x == 1) return dp2[x] = 0;
    281     dp2[x] = calc(x);
    282     for(auto y : divisors[x]) dp2[x] = min(dp2[x], calc(y) + calc2(x / y));
    283     return dp2[x];
    284 }
    285 
    286 int calc(int x)
    287 {
    288     if(dp[x] != -1) return dp[x];
    289     if(x == 1) return dp[x] = 0;
    290     if(x == 3) return dp[x] = 1;
    291     return dp[x] = calc2(x - 2) + 1;
    292 }                       
    293 
    294 int main()
    295 {
    296     ios_base::sync_with_stdio(0);
    297     cin.tie(0);
    298     for(int i = 2; i < N; i++)
    299         for(int j = i * 2; j < N; j += i)
    300             divisors[j].push_back(i);
    301     for(int i = 0; i < N; i++) dp[i] = dp2[i] = -1;
    302 
    303     int t;
    304     cin >> t;
    305     for(int i = 0; i < t; i++)
    306     {
    307         int x;
    308         cin >> x;
    309         if(x % 2 == 0) cout << -1 << endl;
    310         else cout << calc(x + 2) << endl;
    311     }
    312     return 0;
    313 }
    314 ```
    315 
    316 [2112F - Variables and Operations](/contest/2112/problem/F "Educational Codeforces Round 180 (Rated for Div. 2)")
    317 
    318 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    319 
    320 **Tutorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Solution (BledDest)**
    325 
    326 ```
    327 #include<bits/stdc++.h>
    328 
    329 using namespace std;
    330 
    331 const int N = 543;
    332 const long long INF64 = (long long)(1e18);
    333 
    334 long long e[N][N];
    335 long long d[N][N];
    336 int n, m;
    337 
    338 int main()
    339 {
    340     ios_base::sync_with_stdio(0);
    341     cin.tie(0);
    342     cin >> n >> m;
    343     for(int i = 0; i < n; i++)
    344         for(int j = 0; j < n; j++)
    345             if(i != j) e[i][j] = INF64;
    346     for(int i = 0; i < m; i++)
    347     {
    348         int x, y, w;
    349         cin >> x >> y >> w;
    350         --x;
    351         --y;
    352         swap(x, y);
    353         e[x][y] = min(e[x][y], (long long)w);
    354     }
    355     for(int i = 0; i < n; i++)
    356         for(int j = 0; j < n; j++)
    357             d[i][j] = e[i][j];
    358     for(int k = 0; k < n; k++)
    359         for(int i = 0; i < n; i++)
    360             for(int j = 0; j < n; j++)
    361                 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    362 
    363     int q;
    364     cin >> q;
    365     for(int i = 0; i < q; i++)
    366     {
    367         long long op;
    368         cin >> op;
    369         vector<long long> a(n);
    370         for(int j = 0; j < n; j++) cin >> a[j];
    371         vector<long long> min_dist = a;
    372         vector<long long> min_one_edge = a;
    373         for(int j = 0; j < n; j++)
    374             for(int k = 0; k < n; k++)
    375             {
    376                 min_dist[k] = min(min_dist[k], a[j] + d[j][k]);
    377                 min_one_edge[k] = min(min_one_edge[k], a[j] + e[j][k]);
    378             }
    379         vector<long long> min_op(n, INF64);
    380         for(int j = 0; j < n; j++)
    381             for(int k = 0; k < n; k++)
    382             {
    383                 if(d[j][k] < e[j][k]) min_op[k] = min(min_op[k], (d[j][k] + a[j]) - (min_one_edge[k] - 1));
    384             }               
    385         for(int j = 0; j < n; j++)
    386         {
    387             if(min_op[j] <= op) cout << 1;
    388             else cout << 0;
    389         }
    390         cout << endl;
    391     }
    392     
    393     return 0;
    394 }
    395 ```