include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 1e5 + 1; int n; int a[maxn]; vector<int> seg[4 * maxn]; int bnf(int n, vector<int> &v, int k){ int l = 0, r = n - 1, ans = -1; while(l <= r){ int mid = (l + r)/2; if(v[mid] <= k){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } if(ans == -1) return 0; return ans + 1; } void build(int id, int l, int r){ if(l == r){ seg[id].pushback(a[l]); return; } int mid = (l + r)/2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); merge(seg[id * 2].begin(), seg[id * 2].end(), seg[id * 2 + 1].begin(), seg[id * 2 + 1].end(), backinserter(seg[id])); } int get(int id , int l, int r, int u , int v, int k){ if(l > v || r < u) return 0; if(l >= u && r <= v) return bnf(seg[id].size(), seg[id], k); int mid = (l + r)/2; int cnt1 = get(id * 2, l, mid, u, v, k); int cnt2 = get(id * 2 + 1, mid + 1, r, u, v, k); return cnt1 + cnt2; }

signed main() { iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0); int q; cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } build(1, 1, n);cin >> q; while(q--){ int l, r, k; cin >> l >>r>> k; cout << (r - l + 1) - get(1, 1, n, l, r, k) << '\n'; } return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; void build(int id, int l, int r, int tree[], int a[]){ if(l == r){ tree[id] = a[l]; return; } else{ int mid = (l + r)/2, x1 = id * 2, x2 = (id * 2) + 1; build(x1, l, mid, tree, a); build(x2, mid + 1, r, tree, a); tree[id] = min(tree[x1], tree[x2]); } } int getmin(int id, int l, int r, int u, int v, int tree[]){ if(l > v || r < u) return LLONGMAX; if(l >= u && r <= v) return tree[id]; int mid = (l + r)/2; int mn1 = getmin(id * 2, l, mid, u, v, tree); int mn2 = getmin((id * 2) + 1, mid + 1, r, u, v, tree); return min(mn1, mn2); } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); int t; cin >> t; while(t--){ int n, k; cin >> n >> k; int a[n + 1], seg[4 * n + 16]; for(int i = 1;i <= n; i++) cin >> a[i]; build(1, 1, n, seg, a); for(int i = k; i <= n; i++){ cout << getmin(1, 1, n, i - k + 1, i, seg) << ' '; }cout << '\n'; }

return 0;

}

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 2e5 + 1; int a[maxn], seg[4 * maxn], lazy[4 * maxn]; void build(int id, int l, int r){ if(l == r){ seg[id] = a[l]; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); seg[id] = seg[id * 2] + seg[id * 2 + 1]; }

void push(int id, int l, int r){ if(lazy[id] && l != r){ int mid = (l + r)/2; seg[id * 2] += (mid - l + 1)lazy[id]; seg[id * 2 + 1] += (r - mid)lazy[id]; lazy[id * 2] += lazy[id]; lazy[id * 2 + 1] += lazy[id]; lazy[id] = 0; } } void updatelazy(int id, int l, int r, int u, int v, int val){ if(l > v || r < u) return; if(l >= u && r <= v){ seg[id] += val * (r - l + 1); lazy[id]+= val; return; } int mid = (l + r)/2; push(id, l, r); updatelazy(id * 2, l, mid, u, v, val); updatelazy(id * 2 + 1, mid + 1, r, u, v, val); seg[id] = seg[id * 2] + seg[id * 2 + 1]; } int getlazy(int id, int l, int r, int u, int v){ if(l > v || r < u) return 0; if(l >= u && r <= v) return seg[id]; int mid = (l + r)/2; push(id, l, r); int mx1 = getlazy(id * 2, l, mid, u, v); int mx2 = getlazy(id * 2 + 1, mid + 1, r, u, v); return mx1 + mx2; } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); freopen("RANGESUM.INP", "r", stdin); freopen("RANGESUM.OUT", "w", stdout); int n, q; cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); while(q--){ int t; cin >> t; if(t == 2){ int l, r; cin >> l >> r; cout << getlazy(1, 1, n, l, r) << '\n'; }else{ int l, r, v; cin >> l >> r >> v; update_lazy(1, 1, n, l, r, v); }

}
return 0;

}

include <bits/stdc++.h>

define int long long

define s second

define f first

using namespace std; signed main() { iosbase::syncwithstdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n, c; cin >> n >> c; int a[n + 1]; bool dp[2000001]; dp[0] = 1; for(int i = 1; i <= 2000001; i++) dp[i] = 0; unorderedmap<int, int> mp; vector<pair<int, int>> item; for(int i = 1; i <= n; i++){ cin >> a[i]; mp[a[i]]++; } for(auto it: mp){ int cnt = it.s; for(int j = 1; j <= cnt; j *= 2){ item.pushback({j, j * it.f}); cnt -= j; } if(cnt > 0){ item.pushback({cnt, cnt * it.f}); } } for(int i = 0; i < item.size(); i++){ for(int j = c; j >= item[i].s; j--){ if(dp[j - item[i].s]) dp[j] = 1; } } cout << dp[c] << '\n'; } return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 30001; int dp[maxn]; vector<int> a[maxn]; signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); int n; cin >> n; for(int i = 1; i <= n; i++){ int p, k; cin >> p >> k; a[k].pushback(p); } for(int i = 1; i <= maxn; i++){ dp[i] = dp[i - 1]; for(int j = 0; j < a[i].size(); j++){ dp[i] = max(dp[i], dp[a[i][j]] + i - a[i][j]); } } cout << dp[maxn]; return 0; }

include <bits/stdc++.h>

define f first

define s second

define int long long

using namespace std; const int maxn = 1e5 + 1; vector<pair<int, int>> adj[maxn]; bool vis[maxn]; int d[maxn], trace[maxn]; void dijkstra(int s){ d[s] = 0; priorityqueue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push({0, s}); while(!q.empty()){ pair<int, int> top = q.top(); q.pop(); int u = top.s; int kc = top.f; if(kc > d[u]) continue; for(auto it: adj[u]){ int v = it.f; int w = it.s; if(d[v] > d[u] + w){ d[v] = d[u] + w; trace[v] = u; q.push({d[v], v}); } } } } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); int n, m, s, t; cin >> n >> m >> s >> t; while(m--){ int u, v, w; cin >> u >> v >> w; adj[u].pushback({v, w}); } for(int i = 0; i <= n; i++) { d[i] = LLONGMAX; trace[i] = -1; } dijkstra(s); if(d[t] == LLONGMAX){ cout << -1; return 0; } vector<int> path; for(int i = t; i != -1; i = trace[i]){ path.pushback(i); } reverse(path.begin(), path.end()); cout << d[t] << '\n'; for(auto it: path) cout << it << ' '; return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 2e5 + 1; vector<int> adj[maxn]; vector<int> adjrev[maxn]; bool vis[maxn]; vector<vector<int>> c; stack<int> st; int n, m; void dfs1(int u){ vis[u] = 1; for(auto v: adj[u]){ if(!vis[v]) dfs1(v); } st.push(u); } void dfs2(int u, vector<int>& comp){ vis[u] = 1; comp.pushback(u); for(auto v: adjrev[u]){ if(!vis[v]) dfs2(v, comp); } } void kosaraju(){ for(int i = 1; i <= n; i++) if(!vis[i]) dfs1(i); fill(vis + 1, vis + n + 1, 0); while(!st.empty()){ int v = st.top(); st.pop(); if(!vis[v]){ vector<int> b; dfs2(v, b); sort(b.begin(), b.end()); c.pushback(b); } } } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; while(m--){ int u, v; cin >> u >> v; adj[u].pushback(v); adjrev[v].pushback(u); } kosaraju(); cout << c.size() << '\n'; for(auto it: c){ for(auto k: it) cout << k << ' '; cout << '\n'; } return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 2e5 + 1; vector<int> adj[maxn]; vector<vector<int>> c; int num[maxn], low[maxn], timer = 0; stack<int> st; bool instack[maxn]; void dfs(int u){ low[u] = num[u] = ++timer; st.push(u); instack[u] = 1; for(int v: adj[u]){ if(!num[v]){ dfs(v); low[u] = min(low[u], low[v]); }else if(instack[v]) low[u] = min(low[u], num[v]); } if(low[u] == num[u]){ int v; vector<int> comp; while(true){ v = st.top(); comp.pushback(v); st.pop(); instack[v] = 0; if(u == v) break; } sort(comp.begin(), comp.end()); c.pushback(comp); } } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); int n, m; cin >> n >> m; while(m--){ int u, v; cin >> u >> v; adj[u].pushback(v); } for(int i = 1; i <= n; i++) if(!num[i]) dfs(i); cout << c.size() << '\n'; for(auto it: c){ cout << it.size() << ' '; for(auto k: it) cout << k << ' '; cout << '\n'; } return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 1e6 + 1; vector<int> adj[maxn]; bool vis[maxn]; vector<vector<int>> ans; void dfs(int u, vector<int> &path){ vis[u] = 1; path.pushback(u); for(int v: adj[u]){ if(!vis[v]){ dfs(v, path); } } } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); int n, m; cin >> n >> m; while(m--){ int u, v; cin >> u >> v; adj[u].pushback(v); adj[v].pushback(u); } for(int i = 1; i <= n; i++){ if(!vis[i]){ vector<int> v; dfs(i, v); sort(v.begin(), v.end()); ans.push_back(v); } } cout << ans.size() <<'\n'; for(auto it: ans){ for(auto x: it) cout << x << ' '; cout << '\n'; } return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 1e5 + 1; bool vis[maxn]; int par[maxn], d[maxn]; vector<int> adj[maxn]; int n, m; void bfs(int s){ queue<int> q; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 1; for(int v: adj[u]){ if(!vis[v]){ d[v] = d[u] + 1; par[v] = u; vis[v] = 1; q.push(v); //if(v == n) return; } } } } signed main() { iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) par[i] = -1; for(int i = 1; i <= m; i++){ int u, v; cin >> u >> v; adj[u].pushback(v); adj[v].pushback(u); } bfs(1); vector<int> ans; for(int i = n; i != -1; i = par[i]){ ans.pushback(i); } reverse(ans.begin(), ans.end()); cout << ans.size() - 1 << '\n'; for(auto it: ans){ cout << it << " "; } return 0; }

include <bits/stdc++.h>

define int long long

using namespace std; const int maxn = 1e6 + 1; int dp[maxn]; signed main() { iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0); int n, k; cin >> n >> k; dp[0] = 1; for(int i = 1; i <= k; i++) dp[i] = (dp[i - 1] + 1) % 2111992; for(int i = k + 1; i <= n; i++){ dp[i] = (dp[i - k - 1] + dp[i - 1]) % 2111992; } cout << dp[n]; return 0; }

include <bits/stdc++.h>

define int long long

define bignum string

using namespace std; bignum f[102]; bignum add(bignum a, bignum b){ while(a.size() < b.size()) a = '0' + a; while(b.size() < a.size()) b = '0' + b; int carry = 0; bignum c = ""; for(int i = a.size() - 1; i >= 0; i--){ int x = a[i] - '0', y = b[i] - '0'; int sum = x + y + carry; carry = sum/10; c = char(sum % 10 + '0') + c; } if(carry > 0){ c = '1' + c; } return c; } int t; signed main() { iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0);

f[1] = "1"; f[2] = "2";
for(int i = 3; i <= 100; i++) {
       f[i] = add(f[i - 1], f[i - 2]);
}
cin >> t;
while(t--){
    int n; cin >> n;
    cout << f[n] << '\n';
}

return 0;

}