1279.md (6302B)
1 Source: https://codeforces.com/blog/entry/72577 2 3 [1279A - New Year Garland](/contest/1279/problem/A "Educational Codeforces Round 79 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 for t in range(int(input())): 15 a = sorted(list(map(int, input().split()))) 16 print('Yes' if a[2] <= a[0] + a[1] + 1 else 'No') 17 ``` 18 19 [1279B - Verse For Santa](/contest/1279/problem/B "Educational Codeforces Round 79 (Rated for Div. 2)") 20 21 Idea: [Roms](/profile/Roms "Master Roms") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (Roms)** 28 29 ``` 30 for t in range(int(input())): 31 n, t = map(int, input().split()) 32 a = list(map(int, input().split())) 33 id = 0 34 for i in range(n): 35 if a[i] > a[id]: 36 id = i 37 t -= a[i] 38 if t < 0: 39 break 40 41 if t >= 0: 42 id = -1 43 print(id + 1) 44 ``` 45 46 [1279C - Stack of Presents](/contest/1279/problem/C "Educational Codeforces Round 79 (Rated for Div. 2)") 47 48 Idea: [Roms](/profile/Roms "Master Roms") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution (Roms)** 55 56 ``` 57 for t in range(int(input())): 58 n, m = map(int, input().split()) 59 a = [x - 1 for x in list(map(int, input().split()))] 60 b = [x - 1 for x in list(map(int, input().split()))] 61 pos = a[:] 62 for i in range(n): 63 pos[a[i]] = i 64 65 lst = -1 66 res = m 67 for i in range(m): 68 if pos[b[i]] > lst: 69 res += 2 * (pos[b[i]] - i) 70 lst = pos[b[i]] 71 72 print(res) 73 ``` 74 75 [1279D - Santa's Bot](/contest/1279/problem/D "Educational Codeforces Round 79 (Rated for Div. 2)") 76 77 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 78 79 **Tutorial** 80 81 Tutorial is loading... 82 83 **Solution (Ne0n25)** 84 85 ``` 86 #include <bits/stdc++.h> 87 88 using namespace std; 89 90 #define x first 91 #define y second 92 #define pb push_back 93 #define mp make_pair 94 #define sqr(a) ((a) * (a)) 95 #define sz(a) int((a).size()) 96 #define all(a) (a).begin(), (a).end() 97 #define forn(i, n) for (int i = 0; i < int(n); ++i) 98 99 const int MOD = 998244353; 100 const int N = 1e6 + 7; 101 102 int n; 103 vector<int> a[N]; 104 int cnt[N]; 105 int inv[N]; 106 107 int add(int a, int b) { 108 a += b; 109 if (a >= MOD) a -= MOD; 110 return a; 111 } 112 113 int mul(int a, int b) { 114 return a * 1ll * b % MOD; 115 } 116 117 int binpow(int a, int b) { 118 int res = 1; 119 while (b) { 120 if (b & 1) res = mul(res, a); 121 a = mul(a, a); 122 b >>= 1; 123 } 124 return res; 125 } 126 127 int main() { 128 scanf("%d", &n); 129 forn(i, n) { 130 int k; 131 scanf("%d", &k); 132 a[i].resize(k); 133 forn(j, k) scanf("%d", &a[i][j]); 134 forn(j, k) cnt[a[i][j]]++; 135 } 136 137 forn(i, N) inv[i] = binpow(i, MOD - 2); 138 139 int ans = 0; 140 forn(i, n) for (auto x : a[i]) 141 ans = add(ans, mul(mul(inv[n], inv[sz(a[i])]), mul(cnt[x], inv[n]))); 142 143 printf("%d\n", ans); 144 } 145 ``` 146 147 [1279E - New Year Permutations](/contest/1279/problem/E "Educational Codeforces Round 79 (Rated for Div. 2)") 148 149 Idea: [Neon](/profile/Neon "Candidate Master Neon") 150 151 **Tutorial** 152 153 Tutorial is loading... 154 155 **Solution (Ne0n25)** 156 157 ``` 158 #include <bits/stdc++.h> 159 160 using namespace std; 161 162 #define x first 163 #define y second 164 #define pb push_back 165 #define mp make_pair 166 #define sqr(a) ((a) * (a)) 167 #define sz(a) int((a).size()) 168 #define all(a) (a).begin(), (a).end() 169 #define forn(i, n) for (int i = 0; i < int(n); ++i) 170 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 171 172 typedef long long li; 173 typedef long double ld; 174 175 const int N = 55; 176 const li INF = 2e18; 177 178 int n; 179 li k; 180 181 li cycl[N], cnt[N]; 182 bool used[N]; 183 int ans[N]; 184 185 li add(li x, li y) { 186 return min(INF, x + y); 187 } 188 189 li mul(li x, li y) { 190 ld t = ld(x) + y; 191 if (t > INF) return INF; 192 return x * y; 193 } 194 195 void solve() { 196 cin >> n >> k; 197 --k; 198 199 cycl[0] = cycl[1] = 1; 200 fore(i, 2, n + 1) 201 cycl[i] = mul(cycl[i - 1], i - 1); 202 203 cnt[n] = 1; 204 for (int i = n - 1; i >= 0; i--) { 205 cnt[i] = 0; 206 fore(val, i, n) { 207 int len = (val - i) + 1; 208 cnt[i] = add(cnt[i], mul(cnt[i + len], cycl[len - 1])); 209 } 210 } 211 212 if (cnt[0] <= k) { 213 cout << -1 << endl; 214 return; 215 } 216 217 memset(used, 0, sizeof(used)); 218 memset(ans, -1, sizeof(ans)); 219 220 forn(i, n) { 221 fore(val, i, n) { 222 int len = (val - i) + 1; 223 li cur = mul(cnt[i + len], cycl[len - 1]); 224 225 if (cur <= k) { 226 k -= cur; 227 continue; 228 } 229 230 ans[i] = val; 231 used[val] = true; 232 233 for (int j = i + 1; j < i + len; j++) { 234 int lft = len - (j - i) - 1; 235 fore(nval, i, val) if (!used[nval] && j != nval) { 236 if (j != i + len - 1) { 237 int tmp = ans[nval]; 238 while (tmp != -1 && tmp != j) 239 tmp = ans[tmp]; 240 if (tmp == j) continue; 241 } 242 243 li cur = mul(cnt[i + len], cycl[lft]); 244 if (cur <= k) { 245 k -= cur; 246 continue; 247 } 248 249 ans[j] = nval; 250 used[nval] = true; 251 break; 252 } 253 } 254 255 i += len - 1; 256 break; 257 } 258 } 259 260 forn(i, n) cout << ans[i] + 1 << ' '; 261 cout << endl; 262 } 263 264 int main() { 265 int tc; 266 cin >> tc; 267 forn(i, tc) solve(); 268 } 269 ``` 270 271 [1279F - New Year and Handle Change](/contest/1279/problem/F "Educational Codeforces Round 79 (Rated for Div. 2)") 272 273 Idea: [vovuh](/profile/vovuh "Master vovuh") 274 275 **Tutorial** 276 277 Tutorial is loading... 278 279 **Solution (vovuh)** 280 281 ``` 282 #include <bits/stdc++.h> 283 284 using namespace std; 285 286 const int N = 1000 * 1000 + 11; 287 const int INF = 1e9; 288 289 int n, k, l; 290 string s; 291 int a[N]; 292 pair<int, int> dp[N]; 293 294 int calc(int mid) { 295 for (int i = 0; i <= n; ++i) { 296 dp[i] = make_pair(INF, INF); 297 } 298 dp[0] = make_pair(0, 0); 299 for (int i = 0; i < n; ++i) { 300 if (dp[i + 1] > make_pair(dp[i].first + a[i], dp[i].second)) { 301 dp[i + 1] = make_pair(dp[i].first + a[i], dp[i].second); 302 } 303 if (dp[min(n, i + l)] > make_pair(dp[i].first + mid, dp[i].second + 1)) { 304 dp[min(n, i + l)] = make_pair(dp[i].first + mid, dp[i].second + 1); 305 } 306 } 307 return dp[n].second; 308 } 309 310 int solve() { 311 int l = 0, r = n; 312 int res = 0; 313 while (l <= r) { 314 int mid = (l + r) >> 1; 315 if (calc(mid) > k) { 316 l = mid + 1; 317 res = mid; 318 } else { 319 r = mid - 1; 320 } 321 } 322 if (calc(res) <= k) return 0; 323 calc(res + 1); 324 return dp[n].first - (res + 1) * 1ll * k; 325 } 326 327 int main() { 328 #ifdef _DEBUG 329 freopen("input.txt", "r", stdin); 330 // freopen("output.txt", "w", stdout); 331 #endif 332 333 cin >> n >> k >> l >> s; 334 for (int i = 0; i < n; ++i) { 335 a[i] = islower(s[i]) > 0; 336 } 337 int ans = INF; 338 ans = min(ans, solve()); 339 for (int i = 0; i < n; ++i) { 340 a[i] = isupper(s[i]) > 0; 341 } 342 ans = min(ans, solve()); 343 cout << ans << endl; 344 345 return 0; 346 } 347 ```