AtCoder 184

A - Determinant

determinant.cppview raw

#include <iostream>
using namespace std;

int main(){
    int a, b, c, d;
    cin>>a>>b>>c>>d;
    cout<< a*d - b * c<<endl;
    return 0;
}

B - Quizzes
Return the number of points he gets given a string.

quizzes.cppview raw

#include <iostream>
#include <string>
using namespace std;

int main(){
    int n, x;
    string s;
    cin>>n>>x;
    cin>>s;
    for(auto c: s){
        if(c=='o') x +=1;
        else x = max(0, x-1);
    }
    cout<<x<<endl;
    return 0;
}

C - Super Ryuma
Minimum number of steps reaching from (r1, c1) to (r2, c2), using 3 ways.

super-ryuma.cppview raw

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int r1, c1, r2, c2;
    cin>>r1>>c1>>r2>>c2;
    bool flag = false;
    if(r1==r2 && c1==c2) cout<<0<<endl;
    else if(r1-c1==r2-c2 || r1+c1==r2+c2 || abs(r1-r2) + abs(c1-c2)<=3) cout<<1<<endl;
    else if((r1 + c1 + r2 - c2)%2==0) cout<<2<<endl;
    else{
        for(int i=-3;i<=3;i++)
            for(int j=-3;j<=3;j++){
                if(abs(i) + abs(j) > 3) continue;
                int r = r1 + i, c = c1 + j;
                if(r-c==r2-c2 || r+c == r2 + c2 || abs(r-r2) + abs(c -c2) <=3){
                    cout<<2<<endl;
                    return 0;
                }
            }
        cout<<3<<endl;
    }
    return 0;
}

D - increment of coins
Given A, B, C coins, return the expected number of operations to reach 100 points in bag.

incre-coins.cppview raw

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 100;
double ret[maxn][maxn][maxn];

double dfs(vector<int>&coins){
    if(coins[1]==0) return 100.0 - coins[0];
    if(coins[0]==100 || coins[1] ==100 || coins[2]==100) return 0.0;
    double &ans = ret[coins[0]][coins[1]][coins[2]];
    if(ans>=0) return ans;
    int s = 0;
    for(auto c: coins) s += c;
    double res = 0;
    for(int i=0;i<3;i++){
        vector<int>nxt(coins);
        nxt[i] ++;
        res += (double)coins[i] / s * (1+dfs(nxt));
    }
    return ans = res;
}

int main(){
    vector<int> coins(3);
    for(int i=0;i<3;i++) cin>>coins[i];
    sort(coins.rbegin(), coins.rend());
    memset(ret, -1, sizeof ret);
    printf("%.12f\n", dfs(coins));
    return 0;
}

E - Third Avenue
Given 2-dim grids, return the minimum number of steps from start to goal.
An additional way of teleport is abled.

third-avenue.cppview raw

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

const int N = 2010, INF = 0x3f3f3f3f;
char g[N][N];
int dis[N][N];
int n, m;

typedef pair<int,int> PII;
#define x first
#define y second

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int si, sj, ei, ej;
vector<PII> tele[26];
vector<bool> used(26);


int bfs(){
    queue<PII> q;
    q.push({si, sj});
    dis[si][sj] = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        if(t.x == ei && t.y == ej) return dis[t.x][t.y];
        for(int i=0;i<4;i++){
            int mx = t.x + dx[i], my = t.y + dy[i];
            if(mx<0 || mx >=n || my<0 || my>=m || dis[mx][my]!=INF || g[mx][my]=='#') continue;
            dis[mx][my] = dis[t.x][t.y] + 1;
            q.push({mx, my});
        }

        if(g[t.x][t.y]>='a' && g[t.x][t.y]<='z' && !used[g[t.x][t.y] - 'a']){
            used[g[t.x][t.y] - 'a'] = true;
            for(auto [x, y]: tele[g[t.x][t.y] - 'a']){
                if(dis[x][y]==INF){
                    dis[x][y] = dis[t.x][t.y] + 1;
                    q.push({x, y});
                }
            }
        }
    }
    return INF;
}

int main(){
    cin>>n>>m;
    memset(dis, 0x3f, sizeof dis);
    for(int i=0;i<n;i++) {
        scanf("%s", g[i]);
        for(int j=0;j<m;j++){
            if(g[i][j]=='S') si = i, sj = j;
            else if(g[i][j]=='G') ei = i, ej = j;
            else if(g[i][j]>='a' && g[i][j]<='z') tele[g[i][j]-'a'].push_back({i, j});
        }
    }

    int res = bfs();
    if(res==INF) cout<<-1<<endl;
    else cout<<res<<endl;
    return 0;
}

F - Programming Contest
Maximum number of problems that can be solved with maximum T minutes.
This is a typical backpacking problem, but the maximum volume is too large.
Should use meet-in-the-middle to solve.

program-contest.cppview raw

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

const int N = 45;
int a[N];

int main(){
    int n, m;
    cin>>n>>m;
    set<int> L, R;
    L.insert(0), R.insert(0);
    for(int i=0;i<n;i++) cin>>a[i];
    int l = n/2, r = n - l;
    for(int i=0;i<(1<<l);i++){
        int s = 0;
        for(int j=0;j<l;j++){
            if(i&(1<<j)){
                s += a[j];
                if(s>m) break;
            }
        }
        if(s<=m) L.insert(s);
    }

    for(int i=0;i<(1<<r);i++){
        int s = 0;
        for(int j=0;j<r;j++){
            if(i&(1<<j)){
                s += a[l + j];
                if(s>m) break;
            }
        }
        if(s<=m) R.insert(s);
    }

    int res = 0;
    for(int l: L){
        auto it = R.lower_bound(m+1-l);
        if(it!=R.begin())
            it--;
        if(l + * it <=m) res = max(res, l + *it);
        if(res==m) break;
    }
    cout<<res<<endl;
    return 0;
}