ACM ICPC Latin America 2011 – I – In Braille

/* 
 * @author: vudduu - Edwin Guzman
 * @problem: Problem I - In Braille
 * @contest: ACM ICPC Latin America Regional 2011
 */
#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

string s1[] = {".*", "*.", "*.", "**", "**", "*.", "**", "**", "*.", ".*"};
string s2[] = {"**", "..", "*.", "..", ".*", ".*", "*.", "**", "**", "*."};

char ch[305];
char num[105];
char s[3][305];

int it;

void lee(int & n){
   it = n = 0;
   gets(ch);
   while(ch[it]) n = n*10 + ch[it++]-'0';
}

int main(){
   int n;
   lee(n);
   while(n){
      gets(ch);
      it = 0;
      if(ch[0] == 'S'){
         gets(num);
         for(int i=0; i<n ;i++){
            if(i) s[0][it] = ' ', s[1][it] = ' ', s[2][it++] = ' ';
            char numaux = num[i]-'0';
            s[0][it] = s1[ numaux ][0];
            s[1][it] = s2[ numaux ][0];
            s[2][it++] = '.';
            s[0][it] = s1[ numaux ][1];
            s[1][it] = s2[ numaux ][1];
            s[2][it++] = '.';
         }
         s[0][it] = s[1][it] = s[2][it] = 0;
         puts(s[0]);
         puts(s[1]);
         puts(s[2]);
      }
      else{
         for(int i=0; i<3 ;i++)
            gets(s[i]);
         for(int i=0; i<n ;i++){
            int it1 = i*3, j;
            for(j=0; j<10 ;j++){
               if(s[0][it1] == s1[j][0]) if(s[0][it1+1] == s1[j][1])
                  if(s[1][it1] == s2[j][0]) if(s[1][it1+1] == s2[j][1])
                     break;
            }
            num[it++] = j+'0';
         }
         num[it] = 0;
         puts(num);
      }
      lee(n);
   }
}

ACM ICPC Latin America 2011 – K – King’s Poker

/* 
 * @author: vudduu - Edwin Guzman
 * @problem: Problem K - King's Poker
 * @contest: ACM ICPC Latin America Regional 2011
 */
#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

int it;
char ch[30];

int main(){
  int v[3];
  scanf("%d %d %d", &v[0], &v[1], &v[2]);
  while(v[0]){
    sort(v, v+3);
    if(v[0] == v[1] && v[0] == v[2]){
      if(v[0] == 13) printf("*n");
      else printf("%d %d %dn", v[0]+1, v[0]+1, v[0]+1);
    }
    else if(v[0] == v[1]){
      if(v[2] == 13) printf("1 %d %dn", v[0]+1, v[0]+1);
      else printf("%d %d %dn", v[0], v[0], v[2]+1);
    }
    else if(v[1] == v[2]){
      if(v[0] == v[1]-1){
        if(v[1] == 13) printf("1 1 1n");
        else printf("%d %d %dn", v[2], v[2], v[0]+2);
      }
      else printf("%d %d %dn", v[0]+1, v[2], v[2]);
    }
    else printf("1 1 2n");
    scanf("%d %d %d", &v[0], &v[1], &v[2]);
  }
}

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

TopCoder SRM 498 – DIV 1 Level 1

This problem is more simple but the implementation should be carefully.

Solution O(n):
1) get the first ascending sequence
2) get the first descending sequence
3) get the number with no difference
4) get the second ascending sequence
5) get the second ascending sequence

class FoxSequence{
    public:
    string isValid(vector<int> seq) {
        int n = seq.S;
        if(n < 5) return "NO";
//1) get the first ascending sequence
        int dif = seq[1]-seq[0], it = 1;
        if(dif<=0) return "NO";
        while(it<n-3 && seq[it]-seq[it-1] == dif) it++;
//2) get the first descending sequence
        dif = seq[it]-seq[it-1];
        if(dif>=0) return "NO";
        while(it<n-2 && seq[it]-seq[it-1] == dif) it++;
//3) get the number with no difference
        while(it<n-2 && seq[it] == seq[it-1]) it++;
//4) get the second ascending sequence
        dif = seq[it]-seq[it-1];
        if(dif<=0) return "NO";
        while(it<n-1 && seq[it]-seq[it-1] == dif) it++;
//5) get the second ascending sequence
        dif = seq[it]-seq[it-1];
        if(dif>=0) return "NO";
        while(it<n && seq[it]-seq[it-1] == dif) it++;
        if(it != n) return "NO";
        return "YES";
    }
};

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