codeforces-scrape

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

1729.md (7277B)


      1 Source: https://codeforces.com/blog/entry/106916
      2 
      3 [1729A - Two Elevators](/contest/1729/problem/A "Codeforces Round 820 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 t = int(input())
     15 for _ in range(t):
     16     a, b, c = map(int, input().split())
     17     d1 = a - 1
     18     d2 = abs(b - c) + c - 1
     19     ans = 0
     20     if d1 <= d2:
     21         ans += 1
     22     if d1 >= d2:
     23         ans += 2
     24     print(ans)
     25 ```
     26 
     27 [1729B - Decode String](/contest/1729/problem/B "Codeforces Round 820 (Div. 3)")
     28 
     29 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution**
     36 
     37 ```
     38 #include <iostream>
     39 #include <vector>
     40 #include <algorithm>
     41 #include <set>
     42 #include <queue>
     43 
     44 using namespace std;
     45 
     46 char get(int i) {
     47     return 'a' + i - 1;
     48 }
     49 
     50 void solve() {
     51     int n;
     52     string s;
     53     cin >> n >> s;
     54     int i = n - 1;
     55     string res;
     56     while (i >= 0) {
     57         if (s[i] != '0') {
     58             res += get(s[i] - '0');
     59             i--;
     60         } else {
     61             res += get(stoi(s.substr(i - 2, 2)));
     62             i -= 3;
     63         }
     64     }
     65     reverse(res.begin(), res.end());
     66     cout << res << '\n';
     67 }
     68 
     69 int main() {
     70     int t = 1;
     71     cin >> t;
     72     for (int it = 0; it < t; ++it) {
     73         solve();
     74     }
     75     return 0;
     76 }
     77 ```
     78 
     79 [1729C - Jumping on Tiles](/contest/1729/problem/C "Codeforces Round 820 (Div. 3)")
     80 
     81 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Aris](/profile/Aris "Expert Aris")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 typedef long long ll;
     95 
     96 #define forn(i, n) for (int i = 0; i < int(n); i++)
     97 
     98 void solve() {
     99 
    100     string s;
    101     cin >> s;
    102 
    103     int n = s.size();
    104     map<char, vector<int>> let_to_ind;
    105 
    106     for (int i = 0; i < n; ++i) {
    107         let_to_ind[s[i]].push_back(i);
    108     }
    109 
    110     int direction = (s[0] < s[n - 1]) ? 1 : -1;
    111     vector<int> ans;
    112 
    113     for (char c = s[0]; c != s[n - 1] + direction; c += direction) {
    114         for (auto now : let_to_ind[c]) {
    115             ans.push_back(now);
    116         }
    117     }
    118 
    119     int cost = 0;
    120     for (int i = 1; i < ans.size(); i++)
    121         cost += abs(s[ans[i]] - s[ans[i - 1]]);
    122 
    123     cout << cost << " " << ans.size() << '\n';
    124     for (auto now : ans) {
    125         cout << now + 1 << " ";
    126     }
    127     cout << '\n';
    128 }
    129 int main() {
    130     int tests;
    131     cin >> tests;
    132     forn(tt, tests) {
    133         solve();
    134     }
    135 }
    136 ```
    137 
    138 [1729D - Friends and the Restaurant](/contest/1729/problem/D "Codeforces Round 820 (Div. 3)")
    139 
    140 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Aris](/profile/Aris "Expert Aris"), [myav](/profile/myav "Pupil myav")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution**
    147 
    148 ```
    149 #include <bits/stdc++.h>
    150 using namespace std;
    151 using ll = long long;
    152 
    153 void solve(){
    154     int n;
    155     cin >> n;
    156     vector<ll>x(n), y(n);
    157     vector<pair<ll, int>>dif(n);
    158 
    159     for(auto &i : x) cin >> i;
    160     for(auto &i: y) cin >> i;
    161     for(int i = 0; i < n; i++){
    162         dif[i].first = y[i] - x[i];
    163         dif[i].second = i;
    164     }
    165     sort(dif.begin(), dif.end());
    166     reverse(dif.begin(), dif.end());
    167 
    168     int j = n - 1, cnt = 0;
    169 
    170     for(int i = 0; i < n; i++){
    171         while(j > i && dif[i].first + dif[j].first < 0) j--;
    172         if(j <= i) break;
    173         cnt++; j--;
    174     }
    175     cout << cnt << endl;
    176 }
    177 
    178 int main() {
    179     int t;
    180     cin >> t;
    181     while(t--){
    182         solve();
    183     }
    184 }
    185 ```
    186 
    187 [1729E - Guess the Cycle Size](/contest/1729/problem/E "Codeforces Round 820 (Div. 3)")
    188 
    189 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    190 
    191 **Tutorial**
    192 
    193 Tutorial is loading...
    194 
    195 **Solution**
    196 
    197 ```
    198 #include <bits/stdc++.h>
    199 
    200 using namespace std;
    201 
    202 #define forn(i, n) for (int i = 0; i < int(n); i++)
    203 #define sz(v) (int)v.size()
    204 #define all(v) v.begin(),v.end()
    205 #define eb emplace_back
    206 
    207 long long ask(int a, int b) {
    208     cout << "? " << a << ' ' << b << endl;
    209     long long x; cin >> x;
    210     return x;
    211 }
    212 
    213 long long solve() {
    214     for (int i = 2; i <= 26; i++) {
    215         long long x = ask(1, i);
    216         long long y = ask(i, 1);
    217         if (x == -1) return i-1;
    218         if (x != y) return x + y;
    219     }
    220     assert(false);
    221 }
    222 
    223 int main() {
    224     long long ans = solve();
    225     cout << "! " << ans << endl;
    226 }
    227 ```
    228 
    229 [1729F - Kirei and the Linear Function](/contest/1729/problem/F "Codeforces Round 820 (Div. 3)")
    230 
    231 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    232 
    233 **Tutorial**
    234 
    235 Tutorial is loading...
    236 
    237 **Solution**
    238 
    239 ```
    240 #include <bits/stdc++.h>
    241 
    242 #define endl '\n'
    243 
    244 using namespace std;
    245 
    246 typedef pair<int, int> ipair;
    247 
    248 const int MAXSZ = 200200;
    249 const int INF = 2e9;
    250 
    251 inline int add(int a, int b) {
    252 	return (a + b >= 9 ? a + b - 9 : a + b);
    253 }
    254 
    255 inline int sub(int a, int b) {
    256 	return (a < b ? a + 9 - b : a - b);
    257 }
    258 
    259 inline int mul(int a, int b) {
    260 	return a * b % 9;
    261 }
    262 
    263 int sz, n, m;
    264 string s;
    265 int ps[MAXSZ];
    266 vector<int> D[9];
    267 
    268 void build() {
    269 	sz = s.size();
    270 	for (int md = 0; md < 9; ++md)
    271 		D[md].clear();
    272 	for (int i = 0; i < sz; ++i)
    273 		ps[i + 1] = ps[i] + (s[i] - '0');
    274 	for (int i = 0; i + n <= sz; ++i)
    275 		D[(ps[i + n] - ps[i]) % 9].push_back(i);
    276 }
    277 
    278 ipair solve(int l, int r, int k) {
    279 	int x = (ps[r] - ps[l]) % 9;
    280 	ipair ans {INF, INF};
    281 	for (int a = 0; a < 9; ++a) {
    282 		int b = sub(k, mul(a, x));
    283 		if (D[a].empty() || D[b].empty()) continue;
    284 		if (a != b)
    285 			ans = min(ans, make_pair(D[a].front(), D[b].front()));
    286 		else if (D[a].size() >= 2)
    287 			ans = min(ans, make_pair(D[a].front(), D[a][1]));
    288 	}
    289 	if (ans == make_pair(INF, INF))
    290 		return {-2, -2};
    291 	return ans;
    292 }
    293 
    294 int main() {
    295 	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    296 	int t; cin >> t;
    297 	while (t--) {
    298 		cin >> s >> n >> m;
    299 		build();
    300 		for (int i = 0; i < m; ++i) {
    301 			int l, r, k; cin >> l >> r >> k, --l;
    302 			auto [ans1, ans2] = solve(l, r, k);
    303 			cout << ++ans1 << ' ' << ++ans2 << endl;
    304 		}
    305 	}
    306 }
    307 ```
    308 
    309 [1729G - Cut Substrings](/contest/1729/problem/G "Codeforces Round 820 (Div. 3)")
    310 
    311 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    312 
    313 **Tutorial**
    314 
    315 Tutorial is loading...
    316 
    317 **Solution**
    318 
    319 ```
    320 #include<cstdio>
    321 #include<cstring>
    322 const int N=505;
    323 const int Mod=1e9+7;
    324 char s[N],t[N];
    325 int n,m;
    326 int f[N],g[N];
    327 int p[N],tot;
    328 inline void Init(){
    329 	scanf("%s",s+1);
    330 	scanf("%s",t+1);
    331 	n=strlen(s+1);
    332 	m=strlen(t+1);
    333 	tot=0;
    334 	for(int i=1;i+m-1<=n;i++){
    335 		bool flg=1;
    336 		for(int j=1;j<=m;j++)
    337 			if(s[i+j-1]!=t[j]) flg=0;
    338 		if(flg) p[++tot]=i;
    339 	}
    340 	return ;
    341 }
    342 inline int addv(int x,int y){
    343 	int s=x+y;
    344 	if(s>=Mod) s-=Mod;
    345 	return s;
    346 }
    347 inline int subv(int x,int y){
    348 	int s=x-y;
    349 	if(s<0) s+=Mod;
    350 	return s;
    351 }
    352 inline void add(int&x,int y){
    353 	x=addv(x,y);
    354 	return ;
    355 }
    356 inline void sub(int&x,int y){
    357 	x=subv(x,y);
    358 	return ;
    359 }
    360 inline void Solve(){
    361 	memset(f,0x3f,sizeof(f));
    362 	memset(g,0,sizeof(g));
    363 	p[0]=-N;
    364 	f[0]=0;
    365 	g[0]=1;
    366 	p[++tot]=n+m;
    367 	for(int i=0;i<tot;i++){
    368 		int j=i+1;
    369 		while(j<=tot&&p[j]<=p[i]+m-1) j++;
    370 		for(int k=j;p[j]+m-1>=p[k]&&k<=tot;k++){
    371 			if(f[i]+1<f[k]){
    372 				f[k]=f[i]+1;
    373 				g[k]=g[i];
    374 			}
    375 			else if(f[i]+1==f[k]) add(g[k],g[i]);
    376 		}
    377 	}
    378 	printf("%d %d\n",f[tot]-1,g[tot]);
    379 	return ;
    380 }
    381 int T;
    382 int main(){
    383 	for(scanf("%d",&T);T;T--){
    384 		Init();
    385 		Solve();
    386 	}
    387 	return 0;
    388 }
    389 ```