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;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
n, m, _ = map(int, input().split())
print(2 * (n - 1) + (n + 1) * (m - 1))
print("U" * (n - 1) + "L" * (m - 1), end="")
for i in range(n):
if i != 0:
print("D", end="")
if i % 2 == 0:
print("R" * (m - 1), end="")
else:
print("L" * (m - 1), end="")
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
vector<int> p, c;
inline bool read() {
if(!(cin >> n))
return false;
p.resize(n);
c.resize(n);
fore(i, 0, n) {
cin >> p[i];
p[i]--;
}
fore(i, 0, n)
cin >> c[i];
return true;
}
inline void solve() {
vector<int> used(n, 0);
int ans = INF;
fore(st, 0, n) {
if(used[st])
continue;
vector<int> cycle;
int v = st;
while(!used[v]) {
used[v] = 1;
cycle.push_back(v);
v = p[v];
}
fore(step, 1, sz(cycle) + 1) {
if(sz(cycle) % step != 0)
continue;
fore(s, 0, step) {
bool eq = true;
for(int pos = s; pos + step < sz(cycle); pos += step) {
if(c[cycle[pos]] != c[cycle[pos + step]])
eq = false;
}
if(eq) {
ans = min(ans, step);
break;
}
}
}
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (Roms)
MOD = 998244353
p = [1] * 200005
for i in range(1, 200005):
p[i] = (p[i - 1] * 10) % MOD
n = int(input())
for i in range(1, n):
res = 2 * 10 * 9 * p[n - i - 1]
res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
print(res % MOD, end = ' ')
print(10)
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef pair<int, int> pt;
const int MOD = 998244353;
const int N = 500 * 1000 + 13;
int n, k, m;
pair<pt, int> q[N];
int ones[N];
int mx[N], sum[N];
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
return x;
}
int calc(int t) {
memset(ones, 0, sizeof(ones));
memset(mx, -1, sizeof(mx));
forn(i, m) {
int l = q[i].x.x, r = q[i].x.y;
if (q[i].y & (1 << t)) {
ones[l]++;
ones[r + 1]--;
} else {
mx[r] = max(mx[r], l);
}
}
int j = -1;
forn(i, n) {
int cur = 0;
if (!ones[i]) {
cur = sum[i];
if (j == -1) cur = add(cur, 1);
else cur = add(cur, -sum[j]);
}
sum[i + 1] = add(sum[i], cur);
ones[i + 1] += ones[i];
j = max(j, mx[i]);
}
return add(sum[n], j != -1 ? -sum[j] : 1);
}
int main() {
scanf("%d%d%d", &n, &k, &m);
forn(i, m) {
scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
--q[i].x.x; --q[i].x.y;
}
int ans = 1;
forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
printf("%d\n", ans);
}
1327G - Letters and Question Marks
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 8000043;
const int K = 15;
const int M = 1043;
int k;
char buf[N], buf2[M];
vector<string> t;
vector<int> c;
string s;
map<char, int> nxt[M];
int lnk[M];
int p[M];
char pchar[M];
map<char, int> go[M];
int term[M];
int ts = 1;
int A[M][K];
int F[M][K];
int dp[M];
int get_nxt(int x, char c)
{
if(!nxt[x].count(c))
{
p[ts] = x;
pchar[ts] = c;
nxt[x][c] = ts++;
}
return nxt[x][c];
}
void add_string(int i)
{
int cur = 0;
for(auto x : t[i])
{
cur = get_nxt(cur, x);
}
term[cur] += c[i];
}
int get_go(int x, char c);
int get_lnk(int x)
{
if(lnk[x] != -1)
return lnk[x];
if(x == 0 || p[x] == 0)
return lnk[x] = 0;
return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
}
int get_dp(int x)
{
if(dp[x] != -1)
return dp[x];
dp[x] = term[x];
if(get_lnk(x) != x)
dp[x] += get_dp(get_lnk(x));
return dp[x];
}
int get_go(int x, char c)
{
if(go[x].count(c))
return go[x][c];
if(nxt[x].count(c))
return go[x][c] = nxt[x][c];
if(x == 0)
return go[x][c] = 0;
return go[x][c] = get_go(get_lnk(x), c);
}
void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
{
sA = vector<int>(ts);
for(int i = 0; i < ts; i++)
sA[i] = i;
sF = vector<long long>(ts);
for(auto c : s)
{
int ci = int(c - 'a');
for(int i = 0; i < ts; i++)
{
sF[i] += F[sA[i]][ci];
sA[i] = A[sA[i]][ci];
}
}
}
long long solve(const string& s)
{
long long BAD = (long long)(-1e18);
vector<int> pos;
for(int i = 0; i < s.size(); i++)
if(s[i] == '?')
pos.push_back(i);
int cntQ = pos.size();
vector<vector<int> > skip_A(cntQ + 1);
vector<vector<long long> > skip_F(cntQ + 1);
build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
for(int i = 1; i < cntQ; i++)
build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);
vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
vector<int> used(1 << K);
dp[0][skip_A[0][0]] = skip_F[0][0];
queue<int> q;
q.push(0);
used[0] = 1;
long long ans = BAD;
while(!q.empty())
{
int k = q.front();
q.pop();
int step = __builtin_popcount(k);
if(step == cntQ)
{
for(int i = 0; i < ts; i++)
ans = max(ans, dp[k][i]);
continue;
}
for(int i = 0; i < K - 1; i++)
{
if(k & (1 << i)) continue;
int nk = (k ^ (1 << i));
if(used[nk] == 0)
{
used[nk] = 1;
q.push(nk);
}
for(int j = 0; j < ts; j++)
{
if(dp[k][j] == BAD)
continue;
int nj = get_go(j, char('a' + i));
int newSt = skip_A[step + 1][nj];
long long add = get_dp(nj) + skip_F[step + 1][nj];
dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
}
}
}
return ans;
}
int main()
{
scanf("%d", &k);
t.resize(k);
c.resize(k);
for(int i = 0; i < k; i++)
{
scanf("%s %d", buf2, &c[i]);
t[i] = buf2;
}
scanf("%s", buf);
s = buf;
for(int i = 0; i < k; i++)
add_string(i);
for(int i = 0; i < ts; i++)
{
lnk[i] = -1;
dp[i] = -1;
}
for(int i = 0; i < ts; i++)
{
get_lnk(i);
for(char c = 'a'; c <= 'o'; c++)
get_go(i, c);
}
for(int i = 0; i < ts; i++)
get_dp(i);
for(int i = 0; i < ts; i++)
{
for(int j = 0; j < K; j++)
{
A[i][j] = get_go(i, char('a' + j));
F[i][j] = dp[A[i][j]];
}
}
int n = s.size();
vector<int> leftQ(n, -1);
vector<int> rightQ(n, -1);
for(int i = 0; i < n; i++)
{
if(i != 0)
leftQ[i] = leftQ[i - 1];
if(s[i] == '?')
leftQ[i] = i;
}
for(int i = n - 1; i >= 0; i--)
{
if(i != n - 1)
rightQ[i] = rightQ[i + 1];
if(s[i] == '?')
rightQ[i] = i;
}
vector<int> bad(n, 0);
if(leftQ.back() == -1)
bad = vector<int>(n, 1);
long long ans = 0;
int curSt = 0;
string news = "";
for(int i = 0; i < n; i++)
{
int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
if(bad[i])
ans += F[curSt][ci];
curSt = A[curSt][ci];
if(!bad[i])
news.push_back(s[i]);
else if(i != 0 && !bad[i - 1])
news.push_back('o');
}
if(!news.empty())
ans += solve(news);
printf("%lld\n", ans);
}