UVA 260 - Il Gioco dell'X Solution

#include<bits/stdc++.h>
using namespace std;
#define MAX 1111
int color[MAX][MAX],n;
char mat[MAX][MAX];
int X[6]= {-1,-1,0,0,1,1};
int Y[6]= {-1,0,-1,1,0,1};
void bfs(int i,int j)
{
    int vx,ux,vy,uy,k;
    queue<int>Q;
    Q.push(i);
    Q.push(j);
    color[i][j]=1;
    while(!Q.empty())
    {
        ux=Q.front();
        Q.pop();
        uy = Q.front();
        Q.pop();
        for(k=0; k<6; k++)
        {
            vx = ux+X[k];
            vy = uy+Y[k];
            if((vx>=1&&vx<=n) && (vy>=1&&vy<=n) && mat[vx][vy]=='w')
            {
                if(!color[vx][vy])
                {
                    color[vx][vy]=1 ;
                    Q.push(vx);
                    Q.push(vy);
                }
            }
        }
    }
}
int main()
{
    int i ,j,l,cas=0;
    while(cin>>n)
    {
        if(n==0)
        break;
        cas++;
        getchar();
        for(i=0; i<n; i++)
        {
            cin>>mat[i];
        }

        for(i=0; i<n; i++)
        {
            if(mat[i][0] == 'w' && color[i][0]==0)
            {
                bfs(i,0);
            }

        }
        int cou =0;
        for(i=0; i<n; i++)
        {
            if(color[i][n-1]==1)
            {
                cou=1;
                break;
            }
        }
        if(cou==1)
            printf("%d W\n",cas);
        else if(cou ==0)
        {
            printf("%d B\n",cas);
        }

        memset(color,0,sizeof(color));
        memset(mat,'\0',sizeof(mat));
    }
    return 0;

}

Codeforces Round #629 (Div. 3)/B. K-th Beautiful String/ Solution

B. K-th Beautiful String

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

For the given integer n$n$ (n>2$n>2$) let's write down all the strings of length n$n$ which contain n−2$n-2$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order.

Recall that the string s$s$ of length n$n$ is lexicographically less than string t$t$ of length n$n$, if there exists such i$i$ (1≤i≤n$1\le i\le n$), that si<ti$s_i<t_i$, and for any j$j$ (1≤j<i$1\le j<i$) sj=tj$s_j=t_j$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.

For example, if n=5$n=5$ the strings are (the order does matter):

1. aaabb
2. aabab
3. aabba
4. abaab
5. ababa
6. abbaa
7. baaab
8. baaba
9. babaa
10. bbaaa

It is easy to show that such a list of strings will contain exactly n⋅(n−1)2$\frac{n\cdot (n-1)}{2}$ strings.

You are given n$n$ (n>2$n>2$) and k$k$ (1≤k≤n⋅(n−1)2$1\le k\le \frac{n\cdot (n-1)}{2}$). Print the k$k$-th string from the list.

Input

The input contains one or more test cases.

The first line contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases in the test. Then t$t$ test cases follow.

Each test case is written on the the separate line containing two integers n$n$ and k$k$ (3≤n≤105,1≤k≤min(2⋅109,n⋅(n−1)2)$3\le n\le {10}^5,1\le k\le min(2\cdot {10}^9,\frac{n\cdot (n-1)}{2})$.

The sum of values n$n$ over all test cases in the test doesn't exceed 105${10}^5$.

Output

For each test case print the k$k$-th string from the list of all described above strings of length n$n$. Strings in the list are sorted lexicographically (alphabetically).

Example

input

Copy

7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

output

Copy

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

উদারহন টি লক্ষ করিঃ

1. aaabb
2. aabab
3. aabba
4. abaab
5. ababa
6. abbaa
7. baaab
8. baaba
9. babaa
10. bbaaa

যখন দুটি b পাশাপাশি থাকে তখন মাত্র পরের ধাপে বামের b টি ১ ঘর বামে এবং ডানের b টি সর্ব ডানে প্রথিস্থাপন হয়। এর পর পুনয়ায় ডানের b টি এক ঘর করে বামের দিকে আসে। যতক্ষণ না ডানের b টির ঠিক পাশে উপস্থিত হয়।

এক্ষেত্রে, b ২টি পাশাপাশি থাকার ধাপ গুলি হলঃ

১,৩,৬,১০,১৫,২১,২৮,৩৬,৪৫..................।

এই ধারাতি ভেঙ্গে নিখলে পাওয়া যায়ঃ

        ধারাটিঃ           ১,৩,৬,১০,১৫,২১,২৮,৩৬,৪৫..................।

পাশাপাশি দুটি সংখ্যার বিয়গফলঃ২,৩,৪,৫,৬,৭,৮,৯........................।
অর্থাৎ, ধারাটি ২টি ধারার সমষ্টি।

এবার, ধারাটি এবং উদারহন টি খেয়াল করিঃ

ধাপ ১ঃ বামের b টি n-1 এ থাকে

ধাপ ২,৩ঃ বামের b টি n-2 এ থাকে

ধাপ ৪,৫,৬ঃ বামের b টি n-3 এ থাকে

ধাপ ৭,৮,৯,১০ঃ বামের b টি n-4 এ থাকে

ধাপ ১১,১২,১৩,১৪,১৫ঃ বামের b টি n-৫ এ থাকে

অর্থাৎ, দুটি সংখ্যার মধ্যকার সংখ্যা এবং ডানের সংখ্যাটির b (বামের b) টির অবস্থান একই।

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, k;
        cin >> n >> k;
        string s(n, 'a');
        for (int i = n - 2; i >= 0; i--) {


            //cout<<"kii="<<k<<" "<<n - i - 1<<endl;
            if (k <= (n - i - 1)) {
                s[i] = 'b';
                s[n - k] = 'b';
                //cout<<"gv=="<<i<<" "<<n-k<<endl;
                cout << s << endl;
                break;
            }
            //cout<<"kii="<<k<<" "<<n - i - 1<<endl;
             //cout<<"k="<<k<<endl;
            k -= (n - i - 1);

        }
    }
}