Codeforces Beta Round #59 Solution Problem E

This is the code of watashi, he used “backtrack” and a “mask” to solve this problem.

#include <cstdio>
#include <algorithm>

using namespace std;

char str[10][10];
int hash[1<<20];

const int lj[] = {-1, 1, 1, 1, 2, 3};
const int rj[] = {-1, 3, 4, 5, 5, 5};
const int dx[] = {0, 1, 1};
const int dy[] = {1, 0, 1};

bool gao() {
    int index = 0;
    for (int i = 1; i <= 5; ++i){
        for (int j = lj[i]; j <= rj[i]; ++j){
            index <<= 1;
            if (str[i][j] == 'O')
                index ^= 1;
        }
    }
    int& ret = hash[index];
    if (ret == 0) {
        ret = -1;
        for (int i = 1; ret < 0 && i <= 5; ++i) {
            for (int j = lj[i]; ret < 0 && j <= rj[i]; ++j) {
                if (str[i][j] != 'O') continue;
                for (int k = 0; ret < 0 && k < 3; ++k) {
                    int x = i, y = j;
                    while (str[x][y] == 'O') {
                        str[x][y] = 'X';
                        x += dx[k];
                        y += dy[k];
                        if (!gao()) {
                            ret = 1;
                            break;
                        }
                    }
                    while (x != i || y != j) {
                        x -= dx[k];
                        y -= dy[k];
                        str[x][y] = 'O';
                    }
                }
            }
        }
    }
    return ret > 0;
}

int main() {
    for (int i = 1; i <= 5; ++i)
        for (int j = lj[i]; j <= rj[i]; ++j)
            scanf(" %c", &str[i][j]);
    puts(gao() ? "Karlsson" : "Lillebror");
}

Codeforces Beta Round #59 Solution Problem D

In this problem (Problem D) always be a solution for any event.
Many solved this by printing the letters in the form of “snake”.
My solution printed from right to left the necessary letters.
Example 3×3 + 2×2 and 13 = abcdefghijklm

cdijm
behkl
afg..

Example 2×3 + 2×2 and 10 = abcdefghij

afgj
behi
cd..

Always considering to start up for a ‘a’ even and down for a ‘a’ odd.

int main(){
    int a, b, c, d, n, num, itx = 0, ity = 0;
    scanf("%d %d %d %d %d", &a, &b, &c, &d, &n);
    string aux(a+c, '.');
    vector<string> v(max(b,d), aux);
    bool up = false;
    if(a&1){
        itx = b-1;
        ity = 0;
        up = true;
    }
    int tope = b;
    char ch = 'a';
    for(int i=0; i<n ;i++){
        scanf("%d", &num);
        for(int jo=0; jo<num ;jo++){
            v[itx][ity] = ch;
            if(up){
                itx--;
                if(itx < 0){
                    itx = 0;
                    ity++;
                    up = false;
                }
            }
            else{
                itx++;
                if(ity >= a) tope = d;
                if(itx >= tope){
                    itx = tope-1;
                    ity++;
                    up = true;
                }
            }
        }
        ch++;
    }
    printf("YESn");
    for(int i=0; i<v.size() ;i++)
        cout<<v[i]<<endl;
}

Codeforces Beta Round #59 Solution Problem C

This problem (Problem C) was solved by brute force, testing the number from 0123 to 9876 and ask if some number passes the test.
If you spend just a number then that is the answer.
If you spend more than one “Need more data”.
If none passes the test “Incorrect data”.

vector<string> va(10);
vector<int> vb(10), vc(10);
int n;

bool valid(string x){
    for(int i=0; i<n ;i++){
        int b = 0, c = 0;
        for(int j=0; j<4 ;j++)
            if(x[j] == va[i][j])
                b++;
        if(b != vb[i]) return false;
        for(int j=0; j<4 ;j++){
            for(int k=0; k<4 ;k++){
                if(j == k) continue;
                if(va[i][j] == x[k])
                    c++;
            }
        }
        if(c != vc[i]) return false;
    }
    return true;
}

int main(){
    int cnt = 0;
    scanf("%d", &n);
    for(int i=0; i<n ;i++)
        cin>> va[i] >> vb[i] >> vc[i];
    string sol;
    for(char i1='0'; i1<='9' ;i1++){
        for(char i2='0'; i2<='9' ;i2++){
            if(i1 == i2) continue;
            for(char i3='0'; i3<='9' ;i3++){
                if(i1 == i3 || i2 == i3) continue;
                for(char i4='0'; i4<='9' ;i4++){
                    if(i1 == i4 || i2 == i4 || i3 == i4) continue;
                    string act;
                    act.PB(i1);act.PB(i2);act.PB(i3);act.PB(i4);
                    if(valid(act)){
                        cnt++;
                        sol = act;
                    }
                }
            }
        }
    }
    if(cnt){
        if(cnt > 1) printf("Need more datan");
        else cout<<sol<<endl;
    }
    else printf("Incorrect datan");
}

Codeforces Beta Round #59 Solution Problem B

In this problem (Problem B) only had to simulate.
Exist levels 0, 1, 2, 3, 4, …., 100
For example in test input 1:

4 4
1 2 2 3

exist one soldier level 1, two soldiers level 2 and one soldier level 3

int main(){
    int n, k, aux, tot = 0;
    scanf("%d %d", &n, &k);
    vector<int> v(102, 0);
    for(int i=0; i<n ;i++){
        scanf("%d", &aux);
        v[aux]++;
    }
    bool fla = true;
    while(fla){
        fla = false;
        for(int i=k-1; i>0 ;i--){
            if(v[i]){
                v[i]--;
                v[i+1]++;
                fla = true;
            }
        }
        if(fla) tot++;
    }
    cout<<tot<<endl;
}

Codeforces Beta Round #59 Solution Problem A

This problem (Problem A) has O(n) time complexity.
Only has to accommodate each string in its corresponding row.

Row[0] = "rat"
Row[1] = "woman" and "child"
Row[2] = "man"
Row[3] = "captain"

This is my code.

int main(){
    string a, b;
    int n;
    scanf("%d", &n);
    vector<vector<string> > v(4);
    for(int i=0; i<n ;i++){
        cin>>a>>b;
        if("rat" == b) v[0].PB(a);
        if("woman" == b) v[1].PB(a);
        if("child" == b) v[1].PB(a);
        if("man" == b) v[2].PB(a);
        if("captain" == b) v[3].PB(a);
    }
    for(int i=0; i<v.size() ;i++)
        for(int j=0; j<v[i].size() ;j++)
            cout<<v[i][j]<<endl;
}

Codeforces Beta Round #56

A. Where Are My Flakes?

In this problem only you have obtain the “maximum right” parameter and the “minimum left” parameter.
Example:
n = 9
initial

right = 0 and left = n+1 = 9+1 = 10

Always the solution is (left-right-1)

0  1  2  3  4  5  6  7  8  9  10
^right                        ^left  now the solution is (10-0-1) = 9
if insert "To the left of 7"
0  1  2  3  4  5  6  7  8  9  10
^right               ^left           now the solution is (7-0-1) = 6
if insert "To the right of 2"
0  1  2  3  4  5  6  7  8  9  10
      ^right         ^left           now the solution is (7-2-1) = 4
if insert "To the right of 6"
0  1  2  3  4  5  6  7  8  9  10
             right^  ^left           now the solution is (7-6-1) but 0 => -1

This is my code.

int main(){
    int n, m, aux;
    scanf("%d %d", &n, &m);
    int a = 0, b = n+1;
    string ch, pp;
    for(int i=0; i<m ;i++){
        cin>>pp>>pp>>ch>>pp>>aux;
        if(ch[0] == 'l') b = min(b, aux);
        else a = max(a, aux);
    }
    if(a+1 >= b) printf("-1n");
    else printf("%dn", b-a-1);
}

 

B. Serial Time!

This problem was a Tridimensional “Flood Fill” problem and my code is next.

struct ST{
    int x, y, z;
    ST(int a=0, int b=0, int c=0):x(a),y(b),z(c){}
};

int main(){
    int k, n, m, x, y;
    scanf("%d %d %d", &k, &n, &m);
    vector<vector<string> > v(k, vector(n));
    for(int i=0;i<k;i++)
        for(int j=0;j<n;j++)
            cin>>v[i][j];
    scanf("%d %d", &x, &y);
    queue<ST> q;
    q.push(ST(0, x-1, y-1));
    int tot = 0;
    while(!q.empty()){
        ST aux = q.front();
        q.pop();
        if(aux.x < 0 || aux.x >= k) continue;
        if(aux.y < 0 || aux.y >= n) continue;
        if(aux.z < 0 || aux.z >= m) continue;
        if(v[aux.x][aux.y][aux.z] == '.'){
            tot++;
            v[aux.x][aux.y][aux.z] = '$';
            q.push(ST(aux.x-1, aux.y, aux.z));
            q.push(ST(aux.x, aux.y-1, aux.z));
            q.push(ST(aux.x, aux.y, aux.z-1));
            q.push(ST(aux.x+1, aux.y, aux.z));
            q.push(ST(aux.x, aux.y+1, aux.z));
            q.push(ST(aux.x, aux.y, aux.z+1));
        }
    }
    printf("%dn", tot);
}

Codeforces Beta Round #55 – Problem C

Here is the solution for the Problem C
First: change all the obvious question marks, ej:

a ? ? ? b ?
a b ? ? b a
1 2 3 3 2 1 the 3 have multiple solutions

Second: fill all marks with multiple solution from the center outward with the maximal unused letter. ej:

4
c ? ? ? ? ? ? ? ? c
        whit 'd' = 'a'+4-1
c ? ? ? d d ? ? ? c
      with 'b' because 'c' was used
c ? ? b d d b ? ? c
    whit 'a'
c ? a b d d b a ? c
  with 'a' because is the small letter available
c a a b d d b a a c this is the solution.

Here is my implementation in c++

string solve(int k, string s){
    char limit = 'a'+k-1;
    vector<bool> v(k);
    int i = 0, j = s.S-1, kk = k;
    while(i <= j){
        if(s[i] == '?'){
            if(s[j] != '?'){
                if(s[j] > limit) return "IMPOSSIBLE";
                s[i] = s[j];
                v[s[i]-'a'] = true;
            }
        }
        else{
            if(s[j] == '?'){
                if(s[i] > limit) return "IMPOSSIBLE";
                s[j] = s[i];
                v[s[i]-'a'] = true;
            }
            else{
                if(s[i] != s[j]) return "IMPOSSIBLE";
                if(s[i] > limit) return "IMPOSSIBLE";
                v[s[i]-'a'] = true;
            }
        }
        i++;j--;
    }
    i = j = s.size()/2;
    if(!(s.size()&1)) i--;
    k--;
    while(i >= 0){
        if(s[i] == '?'){
            while(v[k] && k > 0) k--;
            s[i] = s[j] = k+'a';
            v[k] = true;
        }
        i--;j++;
    }
    for(int i=0; i<kk ;i++) if(!v[i]) return "IMPOSSIBLE";
    return s;
}

int main() {
    int k;
    string s;
    cin>>k>>s;
    cout<<solve(k, s)<<endl;
}