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 ```