codeforces-scrape

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

1348.md (7497B)


      1 Source: https://codeforces.com/blog/entry/76555
      2 
      3 [1348A - Phoenix and Balance](/contest/1348/problem/A "Codeforces Round 638 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 void solve(){
     16   int N;
     17   cin>>N;
     18   //note: 1<<X means 2^X
     19   //we put largest coin in first pile
     20   int sum1=(1<<N), sum2=0;
     21   //we put n/2-1 smallest coins in first pile
     22   for (int i=1;i<N/2;i++)
     23     sum1+=(1<<i);
     24   //we put remaining n/2 coins in second pile
     25   for (int i=N/2;i<N;i++)
     26     sum2+=(1<<i);
     27   cout<<sum1-sum2<<endl;
     28 }
     29 
     30 int main(){
     31   int t; cin>>t;
     32   while (t--)
     33     solve();
     34 }
     35 ```
     36 
     37 [1348B - Phoenix and Beauty](/contest/1348/problem/B "Codeforces Round 638 (Div. 2)")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 using namespace std;
     48 
     49 void solve(){
     50   int N,K;
     51   cin>>N>>K;
     52   set<int>s;
     53   for (int i=0;i<N;i++){
     54     int a;
     55     cin>>a;
     56     s.insert(a);
     57   }
     58   //if more than K distinct numbers, print -1
     59   if (s.size()>K){
     60     cout<<-1<<endl;
     61     return;
     62   }
     63   cout<<N*K<<endl;
     64   for (int i=0;i<N;i++){
     65     //print the distinct numbers
     66     for (int b:s)
     67       cout<<b<<' ';
     68     //print the extra 1s
     69     for (int j=0;j<K-(int)s.size();j++)
     70       cout<<1<<' ';
     71   }
     72   cout<<endl;
     73 }
     74 
     75 int main(){
     76   int t; cin>>t;
     77   while (t--)
     78     solve();
     79 }
     80 ```
     81 
     82 [1348C — Phoenix and Distribution](https://codeforces.com/contest/1348/problem/C)
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 using namespace std;
     93 
     94 void solve(){
     95   int n,k;
     96   cin>>n>>k;
     97   string s;
     98   cin>>s;
     99   sort(s.begin(),s.end());
    100   //if smallest k letters are not all the same, answer is kth smallest letter
    101   if (s[0]!=s[k-1]){
    102     cout<<s[k-1]<<endl;
    103     return;
    104   }
    105   cout<<s[0];
    106   //if remaining letters aren't the same, we append remaining letters to answer
    107   if (s[k]!=s[n-1]){
    108     for (int i=k;i<n;i++)
    109       cout<<s[i];
    110   }
    111   else{
    112     //remaining letters are the same, so we distribute evenly
    113     for (int i=0;i<(n-k+k-1)/k;i++)
    114       cout<<s[n-1];
    115   }
    116   cout<<endl;
    117 }
    118 
    119 int main(){
    120   int t; cin>>t;
    121   while (t--)
    122     solve();
    123 }
    124 ```
    125 
    126 [1348D - Phoenix and Science](/contest/1348/problem/D "Codeforces Round 638 (Div. 2)")
    127 
    128 **Tutorial**
    129 
    130 Tutorial is loading...
    131 
    132 **Solution**
    133 
    134 ```
    135 #include <bits/stdc++.h>
    136 using namespace std;
    137 
    138 void solve(){
    139   vector<int>inc;   
    140   int N;
    141   cin>>N;
    142   //construct sequence 1, 2, 4, ... while sum <= N
    143   for (int i=1;i<=N;i*=2){
    144     inc.push_back(i);
    145     N-=i;
    146   }
    147   //if sum is not N, we insert and sort
    148   if (N>0){
    149     inc.push_back(N);
    150     sort(inc.begin(),inc.end());
    151   }
    152   cout<<inc.size()-1<<endl;
    153   for (int i=1;i<(int)inc.size();i++)
    154     cout<<inc[i]-inc[i-1]<<' ';
    155   cout<<endl;
    156 }
    157 
    158 int main(){
    159   int t; cin>>t;
    160   while (t--)
    161     solve();
    162 }
    163 ```
    164 
    165 [1348E - Phoenix and Berries](/contest/1348/problem/E "Codeforces Round 638 (Div. 2)")
    166 
    167 **Tutorial**
    168 
    169 Tutorial is loading...
    170 
    171 **Solution**
    172 
    173 ```
    174 //Solution 1
    175 #include <bits/stdc++.h>
    176 using namespace std;
    177 
    178 int N,K;
    179 int a[505],b[505];
    180 bool dp[505][505];  //number of shrubs considered, "extra" red berries
    181 
    182 int main(){
    183   cin>>N>>K;
    184   long long totA=0,totB=0;
    185   for (int i=1;i<=N;i++){
    186     cin>>a[i]>>b[i];
    187     totA+=a[i];
    188     totB+=b[i];
    189   }
    190   dp[0][0]=true;
    191   for (int i=1;i<=N;i++){
    192     for (int j=0;j<K;j++){
    193       //leave a[i]%K extra red berries
    194       dp[i][j]=dp[i-1][(j-a[i]%K+K)%K];
    195       for (int l=0;l<=min(K-1,a[i]);l++){
    196 	//check if we can leave l extra red berries
    197 	if ((a[i]-l)%K+b[i]>=K)
    198 	  dp[i][j]|=dp[i-1][(j-l+K)%K];
    199       }
    200     }
    201   }
    202   long long ans=0;
    203   for (int i=0;i<K;i++){
    204     if (dp[N][i])
    205       ans=max(ans,(totA+totB-i)/K);
    206   }
    207   cout<<ans<<endl;
    208 }
    209 ```
    210 
    211 [1348F - Phoenix and Memory](/contest/1348/problem/F "Codeforces Round 638 (Div. 2)")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution 1**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 using namespace std;
    222 
    223 const int INF=1e9+7;
    224  
    225 int as[200005], bs[200005];
    226          
    227 vector<pair<int,int> > start[200005];
    228 int ans[200005];
    229 int where[200005];
    230 int N;
    231          
    232 void show(){
    233   for(int i=1;i<=N;i++)
    234     cout<<ans[i]<<' ';
    235   cout<<endl;
    236 }
    237  
    238 pair<int,int> st[400005];
    239  
    240 int query(int l,int r){
    241   l--;
    242   pair<int,int> res{INF,INF};
    243   for(l+=N,r+=N;l<r;l>>=1,r>>=1){
    244     if(l&1) res=min(res,st[l++]);
    245     if(r&1) res=min(res,st[--r]);
    246   }
    247   return res.second;
    248 }
    249          
    250 int main(){
    251   cin>>N; 
    252   for(int i=1;i<=N;i++){
    253     cin>>as[i]>>bs[i];
    254     start[as[i]].push_back({bs[i],i});
    255   }
    256   set<pair<int,int> > active;//(right,index)
    257   for(int i=1;i<=N;i++){
    258     active.insert(start[i].begin(),start[i].end());
    259     ans[active.begin()->second]=i;
    260     where[i]=active.begin()->second;
    261     active.erase(active.begin());
    262   }
    263   for(int i=0;i<N;i++){
    264     st[i+N]={as[where[i+1]],i+1};
    265   }
    266   for(int i=N-1;i>0;i--){
    267     st[i]=min(st[i<<1],st[i<<1|1]);
    268   }
    269   for(int i=1;i<=N;i++){
    270     int j=query(i+1,bs[where[i]]);
    271     if(j==INF) continue;
    272     if(as[where[j]]<=i){
    273       cout<<"NO"<<endl;
    274       show();
    275       swap(ans[where[i]],ans[where[j]]);
    276       show();
    277       return 0;
    278     }
    279   }
    280   cout<<"YES"<<endl;
    281   show();
    282 }
    283 ```
    284 
    285 **Solution 2**
    286 
    287 ```
    288 #include <bits/stdc++.h>
    289 using namespace std;
    290 
    291 int N;
    292 int a[200005],b[200005];
    293 int label[200005]; //the label of the person at i-th position in our perfect matching
    294 int label2[200005]; //which position the i-th person is at
    295 
    296 void perfectMatch(){ //finds a perfect matching
    297   deque<pair<pair<int,int>,int>>v;
    298   for (int i=1;i<=N;i++)
    299     v.push_back({{a[i],b[i]},i});
    300   sort(v.begin(),v.end());
    301   multiset<pair<int,int>>mst;
    302   for (int i=1;i<=N;i++){
    303     while ((int)v.size()>0 && v[0].first.first<=i){
    304       mst.insert({v[0].first.second,v[0].second});
    305       v.pop_front();
    306     }
    307     //match person with label to earliest ending interval
    308     label2[i]=mst.begin()->second;
    309     label[mst.begin()->second]=i;
    310     mst.erase(mst.find(*mst.begin()));
    311   }
    312 }
    313 
    314 set<int>active;
    315 int vis[200005];
    316 int from[200005];
    317 int ans[200005];
    318 
    319 void foundAnother(int node, int nextNode){
    320   vector<int>v;
    321   int cur=node;
    322   //backtracks on cycle to find other ordering
    323   while (cur!=label2[nextNode]){
    324     v.push_back(cur);
    325     cur=from[cur];
    326   }
    327   reverse(v.begin(),v.end());
    328   v.push_back(label2[nextNode]);
    329   reverse(v.begin(),v.end());
    330   cout<<"NO"<<endl;
    331   for (int i=1;i<=N;i++)
    332     cout<<label[i]<<' ';
    333   cout<<endl;
    334   for (int i=1;i<=N;i++)
    335     ans[i]=label[i];
    336   int temp=ans[v.back()];
    337   for (int i=0;i<(int)v.size();i++)
    338     swap(temp,ans[v[i]]);
    339   for (int i=1;i<=N;i++)
    340     cout<<ans[i]<<' ';
    341   cout<<endl;
    342   exit(0);
    343 }
    344   
    345 void dfs(int node){
    346   //activates node
    347   vis[node]=1;
    348   queue<int>toRemove;
    349   for (;;){
    350     //binary search for unvisisited neighbor
    351     auto it=active.lower_bound(a[node]);
    352     if (it!=active.end() && *it==label[node]){
    353       toRemove.push(*it);
    354       it++;
    355     }
    356     if (it==active.end() || *it>b[node])
    357       break;
    358     if (vis[label2[*it]]==1) //found cycle (another ordering)
    359       foundAnother(node,*it);
    360     toRemove.push(*it);
    361     if (vis[label2[*it]]==2)
    362       continue;
    363     from[label2[*it]]=node;
    364     dfs(label2[*it]);
    365   }
    366   //removes visited nodes from set
    367   while (!toRemove.empty()){
    368     if (active.count(toRemove.front()))
    369       active.erase(toRemove.front());
    370     toRemove.pop();
    371   }
    372   //deactivates and retire node
    373   vis[node]=2;
    374 }
    375 
    376 int main(){
    377   cin>>N;
    378   for (int i=1;i<=N;i++)
    379     cin>>a[i]>>b[i];
    380   perfectMatch();
    381   for (int i=1;i<=N;i++)
    382     active.insert(i);
    383   for (int i=1;i<=N;i++)
    384     if (vis[i]==0)
    385       dfs(i);
    386   cout<<"YES"<<endl;
    387   for (int i=1;i<=N;i++)
    388     cout<<label[i]<<' ';
    389   cout<<endl;
    390 }
    391 ```