Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (awoo)
for _ in range(int(input())):
n, m = map(int, input().split())
print(n // 2 + 1, m // 2 + 1)
Solution 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n, m;
scanf("%d%d", &n, &m);
int svx = 1, svy = 1;
for (int x = 1; x <= n; ++x){
for (int y = 1; y <= m; ++y){
bool ok = true;
for (int dx : {-2, -1, 1, 2}){
for (int dy : {-2, -1, 1, 2}){
if (abs(dx * dy) != 2) continue;
if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= m)
ok = false;
}
}
if (ok){
svx = x;
svy = y;
}
}
}
printf("%d %d\n", svx, svy);
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
for _ in range(int(input())):
n = int(input())
ans = [0]
for x in map(int, input().split()):
if x != 0 and ans[-1] - x >= 0:
print(-1)
break
else:
ans.append(ans[-1] + x)
else:
print(*ans[1:])
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (BledDest)
#include<bits/stdc++.h>
using namespace std;
long long dp[65][65][3];
void solve(int n)
{
memset(dp, 0, sizeof dp);
int k = n / 2;
dp[0][0][2] = 1;
for(int i = 0; i <= k; i++)
for(int j = 0; j <= k; j++)
for(int t = 0; t <= 2; t++)
{
int turn = (i + j) % 4;
if (turn == 0 || turn == 3)
{
if(i < k) dp[i + 1][j][t == 2 ? 0 : t] += dp[i][j][t];
if(j < k) dp[i][j + 1][t] += dp[i][j][t];
}
else
{
if(i < k) dp[i + 1][j][t] += dp[i][j][t];
if(j < k) dp[i][j + 1][t == 2 ? 1 : t] += dp[i][j][t];
}
}
for(int i = 0; i < 3; i++)
cout << dp[k][k][i] % 998244353 << " ";
cout << endl;
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
solve(n);
}
}
Solution 2 (BledDest)
def fact(n):
return 1 if n == 0 else n * fact(n - 1)
def choose(n, k):
return fact(n) // fact(k) // fact(n - k)
def calc(n):
if n == 2:
return [1, 0, 1]
else:
a = calc(n - 2)
return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1]
t = int(input())
for i in range(t):
mod = 998244353
n = int(input())
a = calc(n)
a = list(map(lambda x: x % mod, a))
print(*a)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n;
vector<vector<int>> g;
vector<int> st;
vector<int> pd;
void init(int v, int d){
st.push_back(v);
if (int(st.size()) - d >= 0)
pd[v] = st[st.size() - d];
for (int u : g[v])
init(u, d);
st.pop_back();
}
vector<char> used;
void dfs(int v){
used[v] = true;
for (int u : g[v]) if (!used[u])
dfs(u);
}
int get(int d){
pd.assign(n, -1);
init(0, d);
vector<int> ord, h(n);
queue<int> q;
q.push(0);
while (!q.empty()){
int v = q.front();
q.pop();
ord.push_back(v);
for (int u : g[v]){
q.push(u);
h[u] = h[v] + 1;
}
}
reverse(ord.begin(), ord.end());
used.assign(n, 0);
int res = 0;
for (int v : ord) if (!used[v] && h[v] > d){
++res;
dfs(pd[v]);
}
return res;
}
int main() {
int t;
scanf("%d", &t);
while (t--){
int k;
scanf("%d%d", &n, &k);
g.assign(n, vector<int>());
for (int i = 1; i < n; ++i){
int p;
scanf("%d", &p);
--p;
g[p].push_back(i);
}
int l = 1, r = n - 1;
int ans = n;
while (l <= r){
int m = (l + r) / 2;
if (get(m) <= k){
ans = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%d\n", ans);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int INF = 1e9;
int main(){
int n;
cin >> n;
vector<string> s(2);
forn(i, 2) cin >> s[i];
vector<array<array<int, 2>, 2>> dp(n + 1);
forn(i, n + 1) forn(j, 2) forn(k, 2) dp[i][j][k] = -INF;
dp[0][0][s[1][0] == '1'] = s[1][0] == '1';
dp[0][0][0] = 0;
forn(i, n - 1) forn(j, 2){
int nxtj = s[j][i + 1] == '1';
int nxtj1 = s[j ^ 1][i + 1] == '1';
dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + nxtj1);
dp[i + 1][j][nxtj1] = max(dp[i + 1][j][nxtj1], dp[i][j][0] + nxtj1 + nxtj);
dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + nxtj);
}
cout << max({dp[n - 1][0][0], dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]}) << '\n';
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 10043;
const int K = 12;
int tsz = 0;
int trie[N][K];
int aut[N][K];
int lnk[N];
int p[N];
int pchar[N];
int cost[N];
int ncost[N];
int newNode()
{
lnk[tsz] = -1;
ncost[tsz] = -1;
cost[tsz] = 0;
for(int i = 0; i < K; i++)
{
trie[tsz][i] = aut[tsz][i] = -1;
}
return tsz++;
}
int nxt(int x, int y)
{
if(trie[x][y] == -1)
{
trie[x][y] = newNode();
pchar[trie[x][y]] = y;
p[trie[x][y]] = x;
}
return trie[x][y];
}
int go(int x, int y);
int get_lnk(int x)
{
if(lnk[x] != -1) return lnk[x];
int& d = lnk[x];
if(x == 0 || p[x] == 0) return d = 0;
return d = go(get_lnk(p[x]), pchar[x]);
}
int go(int x, int y)
{
if(aut[x][y] != -1) return aut[x][y];
int& d = aut[x][y];
if(trie[x][y] != -1) return d = trie[x][y];
if(x == 0) return d = 0;
return d = go(get_lnk(x), y);
}
void add(string s, int c)
{
int cur = 0;
for(auto x : s) cur = nxt(cur, x - 'a');
cost[cur] += c;
}
int calc(int x)
{
if(ncost[x] != -1) return ncost[x];
ncost[x] = cost[x];
int y = get_lnk(x);
if(y != x) ncost[x] += calc(y);
return ncost[x];
}
int main()
{
int root = newNode();
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
string s;
int x;
cin >> x >> s;
map<char, set<char>> adj;
for(int j = 0; j + 1 < s.size(); j++)
{
adj[s[j]].insert(s[j + 1]);
adj[s[j + 1]].insert(s[j]);
}
bool bad = false;
string res = "";
char c;
for(c = 'a'; c <= 'l'; c++)
{
if(!adj.count(c)) continue;
if(adj[c].size() >= 3)
bad = true;
if(adj[c].size() == 1)
break;
}
if(c == 'm' || bad) continue;
res.push_back(c);
while(adj[c].size() > 0)
{
char d = *adj[c].begin();
adj[c].erase(d);
adj[d].erase(c);
c = d;
res.push_back(c);
}
bad |= adj.size() != res.size();
map<char, int> pos;
for(int i = 0; i < res.size(); i++)
pos[res[i]] = i;
for(int i = 0; i + 1 < s.size(); i++)
bad |= abs(pos[s[i]] - pos[s[i + 1]]) > 1;
if(bad) continue;
add(res, x);
reverse(res.begin(), res.end());
add(res, x);
}
int INF = 1e9;
int K = 12;
vector<vector<int>> dp(1 << K, vector<int>(tsz + 1, -INF));
vector<vector<pair<int, int>>> pdp(1 << K, vector<pair<int, int>>(tsz + 1));
dp[0][0] = 0;
for(int i = 0; i < (1 << K); i++)
for(int j = 0; j <= tsz; j++)
{
for(int z = 0; z < K; z++)
{
if(i & (1 << z)) continue;
int nstate = go(j, z);
int add = calc(nstate);
int nmask = i | (1 << z);
if(dp[nmask][nstate] < dp[i][j] + add)
{
dp[nmask][nstate] = dp[i][j] + add;
pdp[nmask][nstate] = {z, j};
}
}
}
string ans = "";
int curmask = (1 << K) - 1;
int curstate = max_element(dp[curmask].begin(), dp[curmask].end()) - dp[curmask].begin();
while(curmask != 0)
{
int cc = pdp[curmask][curstate].first;
int ns = pdp[curmask][curstate].second;
ans.push_back(char('a' + cc));
curmask ^= (1 << cc);
curstate = ns;
}
cout << ans << endl;
}