codeforces-scrape

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

1332.md (9037B)


      1 Source: https://codeforces.com/blog/entry/75432
      2 
      3 Hope you enjoy those tasks!
      4 
      5 [1332A - Exercising Walk](/contest/1332/problem/A "Codeforces Round 630 (Div. 2)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (python by pikmike)**
     12 
     13 ```
     14 t = int(input())
     15 for _ in range(t):
     16 	a, b, c, d = map(int, input().split())
     17 	x, y, x1, y1, x2, y2 = map(int, input().split())
     18 	x += b - a
     19 	y += d - c
     20 	if a + b > 0 and x1 == x2:
     21 		print("No")
     22 	elif c + d > 0 and y1 == y2:
     23 		print("No")
     24 	elif x1 <= x <= x2 and y1 <= y <= y2:
     25 		print("Yes")
     26 	else:
     27 		print("No")
     28 ```
     29 
     30 **Solution (C++)**
     31 
     32 ```
     33 #include<bits/stdc++.h>
     34 using namespace std;
     35 
     36 int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;
     37 
     38 int main(){
     39     int t;
     40     cin>>t;
     41     while (t--){
     42         cin>>a>>b>>c>>d;
     43         cin>>x>>y>>x1>>y1>>x2>>y2;
     44         xx=x,yy=y;
     45         x+=-a+b, y+=-c+d;
     46         if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){
     47             cout<<"Yes\n";
     48         }
     49         else{
     50             cout<<"No\n";
     51         }
     52     }
     53     return 0;
     54 }
     55 ```
     56 
     57 [1332B - Composite Coloring](/contest/1332/problem/B "Codeforces Round 630 (Div. 2)")
     58 
     59 **Tutorial**
     60 
     61 Tutorial is loading...
     62 
     63 **Solution (python by pikmike)**
     64 
     65 ```
     66 from math import gcd
     67 
     68 def getprime(x):
     69 	for i in range(2, x):
     70 		if x % i == 0:
     71 			return i
     72 	return -1
     73 
     74 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
     75 
     76 t = int(input())
     77 for _ in range(t):
     78 	n = int(input())
     79 	a = [int(x) for x in input().split()]
     80 	used = [False for i in range(11)]
     81 	clr = []
     82 	for i in range(n):
     83 		x = primes.index(getprime(a[i]))
     84 		used[x] = True
     85 		clr.append(x)
     86 	cnt = 0
     87 	num = []
     88 	for i in range(11):
     89 		num.append(cnt)
     90 		if used[i]:
     91 			cnt += 1
     92 	print(cnt)
     93 	for i in range(n):
     94 		x = primes.index(getprime(a[i]))
     95 		print(num[x] + 1, end = " ")
     96 	print()
     97 ```
     98 
     99 **Solution (C++)**
    100 
    101 ```
    102 #include<bits/stdc++.h>
    103 using namespace std;
    104  
    105 int n,t;
    106 vector<int> ans[1007];
    107 int res[1007];
    108 int main(){
    109     ios::sync_with_stdio(false);
    110     cin.tie(0), cout.tie(0);
    111     auto f=[&](int u){
    112         for (int i=2;i<=u;++i){
    113             if (u%i==0) return i;
    114         }
    115     };
    116     cin>>t;
    117     while (t--){
    118         cin>>n;
    119         for (int i=1;i<=1000;++i) ans[i].clear();
    120         for (int i=1;i<=n;++i){
    121            int u;
    122            cin>>u; ans[f(u)].push_back(i);
    123         }
    124         int ret=0;
    125         for (int i=1;i<=1000;++i){
    126             if (ans[i].size()){
    127                 ++ret;
    128                 for (auto c:ans[i]){
    129                     res[c]=ret;
    130                 }
    131             }
    132         }
    133         cout<<ret<<"\n";
    134         for (int i=1;i<=n;++i){
    135             cout<<res[i]<<" ";
    136         }
    137         cout<<"\n";
    138     }
    139     return 0;
    140 }
    141 ```
    142 
    143 [1332C - K-Complete Word](/contest/1332/problem/C "Codeforces Round 630 (Div. 2)")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution(python by pikmike)**
    150 
    151 ```
    152 from sys import stdin
    153 
    154 t = int(stdin.readline())
    155 for _ in range(t):
    156 	n, k = map(int, stdin.readline().split())
    157 	s = stdin.readline()
    158 	cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]
    159 	for i in range(n):
    160 		cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1
    161 	ans = 0
    162 	for i in range(k // 2):
    163 		ans += 2 * n // k - max(cnt[i])
    164 	if k % 2 == 1:
    165 		ans += n // k - max(cnt[k // 2])
    166 	print(ans)
    167 ```
    168 
    169 **Solution(C++)**
    170 
    171 ```
    172 #include<bits/stdc++.h>
    173 using namespace std;
    174 
    175 const int maxn=200007;
    176 
    177 int n,k,ans=0;
    178 int cnt[maxn][26];
    179 string s;
    180 
    181 int differ(int u,int v){
    182     int ret=0,mx=0;
    183     for (int j=0;j<26;++j){
    184         ret+=cnt[u][j]+cnt[v][j];
    185         mx=max(mx,cnt[u][j]+cnt[v][j]);
    186     }
    187     return ret-mx;
    188 }
    189 
    190 int main(){
    191     int t;
    192     cin>>t;
    193     while (t--){
    194         cin>>n>>k>>s;
    195         for (int i=0;i<k;++i){
    196             for (int j=0;j<26;++j){
    197                 cnt[i][j]=0;
    198             }
    199         }
    200         for (int i=0;i<n;++i){
    201             cnt[i%k][s[i]-'a']++;
    202         }
    203         int ans=0;
    204         for (int i=0;i<k;++i){
    205             ans+=differ(i,k-1-i);
    206         }
    207         cout<<ans/2<<"\n";
    208     }
    209     return 0;
    210 }
    211 ```
    212 
    213 [1332D - Walk on Matrix](/contest/1332/problem/D "Codeforces Round 630 (Div. 2)")
    214 
    215 **Tutorial**
    216 
    217 Tutorial is loading...
    218 
    219 **Solution(python by pikmike)**
    220 
    221 ```
    222 k = int(input())
    223 x = 2**17
    224 print(2, 3)
    225 print(x^k, x, 0)
    226 print(k, x^k, k)
    227 ```
    228 
    229 [1332E - Height All the Same](/contest/1332/problem/E "Codeforces Round 630 (Div. 2)")
    230 
    231 **Tutorial**
    232 
    233 Tutorial is loading...
    234 
    235 **Solution 1(python by pikmike)**
    236 
    237 ```
    238 MOD = 998244353
    239 
    240 n, m, l, r = map(int, input().split())
    241 if n * m % 2 == 1:
    242 	print(pow(r - l + 1, n * m, MOD))
    243 elif (r - l + 1) % 2 == 0:
    244 	print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD)
    245 else:
    246 	print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD)
    247 ```
    248 
    249 **Solution 2(python by pikmike)**
    250 
    251 ```
    252 MOD = 998244353
    253 
    254 n, m, l, r = map(int, input().split())
    255 if n * m % 2 == 1:
    256 	print(pow(r - l + 1, n * m, MOD))
    257 else:
    258 	e = r // 2 - (l - 1) // 2	
    259 	o = (r - l + 1) - e
    260 	print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD)
    261 ```
    262 
    263 [1332F - Independent Set](/contest/1332/problem/F "Codeforces Round 630 (Div. 2)")
    264 
    265 **Tutorial**
    266 
    267 Tutorial is loading...
    268 
    269 **Solution(C++)**
    270 
    271 ```
    272 #include<bits/stdc++.h>
    273 #define int long long
    274 #define ULL unsigned long long
    275 #define F first
    276 #define S second
    277 #define pb push_back
    278 #define rep(i,n) for(int i=0;i<(int)(n);++i)
    279 #define rep1(i,n) for(int i=1;i<=(int)(n);++i)
    280 #define range(a) a.begin(), a.end()
    281 #define PI pair<int,int>
    282 #define VI vector<int>
    283 #define debug cout<<"potxdy"<<endl; 
    284 using namespace std;
    285  
    286 typedef long long ll;
    287  
    288 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    289 
    290 const int maxn=300007;
    291 const int mod=998244353;
    292 
    293 int n,dp[maxn][2],f[maxn]; 
    294 VI vec[maxn];
    295 
    296 int mult(int u,int v){
    297     u=(u%mod+mod)%mod, v=(v%mod+mod)%mod;
    298     return 1ll*u*v%mod;
    299 }
    300 
    301 void dfs(int u,int p){
    302     dp[u][0]=dp[u][1]=f[u]=1;
    303     for (auto c:vec[u]){
    304         if (c==p) continue;
    305         dfs(c,u);
    306         dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]);
    307         dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]);
    308         f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]);
    309     }
    310 }
    311 
    312 #undef int
    313 int main(){
    314     ios::sync_with_stdio(false);
    315     cin.tie(0), cout.tie(0);
    316     cin>>n;
    317     for (int i=1;i<n;++i){
    318         int u,v;
    319         cin>>u>>v;
    320         vec[u].pb(v), vec[v].pb(u);
    321     }
    322     dfs(1,0);
    323     cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl;
    324     return 0;
    325 }
    326 ```
    327 
    328 [1332G - No Monotone Triples](/contest/1332/problem/G "Codeforces Round 630 (Div. 2)")
    329 
    330 Contributor of idea of the solution: [awoo](/profile/awoo "Master awoo")
    331 
    332 **Tutorial**
    333 
    334 Tutorial is loading...
    335 
    336 **Solution (C++)**
    337 
    338 ```
    339 #include<bits/stdc++.h>
    340 
    341 using namespace std;
    342 
    343 const int maxn=200007;
    344 int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn];
    345 int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2;
    346 int ans1[maxn][4],ans2[maxn][4];
    347 set<int> s;
    348 
    349 bool cmp1(int u,int v){
    350     return a[u]<a[v];
    351 }
    352 
    353 bool cmp2(int u,int v){
    354     return a[u]>a[v];
    355 }
    356 
    357 int main(){
    358     ios::sync_with_stdio(false);
    359     cin.tie(0), cout.tie(0);
    360     cin>>n>>q;
    361     for (int i=1;i<=n;++i){
    362         cin>>a[i];
    363     }
    364     p1=p2=r1=r2=0;
    365     s.insert(n+1);
    366     for (int i=n;i>0;--i){
    367         while (p1){
    368             int u=st1[p1];
    369             if (a[u]>a[i]){
    370                 t[u]--;
    371                 if (!t[u]) s.insert(u);
    372                 p1--;
    373                 r1=0;
    374             }
    375             else{
    376                 break;
    377             }
    378         }
    379         while (p2){
    380             int u=st2[p2];
    381             if (a[u]<a[i]){
    382                 t[u]--;
    383                 if (!t[u]) s.insert(u);
    384                 p2--;
    385                 r2=0;
    386             }
    387             else{
    388                 break;
    389             }
    390         }
    391         s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;
    392         b[i]=i+max(r1,r2)+1;
    393         ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i];
    394         if (s1&&s2){
    395             c[i]=*s.lower_bound(max(st1[s1],st2[s2]));
    396             if (c[i]<=n){
    397                 int u=lower_bound(st1+1,st1+p1+1,c[i],greater<int>())-st1,v=lower_bound(st2+1,st2+p2+1,c[i],greater<int>())-st2;
    398                 ans2[i][0]=i, ans2[i][1]=min(st1[u],st2[v]), ans2[i][2]=max(st1[u],st2[v]), ans2[i][3]=c[i];
    399             }
    400         }
    401         else{
    402             c[i]=n+1;
    403         }
    404         st1[++p1]=i;
    405         st2[++p2]=i;
    406         r1++, r2++;
    407         t[i]+=2;
    408         if (i<n&&b[i]>b[i+1]){
    409             b[i]=b[i+1];
    410             for (int j=0;j<3;++j){
    411                 ans1[i][j]=ans1[i+1][j];
    412             }
    413         }
    414         if (i<n&&c[i]>c[i+1]){
    415             c[i]=c[i+1];
    416             for (int j=0;j<4;++j){
    417                 ans2[i][j]=ans2[i+1][j];
    418             }
    419         }
    420     }
    421     while (q--){
    422         int l,r;
    423         cin>>l>>r;
    424         if (r>=c[l]){
    425             cout<<"4\n";
    426             for (int j=0;j<4;++j){
    427                 cout<<ans2[l][j]<<" ";
    428             }
    429             cout<<"\n";
    430         }
    431         else{
    432             if (r>=b[l]){
    433                 cout<<"3\n";
    434                 for (int j=0;j<3;++j){
    435                     cout<<ans1[l][j]<<" ";
    436                 }
    437                 cout<<"\n";
    438             }
    439             else{
    440                 cout<<"0\n\n";
    441             }
    442         }
    443     }
    444     return 0;    
    445 }
    446 ```