Hope you enjoy those tasks!
Tutorial
Tutorial is loading...
Solution (python by pikmike)
t = int(input())
for _ in range(t):
a, b, c, d = map(int, input().split())
x, y, x1, y1, x2, y2 = map(int, input().split())
x += b - a
y += d - c
if a + b > 0 and x1 == x2:
print("No")
elif c + d > 0 and y1 == y2:
print("No")
elif x1 <= x <= x2 and y1 <= y <= y2:
print("Yes")
else:
print("No")
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;
int main(){
int t;
cin>>t;
while (t--){
cin>>a>>b>>c>>d;
cin>>x>>y>>x1>>y1>>x2>>y2;
xx=x,yy=y;
x+=-a+b, y+=-c+d;
if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (python by pikmike)
from math import gcd
def getprime(x):
for i in range(2, x):
if x % i == 0:
return i
return -1
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
t = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]
used = [False for i in range(11)]
clr = []
for i in range(n):
x = primes.index(getprime(a[i]))
used[x] = True
clr.append(x)
cnt = 0
num = []
for i in range(11):
num.append(cnt)
if used[i]:
cnt += 1
print(cnt)
for i in range(n):
x = primes.index(getprime(a[i]))
print(num[x] + 1, end = " ")
print()
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
int n,t;
vector<int> ans[1007];
int res[1007];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
auto f=[&](int u){
for (int i=2;i<=u;++i){
if (u%i==0) return i;
}
};
cin>>t;
while (t--){
cin>>n;
for (int i=1;i<=1000;++i) ans[i].clear();
for (int i=1;i<=n;++i){
int u;
cin>>u; ans[f(u)].push_back(i);
}
int ret=0;
for (int i=1;i<=1000;++i){
if (ans[i].size()){
++ret;
for (auto c:ans[i]){
res[c]=ret;
}
}
}
cout<<ret<<"\n";
for (int i=1;i<=n;++i){
cout<<res[i]<<" ";
}
cout<<"\n";
}
return 0;
}
Tutorial
Tutorial is loading...
Solution(python by pikmike)
from sys import stdin
t = int(stdin.readline())
for _ in range(t):
n, k = map(int, stdin.readline().split())
s = stdin.readline()
cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]
for i in range(n):
cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1
ans = 0
for i in range(k // 2):
ans += 2 * n // k - max(cnt[i])
if k % 2 == 1:
ans += n // k - max(cnt[k // 2])
print(ans)
Solution(C++)
#include<bits/stdc++.h>
using namespace std;
const int maxn=200007;
int n,k,ans=0;
int cnt[maxn][26];
string s;
int differ(int u,int v){
int ret=0,mx=0;
for (int j=0;j<26;++j){
ret+=cnt[u][j]+cnt[v][j];
mx=max(mx,cnt[u][j]+cnt[v][j]);
}
return ret-mx;
}
int main(){
int t;
cin>>t;
while (t--){
cin>>n>>k>>s;
for (int i=0;i<k;++i){
for (int j=0;j<26;++j){
cnt[i][j]=0;
}
}
for (int i=0;i<n;++i){
cnt[i%k][s[i]-'a']++;
}
int ans=0;
for (int i=0;i<k;++i){
ans+=differ(i,k-1-i);
}
cout<<ans/2<<"\n";
}
return 0;
}
Tutorial
Tutorial is loading...
Solution(python by pikmike)
k = int(input())
x = 2**17
print(2, 3)
print(x^k, x, 0)
print(k, x^k, k)
Tutorial
Tutorial is loading...
Solution 1(python by pikmike)
MOD = 998244353
n, m, l, r = map(int, input().split())
if n * m % 2 == 1:
print(pow(r - l + 1, n * m, MOD))
elif (r - l + 1) % 2 == 0:
print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD)
else:
print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD)
Solution 2(python by pikmike)
MOD = 998244353
n, m, l, r = map(int, input().split())
if n * m % 2 == 1:
print(pow(r - l + 1, n * m, MOD))
else:
e = r // 2 - (l - 1) // 2
o = (r - l + 1) - e
print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD)
Tutorial
Tutorial is loading...
Solution(C++)
#include<bits/stdc++.h>
#define int long long
#define ULL unsigned long long
#define F first
#define S second
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define range(a) a.begin(), a.end()
#define PI pair<int,int>
#define VI vector<int>
#define debug cout<<"potxdy"<<endl;
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn=300007;
const int mod=998244353;
int n,dp[maxn][2],f[maxn];
VI vec[maxn];
int mult(int u,int v){
u=(u%mod+mod)%mod, v=(v%mod+mod)%mod;
return 1ll*u*v%mod;
}
void dfs(int u,int p){
dp[u][0]=dp[u][1]=f[u]=1;
for (auto c:vec[u]){
if (c==p) continue;
dfs(c,u);
dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]);
dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]);
f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]);
}
}
#undef int
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n;
for (int i=1;i<n;++i){
int u,v;
cin>>u>>v;
vec[u].pb(v), vec[v].pb(u);
}
dfs(1,0);
cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl;
return 0;
}
Contributor of idea of the solution: awoo
Tutorial
Tutorial is loading...
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
const int maxn=200007;
int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn];
int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2;
int ans1[maxn][4],ans2[maxn][4];
set<int> s;
bool cmp1(int u,int v){
return a[u]<a[v];
}
bool cmp2(int u,int v){
return a[u]>a[v];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;++i){
cin>>a[i];
}
p1=p2=r1=r2=0;
s.insert(n+1);
for (int i=n;i>0;--i){
while (p1){
int u=st1[p1];
if (a[u]>a[i]){
t[u]--;
if (!t[u]) s.insert(u);
p1--;
r1=0;
}
else{
break;
}
}
while (p2){
int u=st2[p2];
if (a[u]<a[i]){
t[u]--;
if (!t[u]) s.insert(u);
p2--;
r2=0;
}
else{
break;
}
}
s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;
b[i]=i+max(r1,r2)+1;
ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i];
if (s1&&s2){
c[i]=*s.lower_bound(max(st1[s1],st2[s2]));
if (c[i]<=n){
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;
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];
}
}
else{
c[i]=n+1;
}
st1[++p1]=i;
st2[++p2]=i;
r1++, r2++;
t[i]+=2;
if (i<n&&b[i]>b[i+1]){
b[i]=b[i+1];
for (int j=0;j<3;++j){
ans1[i][j]=ans1[i+1][j];
}
}
if (i<n&&c[i]>c[i+1]){
c[i]=c[i+1];
for (int j=0;j<4;++j){
ans2[i][j]=ans2[i+1][j];
}
}
}
while (q--){
int l,r;
cin>>l>>r;
if (r>=c[l]){
cout<<"4\n";
for (int j=0;j<4;++j){
cout<<ans2[l][j]<<" ";
}
cout<<"\n";
}
else{
if (r>=b[l]){
cout<<"3\n";
for (int j=0;j<3;++j){
cout<<ans1[l][j]<<" ";
}
cout<<"\n";
}
else{
cout<<"0\n\n";
}
}
}
return 0;
}