codeforces-scrape

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

1307.md (10994B)


      1 Source: https://codeforces.com/blog/entry/73953
      2 
      3 [1307A - Cow and Haybales](/contest/1307/problem/A)
      4 
      5 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <iostream>
     15 using namespace std;
     16 
     17 int N,D,a[105];
     18 
     19 int main(){
     20   int T; cin>>T;
     21   while (T--){
     22     cin>>N>>D;
     23     for (int i=1;i<=N;i++)
     24       cin>>a[i];
     25     while (D--){ //loop over D days
     26       for (int i=2;i<=N;i++)
     27 	if (a[i]>0){ //move closest haybale over
     28 	  a[i]--;
     29 	  a[i-1]++;
     30 	  break;
     31 	}
     32     }
     33     cout<<a[1]<<endl;
     34   }
     35 }
     36 ```
     37 
     38 **Alternative O(n) Solution:**
     39 
     40 ```
     41 #include <iostream>
     42 using namespace std;
     43 
     44 int N,D,a[105],ans;
     45 
     46 int main(){
     47   int T; cin>>T;
     48   while (T--){
     49     cin>>N>>D;
     50     for (int i=1;i<=N;i++)
     51       cin>>a[i];
     52     for (int i=2;i<=N;i++){
     53       int move=min(a[i],D/(i-1)); //number of haybales we can move from pile i to pile 1
     54       a[1]+=move; //update pile 1
     55       D-=move*(i-1); //update remaining days
     56     }
     57     cout<<a[1]<<endl;
     58   }
     59 }
     60 ```
     61 
     62 [1307B - Cow and Friend](/contest/1307/problem/B)
     63 
     64 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution**
     71 
     72 ```
     73 #include <iostream>
     74 #include <set>
     75 #include <algorithm>
     76 using namespace std;
     77 
     78 set<int>a;
     79 //you don't have to use set, it was just easier for us
     80 
     81 int main(){
     82   int T; cin>>T;
     83   while (T--){
     84     int N,X;
     85     cin>>N>>X;
     86     int far=0; //largest favorite number
     87     for (int i=0;i<N;i++){
     88       int A;
     89       cin>>A;
     90       a.insert(A);
     91       far=max(far,A);
     92     }
     93     if (a.count(X)) //X is favorite number
     94       cout<<1<<endl;
     95     else
     96       cout<<max(2,(X+far-1)/far)<<endl; //expression as explained in tutorial
     97     a.clear();
     98   }
     99 }
    100 ```
    101 
    102 [1307C - Cow and Message](/contest/1307/problem/C)
    103 
    104 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
    105 
    106 **Tutorial**
    107 
    108 Tutorial is loading...
    109 
    110 **Solution**
    111 
    112 ```
    113 #include <iostream>
    114 using namespace std;
    115 
    116 typedef long long ll;
    117 ll arr1[26],arr2[26][26];
    118 
    119 int main(){
    120   string S;
    121   cin>>S;
    122   for (int i=0;i<S.length();i++){
    123     int c=S[i]-'a';
    124     for (int j=0;j<26;j++)
    125       arr2[j][c]+=arr1[j];
    126     arr1[c]++;
    127   }
    128   ll ans=0;
    129   for (int i=0;i<26;i++)
    130     ans=max(ans,arr1[i]);
    131   for (int i=0;i<26;i++)
    132     for (int j=0;j<26;j++)
    133       ans=max(ans,arr2[i][j]);
    134   cout<<ans<<endl;
    135 }
    136 ```
    137 
    138 [1307D - Cow and Fields](/contest/1307/problem/D)
    139 
    140 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution**
    147 
    148 ```
    149 #include <cstdio>
    150 #include <vector>
    151 #include <algorithm>
    152 
    153 const int INF=1e9+7;
    154 
    155 int N;
    156 int as[200005];
    157 
    158 std::vector<int> edges[200005];
    159 
    160 int dist[2][200005];
    161 int q[200005];
    162 
    163 void bfs(int* dist,int s){
    164   std::fill(dist,dist+N,INF);
    165   int qh=0,qt=0;
    166   q[qh++]=s;
    167   dist[s]=0;
    168   while(qt<qh){
    169     int x=q[qt++];
    170     for(int y:edges[x]){
    171       if(dist[y]==INF){
    172 	dist[y]=dist[x]+1;
    173 	q[qh++]=y;
    174       }
    175     }
    176   }
    177 }
    178 
    179 int main(){
    180   int M,K;
    181   scanf("%d %d %d",&N,&M,&K);
    182   for(int i=0;i<K;i++){
    183     scanf("%d",&as[i]);
    184     as[i]--;
    185   }
    186   std::sort(as,as+K);
    187   for(int i=0;i<M;i++){
    188     int X,Y;
    189     scanf("%d %d",&X,&Y);
    190     X--,Y--;
    191     edges[X].push_back(Y);
    192     edges[Y].push_back(X);
    193   }
    194   bfs(dist[0],0);
    195   bfs(dist[1],N-1);
    196   std::vector<std::pair<int,int> > data;
    197   for(int i=0;i<K;i++){
    198     data.emplace_back(dist[0][as[i]]-dist[1][as[i]],as[i]);
    199   }
    200   std::sort(data.begin(),data.end());
    201   int best=0;
    202   int max=-INF;
    203   for(auto it:data){
    204     int a=it.second;
    205     best=std::max(best,max+dist[1][a]);
    206     max=std::max(max,dist[0][a]);
    207   }
    208   printf("%d\n",std::min(dist[0][N-1],best+1));
    209 }
    210 ```
    211 
    212 [1307E - Cow and Treats](/contest/1307/problem/E)
    213 
    214 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
    215 
    216 **Tutorial**
    217 
    218 Tutorial is loading...
    219 
    220 **Solution**
    221 
    222 ```
    223 #include <cstdio>
    224 #include <vector>
    225 #include <algorithm>
    226 #include <cassert>
    227 
    228 const int MOD=1e9+7;
    229 
    230 int modexp(int base,int exp){
    231   int ac=1;
    232   for(;exp;exp>>=1){
    233     if(exp&1) ac=1LL*ac*base%MOD;
    234     base=1LL*base*base%MOD;
    235   }
    236   return ac;
    237 }
    238 
    239 int inverse(int x){
    240   return modexp(x,MOD-2);
    241 }
    242 
    243 int fs[100005];
    244 int left[100005],right[100005];
    245 std::vector<int> cows[100005];//cows[f]: hunger of cows that like flavor f 
    246 int asleep[100005];
    247 int ways[100005];
    248 int total_asleep=0,total_ways=1;
    249 
    250 void calc_ways(int f){
    251   int a=std::upper_bound(cows[f].begin(),cows[f].end(),left[f])-cows[f].begin();
    252   int b=std::upper_bound(cows[f].begin(),cows[f].end(),right[f])-cows[f].begin();
    253   if(a>b) std::swap(a,b);
    254   long long cnt2=1LL*a*b-a;
    255   int cnt1=a+b;
    256   cnt2%=MOD;
    257   if(cnt2>0){
    258     asleep[f]=2;
    259     ways[f]=cnt2;
    260   }else if(cnt1>0){
    261     asleep[f]=1;
    262     ways[f]=cnt1;
    263   }else{
    264     asleep[f]=0;
    265     ways[f]=1;
    266   }
    267 }
    268 
    269 //fixed left cow, with hunger left[i]
    270 //precondition: such cow exists
    271 void calc_ways_stuck(int f){
    272   int b=std::upper_bound(cows[f].begin(),cows[f].end(),right[f])-cows[f].begin();
    273   if(right[f]>=left[f])
    274     b--;
    275   int cnt2=b;
    276   if(cnt2>0){
    277     asleep[f]=2;
    278     ways[f]=cnt2;
    279   }else{
    280     asleep[f]=1;
    281     ways[f]=1;
    282   }
    283 }
    284 
    285 int ans_asleep=0,ans_ways=0;
    286 
    287 void add_to_ans(int asleep,int ways){
    288   if(asleep>ans_asleep){
    289     ans_asleep=asleep;
    290     ans_ways=0;
    291   }
    292   if(asleep==ans_asleep)
    293     ans_ways=(ans_ways+ways)%MOD;
    294 }
    295 
    296 int main(){
    297   int N,M;
    298   scanf("%d %d",&N,&M);
    299   for(int i=1;i<=N;i++){
    300     scanf("%d",&fs[i]);
    301     right[fs[i]]++;
    302   }
    303   for(int i=0;i<M;i++){
    304     int F,H;
    305     scanf("%d %d",&F,&H);
    306     cows[F].push_back(H);
    307   }
    308   for(int f=1;f<=N;f++)
    309     std::sort(cows[f].begin(),cows[f].end());
    310   for(int f=1;f<=N;f++){
    311     calc_ways(f);
    312     total_asleep+=asleep[f];
    313     total_ways=1LL*total_ways*ways[f]%MOD;
    314   }
    315   add_to_ans(total_asleep,total_ways);
    316   for(int i=1;i<=N;i++){
    317     total_asleep-=asleep[fs[i]];
    318     total_ways=1LL*total_ways*inverse(ways[fs[i]])%MOD;
    319     right[fs[i]]--;
    320     left[fs[i]]++;
    321     if(std::binary_search(cows[fs[i]].begin(),cows[fs[i]].end(),left[fs[i]])){
    322       calc_ways_stuck(fs[i]);
    323       int here_asleep=total_asleep+asleep[fs[i]];
    324       int here_ways=1LL*total_ways*ways[fs[i]]%MOD;
    325       add_to_ans(here_asleep,here_ways);
    326     }
    327     calc_ways(fs[i]);
    328     total_asleep+=asleep[fs[i]];
    329     total_ways=1LL*total_ways*ways[fs[i]]%MOD;
    330   }
    331   printf("%d %d\n",ans_asleep,ans_ways);
    332 }
    333 ```
    334 
    335 [1307F - Cow and Vacation](/contest/1307/problem/F)
    336 
    337 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
    338 
    339 **Tutorial**
    340 
    341 Tutorial is loading...
    342 
    343 **Solution**
    344 
    345 ```
    346 #include <cstdio>
    347 #include <vector>
    348 #include <cassert>
    349 #include <queue>
    350 #include <algorithm>
    351 
    352 const int INF=1e9+7;
    353 
    354 std::vector<int> edges[400005];
    355 
    356 int anc[19][400005];
    357 int depth[400005];
    358 
    359 void dfs(int node){
    360   for(int child:edges[node]){
    361     edges[child].erase(std::find(edges[child].begin(),edges[child].end(),node));
    362     anc[0][child]=node;
    363     for(int k=1;k<19;k++){
    364       anc[k][child]=anc[k-1][anc[k-1][child]];
    365     }
    366     depth[child]=depth[node]+1;
    367     dfs(child);
    368   }
    369 }
    370 
    371 int la(int node,int len){
    372   for(int k=19-1;k>=0;k--){
    373     if(len&(1<<k)){
    374       node=anc[k][node];
    375     }
    376   }
    377   return node;
    378 }
    379 
    380 int lca(int a,int b){
    381   if(depth[a]<depth[b]) std::swap(a,b);
    382   a=la(a,depth[a]-depth[b]);
    383   if(a==b) return a;
    384   for(int k=19-1;k>=0;k--){
    385     if(anc[k][a]!=anc[k][b]){
    386       a=anc[k][a];
    387       b=anc[k][b];
    388     }
    389   }
    390   return anc[0][a];
    391 }
    392 
    393 //move x steps from a to b
    394 //assumes x<=dist(a,b)
    395 int walk(int a,int b,int x){
    396   int c=lca(a,b);
    397   if(x<=depth[a]-depth[c]){
    398     return la(a,x);
    399   }
    400   int excess=x-(depth[a]-depth[c]);
    401   assert(excess<=(depth[b]-depth[c]));
    402   return la(b,depth[b]-depth[c]-excess);
    403 }
    404 
    405 int uf[400005];
    406 int dist[400005];//dist[x]=0 iff x is rest stop
    407 
    408 int find(int a){
    409   while(a!=uf[a]){
    410     a=uf[a]=uf[uf[a]];
    411   }
    412   return a;
    413 }
    414 
    415 bool query(int K){
    416   int A,B;
    417   scanf("%d %d",&A,&B);
    418   A--,B--;
    419   int C=lca(A,B);
    420   if(depth[A]+depth[B]-2*depth[C]<=2*K){
    421     return true;
    422   }else{
    423     return find(walk(A,B,K))==find(walk(B,A,K));
    424   }
    425 }
    426 
    427 int main(){
    428   int N,K,R;
    429   scanf("%d %d %d",&N,&K,&R);
    430   int oldN=N;
    431   for(int i=0;i<oldN-1;i++){
    432     int X,Y;
    433     scanf("%d %d",&X,&Y);
    434     X--,Y--;
    435     edges[X].push_back(N);
    436     edges[N].push_back(X);
    437     edges[Y].push_back(N);
    438     edges[N].push_back(Y);
    439     N++;
    440   }
    441   for(int i=0;i<N;i++){
    442     uf[i]=i;
    443   }
    444   std::fill(dist,dist+N,INF);
    445   std::queue<int> frontier;
    446   for(int i=0;i<R;i++){
    447     int X;
    448     scanf("%d",&X);
    449     X--;
    450     dist[X]=0;
    451     frontier.push(X);
    452   }
    453   while(!frontier.empty()){
    454     int x=frontier.front();
    455     if(dist[x]>K-1) break;
    456     frontier.pop();
    457     for(int y:edges[x]){
    458       uf[find(y)]=find(x);
    459       if(dist[y]==INF){
    460 	dist[y]=dist[x]+1;
    461 	frontier.push(y);
    462       }
    463     }
    464   }
    465   dfs(0);
    466   int V;
    467   scanf("%d",&V);
    468   while(V--){
    469     if(query(K)){
    470       printf("YES\n");
    471     }else{
    472       printf("NO\n");
    473     }
    474   }
    475 }
    476 ```
    477 
    478 [1307G - Cow and Exercise](/contest/1307/problem/G)
    479 
    480 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
    481 
    482 **Tutorial**
    483 
    484 Tutorial is loading...
    485 
    486 **Solution**
    487 
    488 ```
    489 #include <cstdio>
    490 #include <queue>
    491 #include <vector>
    492 #include <stdint.h>
    493 #include <algorithm>
    494 
    495 const long long INF=1e9+7;
    496 
    497 const long long MAXV=50;
    498 const long long MAXE=MAXV*(MAXV-1);
    499 
    500 long long SRC,SNK;
    501 
    502 long long elist[MAXE*2];
    503 long long next[MAXE*2];
    504 long long head[MAXV];
    505 long long cap[MAXE*2];
    506 long long cost[MAXE*2];
    507 long long tot=0;
    508 
    509 void add(long long x,long long c,long long w){
    510   elist[tot]=x;
    511   cap[tot]=c;
    512   cost[tot]=w;
    513   next[tot]=head[x];
    514   head[x]=tot++;
    515 }
    516 
    517 long long dist[MAXV];
    518 long long prev[MAXV];
    519 std::queue<long long> q;
    520 
    521 long long total_cost=0;
    522 long long total_flow=0;
    523 
    524 int main(){
    525   long long N,M;
    526   scanf("%lld %lld",&N,&M);
    527   SRC=0,SNK=N-1;
    528   std::fill(head,head+N,-1);
    529   for(long long i=0;i<M;i++){
    530     long long A,B,C;
    531     scanf("%lld %lld %lld",&A,&B,&C);
    532     A--,B--;
    533     add(A,1,C);
    534     add(B,0,-C);
    535   }
    536   std::vector<std::pair<long long,long long> > crit;
    537   crit.push_back({0,0});
    538   while(true){
    539     std::fill(dist,dist+N,INF);
    540     dist[SRC]=0;
    541     prev[SRC]=-1;
    542     q.push(SRC);
    543     while(!q.empty()){
    544       long long node=q.front();
    545       q.pop();
    546       for(long long e=head[node];e!=-1;e=next[e]){
    547 	long long i=elist[e^1];
    548 	if(cap[e]){
    549 	  if(dist[i]>dist[node]+cost[e]){
    550 	    dist[i]=dist[node]+cost[e];
    551 	    prev[i]=e;
    552 	    q.push(i);
    553 	  }
    554 	}
    555       }
    556     }
    557     crit.push_back({1LL*total_flow*dist[SNK]-total_cost,dist[SNK]});
    558     if(dist[SNK]==INF) break;
    559     long long aug=INF;
    560     for(long long x=SNK;x!=SRC;x=elist[prev[x]]){
    561       aug=std::min(aug,cap[prev[x]]);
    562     }
    563     for(long long x=SNK;x!=SRC;x=elist[prev[x]]){
    564       cap[prev[x]]-=aug;
    565       cap[prev[x]^1]+=aug;
    566     }
    567     total_flow+=aug;
    568     total_cost+=1LL*dist[SNK]*aug;
    569   }
    570   long long Q;
    571   scanf("%lld",&Q);
    572   while(Q--){
    573     long long X;
    574     scanf("%lld",&X);
    575     auto it=std::lower_bound(crit.begin(),crit.end(),std::pair<long long,long long>{X+1,0});
    576     double D=(long double)((X-(it-1)->first)*it->second+(it->first-X)*((it-1)->second))/(it->first-(it-1)->first);
    577     printf("%.10lf\n",D);
    578   }
    579   return 0;
    580 }
    581 ```