Idea: FBI
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
x = 0
c = 1
while -n <= x <= n:
if c % 2 == 1:
x -= 2 * c - 1
else:
x += 2 * c - 1
c += 1
if c % 2 == 0:
print("Sakurako")
else:
print("Kosuke")
for tc in range(int(input())):
solve()
Idea: FBI
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
mn = dict()
for i in range(n):
a = [int(x) for x in input().split()]
for j in range(n):
mn[i - j] = min(a[j], mn.get(i - j, 0))
ans = 0
for value in mn.values():
ans -= value
print(ans)
t = int(input())
for _ in range(t):
solve()
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n/2-1;i>=1;i--){
if(a[i]==a[i+1] || a[n-i+1]==a[n-i]){
swap(a[i],a[n-i+1]);
}
}
int re=0;
for(int i=1;i<n;i++){
re+=(a[i]==a[i+1]);
}
cout<<re<<endl;
}
}
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
map<int,int>mp;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int p_su[n+1];
p_su[0]=0;
int lst[n+1];
mp[0]=0;
for(int i=1;i<=n;i++){
p_su[i]=p_su[i-1]+a[i];
if(mp.find(p_su[i])==mp.end()){
lst[i]=-1;
}
else{
lst[i]=mp[p_su[i]];
}
mp[p_su[i]]=i;
}
int dp[n+1];
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
dp[i]=max(dp[i],dp[i-1]);
if(lst[i]!=-1){
dp[i]=max(dp[i],dp[lst[i]]+1);
}
}
cout<<*max_element(dp,dp+n+1)<<endl;
}
}
2033E - Sakurako, Kosuke, and the Permutation
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
cin>>t;
while(t--){
int n;
cin>>n;
int p[n+1];
for(int i=1;i<=n;i++){
cin>>p[i];
}
bool us[n+1];
memset(us,0,sizeof us);
int re=0;
for(int i=1;i<=n;i++){
if(!us[i]){
int cu=i;
int le=0;
while(us[cu]==0){
le++;
us[cu]=1;
cu=p[cu];
}
re+=(le-1)/2;
}
}
cout<<re<<'\n';
}
}
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define ssize(x) (int)(x.size())
#define ALL(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const LL MOD = 1e9 + 7;
int bp(int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 0)
return bp(1LL * a * a % MOD, n / 2);
else
return 1LL * bp(a, n - 1) * a % MOD;
}
int inv(int a) {
return bp(a, MOD - 2);
}
void solve() {
LL n, k;
cin >> n >> k;
n %= MOD;
if (k == 1) {
cout << n << "\n";
return;
}
vector<int> fib(3);
fib[0] = fib[1] = 1;
int cnt = 0;
for (int i = 2; i <= 10 * k; i++) {
fib[i % 3] = (fib[(i + 2) % 3] + fib[(i + 1) % 3]) % k;
if (fib[i % 3] == 0)
cnt++;
if (fib[i % 3] == 1 && fib[(i + 2) % 3] == 0) {
cout << 1LL * i * n % MOD * inv(cnt) % MOD << "\n";
return;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
//#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void precalc(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &maxd, vector<int> &h){
maxd[v] = {0, 0};
if (v != p) h[v] = h[p] + 1;
for(int u: sl[v]){
if (u == p) continue;
precalc(u, v, sl, maxd, h);
if (maxd[v].y < maxd[u].x + 1) {
maxd[v].y = maxd[u].x + 1;
}
if (maxd[v].y > maxd[v].x) {
swap(maxd[v].x, maxd[v].y);
}
}
}
void calc_binups(int v, int p, vector<vector<int>> &sl, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
binup[v][0] = {maxd[p].x, p};
if (maxd[p].x == maxd[v].x + 1) {
binup[v][0].x = maxd[p].y;
}
binup[v][0].x -= h[p];
for(int i = 1; i < 20; ++i){
binup[v][i].y = binup[binup[v][i - 1].y][i - 1].y;
binup[v][i].x = max(binup[v][i - 1].x, binup[binup[v][i - 1].y][i - 1].x);
}
for(int u: sl[v]){
if (u == p) continue;
calc_binups(u, v, sl, binup, maxd, h);
}
}
int get_ans(int v, int k, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
k = min(k, h[v]);
int res = maxd[v].x - h[v];
int ini = h[v];
for(int i = 19; i >= 0; --i){
if ((1 << i) <= k) {
res = max(res, binup[v][i].x);
v = binup[v][i].y;
k -= (1 << i);
}
}
return res + ini;
}
void solve(int tc){
int n;
cin >> n;
vector<vector<int>> sl(n);
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
sl[--u].emplace_back(--v);
sl[v].emplace_back(u);
}
vector<pair<int, int>> maxd(n);
vector<int> h(n);
precalc(0, 0, sl, maxd, h);
vector<vector<pair<int, int>>> binup(n, vector<pair<int, int>>(20));
calc_binups(0, 0, sl, binup, maxd, h);
int q;
cin >> q;
for(int _ = 0; _ < q; ++_){
int v, k;
cin >> v >> k;
cout << get_ans(v - 1, k, binup, maxd, h) << " ";
}
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}