//I #include<bits/stdc++.h> using namespace std; const int maxn = 4e5 + 10; int T, n, m; int a[maxn]; int solve1() { int res = ((a[1] + m < a[2]) ? 1 : 0); int now = a[1] + m; for (int i = 3; i <= (n << 1); i += 2) { int mn = min(a[i], a[i + 1]); int mx = max(a[i], a[i + 1]); if (mn > now) res += 2; if (mn <= now && mx > now) res++; if (mx <= now) { int need = m - (now - mx) - (now - mn); if (need > 0) res++; } } return res; } int solve2() { int res = ((a[1] < a[2] + m) ? 1 : 0), now = a[1]; for (int i = 3; i <= (n << 1); i += 2) { int mn = min(a[i], a[i + 1]); int mx = max(a[i], a[i + 1]); if (mn > now) res += 2; if (mn <= now && mx > now) res += 1 + ((now - mn < m) ? 1 : 0); if (mx <= now) { if (now - mx < m) res++; if (m - (now - mx) > now - mn) res++; } } return res; } int main() { cin >> T; while (T--) { cin >> n >> m; for (int i = 1; i <= (n << 1); i++) cin >> a[i]; cout << solve1() << ' ' << solve2() << '\n'; } return 0; }
//G #include<bits/stdc++.h> using namespace std; int a, b, c; int main() { cin >> a >> b >> c; int m = max(b, a + 1); // x1 cout << 1; for (int i = 1; i <= m - 2; i++) cout << 0; cout << 1; for (int i = 1; i <= a; i++) cout << 0; cout << ' '; // y1 for (int i = 1; i <= m; i++) cout << 9; cout << ' '; // x2 cout << 1; for (int i = 1; i <= a + m - 1; i++) cout << 0; cout << ' '; // y2 for (int i = 1; i <= m; i++) cout << 9; return 0; }
//B #include <bits/stdc++.h> #define int long long using namespace std; const int md=998244353; int T,n,m,a[100010],f[100010],dp[100010],dpp[100010]; signed main(){ ios::sync_with_stdio(0); cin>>T; while(T--){ cin>>n>>m; bool fl=0; for(int i=0;i<=n*2+1;i++){ f[i]=dp[i]=dpp[i]=0; } for(int i=1;i<=m;i++){ cin>>a[i]; if(a[i]<1||a[i]>2*n){ fl=1; } } if(fl){ cout<<0<<endl; continue; } for(int i=1;i<=m;i++){ if(f[a[i]]){ fl=1; } f[a[i]]=1; } if(fl){ cout<<0<<endl; continue; } dp[0]=1; for(int pos=1;pos<=2*n;pos++){ for(int i=0;i<=n;i++){ dpp[i]=0; } for(int j=0;j<=n;j++){ if(dp[j]==0){ continue; } if(!f[pos]){ if(2*j>=pos){ dpp[j]=(dpp[j]+dp[j])%md; } } if(j+1<=n){ int nj=j+1; if(2*nj>=pos){ dpp[nj]=(dpp[nj]+dp[j])%md; } } } for(int i=0;i<=n;i++){ dp[i]=dpp[i]; } } cout<<dp[n]%md<<endl; } return 0; }
//H #include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 10; const int mod = 998244353; int T, n, x; int a[maxn]; void write(__int128 x) { if (x > 9) write(x / 10); putchar(x % 10 + '0'); }void solve() { __int128 ans = 0, t = 0; cin >> n >> x; for (int i = 1; i <= n; i++) cin >> a[i]; if (x == 1) { for (int i = 1; i <= n; i++) ans = (ans + a[i]) % mod; write(ans); putchar('\n'); return ; } for (int i = 1; i <= n; i++) { t += a[i] / x; a[i] %= x; } sort (a + 1, a + n + 1); for (int i = n; i >= 1; i--) { if (!a[i]) continue; int need = x - a[i] - 1; if (need <= t) { t -= need; a[i] = 0; } else break; } for (int i = 1; i <= n; i++) ans = (ans + a[i]) % mod; write((ans + t % (x - 1)) % mod); putchar('\n'); return ; } signed main() { cin >> T; while (T--) solve(); return 0; }
//K #include <bits/stdc++.h> #define int long long using namespace std; const int inf=1e17; int T,n,a,b,k,tot,s,t,cnt,hed[100010],ver[100010],nxt[100010],edg[100010]; int dis[100010],pre[100010],incf[100010],inq[100010],cost[100010]; int pa[100010],ca[100010],pb[100010],cb[100010]; int h[100010],ansflow,anscost; void add(int a,int b,int c,int d){ ver[++tot]=b,nxt[tot]=hed[a],hed[a]=tot,edg[tot]=c,cost[tot]=d; ver[++tot]=a,nxt[tot]=hed[b],hed[b]=tot,edg[tot]=0,cost[tot]=-d; } bool spfa(){ queue<int> q; for(int i=0;i<=cnt;i++){ dis[i]=inf; inq[i]=0; } dis[s]=0; q.push(s); inq[s]=1; while(!q.empty()){ int u=q.front(); q.pop(); inq[u]=0; for(int i=hed[u];i;i=nxt[i]){ int v=ver[i]; if(edg[i]>0&&dis[v]>dis[u]+cost[i]){ dis[v]=dis[u]+cost[i]; if(!inq[v]){ q.push(v); inq[v]=1; } } } } for(int i=0;i<=cnt;i++){ h[i]=(dis[i]==inf?0:dis[i]); } return dis[t]!=inf; } bool dijkstra(){ priority_queue<pair<int, int> > q; for(int i=0;i<=cnt;i++){ dis[i]=inf; pre[i]=incf[i]=0; } dis[s]=0; incf[s]=inf; q.push({0,s}); while(!q.empty()){ int d=-q.top().first,u=q.top().second; q.pop(); if(dis[u]!=d){ continue; } for(int i=hed[u];i;i=nxt[i]){ int v=ver[i]; if(edg[i]>0){ int nd=d+cost[i]+h[u]-h[v]; if(dis[v]>nd){ dis[v]=nd; pre[v]=i; incf[v]=min(incf[u],edg[i]); q.push({-nd,v}); } } } } return dis[t]!=inf; } void solve(){ cin>>n>>a>>b>>k; for(int i=1;i<=a;i++){ cin>>pa[i]>>ca[i]; } for(int i=1;i<=b;i++){ cin>>pb[i]>>cb[i]; } //Ain=1+(u-1)*2,out=in+1 //Bin=a*2+(v-1)*2+1,out=in+1 s=0,t=a*2+b*2+1; cnt=2*a+2*b+1,tot=1,anscost=0,ansflow=0; for(int i=0;i<=cnt;i++){ hed[i]=0; } for(int u=1;u<=a;u++){ add(u*2-1,u*2,ca[u],0); if(pa[u]==0){ add(s,u*2-1,inf,0); continue; } add(pa[u]*2,u*2-1,inf,0); } for(int v=1;v<=b;v++){ add(a*2+v*2-1,a*2+v*2,cb[v],0); if(pb[v]==0){ add(a*2+v*2,t,inf,0); continue; } add(a*2+v*2,a*2+pb[v]*2-1,inf,0); } for(int i=1;i<=n;i++){ int x,y,w; cin>>x>>y>>w; add(x*2,a*2+y*2-1,1,-w); } if(k==0){ cout<<0<<endl; return ; } if(!spfa()){ cout<<-1<<endl; return; } while(ansflow<k&&dijkstra()){ for(int i=0;i<=cnt;i++){ if(dis[i]<inf){ h[i]+=dis[i]; } } int f=incf[t]; if(f>k-ansflow){ f=k-ansflow; } for(int i=t;i!=s;i=ver[pre[i]^1]){ edg[pre[i]]-=f; edg[pre[i]^1]+=f; } ansflow+=f; anscost+=f*(h[t]-h[s]); } if(ansflow<k){ cout<<-1<<endl; return ; } cout<<-anscost<<endl; } signed main(){ ios::sync_with_stdio(0); cin>>T; while(T--){ solve(); } return 0; }