codeforces-scrape

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

1941.md (8139B)


      1 Source: https://codeforces.com/blog/entry/127018
      2 
      3 [1941A - Rudolf and the Ticket](/contest/1941/problem/A "Codeforces Round 933 (Div. 3)")
      4 
      5 Author: [daha.002](/profile/daha.002 "Newbie daha.002")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <iostream>
     15 #include <vector>
     16 
     17 using namespace std;
     18 
     19 int main() {
     20 	int t;
     21 	cin >> t;
     22 	while (t--) {
     23 		int n, m, k;
     24 		cin >> n >> m >> k;
     25 		int ans = 0;
     26 		vector<int> v1(n);
     27 		for (int i = 0; i < n; i++) {
     28 			cin >> v1[i];
     29 		}
     30 		int o;
     31 		for (int j = 0; j < m; j++) {
     32 			cin >> o;
     33 			for (int i = 0; i < n; i++) {
     34 				if ((o + v1[i]) <= k) ans++;
     35 			}
     36 		}
     37 		cout << ans << "\n";
     38 	}
     39 	return 0;
     40 }
     41 ```
     42 
     43 **Rate the problem**
     44 
     45 * Didn't solve
     46 * Good task
     47 * Average task
     48 * Bad task
     49 
     50 [1941B - Rudolf and 121](/contest/1941/problem/B "Codeforces Round 933 (Div. 3)")
     51 
     52 Author: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution**
     59 
     60 ```
     61 def solve():
     62     n = int(input())
     63     a = [int(x) for x in input().split()]
     64     for i in range(n - 2):
     65         if a[i] < 0:
     66             print('NO')
     67             return
     68         op = a[i]
     69         a[i] -= op
     70         a[i + 1] -= 2 * op
     71         a[i + 2] -= op
     72     if a[-1] != 0 or a[-2] != 0:
     73         print('NO')
     74     else:
     75         print('YES')
     76     
     77 
     78 for _ in range(int(input())):
     79     solve()
     80 ```
     81 
     82 **Rate the problem**
     83 
     84 * Didn't solve
     85 * Good task
     86 * Average task
     87 * Bad task
     88 
     89 [1941C - Rudolf and the Ugly String](/contest/1941/problem/C "Codeforces Round 933 (Div. 3)")
     90 
     91 Author: [Mordvin13](/profile/Mordvin13 "Newbie Mordvin13")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution**
     98 
     99 ```
    100 #include <iostream>
    101 #include <vector>
    102 #include <string>
    103 #include <algorithm>
    104 
    105 using namespace std;
    106 
    107 int main() {
    108     long long t;
    109     cin>>t;
    110     for(long long c=0;c<t;c++){
    111 	long long n;
    112 	cin >> n;
    113 	string s;
    114 	cin >> s;
    115 	vector<long long> va;                 
    116 	for (string sul : {"mapie", "pie", "map"}) {
    117 		for (size_t pos = 0; (pos = s.find(sul, pos)) != string::npos;) {
    118 			s[pos + sul.length() / 2] = '?';
    119 			va.push_back(pos + sul.length() / 2);
    120 		}
    121 	}
    122 	cout << va.size() << endl;
    123     }
    124 	return 0;
    125 }
    126 ```
    127 
    128 **Rate the problem**
    129 
    130 * Didn't solve
    131 * Good task
    132 * Average task
    133 * Bad task
    134 
    135 [1941D - Rudolf and the Ball Game](/contest/1941/problem/D "Codeforces Round 933 (Div. 3)")
    136 
    137 Author: [Alexey_Parsh](/profile/Alexey_Parsh "Expert Alexey_Parsh")
    138 
    139 **Tutorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Solution**
    144 
    145 ```
    146 #include <iostream>
    147 #include <set>
    148 
    149 using namespace std;
    150 
    151 int main()
    152 {
    153     int t; cin >> t;
    154     while (t--) {
    155         int n, m, a; cin >> n >> m >> a;
    156         set <int> q[2];
    157         int ix = 0;
    158         q[ix].insert(a);
    159         while (m--) {
    160             int x; char ch; cin >> x >> ch;
    161             while (!q[ix].empty()) {
    162                 int u = *(q[ix].begin());
    163                 q[ix].erase(u);
    164                 if (ch == '?' || ch == '0') {
    165                     q[ix ^ 1].insert((u + x - 1) % n + 1);
    166                 }
    167                 if (ch == '?' || ch == '1') {
    168                     q[ix ^ 1].insert((u - x - 1 + n) % n + 1);
    169                 }
    170             }
    171             ix ^= 1;
    172         }
    173         cout << q[ix].size() << '\n';
    174         for (auto& x : q[ix]) {
    175             cout << x << ' ';
    176         }
    177         cout << '\n';
    178     }
    179     return 0;
    180 }
    181 ```
    182 
    183 **Rate the problem**
    184 
    185 * Didn't solve
    186 * Good task
    187 * Average task
    188 * Bad task
    189 
    190 [1941E - Rudolf and k Bridges](/contest/1941/problem/E "Codeforces Round 933 (Div. 3)")
    191 
    192 Author: [t0rtik](/profile/t0rtik "Expert t0rtik")
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution**
    199 
    200 ```
    201 #include <iostream>
    202 #include <vector>
    203 #include <algorithm>
    204 #include <set>
    205 
    206 using namespace std;
    207 
    208 int main() {
    209 
    210     int t = 1;
    211     cin >> t;
    212     while (t--) {
    213         int N, M, K, D;
    214         cin >> N >> M >> K >> D;
    215         vector<long long> a(N);
    216         for (int i = 0; i < N; i++) {
    217             vector<long long> dp(M, 1e9);
    218             vector<int> v(M);
    219             multiset<long long> mst = {1};
    220             dp[0] = 1;
    221             cin >> v[0];
    222             for (int j = 1; j < M - 1; j++) {
    223                 cin >> v[j];
    224                 dp[j] = *mst.begin() + v[j] + 1;
    225                 if (j - D - 1 >= 0)
    226                     mst.erase(mst.find((dp[j - D - 1])));
    227                 mst.insert(dp[j]);
    228             }
    229             cin >> v.back();
    230             dp.back() = 1 + *mst.begin();
    231             a[i] = dp.back();
    232         }
    233 
    234         long long cur = 0;
    235         for (int i = 0; i < K; i++)
    236             cur += a[i];
    237 
    238         long long mn = cur;
    239 
    240         for (int i = K; i < N; i++) {
    241             cur += a[i] - a[i - K];
    242             mn = min(cur, mn);
    243         }
    244         cout << mn << endl;
    245     }
    246     return 0;
    247 }
    248 ```
    249 
    250 **Rate the problem**
    251 
    252 * Didn't solve
    253 * Good task
    254 * Average task
    255 * Bad task
    256 
    257 [1941F - Rudolf and Imbalance](/contest/1941/problem/F "Codeforces Round 933 (Div. 3)")
    258 
    259 Author: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    260 
    261 **Tutorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution**
    266 
    267 ```
    268 def solve():
    269     n, m, k = map(int, input().split())
    270     a = [int(x) for x in input().split()]
    271     d = [int(x) for x in input().split()]
    272     f = [int(x) for x in input().split()]
    273     d.sort()
    274     f.sort()
    275 
    276     m1, m2 = 0, 0
    277     ind = -1
    278     for i in range(1, n):
    279         e = a[i] - a[i - 1]
    280         m2 = max(m2, e)
    281         if m2 > m1:
    282             m1, m2 = m2, m1
    283             ind = i - 1
    284 
    285     ans = m1
    286 
    287     target = (a[ind] + a[ind + 1]) // 2
    288     for model in d:
    289         l, r = 0, k - 1
    290         while r - l > 1:
    291             mid = (r + l) // 2
    292             if model + f[mid] <= target:
    293                 l = mid
    294             else:
    295                 r = mid
    296         ans = min(ans, max(m2, abs(model + f[l] - a[ind]), abs(model + f[l] - a[ind + 1])))
    297         ans = min(ans, max(m2, abs(model + f[r] - a[ind]), abs(model + f[r] - a[ind + 1])))
    298     print(ans)
    299 
    300 for _ in range(int(input())):
    301     solve()
    302 ```
    303 
    304 **Rate the problem**
    305 
    306 * Didn't solve
    307 * Good task
    308 * Average task
    309 * Bad task
    310 
    311 [1941G - Rudolf and Subway](/contest/1941/problem/G "Codeforces Round 933 (Div. 3)")
    312 
    313 Author: [natalina](/profile/natalina "Expert natalina")
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **Solution**
    320 
    321 ```
    322 #include<bits/stdc++.h>
    323 
    324 using LL = long long;
    325 using ld = long double;
    326 
    327 using namespace std;
    328 
    329 int main() {
    330     ios::sync_with_stdio(false);
    331     cin.tie(0);
    332     cout.tie(0);
    333     cout << fixed << setprecision(10);
    334 
    335     int _ = 0, __ = 1;
    336     cin >> __;
    337 
    338     for (int _ = 0; _ < __; ++_) {
    339         int n, m;
    340         cin >> n >> m;
    341         vector<vector<pair<int, int>>> g(n + 1);
    342         map<int, int> clrs;
    343         int idx = n + 1;
    344         for (int i = 0; i < m; ++i) {
    345             int u, v, c;
    346             cin >> u >> v >> c;
    347             g[u].push_back({v, c});
    348             g[v].push_back({u, c});
    349             if (!clrs.count(c)) {
    350                 clrs[c] = idx;
    351                 idx++;
    352             }
    353         }
    354         int s, t;
    355         cin >> s >> t;
    356         
    357         if (s == t) 
    358         {
    359             cout << 0 << endl;
    360             continue;
    361         }
    362 
    363         vector<set<int>> bg(n + clrs.size() + 3);
    364 
    365         for (int i = 1; i <= n; ++i) {
    366             for(auto &[to, c] : g[i])
    367             {
    368                 int clr_v = clrs[c];
    369                 bg[i].insert(clr_v);
    370                 bg[clr_v].insert(i);
    371 
    372                 bg[to].insert(clr_v);
    373                 bg[clr_v].insert(to);
    374             }
    375         }
    376 
    377         vector<int> used(bg.size());
    378         vector<int> d(bg.size(), -1);
    379         auto bfs = [&](int v)
    380         {
    381             queue<int> q;
    382             q.push(v);
    383             used[v] = 1;
    384             d[v] = 0;
    385             while (!q.empty())
    386             {
    387                 auto from = q.front();
    388                 q.pop();
    389                 for (auto& to : bg[from])
    390                 {
    391                     if (!used[to])
    392                     {
    393                         q.push(to);
    394                         used[to] = 1;
    395                         d[to] = d[from] + 1;
    396                     }
    397                 }
    398             }
    399         };
    400         bfs(s);
    401         if (d[t] > 0) cout << d[t] / 2 << endl;
    402         else cout << -1 << endl;
    403 
    404     }
    405 
    406     return 0;
    407 }
    408 ```
    409 
    410 **Rate the problem**
    411 
    412 * Didn't solve
    413 * Good task
    414 * Average task
    415 * Bad task