codeforces-scrape

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

1759.md (6731B)


      1 Source: https://codeforces.com/blog/entry/109254
      2 
      3 [1759A - Yes-Yes?](/contest/1759/problem/A "Codeforces Round  834 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 full = 'Yes' * 18
     15 t = int(input())
     16 for _ in range(t):
     17     if full.find(input()) >= 0:
     18         print('YES')
     19     else:
     20         print('NO')
     21 ```
     22 
     23 [1759B - Lost Permutation](/contest/1759/problem/B "Codeforces Round  834 (Div. 3)")
     24 
     25 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution**
     32 
     33 ```
     34 t = int(input())
     35 for _ in range(t):
     36     n, s = map(int, input().split())
     37     a = [int(x) for x in input().split()]
     38     s += sum(a)
     39     sm = 0
     40     cnt = 0
     41     for i in range(1, s + 1):
     42         if sm >= s:
     43             break
     44         sm += i
     45         cnt = i
     46     if sm != s or max(a) > cnt or cnt <= n:
     47         print("NO");
     48     else:
     49         print("YES")
     50 ```
     51 
     52 [1759C - Thermostat](/contest/1759/problem/C "Codeforces Round  834 (Div. 3)")
     53 
     54 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution**
     61 
     62 ```
     63 def solve():
     64     l, r, x = map(int, input().split())
     65     a, b = map(int, input().split())
     66     if a == b:
     67         return 0
     68     if abs(a - b) >= x:
     69         return 1
     70     if r - max(a, b) >= x or min(a, b) - l >= x:
     71         return 2
     72     if r - b >= x and a - l >= x or r - a >= x and b - l >= x:
     73         return 3
     74     return -1
     75 
     76 t = int(input())
     77 for _ in range(t):
     78     print(solve())
     79 ```
     80 
     81 [1759D - Make It Round](/contest/1759/problem/D "Codeforces Round  834 (Div. 3)")
     82 
     83 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     84 
     85 **Tutorial**
     86 
     87 Tutorial is loading...
     88 
     89 **Solution**
     90 
     91 ```
     92 #include <bits/stdc++.h>
     93 
     94 using namespace std;
     95 
     96 #define forn(i, n) for (int i = 0; i < int(n); i++)
     97 #define sz(v) (int)v.size()
     98 #define all(v) v.begin(),v.end()
     99 #define eb emplace_back
    100 
    101 using ll = long long;
    102 
    103 void solve() {
    104     ll n,m; cin >> n >> m;
    105     ll n0 = n;
    106     int cnt2 = 0, cnt5 = 0;
    107     ll k = 1;
    108     while (n > 0 && n % 2 == 0) {
    109         n /= 2;
    110         cnt2++;
    111     }
    112     while (n > 0 && n % 5 == 0) {
    113         n /= 5;
    114         cnt5++;
    115     }
    116     while (cnt2 < cnt5 && k * 2 <= m) {
    117         cnt2++;
    118         k *= 2;
    119     }
    120     while (cnt5 < cnt2 && k * 5 <= m) {
    121         cnt5++;
    122         k *= 5;
    123     }
    124     while (k * 10 <= m) {
    125         k *= 10;
    126     }
    127     if (k == 1) {
    128         cout << n0 * m << endl;
    129     } else {
    130         k *= m / k; // 1 <= m/k < 10
    131         cout << n0 * k << endl;
    132     }
    133 }
    134 
    135 int main() {
    136     int t;
    137     cin >> t;
    138 
    139     forn(tt, t) {
    140         solve();
    141     }
    142 }
    143 ```
    144 
    145 [1759E - The Humanoid](/contest/1759/problem/E "Codeforces Round  834 (Div. 3)")
    146 
    147 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution**
    154 
    155 ```
    156 #include <bits/stdc++.h>
    157 
    158 using namespace std;
    159 
    160 const int MAXN = 200200;
    161 
    162 int n;
    163 int arr[MAXN];
    164 
    165 int solve(int i, long long h, int s2, int s3) {
    166 	if (i == n) return 0;
    167 	if (arr[i] < h)
    168 		return solve(i + 1, h + (arr[i] / 2), s2, s3) + 1;
    169 	int ans1 = (s2 ? solve(i, h * 2, s2 - 1, s3) : 0);
    170 	int ans2 = (s3 ? solve(i, h * 3, s2, s3 - 1) : 0);
    171 	return max(ans1, ans2);
    172 }
    173 
    174 int main() {
    175 	int t; cin >> t;
    176 	while(t--) {
    177 		long long h; cin >> n >> h;
    178 		for (int i = 0; i < n; ++i)
    179 			cin >> arr[i];
    180 		sort(arr, arr + n);
    181 		cout << solve(0, h, 2, 1) << endl;
    182 	}
    183 }
    184 ```
    185 
    186 [1759F - All Possible Digits](/contest/1759/problem/F "Codeforces Round  834 (Div. 3)")
    187 
    188 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Solution**
    195 
    196 ```
    197 #pragma GCC optimize("Ofast")
    198 
    199 #include <bits/stdc++.h>
    200 
    201 using namespace std;
    202 
    203 #include <ext/pb_ds/assoc_container.hpp>
    204 
    205 using namespace __gnu_pbds;
    206 
    207 typedef long long ll;
    208 typedef long double ld;
    209 typedef tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
    210 
    211 int newDigit = -1;
    212 
    213 bool check(set<int> digits, int l, int r, bool useNewDigit) {
    214     for (int i = l; i <= r; ++i) {
    215         if (useNewDigit && i == newDigit) {
    216             continue;
    217         }
    218         if (!digits.count(i)) {
    219             return false;
    220         }
    221     }
    222     return true;
    223 }
    224 
    225 void solve() {
    226     int n, p;
    227     cin >> n >> p;
    228     vector<int> a(n + 1);
    229     set<int> digits;
    230     for (int i = 1; i <= n; ++i) {
    231         cin >> a[i];
    232         digits.insert(a[i]);
    233     }
    234     if (digits.size() == p) {
    235         cout << "0\n";
    236         return;
    237     }
    238     for (int i = n - 1; i >= 0; --i) {
    239         if (a[i] < p - 1) {
    240             newDigit = a[i] + 1;
    241             break;
    242         }
    243     }
    244     int l = 0, r = p - 1;
    245     int x = a[n];
    246     while (l < r) {
    247         int m = (l + r) >> 1;
    248         bool res = false;
    249         if (x + m >= p) {
    250             if (check(digits, x + m + 1 - p, x - 1, true)) {
    251                 res = true;
    252             }
    253         } else {
    254             if (check(digits, 0, x - 1, false) && check(digits, x + m + 1, p - 1, false)) {
    255                 res = true;
    256             }
    257         }
    258         if (res) {
    259             r = m;
    260         } else {
    261             l = m + 1;
    262         }
    263     }
    264     cout << l << '\n';
    265 }
    266 
    267 bool multitest = true;
    268 
    269 int main() {
    270     ios_base::sync_with_stdio(0);
    271     cin.tie(0);
    272     cout.tie(0);
    273     cout.precision(25);
    274     size_t number_of_tests = 1;
    275     if (multitest) {
    276         cin >> number_of_tests;
    277     }
    278     for (size_t _ = 0; _ < number_of_tests; ++_) {
    279         solve();
    280     }
    281     return 0;
    282 }
    283 ```
    284 
    285 [1759G - Restore the Permutation](/contest/1759/problem/G "Codeforces Round  834 (Div. 3)")
    286 
    287 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    288 
    289 **Tutorial**
    290 
    291 Tutorial is loading...
    292 
    293 **Solution**
    294 
    295 ```
    296 #include "bits/stdc++.h"
    297 using namespace std;
    298 int n;
    299 
    300 void solve(){
    301     cin >> n;
    302     vector<int>b(n / 2), p(n);
    303     vector<bool>isUsed(n + 1, false);
    304     set<int>unused;
    305 
    306     for(int i = 0; i < n / 2; i++){
    307         cin >> b[i];
    308         p[i * 2 + 1] = b[i];
    309         isUsed[b[i]] = true;
    310     }
    311     for(int i = 1; i <= n; i++){
    312         if(!isUsed[i]) unused.insert(i);
    313     }
    314 
    315     if(int(unused.size()) != n / 2){
    316         cout << "-1\n";
    317         return;
    318     }
    319 
    320     for(int i = n / 2 - 1; i >= 0; i--){
    321         auto k = unused.upper_bound(p[2 * i + 1]);
    322         if(k == unused.begin()){
    323             cout << "-1\n";
    324             return;
    325         }
    326 
    327         k--;
    328 
    329         if(*k < p[2 * i + 1]){
    330             p[2 * i] = *k;
    331             unused.erase(k);
    332         }
    333         else{
    334             cout << "-1\n";
    335             return;
    336         }
    337     }
    338     for(auto i : p) cout << i << ' ';
    339     cout << endl;
    340 }
    341 
    342 int main(){
    343     ios_base::sync_with_stdio(false);
    344     cin.tie(nullptr);
    345 
    346     int t;
    347     cin >> t;
    348     while(t--){
    349         solve();
    350     }
    351 
    352 }
    353 ```