codeforces-scrape

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

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