Codeforces Round #186 (Div. 2)

Problem A. Ilya and Bank Account

In order to solve this problems I have created an Array ‘v’ of digits. With this Array ‘v’ is possible to create the values ‘a’ (doesn’t use v[v.size()-1]) and ‘b’ (doesn’t use v[v.size()-2]). The solution is the maximum value of both. Sigue leyendo

Codeforces Beta Round #67 (Div. 2) Problem D

Link: D. Big Maximum Sum

This is my solution.

typedef long long LL;

int n, v[5010];

struct FOUR{
    LL m, l, r, t;
} T[20010], DP[55];

void crear(int a, int b, int it){
    if(a == b){
        T[it].m = T[it].l = T[it].r = T[it].t = v[a];
        return;
    }
    int mid = (a+b)>>1, left = it<<1, right = left+1;
    crear(a, mid, left);
    crear(mid+1, b, right);
    T[it].t = T[left].t + T[right].t;
    T[it].m = max(max(T[left].m, T[right].m), T[left].r+T[right].l);
    T[it].l = max(max(T[left].l, T[left].t+T[right].l), T[left].t);
    T[it].r = max(max(T[right].r, T[left].r+T[right].t), T[right].t);
}

FOUR unionFour(FOUR auxL, int j){
    FOUR auxR = DP[j], r;
    r.t = auxL.t + auxR.t;
    r.m = max(max(auxL.m, auxR.m), auxL.r+auxR.l);
    r.l = max(max(auxL.l, auxL.t+auxR.l), auxL.t);
    r.r = max(max(auxR.r, auxL.r+auxR.t), auxR.t);
    return r;
}

int main(){
    int m, l, a, ind;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n ;i++){
        scanf("%d", &l);
        for(int j=1; j<=l ;j++)
            scanf("%d", &v[j]);
        crear(1, l, 1);
        DP[i] = T[1];
    }
    scanf("%d", &ind);
    FOUR fr = DP[ind-1];
    for(int i=1; i<m ;i++){
        scanf("%d", &ind);
        fr = unionFour(fr, ind-1);
    }
    cout<< max(max(fr.t, fr.m),max(fr.l, fr.r)) <<endl;
}

Codeforces Beta Round #67 (Div. 2) Problem C

Link: C. Modified GCD

This is my solution.

int main(){
    int a, b, n, x, y;
    scanf("%d %d %d", &a, &b, &n);
    int d = __gcd(a, b);
    set<int> v;
    v.insert(d);
    for(int i=1; i <= sqrt(d) ;i++){
        if(d%i == 0){
            v.insert(i);
            v.insert(d/i);
        }
    }
    vector<int> val(v.begin(), v.end());
    for(int i=0; i<n ;i++){
        scanf("%d %d", &x, &y);
        a = 0, b = val.size()-1;
        while(a != b){
            int mid = ((a+b)/2)+1;
            if(val[mid] > y) b = mid-1;
            else a = mid;
        }
        int r=-1;
        if(a+1 < val.size()){
            if(val[a+1] <= y && val[a+1] >= x)
                r = val[a+1];
        }
        if(val[a] <= y && val[a] >= x)
            r = max(val[a], r);
        if(a-1 >= 0){
            if(val[a-1] <= y && val[a-1] >= x)
                r = max(r, val[a-1]);
        }
        printf("%dn", r);
    }
}

Codeforces Beta Round #67 (Div. 2) Problem B

Link: B. Facetook Priority Wall

This is my solution.

bool comp(const pair<int, string>&a, const pair<int, string>&b){
    if(a.first != b.first) return a.first > b.first;
    return a.second < b.second;
}

int main(){
    int n = 0;
    string s, ch;
    getline(cin, s, 'n');
    getline(cin, ch, 'n');
    for(int i=0; i<ch.size() ;i++)
        n=n*10+ch[i]-'0';
    map<string, int> mapa;
    for(int i=0; i<n ;i++){
        getline(cin, ch, 'n');
        stringstream ss(ch);
        vector<string> v;
        while(ss>>ch) v.push_back(ch);
        if(mapa.find(v[0]) == mapa.end())
            mapa[v[0]] = 0;
        if(v.size() == 4){
            string auxs = v[2].substr(0, v[2].size()-2);
            if(mapa.find(auxs) == mapa.end())
                mapa[auxs] = 0;
            if(auxs == s || v[0] == s)
                mapa[v[0]] += 5, mapa[auxs] += 5;
        }
        else{
            string auxs = v[3].substr(0, v[3].size()-2);
            if(mapa.find(auxs) == mapa.end())
                mapa[auxs] = 0;
            if(auxs == s || v[0] == s){
                if(v[4] == "wall")
                    mapa[v[0]] += 15, mapa[auxs] += 15;
                else
                    mapa[v[0]] += 10, mapa[auxs] += 10;
            }
        }
    }
    vector<pair<int, string> > conj;
    for(map<string, int>::iterator it = mapa.begin(); it!=mapa.end() ;it++)
        if(it->first != s)
            conj.PB(MP(it->second, it->first));
    sort(conj.begin(), conj.end(), comp);
    for(int i=0; i<conj.size() ;i++)
        cout<<conj[i].second<<endl;
}

Codeforces Beta Round #67 (Div. 2) Problem A

Link: A. Life Without Zeros

In this problem, had to create a function to remove zeros, like this:

int removeZeros(int n){
    int r = 0, ten = 1;
    while(n){
        if(n%10){
            r += (n%10)*ten;
            ten *= 10;
        }
        n /= 10;
    }
    return r;
}

Below is my solution.

int removeZeros(int n){
    int r = 0, ten = 1;
    while(n){
        if(n%10){
            r = r + (n%10)*ten;
            ten *= 10;
        }
        n /= 10;
    }
    return r;
}

int main(){
    int n, m;
    cin>>n>>m;
    if(removec(n+m) == removec(n)+removec(m)) printf("YESn");
    else printf("NOn");
}

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");
}