1703.md (6253B)
1 Source: https://codeforces.com/blog/entry/104786 2 3 Thanks for participating! 4 5 [1703A - YES или YES?](/contest/1703/problem/A "Codeforces Round 806 (Div. 4)") 6 7 Idea: [flamestorm](/profile/flamestorm "Кандидат в мастера flamestorm") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 const int MAX = 200007; 21 const int MOD = 1000000007; 22 23 void solve() { 24 string s; 25 cin >> s; 26 if (s[0] != 'y' && s[0] != 'Y') {cout << "NO\n";} 27 else if (s[1] != 'e' && s[1] != 'E') {cout << "NO\n";} 28 else if (s[2] != 's' && s[2] != 'S') {cout << "NO\n";} 29 else {cout << "YES\n";} 30 } 31 32 int main() { 33 ios::sync_with_stdio(false); 34 cin.tie(nullptr); 35 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 36 // solve(); 37 } 38 ``` 39 40 [1703B - ICPC шарики](/contest/1703/problem/B "Codeforces Round 806 (Div. 4)") 41 42 Idea: [flamestorm](/profile/flamestorm "Кандидат в мастера flamestorm") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 const int MAX = 200007; 56 const int MOD = 1000000007; 57 58 void solve() { 59 int n; 60 cin >> n; 61 string s; 62 cin >> s; 63 bool vis[26] = {}; 64 int res = 0; 65 for (char c : s) { 66 if (!vis[c - 'A']) {res += 2; vis[c - 'A'] = true;} 67 else {res++;} 68 } 69 cout << res << '\n'; 70 } 71 72 int main() { 73 ios::sync_with_stdio(false); 74 cin.tie(nullptr); 75 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 76 // solve(); 77 } 78 ``` 79 80 [1703C - Шифр](/contest/1703/problem/C "Codeforces Round 806 (Div. 4)") 81 82 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution** 89 90 ``` 91 #include <bits/stdc++.h> 92 using namespace std; 93 94 void solve() 95 { 96 int n; 97 cin >> n; 98 int a[n]; 99 for(int i = 0; i < n; i++) 100 { 101 cin >> a[i]; 102 } 103 for(int i = 0; i < n; i++) 104 { 105 int b; 106 cin >> b; 107 if(b == 0) 108 { 109 continue; 110 } 111 string now; 112 cin >> now; 113 for(int j = 0; j < b; j++) 114 { 115 if(now[j] == 'U'){a[i]--;} 116 else if(now[j] == 'D'){a[i]++;} 117 if(a[i] < 0){a[i]+=10;} 118 if(a[i] > 9){a[i]-=10;} 119 } 120 } 121 for(int i = 0; i < n; i++) 122 { 123 cout << a[i] << " "; 124 } 125 cout << endl; 126 } 127 128 int main(){ 129 int t; 130 cin>> t; 131 while(t--) 132 { 133 solve(); 134 } 135 return 0; 136 } 137 ``` 138 139 [1703D - Двойные строки](/contest/1703/problem/D "Codeforces Round 806 (Div. 4)") 140 141 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 142 143 **Tutorial** 144 145 Tutorial is loading... 146 147 **Solution** 148 149 ``` 150 #include <bits/stdc++.h> 151 152 using namespace std; 153 154 const int MAX = 200007; 155 const int MOD = 1000000007; 156 157 void solve() { 158 int n; 159 cin >> n; 160 string s[n]; 161 map<string, bool> mp; 162 for (int i = 0; i < n; i++) { 163 cin >> s[i]; 164 mp[s[i]] = true; 165 } 166 for (int i = 0; i < n; i++) { 167 bool ok = false; 168 for (int j = 1; j < s[i].length(); j++) { 169 string pref = s[i].substr(0, j), suff = s[i].substr(j, s[i].length() - j); 170 if (mp[pref] && mp[suff]) {ok = true;} 171 } 172 cout << ok; 173 } 174 cout << '\n'; 175 } 176 177 int main() { 178 ios::sync_with_stdio(false); 179 cin.tie(nullptr); 180 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 181 // solve(); 182 } 183 ``` 184 185 [1703E - Симметричная решётка](/contest/1703/problem/E "Codeforces Round 806 (Div. 4)") 186 187 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 188 189 **Tutorial** 190 191 Tutorial is loading... 192 193 **Solution** 194 195 ``` 196 #include <bits/stdc++.h> 197 using namespace std; 198 199 void solve() 200 { 201 int n; 202 cin >> n; 203 int a[n][n]; 204 for(int i = 0; i < n; i++) 205 { 206 for(int j = 0; j < n; j++) 207 { 208 char c; 209 cin >> c; 210 a[i][j] = c-'0'; 211 } 212 } 213 int ans = 0; 214 for(int i = 0; i < (n+1)/2; i++) 215 { 216 for(int j = 0; j < n/2; j++) 217 { 218 int nowi = i, nowj = j; 219 int oldnowj = nowj; 220 int sum = a[nowi][nowj]; 221 nowj = n-nowi-1; 222 nowi = oldnowj; 223 sum+=a[nowi][nowj]; 224 oldnowj = nowj; 225 nowj = n-nowi-1; 226 nowi = oldnowj; 227 sum+=a[nowi][nowj]; 228 oldnowj = nowj; 229 nowj = n-nowi-1; 230 nowi = oldnowj; 231 sum+=a[nowi][nowj]; 232 ans+=min(sum, 4-sum); 233 } 234 } 235 cout << ans << endl; 236 } 237 238 int main(){ 239 int t; 240 cin>> t; 241 while(t--) 242 { 243 solve(); 244 } 245 return 0; 246 } 247 ``` 248 249 [1703F - Очередная задача про пары, удовлетворяющие неравенству](/contest/1703/problem/F "Codeforces Round 806 (Div. 4)") 250 251 Idea: [flamestorm](/profile/flamestorm "Кандидат в мастера flamestorm") 252 253 **Tutorial** 254 255 Tutorial is loading... 256 257 **Solution** 258 259 ``` 260 #include <bits/stdc++.h> 261 262 using namespace std; 263 264 const int MAX = 200007; 265 const int MOD = 1000000007; 266 267 void solve() { 268 int n; 269 cin >> n; 270 int a[n + 1]; 271 for (int i = 1; i <= n; i++) { 272 cin >> a[i]; 273 } 274 long long res = 0; 275 vector<int> v; 276 for (int i = 1; i <= n; i++) { 277 if (a[i] >= i) {continue;} 278 res += (long long)(lower_bound(v.begin(), v.end(), a[i]) - v.begin()); 279 v.push_back(i); 280 } 281 cout << res << '\n'; 282 } 283 284 int main() { 285 ios::sync_with_stdio(false); 286 cin.tie(nullptr); 287 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 288 // solve(); 289 } 290 ``` 291 292 [1703G - Хороший ключ, плохой ключ](/contest/1703/problem/G "Codeforces Round 806 (Div. 4)") 293 294 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 295 296 **Tutorial** 297 298 Tutorial is loading... 299 300 **Solution** 301 302 ``` 303 #include <bits/stdc++.h> 304 using namespace std; 305 306 void solve() 307 { 308 int n, k; 309 cin >> n >> k; 310 int a[n]; 311 for(int i = 0; i < n; i++) 312 { 313 cin >> a[i]; 314 } 315 long long ans = 0; 316 long long sum = 0; 317 for(int i = -1; i < n; i++) 318 { 319 long long now = sum; 320 for(int j = i+1; j < min(n, i+32); j++) 321 { 322 int copy = a[j]; 323 copy>>=j-i; 324 now+=copy; 325 } 326 ans = max(ans, now); 327 if(i+1 != n) 328 { 329 sum+=a[i+1]-k; 330 } 331 } 332 cout << ans << endl; 333 } 334 335 int main(){ 336 int t; 337 cin >> t; 338 while(t--) 339 { 340 solve(); 341 } 342 return 0; 343 } 344 ```