codeforces-scrape

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

1622.md (6380B)


      1 Source: https://codeforces.com/blog/entry/98453
      2 
      3 [1622A - Construct a Rectangle](/contest/1622/problem/A "Educational Codeforces Round 120 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     vector<int> l(3);
     23     for (int i = 0; i < 3; ++i)
     24       cin >> l[i];
     25     bool ok = false;
     26     for (int i = 0; i < 3; ++i)
     27       ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3];
     28     for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0)
     29       ok |= l[(i + 1) % 3] == l[(i + 2) % 3];
     30     cout << (ok ? "YES\n" : "NO\n");
     31   }
     32 }
     33 ```
     34 
     35 [1622B - Berland Music](/contest/1622/problem/B "Educational Codeforces Round 120 (Rated for Div. 2)")
     36 
     37 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (awoo)**
     44 
     45 ```
     46 for _ in range(int(input())):
     47 	n = int(input())
     48 	p = [int(x) for x in input().split()]
     49 	s = input()
     50 	l = sorted([[s[i], p[i], i] for i in range(n)])
     51 	q = [-1 for i in range(n)]
     52 	for i in range(n):
     53 		q[l[i][2]] = i + 1
     54 	print(*q)
     55 ```
     56 
     57 [1622C - Set or Decrease](/contest/1622/problem/C "Educational Codeforces Round 120 (Rated for Div. 2)")
     58 
     59 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     60 
     61 **Tutorial**
     62 
     63 Tutorial is loading...
     64 
     65 **Solution (adedalic)**
     66 
     67 ```
     68 #include<bits/stdc++.h>
     69 
     70 using namespace std;
     71 
     72 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     73 #define sz(a) int((a).size())
     74 
     75 typedef long long li;
     76 
     77 const int INF = int(1e9);
     78 const li INF64 = li(1e18);
     79 
     80 int n;
     81 li k;
     82 vector<int> a;
     83 
     84 inline bool read() {
     85 	if(!(cin >> n >> k))
     86 		return false;
     87 	a.resize(n);
     88 	fore (i, 0, n)
     89 		cin >> a[i];
     90 	return true;
     91 }
     92 
     93 li accurateFloor(li a, li b) {
     94 	li val = a / b;
     95 	while (val * b > a)
     96 		val--;
     97 	return val;
     98 }
     99 
    100 inline void solve() {
    101 	sort(a.begin(), a.end());
    102 	vector<li> pSum(n + 1, 0);
    103 	fore (i, 0, n)
    104 		pSum[i + 1] = pSum[i] + a[i];
    105 	
    106 	li ans = 1e18;
    107 	fore (y, 0, n) {
    108 		//(a[0] - x)(y + 1) + (pSum[n - y] - a[0]) <= k
    109 		//a[0] - x <= (k - pSum[n - y] + a[0]) / (y + 1)
    110 		//x == a[0] - (k - pSum[n - y] + a[0]) / (y + 1)
    111 		
    112 		li x = a[0] - accurateFloor(k - pSum[n - y] + a[0], y + 1);
    113 		ans = min(ans, y + max(0LL, x));
    114 	}
    115 	cout << ans << endl;
    116 }
    117 
    118 int main() {
    119 #ifdef _DEBUG
    120 	freopen("input.txt", "r", stdin);
    121 #endif
    122 	ios_base::sync_with_stdio(false);
    123 	cin.tie(0), cout.tie(0);
    124 	
    125 	int t; cin >> t;
    126 	while (t--) {
    127 		read();
    128 		solve();
    129 	}
    130 	return 0;
    131 }
    132 ```
    133 
    134 [1622D - Shuffle](/contest/1622/problem/D "Educational Codeforces Round 120 (Rated for Div. 2)")
    135 
    136 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    137 
    138 **Tutorial**
    139 
    140 Tutorial is loading...
    141 
    142 **Solution (BledDest)**
    143 
    144 ```
    145 #include <bits/stdc++.h>     
    146 
    147 using namespace std;
    148 
    149 const int MOD = 998244353;
    150 
    151 int add(int x, int y)
    152 {
    153     x += y;
    154     while(x >= MOD) x -= MOD;
    155     while(x < 0) x += MOD;
    156     return x;
    157 }
    158 
    159 int main()
    160 {
    161     int n;
    162     cin >> n;
    163     int k;
    164     cin >> k;
    165     string s;
    166     cin >> s;
    167     vector<int> p(n + 1);
    168     for(int i = 0; i < n; i++) p[i + 1] = p[i] + (s[i] - '0');
    169     vector<vector<int>> C(n + 1);
    170     for(int i = 0; i <= n; i++)
    171     {
    172         C[i].resize(i + 1);
    173         C[i][0] = C[i][i] = 1;
    174         for(int j = 1; j < i; j++)
    175             C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    176     }
    177     int ans = 1;
    178     for(int i = 0; i < n; i++)
    179         for(int j = i + 1; j < n; j++)
    180         {
    181             int cnt = j + 1 - i;
    182             int cnt1 = p[j + 1] - p[i];
    183             if(cnt1 > k || p[n] < k) continue;
    184             cnt -= 2;
    185             if(s[i] == '0') cnt1--;
    186             if(s[j] == '0') cnt1--;
    187             if(cnt1 <= cnt && cnt1 >= 0 && cnt >= 0)
    188                 ans = add(ans, C[cnt][cnt1]);
    189         }
    190     cout << ans << endl;
    191 }
    192 ```
    193 
    194 [1622E - Math Test](/contest/1622/problem/E "Educational Codeforces Round 120 (Rated for Div. 2)")
    195 
    196 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    197 
    198 **Tutorial**
    199 
    200 Tutorial is loading...
    201 
    202 **Solution (Neon)**
    203 
    204 ```
    205 #include <bits/stdc++.h>
    206 
    207 using namespace std;
    208 
    209 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    210 
    211 int main() {
    212   int t;
    213   scanf("%d", &t);
    214   while (t--) {
    215     int n, m;
    216     scanf("%d%d", &n, &m);
    217     vector<int> x(n);
    218     forn(i, n) scanf("%d", &x[i]);
    219     vector<vector<int>> a(n, vector<int>(m));
    220     forn(i, n) forn(j, m) scanf("%1d", &a[i][j]);
    221     
    222     int ans = -1;
    223     vector<int> best;
    224     forn(mask, 1 << n) {
    225       vector<int> val(m);
    226       forn(i, n) forn(j, m) if (a[i][j]) val[j] += ((mask >> i) & 1) ? +1 : -1;
    227       int res = 0;
    228       forn(i, n) res += ((mask >> i) & 1) ? -x[i] : x[i];
    229       vector<int> p(m);
    230       iota(p.begin(), p.end(), 0);
    231       sort(p.begin(), p.end(), [&](int x, int y) { return val[x] < val[y]; });
    232       forn(i, m) res += val[p[i]] * (i + 1);
    233       if (res > ans) ans = res, best = p;
    234     }
    235     
    236     vector<int> ansPerm(m);
    237     forn(i, m) ansPerm[best[i]] = i;
    238     forn(i, m) printf("%d ", ansPerm[i] + 1);
    239     puts("");
    240   }
    241 }
    242 ```
    243 
    244 [1622F - Quadratic Set](/contest/1622/problem/F "Educational Codeforces Round 120 (Rated for Div. 2)")
    245 
    246 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    247 
    248 **Tutorial**
    249 
    250 Tutorial is loading...
    251 
    252 **Solution (Neon)**
    253 
    254 ```
    255 #include <bits/stdc++.h>
    256 
    257 using namespace std;
    258 
    259 const int N = 1000 * 1000 + 13;
    260 
    261 using li = unsigned long long;
    262 
    263 int pr[N];
    264 li hs[N], f[N];
    265 unordered_map<li, int> rf;
    266 
    267 int main() {
    268   int n;
    269   scanf("%d", &n);
    270   
    271   mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
    272   iota(pr, pr + N, 0);
    273   for (int i = 2; i <= n; ++i) if (pr[i] == i) {
    274     for (int j = i; j <= n; j += i) pr[j] = min(pr[j], i);
    275     hs[i] = rnd();
    276   }
    277   for (int i = 2; i <= n; ++i) {
    278     f[i] = f[i - 1];
    279     int x = i;
    280     while (x != 1) {
    281       f[i] ^= hs[pr[x]];
    282       x /= pr[x];
    283     }
    284     rf[f[i]] = i;
    285   }
    286   
    287   auto solve = [&] (int n) -> vector<int> {
    288     li fp = 0;
    289     for (int i = 2; i <= n; ++i) fp ^= f[i];
    290     if (fp == 0) return {};
    291     if (rf.count(fp)) return {rf[fp]};
    292     for (int i = 2; i <= n; ++i) {
    293         li x = f[i] ^ fp;
    294         if (rf.count(x) && rf[x] != i) return {rf[x], i};
    295     }
    296     return {2, n / 2, n};
    297   };
    298   
    299   auto ans = solve(n);
    300   printf("%d\n", n - (int)ans.size());
    301   for (int i = 1; i <= n; ++i)
    302     if (find(ans.begin(), ans.end(), i) == ans.end()) printf("%d ", i);
    303   puts("");
    304 }
    305 ```