codeforces-scrape

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

1594.md (11537B)


      1 Source: https://codeforces.com/blog/entry/95525
      2 
      3 [1594A - Загадка последовательной суммы](/contest/1594/problem/A "Codeforces Round 747 (Div. 2)")
      4 
      5 **Hint**
      6 
      7 See how $n = 2$ case works.
      8 
      9 **Solution**
     10 
     11 Tutorial is loading...
     12 
     13 **Code (C++)**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 using namespace std;
     18 typedef long long ll;
     19 int main(void){
     20     ios_base::sync_with_stdio(0);
     21     cin.tie(0);
     22     int t;
     23     cin>>t;
     24     while(t--){
     25         ll n;
     26         cin>>n;
     27         cout<<-n+1<<" "<<n<<endl;
     28     }
     29 }
     30 ```
     31 
     32 [1594B - Особые числа](/contest/1594/problem/B "Codeforces Round 747 (Div. 2)")
     33 
     34 **Hint**
     35 
     36 Think of the numbers in base $n$.
     37 
     38 **Solution**
     39 
     40 Tutorial is loading...
     41 
     42 **Code (C++)**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 using namespace std;
     47 typedef long long ll;
     48 const ll INF = 1e9+7;
     49 const ll MOD = 998244353;
     50 typedef pair<ll,ll> ii;
     51 #define iii pair<ll,ii>
     52 #define f(i,a,b) for(ll i = a;i < b;i++)
     53 #define pb push_back
     54 #define vll vector<ll>
     55 #define F first
     56 #define S second
     57 #define all(x) (x).begin(), (x).end()
     58 int main(void){
     59     ios_base::sync_with_stdio(0);
     60     cin.tie(0);
     61     int t;
     62     cin>>t;
     63     while(t--){
     64         ll n,k;
     65         cin>>n>>k;
     66         ll p = 1;
     67         ll ans = 0;
     68         f(j,0,31){
     69             if(k & (1<<j)){
     70                 ans = (ans + p) % INF;
     71             }
     72             p *= n;
     73             p %= INF;
     74         }
     75         cout<<ans<<"\n";
     76     }
     77 }
     78 ```
     79 
     80 [1594C - Сделай их равными](/contest/1594/problem/C "Codeforces Round 747 (Div. 2)")
     81 
     82 **Hint**
     83 
     84 You need atmost 2 operations.
     85 
     86 **Solution**
     87 
     88 Tutorial is loading...
     89 
     90 **Code (C++)**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 using namespace std;
     95 typedef long long ll;
     96 const ll INF = 1e9+7;
     97 const ll MOD = 998244353;
     98 typedef pair<ll,ll> ii;
     99 #define iii pair<ll,ii>
    100 #define f(i,a,b) for(int i = a;i < b;i++)
    101 #define pb push_back
    102 #define vll vector<ll>
    103 #define F first
    104 #define S second
    105 #define all(x) (x).begin(), (x).end()
    106 int main(void){
    107     ios_base::sync_with_stdio(0);
    108     cin.tie(0);
    109     int t;
    110     cin>>t;
    111     while(t--){
    112         ll n;
    113         cin>>n;
    114         char c;
    115         cin>>c;
    116         string s;
    117         cin>>s;
    118         vector<int>ans;
    119         bool ok = true;
    120         for(auto x:s){
    121             if(x != c){
    122                 ok = false;
    123             }
    124         }
    125         if(!ok){
    126             f(i,1,n+1){
    127                 ok = true;
    128                 f(j,i,n+1){
    129                     ok &= (s[j-1] == c);
    130                     j += i-1;
    131                 }
    132                 if(ok){
    133                     ans.pb(i);
    134                     break;
    135                 }
    136             }
    137             if(!ok){
    138                 ans.pb(n);
    139                 ans.pb(n-1);
    140             }
    141         }
    142         cout<<ans.size()<<"\n";
    143         for(auto x:ans){
    144             cout<<x<<" ";
    145         }
    146         cout<<"\n";
    147     }
    148 }
    149 ```
    150 
    151 [1594D - Количество предателей](/contest/1594/problem/D "Codeforces Round 747 (Div. 2)")
    152 
    153 **Hint**
    154 
    155 Construct a graph from the comments.
    156 
    157 **Solution**
    158 
    159 Tutorial is loading...
    160 
    161 **Code 1(C++)**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 using namespace std;
    166 typedef long long ll;
    167 const ll INF = 1e9+7;
    168 const ll MOD = 998244353;
    169 typedef pair<ll,ll> ii;
    170 #define iii pair<ll,ii>
    171 #define f(i,a,b) for(int i = a;i < b;i++)
    172 #define pb push_back
    173 #define vll vector<ll>
    174 #define F first
    175 #define S second
    176 #define all(x) (x).begin(), (x).end()
    177 vector<vector<ii> >adj;
    178 int c[2];
    179 int colour[700005];
    180 bool ok;
    181 int n;
    182 void dfs(int idx){
    183     c[colour[idx]]+= (idx <= n);
    184     for(auto x:adj[idx]){
    185         if(colour[x.F] == -1){
    186             colour[x.F] = colour[idx] ^ x.S;
    187             dfs(x.F);
    188         }
    189         else if(colour[x.F] != (colour[idx] ^ x.S)){
    190             ///impossible
    191             ok = false;
    192         }
    193     }
    194 }
    195 int main(void){
    196     ios_base::sync_with_stdio(0);
    197     cin.tie(0);
    198     int t;
    199     cin>>t;
    200     while(t--){
    201         int m;
    202         cin>>n>>m;
    203         ///n original + m atmost fake nodes
    204         adj.assign(n+m+5,vector<ii>());
    205         f(i,0,n+m+5){
    206             colour[i] = -1;
    207         }
    208         int fake = n+1;
    209         f(i,0,m){
    210             int a,b;
    211             string c;
    212             cin>>a>>b>>c;
    213             if(c == "crewmate"){
    214                 ///same team
    215                 adj[a].pb(ii(fake,1));
    216                 adj[fake].pb(ii(a,1));
    217                 adj[fake].pb(ii(b,1));
    218                 adj[b].pb(ii(fake,1));
    219                 fake++;
    220             }
    221             else{
    222                 ///different team
    223                 adj[a].pb(ii(b,1));
    224                 adj[b].pb(ii(a,1));
    225             }
    226         }
    227         int ans = 0;
    228         ok = true;
    229         f(i,1,n+1){
    230             if(colour[i] == -1){
    231                 colour[i] = 0;
    232                 c[0] = c[1] = 0;
    233                 dfs(i);
    234                 ans += max(c[0],c[1]);
    235             }
    236         }
    237         if(!ok){
    238             ans = -1;
    239         }
    240         cout<<ans<<"\n";
    241     }
    242 }
    243 ```
    244 
    245 **Code 2(C++)**
    246 
    247 ```
    248 #include <bits/stdc++.h>
    249 using namespace std;
    250 typedef long long ll;
    251 const ll INF = 1e9+7;
    252 const ll MOD = 998244353;
    253 typedef pair<ll,ll> ii;
    254 #define iii pair<ll,ii>
    255 #define f(i,a,b) for(int i = a;i < b;i++)
    256 #define pb push_back
    257 #define vll vector<ll>
    258 #define F first
    259 #define S second
    260 #define all(x) (x).begin(), (x).end()
    261 vector<vector<ii> >adj;
    262 int c[2];
    263 int colour[200005];
    264 bool ok;
    265 void dfs(int idx){
    266     c[colour[idx]]++;
    267     for(auto x:adj[idx]){
    268         if(colour[x.F] == -1){
    269             colour[x.F] = colour[idx] ^ x.S;
    270             dfs(x.F);
    271         }
    272         else if(colour[x.F] != (colour[idx] ^ x.S)){
    273             ///impossible
    274             ok = false;
    275         }
    276     }
    277 }
    278 int main(void){
    279     ios_base::sync_with_stdio(0);
    280     cin.tie(0);
    281     int t;
    282     cin>>t;
    283     while(t--){
    284         int n,m;
    285         cin>>n>>m;
    286         adj.assign(n+5,vector<ii>());
    287         f(i,0,n+5){
    288             colour[i] = -1;
    289         }
    290         f(i,0,m){
    291             int a,b;
    292             string c;
    293             cin>>a>>b>>c;
    294             if(c == "crewmate"){
    295                 ///same team
    296                 adj[a].pb(ii(b,0));
    297                 adj[b].pb(ii(a,0));
    298             }
    299             else{
    300                 ///different team
    301                 adj[a].pb(ii(b,1));
    302                 adj[b].pb(ii(a,1));
    303             }
    304         }
    305         int ans = 0;
    306         ok = true;
    307         f(i,1,n+1){
    308             if(colour[i] == -1){
    309                 colour[i] = 0;
    310                 c[0] = c[1] = 0;
    311                 dfs(i);
    312                 ans += max(c[0],c[1]);
    313             }
    314         }
    315         if(!ok){
    316             ans = -1;
    317         }
    318         cout<<ans<<"\n";
    319     }
    320 }
    321 ```
    322 
    323 [1594E1 - Раскраска кубика Рубика (простая версия)](/contest/1594/problem/E1 "Codeforces Round 747 (Div. 2)")
    324 
    325 **Hint**
    326 
    327 Think of how many colorings there are if you color only the root with one color.
    328 
    329 **Solution**
    330 
    331 Tutorial is loading...
    332 
    333 **Code (C++)**
    334 
    335 ```
    336 #include <bits/stdc++.h>
    337 using namespace std;
    338 typedef long long ll;
    339 const ll INF = 1e9+7;
    340 const ll MOD = 998244353;
    341 typedef pair<ll,ll> ii;
    342 #define iii pair<ii,ll>
    343 #define f(i,a,b) for(ll i = a;i < b;i++)
    344 #define pb push_back
    345 #define vll vector<ll>
    346 #define F first
    347 #define S second
    348 #define all(x) (x).begin(), (x).end()
    349 ll power(ll a,ll b,ll mod){
    350     if(b == 0){
    351         return 1;
    352     }
    353     ll ans = power(a,b/2,mod);
    354     ans *= ans;
    355     ans %= mod;
    356     if(b % 2){
    357         ans *= a;
    358     }
    359     return ans % mod;
    360 }
    361 int main(void){
    362     ios_base::sync_with_stdio(0);
    363     cin.tie(0);
    364     ll k;
    365     cin>>k;
    366     ll othernodes = (1LL<<k) - 2;
    367     ll ans = power(4,othernodes,INF);
    368     ans *= 6;
    369     ans %= INF;
    370     cout<<ans<<"\n";
    371 }
    372 ```
    373 
    374 [1594E2 - Раскраска кубика Рубика (сложная версия)](/contest/1594/problem/E2 "Codeforces Round 747 (Div. 2)")
    375 
    376 **Hint**
    377 
    378 If you have a tree with a root with a fixed color and the others are all not predefined the number of colorings is $4^{nodes-1}$.
    379 
    380 **Solution**
    381 
    382 Tutorial is loading...
    383 
    384 **Code (C++)**
    385 
    386 ```
    387 #include <bits/stdc++.h>
    388 using namespace std;
    389 typedef long long ll;
    390 const ll INF = 1e9+7;
    391 const ll MOD = 998244353;
    392 typedef pair<ll,ll> ii;
    393 #define iii pair<ii,ll>
    394 #define f(i,a,b) for(ll i = a;i < b;i++)
    395 #define pb push_back
    396 #define vll vector<ll>
    397 #define F first
    398 #define S second
    399 #define all(x) (x).begin(), (x).end()
    400 ll dp[(60 * 10000) + 5][6];
    401 vll color[6];
    402 vector<vector<int> >adj;
    403 map<ll,int>label;
    404 ll c[(60 * 10000) + 5];
    405 ll solve(int i,int j){
    406     if(c[i] != -1 && c[i] != j){
    407         return 0;
    408     }
    409     if(dp[i][j] != -1){
    410         return dp[i][j];
    411     }
    412     ll ans = 0;
    413     ll sum[2] = {0};
    414     for(auto x:color[j]){
    415         f(j,0,adj[i].size()){
    416             sum[j] += solve(adj[i][j],x);
    417             sum[j] %= INF;
    418         }
    419     }
    420     if(adj[i].empty()){
    421         sum[0] = sum[1] = 1;
    422     }
    423     if((ll)adj[i].size() == 1){
    424         sum[1] = 1;
    425     }
    426     ans = (sum[0] * sum[1]) % INF;
    427     return dp[i][j] = ans;
    428 }
    429 ll power(ll a,ll b,ll mod){
    430     if(b == 0){
    431         return 1;
    432     }
    433     ll ans = power(a,b/2,mod);
    434     ans *= ans;
    435     ans %= mod;
    436     if(b % 2){
    437         ans *= a;
    438     }
    439     return ans % mod;
    440 }
    441 int main(void){
    442     ios_base::sync_with_stdio(0);
    443     cin.tie(0);
    444     color[0] = {1,2,4,5};
    445     color[1] = {0,2,3,5};
    446     color[2] = {0,1,3,4};
    447     color[3] = {1,2,4,5};
    448     color[4] = {0,2,3,5};
    449     color[5] = {0,1,3,4};
    450     map<string,ll>mp;
    451     mp["white"] = 0;
    452     mp["blue"] = 1;
    453     mp["red"] = 2;
    454     mp["yellow"] = 3;
    455     mp["green"] = 4;
    456     mp["orange"] = 5;
    457     memset(dp,-1,sizeof dp);
    458     memset(c,-1,sizeof c);
    459     ll k;
    460     cin>>k;
    461     ll n;
    462     cin>>n;
    463     ll posoi = (1LL<<k) - 1;
    464     int lab = 0;
    465     map<ll,int>ar;
    466     f(i,0,n){
    467         ll x;
    468         cin>>x;
    469         string s;
    470         cin>>s;
    471         ar[x] = mp[s];
    472         ll cur = x;
    473         while(cur >= 1 && !label.count(cur)){
    474             label[cur] = lab;
    475             lab++;
    476             posoi--;
    477             cur /= 2;
    478         }
    479     }
    480     adj.assign(lab + 5,vector<int>());
    481     for(auto x:label){
    482         if(ar.count(x.F)){
    483             c[x.S] = ar[x.F];
    484         }
    485         if(label.count(x.F * 2)){
    486             adj[x.S].pb(label[x.F * 2]);
    487         }
    488         if(label.count(x.F * 2 + 1)){
    489             adj[x.S].pb(label[x.F * 2 + 1]);
    490         }
    491     }
    492     ll ans = power(4,posoi,INF);
    493     ll sum = 0;
    494     f(j,0,6){
    495         sum += solve(label[1],j);
    496         sum %= INF;
    497     }
    498     ans *= sum;
    499     ans %= INF;
    500     cout<<ans<<"\n";
    501 }
    502 ```
    503 
    504 [1594F - Идеальная ферма](/contest/1594/problem/F "Codeforces Round 747 (Div. 2)")
    505 
    506 **Solution**
    507 
    508 Tutorial is loading...
    509 
    510 **Code (C++)**
    511 
    512 ```
    513 #include <bits/stdc++.h>
    514 using namespace std;
    515 typedef long long ll;
    516 ll INF = 1e9+7;
    517 ll MOD = 998244353;
    518 typedef pair<ll,ll> ii;
    519 #define iii pair<ii,ll>
    520 #define f(i,a,b) for(int i = a;i < b;i++)
    521 #define pb push_back
    522 #define vll vector<ll>
    523 #define F first
    524 #define S second
    525 #define all(x) (x).begin(), (x).end()
    526 int main(void){
    527     ios_base::sync_with_stdio(0);
    528     cin.tie(0);
    529     int t;
    530     cin>>t;
    531     while(t--){
    532         ll n,k,s;
    533         cin>>s>>n>>k;
    534         if(s == k){
    535             cout<<"YES\n";
    536         }
    537         else if(k > s){
    538             cout<<"NO\n";
    539         }
    540         else{
    541             ll posa = s+k;
    542             ll l = s-k+1,r = s;
    543             ll siz = r - l + 1;
    544             ll a = 0,b = 0;
    545             ll num = (s / k) * k;
    546             b = r - num + 1;
    547             a = siz - b;
    548             if((s / k) % 2 == 1){
    549                 posa -= b;
    550             }
    551             else{
    552                 posa -= a;
    553             }
    554             if((2 * n + 1) > posa){
    555                 cout<<"YES\n";
    556             }
    557             else{
    558                 cout<<"NO\n";
    559             }
    560         }
    561     }
    562 }
    563 ```