Skip to content

DAA ELAB SRM Solutions – Design and Analysis of Algorithms codes answers 2023 Part 2

    srmnotesadda

    Table of Contents

    Devika is addicted to meat! malik wants to keep

     

     

    #include<iostream> using namespace std;

    #define f(n) for(n=n;n>0;–n) int main()

    {

    int n,r=0,m=100,x,y;

     

    cin>>n; f(n){

    cin>>x>>y; if(y<m) m=y; r+=m*x;

    }

    printf("%d",r);

     

    }

     

     

     

     

    Students in a class are making towers of blocks.

     

     

    #include<iostream>

     

     

    using namespace std;

     

     

    int m, n, x; int main()

    {

    cin>>n>>m; x = 1;

    while((x/2) < n || (x/3) < m || x/2 + x/3 – x/6 < m+n)

    ++x;

    cout << x; return 0;

    }

     

    shiv has given a rebus of form ?+?

     

     

    #include <bits/stdc++.h> using namespace std; int p = 1, n, j, a[105]; char c;

    int main()

    {

    a[j++] = 1;

    while (cin>>c && c != '=')

    {

    if (c == '-') p–, a[j++] = -1; if (c == '+') p++, a[j++] = 1;

    }

    cin>>n;

    for(int i=0;i<j;i++)

    {

    if(a[i]>0)while (p<n && a[i]<n) a[i]++, p++;

    else while (p>n&&a[i]<0 && a[i]>-n) a[i]–, p–;

    }

    if (p != n) { cout << "Impossible\n"; return 0; } cout << "Possible\n";

    for(int i=0;i<j;i++)

    cout << (i ? (a[i]<0 ? "- " : "+ ") : "") << abs(a[i]) << " ";

    cout << "= " << n;

     

     

    }

     

    It's a very unfortunate day for lavanya today

     

     

    #include <bits/stdc++.h> using namespace std;

    #define res cin>>a[i],num+=a[i]; #define f1            for(int i=1;i<=n;i++) double n,v,a[25],b[25],sum,mx=1e9; int main(){

    cin>>n>>v; f1{

    cin>>a[i]; sum+=a[i];

    }

    for(int i=1;i<=n;i++)

    cin>>b[i]; for(int i=1;i<=n;i++)

    mx=min(mx,b[i]/a[i]);

    cout << fixed<<setprecision(1)<<min(mx*sum,v); return 0;

    }

     

     

     

     

    A stealing got into a matches warehouse and wants to steal

     

     

    #include<bits/stdc++.h> using namespace std;

    #define res cin>>a>>b; cin>>s>>d; int n,m,s,a,b,d[11];

    int main(){ cin>>n>>m;

    while(m–)cin>>a>>b,d[b]+=a;

     

    for(int i=10;i>0&&n>0;i–)s+=i*min(n,d[i]),n-=d[i]; cout<<s;

    }

     

     

     

     

    A long time ago, in a galaxy far far away

     

     

    #include<bits/stdc++.h>

     

     

    int a,i;

    int main()

    {std::string s,t; std::cin>>s>>t;

    for(i=s.find(t);i+1;++a,i=s.find(t,i+t.size()));std::cout<<a;}

     

     

     

     

     

    the spring is coming and it means that a lot

     

     

    #include<bits/stdc++.h> using namespace std; map <string,int> p;

    int n,m,g[102],c[102],cnt; string s;

    int main()

    {

    cin>>n>>m; for(int i=0;i<n;i++)

    cin>>g[i]; sort(g,g+n);

    for(int i=0;i<m;i++){

     

    cin>>s; if(!p[s])p[s]=++cnt; c[p[s]]++;

    }

    sort(c+1,c+cnt+1); int num=0;

    for(int i=1;i<=cnt;i++)

    num+=c[i]*g[cnt-i]; cout<<num<<" ";

    num=0;

    for(int i=1;i<=cnt;i++)

    num+=c[i]*g[n-cnt+i-1]; cout<<num;

    return 0;

     

    }

     

     

     

     

     

    If There are n banks in the city where vishnu lives

     

     

    #include<bits/stdc++.h> using namespace std; #define maxs long long

     

    map <maxs,maxs> a; maxs i,n,k,x,p;

    int main(){ cin>>n;

    for(;i<n;i++)cin>>x,k+=x,a[k]++,p=max(p,a[k]); cout<<n-p;

    }

     

    You have infinite cards for each number between 1 and N

     

     

    #include <bits/stdc++.h> using namespace std; using ll = long long int; int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cout.tie(NULL);

    //preSum(); ll t;

    cin>>t; while(t–){

    ll n; cin>>n; if(n==1)

    printf("1\n"); else if(n==2)

    printf("4\n"); else if(n==3)

    printf("10\n");

    else

    printf("%lld\n",9*n-18);

    }

    }

     

     

     

     

    Samy has bought a box of chocolate and has brought them to Anand house.

     

     

    #include<stdio.h>

    int function(int arr[],int i,int j,int memo[][1001],int k)

     

    {

     

    if(i>j)

    return 0; if(arr[i]!=arr[j])

    return 0; if(i==j)

    return 1; if(memo[i][j]!=-1)

    return memo[i][j]; else

    {

    int answer=0;

    for(int p=1;p<=k;p++)

    {

    for(int q=1;q<=k;q++)

    {

    answer+=function(arr,i+p,j-q,memo,k);

    }

    }

    if(answer!=0) answer=1; memo[i][j]=answer; return answer;

    }

     

    }

    int main()

    {

    int n,k; scanf("%d%d",&n,&k); int j,arr[n+1]; for(j=1;j<=n;j++)

     

    scanf("%d",&arr[j]); int memo[1001][1001];

    //            int answer=0; int i;

    for(i=0;i<=1000;i++)

    {

    for(j=0;j<=1000;j++)

    {

    memo[i][j]=-1;

    }

    }

    int answer=function(arr,1,n,memo,k); if(answer==0)

    printf("NO\n"); else

    printf("YES\n");

    }

     

     

     

     

     

    There are N knights sitting at the round table at an equal distance from each other.

     

     

    #include<bits/stdc++.h> using namespace std; int n,a[100020],z;

    int main()

    {

    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i]; for(int i=1;i<=n/3;i++)

    if(n%i==0)

     

    for(int j=0;j<i;j++)

    {

    z=1;

    for(int k=j;k<n;k+=i) z&=a[k]; if(z)

    {cout<<"YES";return 0;}

    }

     

    cout<<"NO"; return 0;

    }

     

     

     

     

    Venkat plays the age of emperor II. He was bored of playing

     

     

    #include <bits/stdc++.h> using namespace std;

    int n, k, c, p[101][101][30], a[30][30];

    char u, v, s[101];

    void play(int &x,int y){ cout<<"strlen";} int solve(int xd=0, int rm=k, int pr=26) {

    if (rm<0) {

    return -1e9;

    }

    if (!s[xd]) {

    return 0;

    }

    int& rt=p[xd][rm][pr]; if (~rt) {

    return rt;

    }

    rt=solve(xd+1, rm, s[xd]-'a')+a[pr][s[xd]-'a'];

     

    for (int i=0; i<26; i++) {

    rt=max(rt, solve(xd+1, rm-1, i)+a[pr][i]);

    }

    return rt;

     

    }

    int main() {

    cin>>s>>k>>n; while (n–) {

    cin>>u>>v>>c; a[u-'a'][v-'a']=c;

    }

    memset(p, -1, sizeof(p)); cout << solve();

    }

     

     

     

     

    This is the easy version of the problem. The only difference is maximum value

     

     

     

     

    #include<bits/stdc++.h> #define int long long using namespace std;

    int const M=5000000;int i,j,n,s,x,e[M+100],f[M+100],d[M+100]; signed main(){

    cin>>n;

    for (i=1;i<=n;i++) scanf("%lld",&x),f[x]++; for (i=1;i<=M;i++)

    for (j=i;j<=M;j+=i)

    e[i]+=f[j];

    for (i=M;i>0;i–){

    for (s=0,j=i*2;j<=M;j+=i) s=max(s,d[j]-e[j]*i);

     

    d[i]=e[i]*i+s;

     

    }

    printf("%lld\n",d[1]); return 0;

    }

     

     

     

     

     

    There are N sprinklers in a field. Each sprinkler has some range up to where it can sprinkle

     

     

     

     

    #include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define endl "\n"

    #define test ll t; cin>>t; while(t–) typedef long long int ll;

    int main() { test

    {

    ll n,q; cin>>n>>q; vector<ll>x(n),r(n); for(auto &it:x) cin>>it; for(auto &it:r) cin>>it; vector<ll>ans(4*n+5,0); for(int i=0;i<n;i++){

    ll left=x[i]-r[i]+2*n;

    ll right=x[i]+r[i]+2*n+1; if(x[i]>0){

    left=max(left,2*n);

    }

     

    else{

    right=min(right,2*n);

    }

    ans[left]++; ans[right]–;

    }

    for(int i=1;i<4*n+5;i++){ ans[i]+=ans[i-1];

    }

    while(q–){

    int inp; cin>>inp; inp+=2*n; cout<<ans[inp]<<endl;

    }

     

    }

     

    return 0;

     

    }

     

     

     

     

     

    Professor Wiki has performed some experiments on rays. The setup for n rays

     

     

    #include<bits/stdc++.h> using namespace std; int n,x,i;

    int a[1000020]; int p[1000020]; int f[1000020];

    int main()

    {

    cin>>n;

     

    for(i=0;i<n;i++)

    {

    cin>>x; p[x]=i;

    }

     

    for(i=0;i<n;i++)

    {

    scanf("%d",&x);

    a[i]=-p[x]-1;

     

    }

     

    for(i=0;i<n;i++)

    *lower_bound(f,f+n,a[i])=a[i];

    int zero=0;

    printf("%ld\n",lower_bound(f,f+n,zero)-f); return 0;

    }

     

     

     

     

     

    There are N sprinklers in a field. Each sprinkler has some range up

     

     

    #include <stdio.h> int min(int a,int b){

    if (a<b){

    return(a);

    }

    else{

    return(b);

    }

    }

    int max(int a,int b){

     

    if (a>b){

     

    return(a);

     

    }

    else{

     

    return(b);

     

    }

     

    }

    int main(){

    int t; scanf("%d",&t); for(int i=0;i<t;i++){

    int n,q,k;

    scanf("%d %d",&n,&q);

    int a[n],b[n]; for(int j=0;j<n;j++){

    scanf("%d",&a[j]);

    }

    for(int m=0;m<n;m++){ scanf("%d",&b[m]);

    }

    int x=(4*n)+1; int sum[x];

    for (int m=0;m<x;m++){

    sum[m]=0;

    }

    for (int m=0;m<n;m++)

    {

    int low=a[m]-b[m]; int up=a[m]+b[m]+1; if (a[m]>0){

    low=max(1,low);

     

    }

    if (a[m]<0){

    up=min(0,up);

    }

    low +=2*n; up +=2*n; sum[low]+=1; sum[up]-=1;

    }

    for (int y=1;y< 4*n+1;y++){

    sum[y]+=sum[y-1];

    }

    for(int m=0;m<q;m++){

    scanf("%d",&k); printf("%d\n",sum[k+(2*n)]);

    }

     

    }

     

    }

     

     

     

     

     

     

     

    Bob goes to the fruit shop to buy apples. There are N apples numbered from 1 to N

     

     

    #include<bits/stdc++.h> using namespace std;

    int i,n, m, sum, a[1002][2]; void sol()

    {

    cin >> n >> m;

    for(int i = 1; i <= m; i ++)a[i][0] = a[i][1] = -1;

     

    a[0][0] = 0;

    a[0][1] = -1;

    sum = 0; for(i=1;i<=n;i++)

    {

    int v, p;

    cin >> v >> p;

    for(int j = min(m-p/2, sum); j >= 0; j –)

    {

    if(a[j][1] != -1 && j + p <= m)a[j+p][1] = max(a[j+p][1], a[j][1] + v); if(a[j][0] != -1)

    {

    if(j + p <= m)a[j+p][0] = max(a[j+p][0], a[j][0] + v);

    a[j+p/2][1] = max(a[j+p/2][1], a[j][0] + v);

    }

    }

    sum = min(m, sum + p);

    }

    int ans =0 ;

    for(int i = 1; i <= m; i ++)ans = max(ans, max(a[i][0], a[i][1])); cout << ans << '\n';

    }

    int main()

    {

    int ntest = 1; cin >> ntest;

    while(ntest — > 0)sol();

    }

     

    Krishnes has given a directed acyclic graph with N vertices and M edges.

     

     

     

     

    #include <bits/stdc++.h> using namespace std;

    int T,n,m,pr[150010],l[150010],f[150010][2],a[4],b[4];

    vector<int>E[150010]; void direction(int x,int c){} void pairs();

    void pairs(){

    scanf("%d%d",&n,&m);

    for(int i=0;i<=n+1;i++) E[i].clear(),pr[i]=0,f[i][0]=f[i][1]=0; for(int i=1,u,v;i<=m;i++){

    scanf("%d%d",&u,&v); if(u+1==v) pr[v]=1; else E[v].push_back(u);

    }

    pr[1]=pr[n+1]=1;

    for(int i=2;i<=n;i++) E[i].push_back(0),E[n+1].push_back(i-1); int L=0,R=n+1;

    while(L<=n&&pr[L+1]) L++; while(R&&pr[R]) R–;

    if(R==0) return printf("%lld\n",1ll*n*(n-1)/2),void(); for(int i=1;i<=n;i++) l[i]=pr[i]?l[i-1]:i;

    f[L][0]=1,f[L][1]=2;

    for(int i=L;i<=n;i++) for(int u:E[i+1]) for(int k=0;k<2;k++) if(l[i]<=u+1) f[i][k]|=f[u][k^1]; for(int i=L;i>=1;i–) for(int u:E[i+1]) for(int k=0;k<2;k++) if(l[i]<=u+1) f[u][k]|=f[i][k^1]; for(int i=0;i<4;i++) a[i]=b[i]=0;

    for(int i=0;i<=L;i++) a[f[i][0]]++;

    for(int i=R-1;i<=n;i++) b[f[i][0]]++; long long ans=0;

     

    for(int p=0;p<4;p++) for(int q=0;q<4;q++) if(p&q) ans+=1ll*a[p]*b[q]; printf("%lld\n",ans-(L+1==R));

    }

    int main(){

    scanf("%d",&T);

    while(T–) pairs();

    }

     

    SESSION 6:

     

    Given a chess board having NxN cells, you need to place N queens on the board in such

     

     

    #include<iostream> using namespace std;

     

    int n;

    bool grid[10][10];

     

     

    bool isSafe(int row, int col){ int i,j;

    for(i=0;i<row;++i) if(grid[i][col]) return false; for(i=row,j=col;i>=0 and j>=0;–i,–j) if(grid[i][j]) return false; for(i=row,j=col;i>=0 and j<n;–i,++j) if(grid[i][j]) return false; return true;

    }

     

     

    bool solveQueen(int row){ if(row>=n) return true; for(int col=0;col<n;++col){ if(isSafe(row,col)){

    grid[row][col]=true; if(solveQueen(row+1)) return true; grid[row][col]=false;

    }

    }

    return false;

    }

     

    int main(){ cin>>n; int i;

    if(solveQueen(0)){ for(i=0;i<n;++i){

    for(int j=0;j<n;++j) cout<<grid[i][j]<<" "; cout<<endl;

    }

    }

    else cout<<"Not possible\n"; return 0;

    }

     

     

     

     

     

    Chef started watching a movie that runs for a total of XX minutes.

     

     

    #include<bits/stdc++.h> using namespace std;

     

    void solve()

    {

    int x,y; cin>>x>>y;

     

    cout<<(x-y)+y/2<<"\n";

    }

     

     

    int main()

    {

    int t;

     

    t=1;

    while(t–)

    solve();

    }

     

     

     

     

    Samu is playing a shooting game in play station.

     

     

    #include<bits/stdc++.h> using namespace std; #define MAXN 1010

    #define MAXW 1010 double DP[MAXN][MAXW];

    int main(){

    int t; cin>>t; while(t–){

    int X,Y,N,W,P1,P2; cin>>X>>Y>>N>>W>>P1>>P2;

    for(int i=0;i<=N;i++){

    for(int j=0;j<=W;j++){

    DP[i][j]=0;

    }

    }

    double p1 = 0.01 * P1; double p2 = 0.01 * P2; for (int i=0;i<=N;i++) DP[i][0] = 1;

    for (int i=1;i<=W;i++)

    DP[0][i] = 0;

    for (int i=1;i<=N;i++){

     

    for (int j=1;j<=W;j++) {

    DP[i][j] = max(p1*DP[i-1][max(j-X,0)] + (1-p1)*DP[i-1][max(j,0)], p2*DP[i-1][max(j- Y,0)] + (1-p2)*DP[i-1][max(j,0)]);

    }

    }

    printf("%.6f\n",DP[N][W]*100);

     

     

    }

    }

     

     

     

     

    Given integer N, you need to find four integers A,B,C,D, such that they're all factors

     

     

    #include<bits/stdc++.h> using namespace std; void solve(){}

    int main(){

    int t; cin>>t; while(t–){ long long n; cin>>n;

    if(n&1 or n<4) cout<<"-1\n";

    else if(!(n%4)) cout<<((n>>2)*(n>>2)*(n>>2)*(n>>2))<<'\n';

    else if(!(n%6)) cout<<((n/6)*(n/6)*(n/3)*(n/3))<<'\n';

    else if(!(n%10)) cout<<((n/10)*(n/5)*(n/5)*(n>>1))<<'\n'; else cout<<"-1\n";

    }

    return 0;

    }

     

     

     

     

     

    There is a mysterious temple in mysteryland. The door of the temple is always

     

    #include <bits/stdc++.h>

     

     

    using namespace std;

     

     

    int arr [100 + 5]; bool flag;

    bool vis [100 + 5][10000 + 5];

    int sum , n;

     

     

    void rec(int index, int tot){

     

     

    if(index == n){                       // base case

     

     

    if(tot == sum / 2) flag = true;      //valid case return;

    }

     

     

    if(vis[index][tot]) return;               // check if this state visited before

     

     

    rec(index + 1, tot + arr[index]);         // add this item to first box rec(index + 1, tot);               // add this item to second box vis[index][tot] = true;           // mark this state is visited

    }

     

     

    int main()

    {

    int t;

     

     

    cin >> t;

     

     

    while(t–){

     

     

    cin >> n;

     

     

    sum = 0; flag = false;

    memset(vis, false, sizeof vis);

     

     

    for(int i = 0; i < n; i++){

     

     

    cin >> arr[i]; sum += arr[i];

    }

     

     

    if(sum % 2 != 0) cout << "NO\n";                  // invalid case else {

     

    rec(0 , 0);

    if(flag) cout << "YES\n"; else cout << "NO\n";

    }

     

    }

     

     

    return 0;

     

    }

     

     

     

     

     

    You are given three arrays a1…n,b1…n,c1…n and two numbers M and K.

     

     

    #include <iostream> #include<bits/stdc++.h>

     

    #define f1 for(i=0;i<n;i++) using namespace std;

    long long int min(long long int x, long long int y){ if(x < y)

    return x; else

    return y;

    }

    int main(){

    int n, m, K;

    cin >> n >> m >> K;

    long long int a[n],b[n],c[n]; long long int i,j,l;

    int p,T = 0;

    for(i = 0; i < n; i++)

    cin >> a[i] >> b[i] >> c[i]; long long int lx,rx,ly,ry,lz,rz; cin >> lx >> rx;

    cin >> ly >> ry; cin >> lz >> rz;

    for(i = lx; i < min(rx, lx + m); i++){

    for(j = ly; j < min(ry,ly + m);j++){

    for(l = lz;l < min(rz,lz + m);l++){ T=0;

    for(p = 0; p < n; p++){

    if((a[p] * i + b[p] * j- c[p] * l) % m == 0) T++;

    } if(T==K)

    break;

    }

     

    if(l < min(rz,lz + m)) break;

    }

    if(j < min(ry,ly + m)) break;

     

     

    }

    if(i < min(rx, lx + m)){

    cout << i << " " << j << " " << l;

    }

    else

    cout << "-1" << endl;

     

    }

     

     

     

     

    The end semester exams are now approaching. Ritu is the computer

     

     

    #include<iostream> #include<bits/stdc++.h> using namespace std; int arr[1001][1001];

    int dp[1001][1001];

    const int mod = 1e9+7; void solve(){

    cout<<"for(i=0;i<N;i++)";}

    long int decrease_path(int i , int j,int n)

    {

    if(arr[i][j]==1) return 1; if(dp[i][j]!=-1) return dp[i][j];

    long int a = (i>0 && arr[i-1][j]<arr[i][j])?decrease_path(i-1,j,n):0;

    long int b = (j>0 && arr[i][j-1]<arr[i][j])?decrease_path(i,j-1,n):0;

     

    long int c = (i<n-1 && arr[i+1][j]<arr[i][j])?decrease_path(i+1,j,n):0; long int d = (j<n-1 && arr[i][j+1]<arr[i][j])?decrease_path(i,j+1,n):0; dp[i][j] = a+b+c+d+1;

    dp[i][j]%=mod;

    return dp[i][j];

     

    }

    int main()

    {

    cin.tie(NULL); ios_base::sync_with_stdio(false); int n;

    cin>>n;

    for(int i = 0;i<n;i++)

    {

    for(int j = 0;j<n;j++)

    {

    cin>>arr[i][j];

    }

    }

    memset(dp,-1,sizeof(dp)); long int count = 0;

    for(int i = 0;i<n;i++)

    {

    for(int j = 0;j<n;j++)

    {

    long int a = decrease_path(i,j,n); count+=a;

    count%=mod;

    }

    }

    cout<<count<<'\n';

     

    }

     

     

     

     

     

    You are given two numbers n and k. for each number in the interval [1,n], your task is to

     

     

    #include<bits/stdc++.h> using namespace std;

     

    using ll = long long;

     

     

    long long f(int n, int k) { if (n == 0) return 0; long long res = (n/k);

    return f(n/k, k) + n * (ll)(n+1) / 2ll – (res * (res + 1) / 2ll) * k;

    }

     

     

    int main () { int T = 1;

    scanf("%d", &T);

    assert(T >= 1 && T <= 300000); while(T–) {

     

    int n, k;

    scanf("%d%d", &n, &k); assert(n <= 1e9);

    assert(k >= 2 && k <= 1e9);

     

     

    printf("%lld\n", f(n, k));

     

     

    }

     

     

    return 0;

     

    }

     

     

     

     

    Lucky numbers are defined as the numbers consisting only of digits 3 and 5.

     

     

    #include<bits/stdc++.h> using namespace std;

     

    string solve(string& s)

    {

    int n = s.size(), i = 0;

    while(i < n && (s[i] == '3' || s[i] == '5'))

    ++i;

    if(i < n && (s[i] < '5'))

    {

    if(s[i] == '4')

    s[i] = '5';

    else

    s[i]='3';

    ++i;

    while(i<n)

    {

    s[i] = '3';

    ++i;

    }

    }

    else

    {

    while(i >= 0 && (s[i] != '3'))

     

    –i;

    if(i < 0)

    return string(n + 1, '3');

    s[i] = '5';

    ++i;

    while(i < n)

    {

    s[i] = '3';

    ++i;

    }

     

    }

    return s;

     

    }

     

     

    int main()

    {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int t;

    cin >> t; while(t–)

    {

    string s; cin >> s;

    cout << solve(s) << endl;

    }

    }

     

    SESSION 7: GRAPH COLOURING:-

     

    Adiththi likes drawing. She has drawn many graphs already, both directed and not.

     

     

    #include<bits/stdc++.h> using namespace std;

    #define ggg int find(int p) unite(int p,int q) cin>>u>>v; int i,j,x,y,n,m,ans,f[502],a[502];

    int find(int x){return (f[x]==x)?x:f[x]=find(f[x]);} int main (){

    scanf("%d %d",&n,&m);

    if (m>n) return printf("NO\n"),0; for (i=1;i<=n;i++) f[i]=i;

    for (i=1;i<=m;i++){

    scanf("%d %d",&x,&y);a[x]++;a[y]++;

    if (find(x)==find(y)&&i!=n) return printf("NO\n"),0; f[find(x)]=find(y);

    }

    for (i=1;i<=n;i++)

    if (a[i]>2)

    return printf("NO\n"),0; printf("YES\n%d\n",n-m);

    for (i=1;i<=n;i++)

    while (a[i]<2){

    ans=i+(n!=1);

    for (j=ans;j<=n;j++)

    if (a[j]<2&&(n<=2||m+1==n||find(i)!=find(j)))

    {printf("%d

    %d\n",i,j);m++;a[i]++;a[j]++;f[find(i)]=find(j);break;}

    }

    return 0;

     

    }

     

     

    Nowadays the one-way traffic is introduced all over the world in order to improve

     

     

    #include<bits/stdc++.h> using namespace std; int s[105],e[105];

    int main(){

    int n,ans=0,res=0;cin>>n; while(n–){

    int a,b,c;cin>>a>>b>>c; if(s[a]||e[b])res+=c,s[b]=e[a]=1; else s[a]=e[b]=1;

    ans+=c;

    }

    cout<<min(res,ans-res);

     

     

    }

     

     

     

     

    Bragadesh got a job as a system administrator in X corporation.

     

     

    #include<bits/stdc++.h> using namespace std; int n,m,v,u;

    int main(){

    cin>>n>>m>>v;

    if(m<n-1 || m>(n-1)*(n-2)/2+1)return printf("-1"),0; for(int i=1;i<=n;++i)if(i!=v)printf("%d %d\n",i,v),u=i; m-=n-1;

    if(m)for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(i!=v && j!=u && i!=u && j!=v){

     

    printf("%d %d\n",i,j); m–;

    if(!m)return 0;

     

    }

     

    }

     

     

     

     

    We call two numbers x and y similar if they have the same parity

     

     

    #include<bits/stdc++.h>

    #define solve int t,n,q,i,j,w,a[55],b[55]; while(t!=0) { int t,n,a[52],s,o,i;

    int main(){

    for(scanf("%d",&t);t–;){

    for(scanf("%d",&n),o=0;i<n;) scanf("%d",a+i), o+=a[i++]&1;

    for(std::sort(a,a+n),s=0;–i;) s|=(a[i]-a[i-1]==1); puts(o&1&(!s)?"NO":"YES");

    }

    }

     

     

     

     

     

    One Egyptian boy called Aabid wants to present a string of beads to his friend

     

     

    #include <bits/stdc++.h> using namespace std;

    #define solve int beads(int len,int lim1,int lim2) cin>>n>>m; #define rep(i,s,t) for(I i=s;i<=t;++i)

    #define c(f) memset(f,-1,sizeof f); #define R return

    #define I int

     

    #define L long long

    L f[55][2][2],K,d;I a[55],n; L C(I l,I r,I x,I y){

    if (l>r)R 1;L&F=f[l][x][y];if(~F)R F;F=0;

    rep(i,0,1)rep(j,0,1)if(a[l]-!i&&a[r]-!j&&(l<r||i==j)&&(x||i<=j)&&(y||i<=(!j)))F+=C(l+1,r- 1,x||(i<j),y||(i<!j));R F;

    }

    I main(){

    cin>>n>>K;c(a)c(f)if(C(1,n,a[1]=0,0)<++K)R cout<<-1,0;

    rep(i,2,n){c(f)d=C(1,n,a[i]=0,0);K-=(a[i]=(d<K))*d;} rep(i,1,n)cout<<a[i];

    }

     

     

     

     

    Students of Winter Informatics School are going to live in a set of houses connected by underground passages.

     

     

    #include "bits/stdc++.h" using namespace std;

    #define mandatory cout<<"scanf("%d", &T); scanf("%d%d", &n, &m); while(T–)" #define pb push_back

    #define mp make_pair

     

     

    const int MX = 3e6 + 5; void solve2(){}

     

    int N, M; int col[MX];

    bool visited[MX]; vector<int> adj[MX];

     

    void dfs(int at) {

    col[at] = 1;

    for (auto x: adj[at]) if (col[x]) col[at] = 0;

    for (auto x: adj[at]) if (!visited[x]) { visited[x] = 1;

    dfs(x);

    }

    }

     

     

     

     

    void solve() {

    cin >> N >> M;

    for (int i = 0; i <= N; i++) {

    visited[i] = 0;

    col[i] = 0; adj[i].clear();

    }

    for (int i = 0; i < M; i++) {

    int a, b; cin >> a >> b; adj[a].pb(b), adj[b].pb(a);

    }

     

     

    visited[1] = 1; dfs(1);

    for (int i = 1; i <= N; i++) if (!visited[i]) { cout << "NO\n";

    return;

    }

    vector<int> ans;

    for (int i = 1; i <= N; i++) if (col[i]) ans.pb(i); cout << "YES\n";

    cout << (int)ans.size() << "\n";

     

    for (auto x: ans) cout << x << " "; cout << "\n";

    }

     

     

     

     

    int main() {

    int t; cin >> t; while (t–) {

    solve();

    }

    }

     

     

     

     

    During the break the schoolchildren, boys and girls, formed a queue of n people in the canteen.

     

     

    #include<bits/stdc++.h> using namespace std;

    #define madatory cout<<"int i,k,n; while(k){ char a[n+3];" string s;

    int n,t,i; int main(){

    cin>>n>>t>>s;

    while(t–) for(i=0;i<n-1;i++) if(s[i]=='B'&&s[i+1]=='G'){swap(s[i],s[i+1]);i++;} cout<<s;

    }

     

     

     

     

    The houses are numbered from 1 to N. Underground water pipes connect these houses together.

     

     

    #include<iostream> using namespace std;

     

    #define N 1010

    int a[N],w[N],b[N]; int main()

    {

    int n,p,x,y,z,i,t,min; cin>>n>>p;

    while(p–)

    {

    cin>>x>>y>>z; a[x]=y;

    w[x]=z;

    b[x]++;

    b[y]+=2;

    }

    for(t=0,i=1;i<=n;i++)if(b[i]==1)t++; printf("%d\n",t); for(i=1;i<=n;i++)if(b[i]==1)

    {

    min=w[i];

    t=a[i]; while(a[t]!=0)

    {

    if(w[t]<min)min=w[t]; t=a[t];

    }

    printf("%d %d %d\n",i,t,min);

    }

    return 0;

    }

     

    Session 9 : SUM of Subset

     

    Palani goes to the Koyembedu Vegetables Market to buy some Vegetables.

     

     

    #include<bits/stdc++.h> using namespace std; #define if hha

    int main()

    {

    int i,t; cin>>t; while(t–){

    int a[3]; for(i=0;i<3;i++) cin>>a[i]; sort(a,a+3);

    cout<<a[2]+a[1]<<endl;

    }

    return 0;

    }

     

     

     

     

    Mano went shopping and bought items worth X dollors

     

     

    #include <stdio.h> void solve(){}

    int main()

    {

    int x,t; scanf("%d",&t);

    while(t–){

     

    scanf("%d",&x);

    printf("%d\n",100-x);

     

    }

     

    return 0;

     

    }

     

     

    Tesla recently found a new rectangular electric board that he would like to recycle

     

     

    #include<bits/stdc++.h> using namespace std; const int inf = 1012345678; int A[309][309];

    int H, W, K; bool ok[309][309][309];

    int main() {

    int Q,rep; cin >> Q;

    for (rep = 1; rep <= Q; ++rep) { cin >> H >> W >> K;

    for (int i = 0; i < H; ++i) {

    for (int j = 0; j < W; ++j) {

    cin >> A[i][j];

    }

    }

    for (int i = 0; i < H; ++i) {

    for (int j = 0; j < W; ++j) {

    int cl = inf, cr = -inf;

    for (int k = j; k < W; ++k) {

    cl = min(cl, A[i][k]);

    cr = max(cr, A[i][k]); if (cr – cl <= K) {

    ok[i][j][k] = true;

     

    }

    else {

     

    ok[i][j][k] = false;

     

    }

     

    }

     

    }

     

    }

    int ans = 0;

    for (int i = 0; i < W; ++i) {

    for (int j = i; j < W; ++j) {

    int cont = 0;

    for (int k = 0; k < H; ++k) {

    if (ok[k][i][j]) ++cont; else cont = 0;

    ans = max(ans, cont * (j – i + 1));

    }

    }

    }

    cout << ans << endl;

     

    }

    return 0;

     

    }

     

     

     

     

    Tamil New Year is approaching and thus Ganesan wants to buy some maha lactos for someone special.

     

     

    #include <stdio.h> void solve(){}

    int main()

    {

     

    int t; scanf("%d",&t); for(int i=0;i<t;i++){

    int a,b;

    scanf("%d %d",&a,&b);

    printf("%d\n",a/b);

    }

    return 0;

     

    }

     

     

     

     

    Mani bought N items from a Nilgiris super market. Although it is hard to carry all these items in hand,

     

     

    #include<iostream> using namespace std; void solve(){}

    int main()

    {

    double n; cin>>n; while(n–){

    int x; cin>>x;

    x%10==0 ? cout<<x/10<<endl : cout<<x/10+1<<endl;

    //if(x%10==0)

    //cout<<x/10<<endl;

    // else

    // cout<<x/10+1<<endl;

    }

    }

    Leave a Reply