ProgrammingContestChallengeBook-白红宇

ProgrammingContestChallengeBook

阅读量：6428 次

发布时间：2019-06-23

本文共 95738 字，大约阅读时间需要 319 分钟。

Ants

#include 
    
     #include 
     
      using namespace std;int main(){    int t;    scanf("%d", &t);    while(t--){        int l, n;        scanf("%d %d", &l, &n);        int ansmin = 0, ansmax = 0;        while(n--){            int pos;            scanf("%d", &pos);            ansmin = max(ansmin, min(pos, l - pos));            ansmax = max(ansmax, max(pos, l - pos));        }        printf("%d %d\n", ansmin, ansmax);    }    return 0;}

Lake Counting

#include 
    
     using namespace std;const int N = 111;char maze[N][N];int n, m, ans;void dfs(int x, int y){    maze[x][y] = '.';    for(int cx = -1; cx <= 1; ++cx)        for(int cy = -1; cy <= 1; ++cy){            int nx = x + cx, ny = y + cy;            if(0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] == 'W')                dfs(nx, ny);        }}int main(){    while(cin >> n >> m){        for(int i = 0; i < n; ++i)            for(int j = 0; j < m; ++j)                cin >> maze[i][j];        ans = 0;        for(int i = 0; i < n; ++i)            for(int j = 0; j < m; ++j)                if(maze[i][j] == 'W'){                    ++ans;                    dfs(i, j);                }        cout << ans << endl;    }    return 0;}

Red and Black

#include 
    
     using namespace std;const int N = 22;int w, h, ans, sx, sy;char maze[N][N];const int cx[] = {1, -1, 0, 0}, cy[] = {0, 0, 1, -1};void dfs(int x, int y){    ++ans;    maze[x][y] = '#';    for(int i = 0; i < 4; ++i){        int nx = x + cx[i], ny = y + cy[i];        if(0 <= nx && nx < h && 0 <= ny && ny < w && maze[nx][ny] == '.')            dfs(nx, ny);    }}int main(){    while(cin >> w >> h, (w && h)){        for(int i = 0; i < h; ++i)            for(int j = 0; j < w; ++j){                cin >> maze[i][j];                if(maze[i][j] == '@'){                    sx = i; sy = j;                    maze[sx][sy] = '.';                }            }        ans = 0;        dfs(sx, sy);        cout << ans << endl;    }    return 0;}

Property Distribution

#include 
    
     using namespace std;const int N = 111;int w, h, ans;char ch, maze[N][N];const int cx[] = {1, -1, 0, 0}, cy[] = {0, 0, 1, -1};void dfs(int x, int y){    maze[x][y] = '-';    for(int i = 0; i < 4; ++i){        int nx = x + cx[i], ny = y + cy[i];        if(0 <= nx && nx < h && 0 <= ny && ny < w && maze[nx][ny] == ch)            dfs(nx, ny);    }}int main(){    while(cin >> h >> w, (h && w)){        for(int i = 0; i < h; ++i)            for(int j = 0; j < w; ++j)                cin >> maze[i][j];        ans = 0;        for(int i = 0; i < h; ++i)            for(int j = 0; j < w; ++j){                if(maze[i][j] != '-'){                    ch = maze[i][j];                    ++ans;                    dfs(i, j);                }            }        cout << ans << endl;    }    return 0;}

Ball

#include 
    
     #include 
     
      using namespace std;int ball[11];bool flag;bool dfs(int index, int left, int right){    if(index == 10) return true;    if(ball[index] > left && dfs(index + 1, ball[index], right)) return true;    if(ball[index] > right && dfs(index + 1, left, ball[index])) return true;    return false;}int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n;    int left = 0, right = 0;    cin >> n;    while(n--){        for(int i = 0; i < 10; ++i) cin >> ball[i];        flag = dfs(0, 0, 0);        cout << (flag ? "YES" : "NO") << endl;    }    return 0;}

Curling 2.0

#include 
    
     #include 
     
      using namespace std;const int N = 22;const int cx[] = {1, -1, 0, 0}, cy[] = {0, 0, 1, -1};int w, h, ans, sx, sy, ex, ey;int maze[N][N];void dfs(int px, int py, int step){    if(step > 10) return ;    for(int i = 0; i < 4; ++i){        int nx = px + cx[i], ny = py + cy[i];        if(nx == ex && ny == ey){            ans = min(ans, step + 1);            continue;        }        if(nx < 0 || h <= nx || ny < 0 || w <= ny || maze[nx][ny] == 1) continue;        while(true){            nx += cx[i], ny += cy[i];            if(nx < 0 || h <= nx || ny < 0 || w <= ny) break;            if(!maze[nx][ny]) continue;            if(nx == ex && ny == ey){                ans = min(ans, step + 1);                return ;            }            maze[nx][ny] = 0;            dfs(nx - cx[i], ny - cy[i], step + 1);            maze[nx][ny] = 1;            break;        }    }}int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    while(cin >> w >> h, (w && h)){        for(int i = 0; i < h; ++i)            for(int j = 0; j < w; ++j){                cin >> maze[i][j];                if(maze[i][j] == 2){                    sx = i;                    sy = j;                    maze[i][j] = 0;                }                if(maze[i][j] == 3){                    ex = i;                    ey = j;                    maze[i][j] = 1;                }            }        ans = 0x3f3f3f3f;        dfs(sx, sy, 0);        cout << (ans > 10 ? -1 : ans) << endl;    }    return 0;}

Cheese

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 1111;const int cx[] = {0, 0, 1, -1}, cy[] = {1, -1, 0, 0};char maze[N][N];int step[N][N];int h, w, n, sx, sy, ans;int bfs(int cheese){    memset(step, -1, sizeof(step));    queue
       
        
          > que;    que.push(make_pair(sx, sy));    step[sx][sy] = 0;    while(!que.empty()){        int x = que.front().first, y = que.front().second;        que.pop();        for(int i = 0; i < 4; ++i){            int nx = x + cx[i], ny = y + cy[i];            if(nx < 0 || h <= nx || ny < 0 || w <= ny || maze[nx][ny] == 'X' || step[nx][ny] != -1) continue;            step[nx][ny] = step[x][y] + 1;            if(maze[nx][ny] - '0' == cheese){                sx = nx;                sy = ny;                return step[nx][ny];            }            que.push(make_pair(nx, ny));        }    }    return 0;}int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    while(cin >> h >> w >> n){        for(int i = 0; i < h; ++i)            for(int j = 0; j < w; ++j){                cin >> maze[i][j];                if(maze[i][j] == 'S'){                    sx = i;                    sy = j;                }            }        ans = 0;        for(int i = 1; i <= n; ++i)            ans += bfs(i);        cout << ans << endl;    }    return 0;}

Meteor Shower

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 1111;const int cx[] = {1, -1, 0, 0}, cy[] = {0, 0, 1, -1};int maze[N][N], step[N][N];int n, sx, sy;int bfs(){    queue
       
        
          > que;    que.push(make_pair(0, 0));    while(!que.empty()){        int x = que.front().first, y = que.front().second;        que.pop();        if(step[x][y] >= maze[x][y]) continue;        if(maze[x][y] == 0x3f3f3f3f) return step[x][y];        for(int i = 0; i < 4; ++i){            int nx = x + cx[i], ny = y + cy[i];            if(nx < 0 || ny < 0 || step[nx][ny] != -1) continue;            que.push(make_pair(nx, ny));            step[nx][ny] = step[x][y] + 1;        }    }    return -1;}int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    while(cin >> n){        memset(maze, 0x3f, sizeof(maze));        while(n--){            int x, y, t;            cin >> x >> y >> t;            maze[x][y] = min(maze[x][y], t);            for(int i = 0; i < 4; ++i){                int nx = x + cx[i], ny = y + cy[i];                if(nx < 0 || ny < 0) continue;                maze[nx][ny] = min(maze[nx][ny], t);            }        }        memset(step, -1, sizeof(step));        step[0][0] = 0;        cout << bfs() << endl;    }    return 0;}

Seven Puzzle

#include #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int cd[] = {-1, 1, 4, -4};map
         
           dp;void dfs(){ dp["01234567"] = 0; queue
          
            que; que.push("01234567"); while(!que.empty()){ string str = que.front(); que.pop(); int zpos = 0; for(int i = 0; str[i]; ++i) if(str[i] == '0'){ zpos = i; break; } for(int i = 0; i < 4; ++i){ int npos = zpos + cd[i]; if(npos < 0 || 7 < npos || (zpos == 3 && cd[i] == 1) || (zpos == 4 && cd[i] == -1)) continue; string nstr = str; swap(nstr[zpos], nstr[npos]); if(dp.find(nstr) == dp.end()){ dp[nstr] = dp[str] + 1; que.push(nstr); } } }}int main(){ ios::sync_with_stdio(false); cin.tie(NULL); dfs(); string str; while(getline(cin, str)){ str.erase(remove(str.begin(), str.end(), ' '), str.end()); cout << dp[str] << endl; } return 0;}

Smallest Difference

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int t;    cin >> t;    cin.ignore();    while(t--){        string str;        getline(cin, str);        str.erase(remove(str.begin(), str.end(), ' '), str.end());        sort(str.begin(), str.end());        int mid = str.size() >> 1;        int ans = 0x3f3f3f3f;        do{            if(str.size() > 2 && (str[0] == '0' || str[mid] == '0')) continue;            int fnum = 0, anum = 0;            for(int i = 0; i < mid; ++i) fnum = fnum * 10 + str[i] - '0';            for(int i = mid; i < str.size(); ++i) anum = anum * 10 + str[i] - '0';            ans = min(ans, abs(fnum - anum));        }while(next_permutation(str.begin(), str.end()));        cout << ans << endl;    }    return 0;}

Backward Digit Sums

#include 
    
     #include 
     
      using namespace std;int PT[11][11]; // Pascal's Triangleint seq[11];void init(){    PT[0][0] = 1;    for(int i = 1; i < 11; ++i){        PT[i][0] = 1;        for(int j = 1; j < i; ++j)            PT[i][j] = PT[i-1][j] + PT[i-1][j-1];        PT[i][i] = 1;    }}int main(){    init();    ios::sync_with_stdio(false);    cin.tie(NULL);    int n, sum;    while(cin >> n >> sum){        for(int i = 1; i <= n; ++i) seq[i - 1] = i;        do{            long long tmp = 0;            for(int i = 0; i < n; ++i)                tmp += seq[i] * PT[n-1][i];            if(tmp == sum){                for(int i = 0; i < n; ++i){                    if(i) cout << " ";                    cout << seq[i];                }                cout << endl;                break;            }        }while(next_permutation(seq, seq + n));    }    return 0;}

Hopscotch

#include 
    
     #include 
     
      using namespace std;int grid[5][5];set
      
        ans;const int cx[] = {1, -1, 0, 0}, cy[] = {0, 0, 1, -1};void dfs(int px, int py, int step, int sum){    if(step == 5){        ans.insert(sum);        return ;    }    for(int i = 0; i < 4; ++i){        int nx = px + cx[i], ny = py + cy[i];        if(nx < 0 || 4 < nx || ny < 0 || 4 < ny) continue;        dfs(nx, ny, step + 1, sum * 10 + grid[nx][ny]);    }}int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    for(int i = 0; i < 5; ++i)        for(int j = 0; j < 5; ++j)            cin >> grid[i][j];    for(int i = 0; i < 5; ++i)        for(int j = 0; j < 5; ++j)            dfs(i, j, 0, grid[i][j]);    cout << ans.size() << endl;    return 0;}

Osenbei

#include 
    
     #include 
     
      using namespace std;bitset<10000> maze[10];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int r, c;    while(cin >> r >> c, (r && c)){        for(int i = 0; i < r; ++i)            for(int j = 0; j < c; ++j){                bool tmp;                cin >> tmp;                maze[i][j] = tmp;            }        int time = 1 << r;        int ans = 0;        for(int i = 0; i < time; ++i){            for(int j = 0; j < r; ++j)                if(i & (1 << j))                    maze[j].flip();                        int result = 0;            for(int C = 0; C < c; ++C){                int cntpercol = 0;                for(int R = 0; R < r; ++R)                    if(maze[R][C])                        ++cntpercol;                result += max(cntpercol, r - cntpercol);            }            ans = max(ans, result);                        for(int j = 0; j < r; ++j)                if(i & (1 << j))                    maze[j].flip();        }        cout << ans << endl;    }    return 0;}

Best Cow Line

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    string s = "";    int n;    while(cin >> n){        cin.ignore();        for(int i = 0; i < n; ++i){            char ch;            cin >> ch;            s += ch;        }        string ans = "";        for(int i = 0; i < n; ++i){            string tmp = s;            reverse(tmp.begin(), tmp.end());            if(s < tmp){                ans += s[0];                s = s.substr(1);            }            else{                ans += s[s.size() - 1];                s.erase(s.end()-1, s.end());            }        }        int cnt = 0;        for(int i = 0; i < n; ++i){            if(cnt == 80){                cout << endl;                cnt = 0;            }            cout << ans[i];            ++cnt;        }        cout << endl;    }    return 0;}

Saruman's Army

#include 
    
     #include 
     
      #include 
      
       using namespace std;vector
       
         arr;int r, n;int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int r, n;    while(cin >> r >> n, ~r){        arr.clear();        for(int i = 0; i < n; ++i){            int tmp;            cin >> tmp;            arr.push_back(tmp);        }        sort(arr.begin(), arr.end());        arr.erase(unique(arr.begin(), arr.end()), arr.end());        int ans = 0;        for(vector
        
         ::iterator i = arr.begin(); i != arr.end(); ){            i = upper_bound(i, arr.end(), *i + r) - 1;            ++ans;            i = upper_bound(i, arr.end(), *i + r);        }        cout << ans << endl;    }    return 0;}

Fence Repair

#include 
    
     #include 
     
      using namespace std;typedef long long ll;int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    priority_queue
      
       , greater
       
         > q;    int n;    while(cin >> n){        while(!q.empty()) q.pop();        for(int i = 0; i < n; ++i){            ll tmp;            cin >> tmp;            q.push(tmp);        }        ll ans = 0;        while(q.size() > 1){            ll t = q.top();            q.pop();            t += q.top();            q.pop();            q.push(t);            ans += t;        }        cout << ans << endl;    }    return 0;}

Cleaning Shifts

#include 
    
     #include 
     
      using namespace std;const int N = 25252;struct cow{    int begin, ending;};cow p[N];int n, t, ans, begintime, endtime;bool cmp(cow a, cow b){ return a.begin == b.begin ? a.ending < b.ending : a.begin < b.begin; }int main(){    while(cin >> n >> t){        for(int i = 0; i < n; ++i) cin >> p[i].begin >> p[i].ending;        sort(p, p + n, cmp);        if(p[0].begin > 1){            cout << -1 << endl;            continue;        }        ans = begintime = endtime = 1;        for(int i = 0; i < n; ++i){            if(p[i].begin <= begintime) endtime = max(endtime, p[i].ending);            else{                ++ans;                begintime = endtime + 1;                if(p[i].begin <= begintime) endtime = max(endtime, p[i].ending);                else{                    ans = -1;                    break;                }            }            if(endtime >= t) break;        }        if(endtime < t) ans = -1;        cout << ans << endl;    }    return 0;}

Radar Installation

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 1111;struct coordinate{ double x, y; };struct interval{ double begin, ending; };coordinate island[N];interval cover[N];bool cmp(interval a, interval b){ return a.begin < b.begin; }int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n, d, t = 1;    while(cin >> n >> d, n && d){        cout << "Case " << t++ << ": ";        bool flag = true;        for(int i = 0; i < n; ++i){            cin >> island[i].x >> island[i].y;            if(island[i].y > d) flag = false;        }        if(!flag) cout << -1 << endl;        else{            int ans = 0;            for(int i = 0; i < n; ++i){                double len = sqrt(d * d - island[i].y * island[i].y);                cover[i].begin = island[i].x - len;                cover[i].ending = island[i].x + len;            }            sort(cover, cover + n, cmp);            double pos = -numeric_limits
        
         ::max();            for(int i = 0; i < n; ++i){                if(pos < cover[i].begin){                    ++ans;                    pos = cover[i].ending;                }                else if(pos > cover[i].ending)                    pos = cover[i].ending;            }            cout << ans << endl;        }    }    return 0;}

Stall Reservations

#include 
    
     #include 
     
      #include 
      
       using namespace std;struct Cow{    int index;    int begin, ending;    bool operator< (const Cow& other) const {        return begin < other.begin;    }};struct Stall{    int id;    int ending;    bool operator< (const Stall& other) const {        return ending > other.ending;    }    Stall(){}    Stall(int _id, int _ending): id(_id), ending(_ending) {}};const int N = 55555;Cow cow[N];int result[N];priority_queue
       
         que;void put_cow(int i, bool new_stall){    Stall s;    if(new_stall) s.id = que.size() + 1;    else{        s.id = que.top().id;        que.pop();    }    result[cow[i].index] = s.id;    s.ending = cow[i].ending;    que.push(s);}int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n;    while(cin >> n){        while(!que.empty()) que.pop();        for(int i = 0; i < n; ++i){            cow[i].index = i;            cin >> cow[i].begin >> cow[i].ending;        }        sort(cow, cow+n);        put_cow(0, true);        for(int i = 1; i < n; ++i)            put_cow(i, cow[i].begin <= que.top().ending);        cout << que.size() << endl;        for(int i = 0; i < n; ++i) cout << result[i] << endl;    }    return 0;}

Yogurt Factory

#include 
    
     #include 
     
      using namespace std;int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n, scost;    while(cin >> n >> scost){        long long ans = 0;        int lowest = 0x3f3f3f3f;        while(n--){            int cost, puc;            cin >> cost >> puc;            lowest = min(lowest+scost, cost);            ans += lowest * puc;        }        cout << ans << endl;    }    return 0;}

Packets

#include 
    
     using namespace std;int puc[6];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    while(true){        bool flag = false;        for(int i = 0; i < 6; ++i){            cin >> puc[i];            if(puc[i]) flag = true;        }        if(!flag) break;        int ans = puc[5] + puc[4] + puc[3];        puc[0] = max(0, puc[0] - puc[4] * 11);        if(puc[1] > puc[3] * 5) puc[1] -= puc[3] * 5;        else puc[0] = max(0, puc[0] - puc[3] * 20 + puc[1] * 4), puc[1] = 0;        ans += (puc[2] + 3) / 4;        puc[2] %= 4;        if(puc[2]){            if(puc[1] >= 7 - 2 * puc[2]){                puc[1] -= 7 - 2 * puc[2];                puc[0] = max(0, puc[0] - (8 - puc[2]));            }            else{                puc[0] = max(0, puc[0] - (36 - 9 * puc[2] - 4 * puc[1]));                puc[1] = 0;            }        }        ans += (puc[1] + 8) / 9;        puc[1] %= 9;        if(puc[1]) puc[0] = max(0, puc[0] - (36 - 4 * puc[1]));        ans += (puc[0] + 35) / 36;        cout << ans << endl;    }    return 0;}

Allowance

#include 
    
     #include 
     
      #include 
      
       using namespace std;struct Coin{    int value, amount;    bool operator < (const Coin& other) const {        return value < other.value;    }};const int N = 22;int n, c;Coin coin[N];int need[N];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    while(cin >> n >> c){        for(int i = 0; i < n; ++i) cin >> coin[i].value >> coin[i].amount;        sort(coin, coin + n);        long long ans = 0;        for(int i = 0; i < n; ++i)            if(coin[i].value >= c){                ans += coin[i].amount;                coin[i].amount = 0;            }        while(true){            memset(need, 0, sizeof(need));            int l = c;            for(int i = n-1; ~i; --i){                need[i] = min(l / coin[i].value, coin[i].amount);                l -= coin[i].value * need[i];            }            if(l > 0){                for(int i = 0; i < n; ++i){                    if(coin[i].amount && coin[i].value >= l){                        ++need[i];                        l = 0;                        break;                    }                }            }            if(l > 0) break;            int tmp = 0x3f3f3f3f;            for(int i = 0; i < n; ++i)                if(need[i])                    tmp = min(tmp, coin[i].amount / need[i]);            ans += tmp;            for(int i = 0; i < n; ++i)                if(need[i])                    coin[i].amount -= need[i] * tmp;        }        cout << ans << endl;    }    return 0;}

Stripies

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    int n;    while(~scanf("%d", &n)){        priority_queue
       
         que;        while(n--){            double k;            scanf("%lf", &k);            que.push(k);        }        while(que.size() > 1){            double a1 = que.top(); que.pop();            double a2 = que.top(); que.pop();            que.push(2 * sqrt(a1 * a2));        }        printf("%.3f\n", que.top());        que.pop();    }    return 0;}

Protecting the Flowers

#include 
    
     #include 
     
      using namespace std;typedef long long ll;struct Cow{    ll distance, damage;    bool operator < (const Cow& other) const {        return distance * other.damage < other.distance * damage;    }};const int N = 111111;Cow cow[N];int n;int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    while(cin >> n){        ll total = 0;        for(int i = 0; i < n; ++i){            cin >> cow[i].distance >> cow[i].damage;            total += cow[i].damage;        }        sort(cow, cow + n);        ll ans = 0;        for(int i = 0; i < n; ++i){            total -= cow[i].damage;            ans += total * cow[i].distance * 2;        }        cout << ans << endl;    }    return 0;}

Cow Bowling

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 365;int origin[N][N], dp[N][N];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n;    while(cin >> n){        for(int i = 0; i < n; ++i)            for(int j = 0; j <= i; ++j)                cin >> origin[i][j];        memset(dp, 0, sizeof(dp));        dp[0][0] = origin[0][0];        for(int i = 0; i < n; ++i)            for(int j = 0; j <= i; ++j){                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + origin[i+1][j]);                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + origin[i+1][j+1]);            }        int ans = -1;        for(int i = 0; i < n; ++i) ans = max(ans, dp[n-1][i]);        cout << ans << endl;    }    return 0;}

Sumsets

#include 
    
     using namespace std;int dp[1111111] = {0, 1};int main(){    int n;    for(int i = 2; i < 1000001; ++i)        if(i & 1) dp[i] = dp[i-1];        else dp[i] = (dp[i-1] + dp[i>>1]) % 1000000000;    while(cin >> n) cout << dp[n] << endl;    return 0;}

Apple Catching

#include 
    
     #include 
     
      #include 
      
       using namespace std;int arr[1111];int dp[2][33][1111];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int t, w;    while(cin >> t >> w){        for(int i = 0; i < t; ++i){            int t;            cin >> t;            arr[i] = t - 1;        }        memset(dp, 0, sizeof(dp));        if(arr[0]) dp[1][1][0] = 1;        else dp[0][0][0] = 1;        for(int i = 0; i <= w; ++i)            for(int j = 0; j < t; ++j)                for(int k = 0; k < 2; ++k){                    dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j] + (k == arr[j+1]));                    dp[k^1][i+1][j+1] = max(dp[k^1][i+1][j+1], dp[k][i][j] + ((k^1) == arr[j+1]));                }        cout << max(*max_element(dp[0][w], dp[0][w]+t), *max_element(dp[1][w], dp[1][w]+t)) << endl;    }    return 0;}

Milking Time

#include 
    
     #include 
     
      using namespace std;struct interval{    int stime, etime, efficiency;    bool operator < (const interval& o) const {        return stime < o.stime;    }};const int N = 1111;int dp[N];interval p[N];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n, m, r;    while(cin >> n >> m >> r){        for(int i = 0; i < m; ++i){            cin >> p[i].stime >> p[i].etime >> p[i].efficiency;            p[i].etime += r;        }        sort(p, p + m);        for(int i = 0; i < m; ++i){            dp[i] = p[i].efficiency;            for(int j = 0; j < i; ++j){                if(p[i].stime >= p[j].etime)                    dp[i] = max(dp[i], dp[j] + p[i].efficiency);            }        }        cout << *max_element(dp, dp + m) << endl;    }    return 0;}

Cheapest Palindrome

#include 
    
     #include 
     
      using namespace std;const int N = 2222;int dp[N][N], cost[N];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n, m;    string s;    while(cin >> n >> m){        cin >> s;        for(int i = 0; i < n; ++i){            cin.ignore();            char ch;            int x, y;            cin >> ch >> x >> y;            cost[ch] = min(x, y);        }        for(int k = 1; k < m; ++k){            for(int i = 0, j = k; j < m; ++i, ++j){                dp[i][j] = 0x3f3f3f3f;                if(s[i] == s[j]) dp[i][j] = min(dp[i][j], dp[i+1][j-1]);                else dp[i][j] = min(dp[i][j], min(dp[i+1][j] + cost[s[i]], dp[i][j-1] + cost[s[j]]));            }        }        cout << dp[0][m-1] << endl;    }    return 0;}

Coins

#include 
    
     #include 
     
      using namespace std;const int N = 101, M = 100001;int cost[N], num[N], dp[M];int main(){    ios::sync_with_stdio(false);    cin.tie(NULL);    int n, m;    while(cin >> n >> m, n){        for(int i = 0; i < n; ++i) cin >> cost[i];        for(int i = 0; i < n; ++i) cin >> num[i];        memset(dp, -1, sizeof(dp));        dp[0] = 0;        for(int i = 0; i < n; ++i){            for(int j = 0; j <= m; ++j){                if(dp[j] >= 0) dp[j] = num[i];                else if(j < cost[i] || dp[j-cost[i]] < 0) dp[j] = -1;                else dp[j] = dp[j-cost[i]] - 1;            }        }        int ans = 0;        for(int i = 1; i <= m; ++i) ans += !(dp[i] == -1);        cout << ans << endl;    }    return 0;}

Ant Counting

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 1111;const int MOD = 1000000;int num[N], dp[2][100005];int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int t, a, s, b;    while(cin >> t >> a >> s >> b){        memset(num, 0, sizeof(num));        for(int i = 0;i < a; ++i){            int index;            cin >> index;            ++num[index];        }        memset(dp, 0, sizeof(dp));        dp[0][0] = dp[1][0] = 1;        for(int i = 1; i <= t; ++i){            int m = i & 1, n = (i-1) & 1;            for(int j = 1; j < 100003; ++j){                dp[m][j] = dp[m][j-1] + dp[n][j];                if(j > num[i]) dp[m][j] = dp[m][j] - dp[n][j-1-num[i]] + MOD;                while(dp[m][j] >= MOD) dp[m][j] -= MOD;           }       }        int ans = 0; t &= 1;        for(int i = s; i <= b; ++i){            ans += dp[t][i];            while(ans >= MOD) ans -= MOD;        }        cout << ans << endl;    }    return 0;}

Dollar Dayz

import java.util.*;import java.math.*;public class Main{    static final int N = 1111;    static final int K = 111;    static BigInteger dp[][] = new BigInteger[K][N];    static void init(){        for(int i = 0; i < N; ++i) dp[0][i] = BigInteger.ZERO;        for(int i = 0; i < K; ++i) dp[i][0] = BigInteger.ONE;        for(int i = 1; i < K; ++i)            for(int j = 1; j < N; ++j){                dp[i][j] = dp[i-1][j];                if(j >= i) dp[i][j] = dp[i][j].add(dp[i][j-i]);            }    }    public static void main(String[] args){        Scanner scan = new Scanner(System.in);        init();        while(scan.hasNext()){            int n = scan.nextInt();            int k = scan.nextInt();            System.out.println(dp[k][n]);        }        scan.close();    }}

Wooden Sticks

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef pair
        
          stick;const int N = 5555;stick p[N];int dp[N];int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int t;    cin >> t;    while(t--){        int n;        cin >> n;        for(int i = 0; i < n; ++i) cin >> p[i].first >> p[i].second;        sort(p, p + n);        memset(dp, -1, sizeof(dp));        for(int i = 0; i < n; ++i)            *lower_bound(dp, dp + n, p[i].second, greater
         
          ()) = p[i].second; cout << lower_bound(dp, dp + n, -1, greater
          
           ()) - dp << endl; } return 0;}

Bridging signals

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 44444;const int INF = 0x3f3f3f3f;int arr[N], dp[N];int main(){    int t;    scanf("%d", &t);    while(t--){        int n;        scanf("%d", &n);        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);        memset(dp, INF, sizeof(dp));        for(int i = 0; i < n; ++i) *lower_bound(dp, dp+n, arr[i]) = arr[i];        printf("%d\n", lower_bound(dp, dp+n, INF) - dp);    }    return 0;}

Making the Grade

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N = 2016;const ll INF = numeric_limits
        
         ::max();ll arr[N], srt[N], dp[N][N];ll _abs(ll a){ return a < 0 ? -a : a; }int main(){    int n;    while(~scanf("%d", &n)){        for(int i = 1; i <= n; ++i){            scanf("%lld", &arr[i]);            srt[i] = arr[i];        }        sort(srt + 1, srt + n + 1);        for(int i = 1; i <= n; ++i){            ll mini = INF;            for(int j = 1; j <= n; ++j){                mini = min(mini, dp[i-1][j]);                dp[i][j] = _abs(arr[i] - srt[j]) + mini;            }        }        ll ans = INF;        for(int i = 1; i <= n; ++i) ans = min(ans, dp[n][i]);        printf("%lld\n", ans);    }    return 0;}

Space Elevator

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 40404;struct block{    int h, l, n;    const bool operator < (const block& o) const {        return l < o.l;    }};block arr[404];int dp[2][40404];pair
       
         que[40404];int main(){    int n;    while(~scanf("%d", &n)){        for(int i = 0; i < n; ++i) scanf("%d %d %d", &arr[i].h, &arr[i].l, &arr[i].n);        sort(arr, arr + n);        int cur = 0, pre = 1;        for(int i = 0; i < n; ++i){            swap(cur, pre);            int v = arr[i].h, w = arr[i].h, V = arr[i].l, c = arr[i].n;            for(int mod = 0; mod < w; ++mod){                int l = 0, r = 0;                for(int j = 0; mod + j * w <= V; ++j){                    while(r > l && dp[pre][mod+j*w] - j*v > que[r-1].first) --r;                    que[r++] = make_pair(dp[pre][mod+j*w]-j*v, j);                    if(r > l && j - que[l].second > c) ++l;                    dp[cur][mod+j*w] = que[l].first + j*v;                }            }        }        int ans = *max_element(dp[cur], dp[cur]+arr[n-1].l+1);        printf("%d\n", ans);    }    return 0;}

Cow Exhibition

#include 
    
     #include 
     
      using namespace std;typedef long long ll;const int N = 111, M = 233333;const int INF = 0x3f3f3f3f;struct{ int s, f; } cow[N];int dp[M];int main(){    int n;    while(~scanf("%d", &n)){        for(int i = 0; i < n; ++i) scanf("%d %d", &cow[i].s, &cow[i].f);        for(int i = 0; i < M; ++i) dp[i] = -INF;        dp[100000] = 0;        for(int i = 0; i < n; ++i){            if(cow[i].s < 0 && cow[i].f < 0) continue;            if(cow[i].s > 0){                for(int j = 200000; j >= cow[i].s; --j)                    if(dp[j - cow[i].s] > -INF)                        dp[j] = max(dp[j], dp[j - cow[i].s] + cow[i].f);            }            else{                for(int j = cow[i].s; j <= 200000 + cow[i].s; ++j)                    if(dp[j - cow[i].s] > -INF)                        dp[j] = max(dp[j], dp[j - cow[i].s] + cow[i].f);            }        }        int ans = 0;        for(int i = 100000; i <= 200000; ++i)            if(dp[i] >= 0)                ans = max(ans, dp[i] + i - 100000);        printf("%d\n", ans);    }    return 0;}

Expedition

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 11111;int n, l, p;struct shop {    int dis, fuel;    shop(){}    shop(int dd, int ff): dis(dd), fuel(ff) {}    const bool operator < (const shop& o) const {        return dis < o.dis;    }} arr[N];priority_queue
       
         que;int main(){    while(~scanf("%d", &n)){        while(!que.empty()) que.pop();        for(int i = 0; i < n; ++i) scanf("%d %d", &arr[i].dis, &arr[i].fuel);        scanf("%d %d", &l, &p);        for(int i = 0; i < n; ++i) arr[i].dis = l - arr[i].dis;        arr[n] = shop(l, 0);        sort(arr, arr + n + 1);        int ans = 0, dis = 0;        for(int i = 0; i <= n; ++i){            dis = arr[i].dis - dis;            while(p < dis){                if(que.empty()){                    ans = -1;                    break;                }                p += que.top();                que.pop();                ++ans;            }            if(ans == -1) break;            que.push(arr[i].fuel);            p -= dis;            dis = arr[i].dis;        }        printf("%d\n", ans);    }    return 0;}

Sunscreen

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 25555;int c, l;struct Cow {    int minr, maxr;    const bool operator < (const Cow& other) const {        return minr == other.minr ? maxr < other.maxr : minr < other.minr;    }} cow[N];struct Lotion {    int r, cover;    const bool operator < (const Lotion& other) const {        return r == other.r ? cover < other.cover : r < other.r;    }} lotion[N];int main(){    while(~scanf("%d %d", &c, &l)){        for(int i = 0; i < c; ++i) scanf("%d %d", &cow[i].minr, &cow[i].maxr);        for(int i = 0; i < l; ++i) scanf("%d %d", &lotion[i].r, &lotion[i].cover);        sort(cow, cow + c);        sort(lotion, lotion + l);        priority_queue

, greater

> q; int ans = 0; for(int i = 0, index = 0; i < l; ++i){ while(index < c && cow[index].minr <= lotion[i].r){ q.push(cow[index].maxr); ++index; } while(!q.empty() && lotion[i].cover){ int minr = q.top(); q.pop(); if(minr >= lotion[i].r){ ++ans; --lotion[i].cover; } } } printf("%d\n", ans); } return 0;}

Moo University - Financial Aid

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 111111;const int INF = 0x3f3f3f3f;struct Cow {    int score, aid;    const bool operator < (const Cow& o) const {        return score == o.score ? aid < o.aid : score < o.score;    }} cow[MAXN];int N, C, F, lower[MAXN], upper[MAXN];int main (){    while(~scanf("%d %d %d", &N, &C, &F)){        for(int i = 0; i < C; ++i) scanf("%d %d", &cow[i].score, &cow[i].aid);        sort(cow, cow + C);        int median = N >> 1;        priority_queue
        
          q;        for(int i = 0, total = 0; i < C; ++i){            lower[i] = q.size() == median ? total : INF;            q.push(cow[i].aid);            total += cow[i].aid;            if(q.size() > median){                total -= q.top();                q.pop();            }        }        while(!q.empty()) q.pop();        for(int i = C - 1, total = 0; i >= 0; --i){            upper[i] = q.size() == median ? total : INF;            q.push(cow[i].aid);            total += cow[i].aid;            if(q.size() > median){                total -= q.top();                q.pop();            }        }        int ans = -1;        for(int i = C - 1; i >= 0; --i){            if(lower[i] + cow[i].aid + upper[i] <= F){                ans = cow[i].score;                break;            }        }        printf("%d\n", ans);    }}

食物链

#include 
    
     const int N = 233333;class UnionFind {public:    int father[N];    void init(int n){ for(int i = 0; i < n; ++i) father[i] = i; }    int find(int n){ return n == father[n] ? n : father[n] = find(father[n]); }    bool same(int x, int y){ return find(x) == find(y); }    void unite(int x, int y){        x = find(x); y = find(y);        if(x != y) father[x] = y;    }};int n, k;void AC(){    UnionFind p = UnionFind();    p.init(n * 3);    int type, x, y, ans = 0;    while(k--){        scanf("%d %d %d", &type, &x, &y);        --x; --y;        if(x < 0 || n <= x || y < 0 || n <= y){            ++ans;            continue;        }        if(type == 1){            if(p.same(x, y + n) || p.same(x, y + 2 * n)) ++ans;            else{                p.unite(x, y);                p.unite(x + n, y + n);                p.unite(x + 2 * n, y + 2 * n);            }        }        else{            if(p.same(x, y) || p.same(x, y + 2 * n)) ++ans;            else{                p.unite(x, y + n);                p.unite(x + n, y + 2 * n);                p.unite(x + 2 * n, y);            }        }    }    printf("%d\n", ans);}int main(){    scanf("%d %d", &n, &k);    AC();    return 0;}

Wireless Network

#include 
    
     #include 
     
      const int N = 1111;const int INF = 0x3f3f3f3f;class UnionFind {public:    int father[N];    void init(int n){ for(int i = 0; i <= n; ++i) father[i] = i; }    int find(int n){ return n == father[n] ? n : father[n] = find(father[n]); }    bool same(int x, int y){ return find(x) == find(y); }    void unite(int x, int y){        x = find(x); y = find(y);        if(x != y) father[x] = y;    }};int n, d;int x[N], y[N], dis[N][N];bool repaired[N];int distance(int x1, int y1, int x2, int y2){ return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); }int main(){    UnionFind p = UnionFind();    memset(repaired, false, sizeof(repaired));    memset(dis, INF, sizeof(dis));    scanf("%d %d", &n, &d);    d *= d;    for(int i = 1; i <= n; ++i){        scanf("%d %d", &x[i], &y[i]);        for(int j = 1; j < i; ++j)            dis[i][j] = dis[j][i] = distance(x[i], y[i], x[j], y[j]);    }    int xx, yy;    char ch;    p.init(n);    getchar();    while(~scanf("%c", &ch)){        if(ch == 'O'){            scanf("%d", &xx);            repaired[xx] = true;            for(int i = 1; i <= n; ++i)                if(repaired[i] && dis[xx][i] <= d)                    p.unite(p.father[i], xx);        }        else{            scanf("%d %d", &xx, &yy);            printf("%s\n", p.same(xx, yy) ? "SUCCESS" : "FAIL");        }        getchar();    }    return 0;}

Find them, Catch them

#include 
    
     const int N = 233333;class UnionFind {public:    int father[N];    void init(int n){ for(int i = 0; i <= n; ++i) father[i] = i; }    int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }    int same(int x, int y){ return find(x) == find(y); }    void unite(int x, int y){        x = find(x); y = find(y);        if(x != y) father[x] = y;    }};int T, n, m;int main(){    scanf("%d", &T);    while(T--){        scanf("%d %d", &n, &m);        UnionFind p = UnionFind();        p.init(n<<1);        char ch;        int x, y;        while(m--){            getchar();            scanf("%c %d %d", &ch, &x, &y);            if(ch == 'A'){                if(p.same(x, y)) puts("In the same gang.");                else if(p.same(x, y + n)) puts("In different gangs.");                else puts("Not sure yet.");            }            else{                p.unite(x, y + n);                p.unite(x + n, y);            }        }    }    return 0;}

Marked Ancestor

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 111111;int father[N], _rank[N];void init(int n){ for(int i = 0; i < n; ++i){ father[i] = i; _rank[i] = 0; } }int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }int same(int x, int y){ return find(x) == find(y); }void unite(int x, int y){    x = find(x); y = find(y);    if(x != y){        _rank[x] < _rank[y] ? father[x] = y : father[y] = x;        _rank[x] == _rank[y] ? ++_rank[x] : 0;    }}int n, q, parent[N], ancestor[N];bool marked[N];vector
        
          son[N];stack
         
           operation;stack
          
            target;void bfs(int index, int iancestor){ queue
           
             qi, qa; qi.push(index); qa.push(iancestor); while(!qi.empty()){ index = qi.front(); qi.pop(); iancestor = qa.front(); qa.pop(); if(marked[index]) iancestor = index; ancestor[index] = iancestor; for(vector
            
             ::iterator i = son[index].begin(); i != son[index].end(); ++i){ qi.push(*i); qa.push(iancestor); } }}int main(){ while(scanf("%d %d", &n, &q), (n || q)){ for(int i = 0; i < n; ++i){ son[i].clear(); marked[i] = false; } marked[0] = true; for(int i = 1; i < n; ++i){ scanf("%d", &parent[i]); --parent[i]; son[parent[i]].push_back(i); } while(q--){ char ch; int x; scanf("%*c%c %d", &ch, &x); --x; if(ch == 'M'){ if(marked[x]) continue; marked[x] = true; } operation.push(ch); target.push(x); } bfs(0, 0); init(n); for(int i = 0; i < n; ++i) unite(i, ancestor[i]); long long ans = 0; while(!operation.empty()){ char o = operation.top(); operation.pop(); int t = target.top(); target.pop(); if(o == 'Q') ans += ancestor[find(t)] + 1; else{ int p = ancestor[find(parent[t])]; unite(t, parent[t]); ancestor[find(t)] = p; } } printf("%lld\n", ans); } return 0;}

Convenient Location

#include 
    
     using namespace std;int path[11][11];int main(){    int n;    while(cin >> n, n){        memset(path, 0x3f3f3f3f, sizeof(path));        for(int i = 0; i < 10; ++i) path[i][i] = 0;        while(n--){            int a, b, c;            cin >> a >> b >> c;            path[a][b] = min(path[a][b], c);            path[b][a] = min(path[b][a], c);        }        for(int k = 0; k < 10; ++k)            for(int i = 0; i < 10; ++i)                for(int j = 0; j < 10; ++j)                    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);        int town = -1, total = 0x3f3f3f3f;        for(int i = 0; i < 10; ++i){            int tmp = 0;            bool flag = false;            for(int j = 0; j < 10; ++j){                if(path[i][j] != 0x3f3f3f3f && path[i][j] != 0) flag = true;                tmp += path[i][j] == 0x3f3f3f3f ? 0 : path[i][j];            }            if(flag && tmp < total){                town = i;                total = tmp;            }        }        cout << town << " " << total << endl;    }}

Six Degrees of Cowvin Bacon

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 305;int relat[N][N], arr[N];int main(){    int n, m;    while(~scanf("%d %d", &n, &m)){        memset(relat, 0x3f3f3f3f, sizeof(relat));        for(int i = 1; i <= n; ++i) relat[i][i] = 0;        while(m--){            int k;            scanf("%d", &k);            for(int i = 0; i < k; ++i){                scanf("%d", &arr[i]);                for(int j = 0; j < i; ++j)                    relat[arr[i]][arr[j]] = relat[arr[j]][arr[i]] = 1;            }        }        for(int k = 1; k <= n; ++k)            for(int i = 1; i <= n; ++i)                for(int j = 1; j <= n; ++j)                    relat[i][j] = min(relat[i][j], relat[i][k] + relat[k][j]);        memset(arr, 0, sizeof(arr));        for(int i = 1; i <= n; ++i)            for(int j = 1; j <= n; ++j)                arr[i] += relat[i][j];        int ans = 0x3f3f3f3f;        for(int i = 1; i <= n; ++i)            ans = min(ans, arr[i]);        printf("%d\n", int(ans * 100 / double(n-1)));    }    return 0;}

Wormholes

#include 
    
     #include 
     
      #include 
      
       using namespace std;struct Edge {    int from, to, cost;    Edge() {}    Edge(int _from, int _to, int _cost): from(_from), to(_to), cost(_cost) {}} edge[5555];int dist[555];int main(){    int t;    scanf("%d", &t);    while(t--){        int n, m, w;        scanf("%d %d %d", &n, &m, &w);        int index = 0;        while(m--){            int s, e, k;            scanf("%d %d %d", &s, &e, &k);            edge[index].from = s;            edge[index].to = e;            edge[index++].cost = k;            edge[index].from = e;            edge[index].to = s;            edge[index++].cost = k;        }        while(w--){            int s, e, k;            scanf("%d %d %d", &s, &e, &k);            edge[index].from = s;            edge[index].to = e;            edge[index++].cost = -k;        }        bool flag = false;        memset(dist, 0, sizeof(dist));        for(int i = 0; i < n; ++i){            for(int j = 0; j < index; ++j){                Edge e = edge[j];                if(dist[e.to] > dist[e.from] + e.cost){                    dist[e.to] = dist[e.from] + e.cost;                    if(i == n - 1){                        flag = true;                        break;                    }                }            }            if(flag) break;        }        puts(flag ? "YES" : "NO");    }    return 0;}

Silver Cow Party

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 111111;int n, m, x;int dist[N], rdist[N];bool inque[N];vector
         
          
            > g[N], rg[N];queue
           
             q;void spfa(int d[], int src, vector
            
             
               > fg[]){ while(!q.empty()) q.pop(); memset(inque, false, sizeof(inque)); d[src] = 0; q.push(src); inque[src] = true; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = 0; i < fg[u].size(); ++i){ pair
              
                p = fg[u][i]; if(d[p.first] > d[u] + p.second){ d[p.first] = d[u] + p.second; if(!inque[p.first]){ inque[p.first] = true; q.push(p.first); } } } inque[u] = false; }}int main(){ while(~scanf("%d %d %d", &n, &m, &x)){ for(int i = 0; i < m; ++i){ int a, b, t; scanf("%d %d %d", &a, &b, &t); g[a].push_back(make_pair(b, t)); rg[b].push_back(make_pair(a, t)); } memset(dist, 0x3f, sizeof(dist)); memset(rdist, 0x3f, sizeof(rdist)); spfa(dist, x, g); spfa(rdist, x, rg); int ans = 0; for(int i = 1; i <= n; ++i) if(dist[i] != 0x3f3f3f3f && rdist[i] != 0x3f3f3f3f) ans = max(ans, dist[i] + rdist[i]); printf("%d\n", ans); } return 0;}

Road Construction

Solution 1:

#include 
    
     using namespace std;const int N = 12345;struct edge {    int to, len, cost;    edge(){}    edge(int tt, int ll, int cc): to(tt), len(ll), cost(cc){}};vector
     
       g[N];int dist[N], n, m;typedef pair
      
        P;void dijkstra(int src){    priority_queue
       
        , greater
         > q;    memset(dist, 0x3f, sizeof(dist));    dist[src] = 0;    q.push(P(0, src));    while(!q.empty()){        P p = q.top(); q.pop();        int v = p.second;        if(dist[v] < p.first) continue;        for(int i = 0; i < g[v].size(); ++i){            edge e = g[v][i];            if(dist[e.to] > dist[v] + e.len){                dist[e.to] = dist[v] + e.len;                q.push(P(dist[e.to], e.to));            }        }    }}int main(){    while(scanf("%d %d", &n, &m), n || m){        for(int i = 0; i <= n; ++i) g[i].clear();        while(m--){            int a, b, l, c;            scanf("%d %d %d %d", &a, &b, &l, &c);            g[a].push_back(edge(b, l, c));            g[b].push_back(edge(a, l, c));        }        dijkstra(1);        int ans = 0;        for(int i = 2; i <= n; ++i){            int minc = 0x3f3f3f3f;            for(int j = 0; j < g[i].size(); ++j)                if(dist[g[i][j].to] + g[i][j].len == dist[i] && g[i][j].cost < minc)                    minc = g[i][j].cost;            ans += minc;        }        printf("%d\n", ans);    }    return 0;}

Solution 2:

#include 
    
     using namespace std;const int N = 12345;struct edge {    int to, len, cost;    edge(){}    edge(int tt, int ll, int cc): to(tt), len(ll), cost(cc) {}    const bool operator > (const edge& o) const {        return len == o.len ? cost > o.cost : len > o.len;    }};vector
     
       g[N];int n, m;bool visited[N];int dijkstra(int src){    memset(visited, false, sizeof(visited));    priority_queue
      
       , greater
       
         > q;    q.push(edge(src, 0, 0));    int ans = 0;    while(!q.empty()){        edge e = q.top(); q.pop();        int v = e.to;        if(visited[v]) continue;        visited[v] = true;        ans += e.cost;        for(int i = 0; i < g[v].size(); ++i)            q.push(edge(g[v][i].to, e.len + g[v][i].len, g[v][i].cost));    }    return ans;}int main(){    while(scanf("%d %d", &n, &m), n || m){        for(int i = 1; i <= n; ++i) g[i].clear();        while(m--){            int a, b, l, c;            scanf("%d %d %d %d", &a, &b, &l, &c);            g[a].push_back(edge(b, l, c));            g[b].push_back(edge(a, l, c));        }        printf("%d\n", dijkstra(1));    }    return 0;}

Mr.Rito Post Office

#include 
    
     using namespace std;const int N = 233, M = 1111, INF = 111111111;int n, m, r, dl[N][N], ds[N][N], dp[M][N], t[M];int main(){    while(scanf("%d %d", &n, &m), n || m){        for(int i = 0; i < n; ++i)            for(int j = 0; j < n; ++j)                dl[i][j] = ds[i][j] = i == j ? 0 : INF;        while(m--){            int x, y, l; char o;            scanf("%d %d %d %c", &x, &y, &l, &o);            --x; --y;            if(o == 'L') dl[x][y] = dl[y][x] = min(dl[y][x], l);            else ds[x][y] = ds[y][x] = min(ds[y][x], l);        }        for(int k = 0; k < n; ++k)            for(int i = 0; i < n; ++i)                for(int j = 0; j < n; ++j){                    dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]);                    ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);                }        scanf("%d", &r);        for(int i = 0; i < r; ++i){ scanf("%d", &t[i]); --t[i]; }        for(int i = 0; i < r; ++i)            for(int j = 0; j < n; ++j)                dp[i][j] = INF;        for(int i = 0; i < n; ++i)            dp[0][i] = ds[t[0]][i] + dl[i][t[0]];        for(int i = 1; i < r; ++i)            for(int j = 0; j < n; ++j)                for(int k = 0; k < n; ++k)                    dp[i][k] = j == k ?                         min(dp[i][j], dp[i-1][j] + dl[t[i-1]][t[i]]) :                             min(dp[i][k], dp[i-1][j] + dl[t[i-1]][j] + ds[j][k] + dl[k][t[i]]);        printf("%d\n", *min_element(dp[r-1], dp[r-1] + n));    }    return 0;}

Agri-Net

#include 
    
     #include 
     
      using namespace std;typedef pair
      
        pii;typedef pair
       
         P;priority_queue
        
         , greater
          > q;int n, father[111];int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }void kruskal(){ for(int i = 0; i <= n; ++i) father[i] = i; int ans = 0; while(!q.empty()){ P p = q.top(); q.pop(); if(find(p.second.first) == find(p.second.second)) continue; father[find(p.second.first)] = find(p.second.second); ans += p.first; } printf("%d\n", ans);}int main(){ while(~scanf("%d", &n)){ while(!q.empty()) q.pop(); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j){ int x; scanf("%d", &x); q.push(P(x, pii(i, j))); } kruskal(); } return 0;}

Bad Cowtractors

#include 
    
     #include 
     
      using namespace std;typedef pair
      
        pii;typedef pair
       
         P;priority_queue
         q;int n, m, father[1111];int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }void kruskal(){    for(int i = 0; i <= n; ++i) father[i] = i;    int ans = 0, cnt = 0;    while(!q.empty()){        if(cnt == n-1) break;        P p = q.top(); q.pop();        if(find(p.second.first) == find(p.second.second)) continue;        ++cnt;        ans += p.first;        father[find(p.second.first)] = find(p.second.second);    }    printf("%d\n", cnt == n-1 ? ans : -1);}int main(){    while(~scanf("%d %d", &n, &m)){        while(!q.empty()) q.pop();        while(m--){            int x, y, l;            scanf("%d %d %d", &x, &y, &l);            q.push(P(l, pii(x, y)));        }        kruskal();    }    return 0;}

Save your cat

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 11111;typedef pair
       
         pii;typedef pair
        
          > P;pii pile[N];priority_queue
          q;int n, m, father[N];int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }void kruskal(){ double ans = 0.0; while(!q.empty()){ P p = q.top(); q.pop(); if(find(p.second.first) == find(p.second.second)){ ans += p.first; continue; } father[find(p.second.first)] = find(p.second.second); } printf("%.3f\n", ans);}int main(){ while(~scanf("%d %d", &n, &m)){ for(int i = 1; i <= n; ++i) father[i] = i; while(!q.empty()) q.pop(); for(int i = 1; i <= n; ++i) scanf("%d %d", &pile[i].first, &pile[i].second); while(m--){ int x, y; scanf("%d %d", &x, &y); int dx = pile[x].first - pile[y].first, dy = pile[x].second - pile[y].second; q.push(P(sqrt(double(dx*dx + dy*dy)), pii(x, y))); } kruskal(); } return 0;}

Out of Hay

#include 
    
     #include 
     
      using namespace std;typedef pair
      
        pii;typedef pair
       
         P;priority_queue
        
         , greater
          > q;int n, m, father[2333];int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }void kruskal(){ int ans = -1; while(!q.empty()){ P p = q.top(); q.pop(); if(find(p.second.first) == find(p.second.second)) continue; ans = max(ans, p.first); father[find(p.second.first)] = find(p.second.second); } printf("%d\n", ans);}int main(){ while(~scanf("%d %d", &n, &m)){ while(!q.empty()) q.pop(); for(int i = 1; i <= n; ++i) father[i] = i; while(m--){ int x, y, l; scanf("%d %d %d", &x, &y, &l); q.push(P(l, pii(x, y))); } kruskal(); } return 0;}

Roadblocks

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 5555, INF = 0x3f3f3f3f;struct edge{ int to, cost; };vector
       
         g[N];typedef pair
        
          P;priority_queue
          q;int n, r, dis[N], dis2[N];void dijkstra(){ for(int i = 0; i <= n; ++i) dis[i] = dis2[i] = INF; dis[1] = 0; q.push(P(0, 1)); while(!q.empty()){ P p = q.top(); q.pop(); if(dis2[p.second] < p.first) continue; int v = p.second; for(int i = 0; i < g[v].size(); ++i){ edge e = g[v][i]; int d = p.first + e.cost; if(dis[e.to] > d){ swap(dis[e.to], d); q.push(P(dis[e.to], e.to)); } if(dis2[e.to] > d && dis[e.to] < d){ dis2[e.to] = d; q.push(P(dis2[e.to], e.to)); } } } for(int i = 1; i <= n; ++i) printf("%d %d\n", dis[i], dis2[i]);}int main(){ while(~scanf("%d %d", &n, &r)){ for(int i = 0; i <= n; ++i) g[i].clear(); while(!q.empty()) q.pop(); while(r--){ int x, y, l; scanf("%d %d %d", &x, &y, &l); g[x].push_back(edge{y, l}); g[y].push_back(edge{x, l}); } dijkstra(); } return 0;}

Conscription

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 11111;int n, m, r, father[N<<1];typedef pair
       
         pii;typedef pair
        
          P;priority_queue
          q;int find(int x){ return x == father[x] ? x : father[x] = find(father[x]); }void kruskal(){ int ans = 0; while(!q.empty()){ P p = q.top(); q.pop(); if(find(p.second.first) == find(p.second.second)) continue; ans += p.first; father[find(p.second.first)] = find(p.second.second); } printf("%d\n", 10000 * (n + m) - ans);}int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d %d %d", &n, &m, &r); while(!q.empty()) q.pop(); for(int i = 0, limit = n + m; i < limit; ++i) father[i] = i; while(r--){ int x, y, l; scanf("%d %d %d", &x, &y, &l); q.push(P(l, pii(x, y + n))); } kruskal(); } return 0;}

Layout

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 11111, INF = 0x3f3f3f3f;int n, ml, md, d[N];struct edge { int from, to, cost; };vector
       
         g;void bellmen_ford(){    memset(d, INF, sizeof(d));    d[1] = 0;    bool flag = false;    for(int i = 0; i < n; ++i){        for(vector
        
         ::iterator it = g.begin(); it != g.end(); ++it){            edge e = *it;            if(d[e.to] > d[e.from] + e.cost){                d[e.to] = d[e.from] + e.cost;                if(i == n-1) flag = true;            }        }    }    if(flag) puts("-1");    else if(d[n] == INF) puts("-2");    else printf("%d\n", d[n]);}int main(){    while(~scanf("%d %d %d", &n, &ml, &md)){        g.clear();        for(int i = n; i; --i) g.push_back(edge{i, i-1, 0});        while(ml--){            int al, bl, ll;            scanf("%d %d %d", &al, &bl, &ll);            g.push_back(edge{al, bl, ll});        }        while(md--){            int ad, bd, ld;            scanf("%d %d %d", &ad, &bd, &ld);            g.push_back(edge{bd, ad, -ld});        }        bellmen_ford();    }    return 0;}

Carmichael Numbers

#include 
    
     using namespace std;const int N = 66666;bool isprime[N];int n;void init(){    memset(isprime, true, sizeof(isprime));    isprime[0] = isprime[1] = false;    for(int i = 2, limit = sqrt(N); i <= limit; ++i){        if(isprime[i]){            for(int j = i; i * j < N; ++j)                isprime[i * j] = false;        }    }}typedef long long ll;bool pow_mod(ll x, ll n, ll mod){    ll ans = 1, t = x;    while(n){        if(n & 1) ans = ans * x % mod;        x = x * x % mod;        n >>= 1;    }    return ans != t;}int main(){    init();    while(cin >> n, n){        if(isprime[n]) printf("%d is normal.\n", n);        else{            bool flag = true;            for(int i = 2; i < n; ++i) if(pow_mod(i, n, n)){ flag = false; break; }            if(flag) printf("The number %d is a Carmichael number.\n", n);            else printf("%d is normal.\n", n);        }    }    return 0;}

Minimum Scalar Product

#include 
    
     #include 
     
      using namespace std;const int N = 1111;typedef long long ll;ll t, n, a[N], b[N];int main(){    cin >> t;    for(int x = 1; x <= t; ++x){        cout << "Case #" << x << ": ";        cin >> n;        for(int i = 0; i < n; ++i) cin >> a[i];        for(int i = 0; i < n; ++i) cin >> b[i];        sort(a, a + n); sort(b, b + n);        ll ans = 0;        for(int i = 0; i < n; ++i) ans += a[i] * b[n-i-1];        cout << ans << endl;    }    return 0;}

Crazy Rows

#include 
    
     #include 
     
      using namespace std;const int N = 44;int a[N], t, n;int main(){    cin >> t;    for(int x = 1; x <= t; ++x){        cout << "Case #" << x << ": ";        int ans = 0;        cin >> n;        for(int i = 0; i < n; ++i){            a[i] = -1;            for(int j = 0; j < n; ++j){                char k;                cin >> k;                if(k-'0') a[i] = j;            }        }        for(int i = 0; i < n; ++i){            int pos = -1;            for(int j = i; j < n; ++j) if(a[j] <= i){ pos = j; break; }            for(int j = pos; j > i; --j){                swap(a[j], a[j-1]);                ++ans;            }        }        cout << ans << endl;    }}

Bribe the Prisoners

Millionaire

GCD and LCM

#include 
    
     using namespace std;typedef long long ll;ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a; }ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }int main(){    ll a, b;    while(cin >> a >> b) cout << gcd(a, b) << " " << lcm(a, b) << endl;    return 0;}

GCD & LCM Inverse

#include #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;ll mul_mod(ll a, ll b, ll mod){    ll ans = 0, exp = a;    while(exp >= mod) exp -= mod;    while(b){        if(b & 1){            ans += exp;            if(ans >= mod) ans -= mod;        }        exp <<= 1;        if(exp >= mod) exp -= mod;        b >>= 1;    }    return ans;}ll pow_mod(ll x, ll n, ll mod){    ll ans = 1, exp = x;    while(exp >= mod) exp -= mod;    while(n){        if(n & 1) ans = mul_mod(ans, exp, mod);        exp = mul_mod(exp, exp, mod);        n >>= 1;    }    return ans;}const int MP = 233333;vector
        
          primes;vector
         
           isprime;void init_primes(){ isprime = vector
          
           (MP, true); isprime[0] = isprime[1] = false; for(int i = 2; i < MP; ++i){ if(isprime[i]) primes.push_back(i); for(int j = 0; j < primes.size() && i * primes[j] < MP; ++j){ isprime[i * primes[j]] = false; if(i % primes[j] == 0) break; } }}bool miller_rabin(ll n){ if(n < 2) return false; if(n == 2) return true; if(!(n & 1)) return false; ll p = n - 1; int k = 0; while(!(p & 1)){ ++k; p >>= 1; } for(int i = 0; i < 20; ++i){ ll a = rand() % (n - 1) + 1; ll x = pow_mod(a, p, n); if(x == 1) continue; bool flag = false; for(int j = 0; j < k; ++j){ if(x == n - 1){ flag = true; break; } x = mul_mod(x, x, n); } if(flag) continue; return false; } return true;}bool is_prime(ll n){ if(n < MP) return isprime[n]; else return miller_rabin(n);}ll pollard_rho(ll n, int a){ ll x = 2, y = 2, d = 1; while(d == 1){ x = mul_mod(x, x, n) + a; y = mul_mod(y, y, n) + a; y = mul_mod(y, y, n) + a; d = __gcd((x >= y ? x - y : y - x), n); } if(d == n) return pollard_rho(n, a + 1); return d;}void factorize(ll n, map
           
            & factors){ if(is_prime(n)) ++factors[n]; else{ for(int i = 0; i < primes.size(); ++i) while(!(n % primes[i])){ ++factors[primes[i]]; n /= primes[i]; } if(n != 1){ if(is_prime(n)) ++factors[n]; else{ ll d = pollard_rho(n, 1); factorize(d, factors); factorize(n / d, factors); } } }}int main(){ ios::sync_with_stdio(false); cin.tie(0); ll a, b; init_primes(); while(cin >> a >> b){ ll c = b / a; map
            
              factors; factorize(c, factors); vector
             
               p_factors; for(map
              
               ::iterator it = factors.begin(); it != factors.end(); ++it){ ll tmp = 1; while(it->second--) tmp *= it->first; p_factors.push_back(tmp); } ll x = 1, y = c, sum = 1e18; for(int i = 0; i < (1 << p_factors.size()); ++i){ ll tx = 1; for(int j = 0; j < p_factors.size(); ++j) if(i & (1 << j)) tx *= p_factors[j]; ll ty = c / tx; if(tx < ty && tx + ty < sum){ x = tx; y = ty; sum = x + y; } } cout << x * a << " " << y * a << endl; } return 0;}

Dead Fraction

Prime Number

#include 
    
     using namespace std;const int N = 1111111;int primes[N], total;bool isprime[N];void init_primes(){    memset(isprime, true, sizeof(isprime));    isprime[0] = isprime[1] = false;    total = 0;    for(int i = 2; i < N; ++i){        if(isprime[i]) primes[total++] = i;        for(int j = 0; j < total && i * primes[j] < N; ++j){            isprime[i * primes[j]] = false;            if(i % primes[j] == 0) break;        }    }}int main(){    init_primes();    int n;    while(cin >> n) cout << upper_bound(primes, primes + total, n) - primes << endl;    return 0;}

Prime Path

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 11111;int primes[N], total;bool isprime[N];void init_primes(){    memset(isprime, true, sizeof(isprime));    isprime[0] = isprime[1] = false;    total = 0;    for(int i = 2; i < N; ++i){        if(isprime[i]) primes[total++] = i;        for(int j = 0; j < total && i * primes[j] < N; ++j){            isprime[i * primes[j]] = false;            if(i % primes[j] == 0) break;        }    }}int main(){    init_primes();    int t;    cin >> t;    while(t--){        int a, b;        cin >> a >> b;        queue
        
          q;        q.push(a);        vector
         
           step = vector
          
           (N, -1); step[a] = 0; while(!q.empty()){ int num = q.front(); q.pop(); if(num == b){ cout << step[num] << endl; break; } for(int i = 0; i < 4; ++i){ int digit[] = {num/1000, (num%1000)/100, (num%100)/10, num%10}; for(int j = 0; j < 10; ++j){ digit[i] = j; int newn = digit[0]*1000 + digit[1]*100 + digit[2]*10 + digit[3]; if(newn < 1000 || !isprime[newn] || ~step[newn]) continue; q.push(newn); step[newn] = step[num] + 1; } } } } return 0;}

X-factor Chains

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;vector
       
         factorize(int n){    vector
        
          ans;    for(int i = 2; i * i <= n; ++i){        int tmp = 0;        while(n % i == 0){            ++tmp;            n /= i;        }        ans.push_back(tmp);    }    if(n != 1) ans.push_back(1);    return ans;}ll factorial(int n){    ll ans = 1;    while(n) ans *= n--;    return ans;}int main(){    int n;    while(cin >> n){        vector
         
           p_factors = factorize(n); int length = accumulate(p_factors.begin(), p_factors.end(), 0); ll num = factorial(length); for(vector
          
           ::iterator it = p_factors.begin(); it != p_factors.end(); ++it) num /= factorial(*it); cout << length << " " << num << endl; } return 0;}

Semi-prime H-numbers

Pseudoprime numbers

#include 
    
     using namespace std;typedef long long ll;ll mul_mod(ll a, ll b, ll mod){    ll ans = 0, exp = a % mod;    while(b){        if(b & 1){            ans += exp;            while(ans >= mod) ans -= mod;        }        exp <<= 1;        while(exp >= mod) exp -= mod;        b >>= 1;    }    return ans;}ll pow_mod(ll x, ll n, ll mod){    ll ans = 1, exp = x % mod;    while(n){        if(n & 1) ans = mul_mod(ans, exp, mod);        exp = mul_mod(exp, exp, mod);        n >>= 1;    }    return ans;}bool isprime(ll n){    for(int i = 2; i * i <= n; ++i)        if(n % i == 0)            return false;    return true;}int main(){    ll p, a;    while(cin >> p >> a, p || a){        if(!isprime(p) && pow_mod(a, p, p) == a) cout << "yes" << endl;        else cout << "no" << endl;    }    return 0;}

Raising Modulo Numbers

#include 
    
     #include 
     
      using namespace std;typedef long long ll;ll mul_mod(ll a, ll b, ll mod){    ll ans = 0, exp = a % mod;    while(b){        if(b & 1){            ans += exp;            while(ans >= mod) ans -= mod;        }        exp <<= 1;        while(exp >= mod) exp -= mod;        b >>= 1;    }    return ans;}ll pow_mod(ll x, ll n, ll mod){    ll ans = 1, exp = x % mod;    while(n){        if(n & 1) ans = mul_mod(ans, exp, mod);        exp = mul_mod(exp, exp, mod);        n >>= 1;    }    return ans;}const int N = 50000;int ans[N];int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int t;    cin >> t;    while(t--){        int mod, h;        cin >> mod >> h;        for(int i = 0; i < h; ++i){            int a, b;            cin >> a >> b;            ans[i] = pow_mod(a, b, mod);        }        cout << accumulate(ans, ans + h, 0) % mod << endl;    }    return 0;}

Cable master

#include 
    
     #include 
     
      using namespace std;const int N = 12345;int n, k;double len[N];int main(){    while(~scanf("%d %d", &n, &k)){        for(int i = 0; i < n; ++i) scanf("%lf", &len[i]);        double l = 0, r = 1<<30;        for(int i = 0; i < 100; ++i){            double mid = (l + r) / 2.0;            int t = 0;            for(int j = 0; j < n; ++j) t += int(len[j] / mid);            if(t >= k) l = mid;            else r = mid;        }        printf("%.2f\n", floor(r * 100) / 100);    }    return 0;}

Aggressive cows

#include 
    
     #include 
     
      using namespace std;const int N = 100002;int n, c, x[N];bool check(int dis){    int k = 0;    for(int i = 1; i < c; ++i){        int pos = k + 1;        while(pos < n && x[pos] - x[k] < dis) ++pos;        if(pos == n) return false;        k = pos;     }    return true;}int main(){    while(~scanf("%d %d", &n, &c)){        for(int i = 0; i < n; ++i) scanf("%d", &x[i]);        sort(x, x + n);        int l = 0, r = 0x3f3f3f3f;        for(int i = 0; i < 100; ++i){            int mid = (l + r) >> 1;            if(check(mid)) l = mid;            else r = mid;        }        printf("%d\n", l);    }    return 0;}

Subsequence

#include 
    
     #include 
     
      using namespace std;const int N = 100002;int n, s, arr[N];int main(){    int t;    scanf("%d", &t);    while(t--){        scanf("%d %d", &n, &s);        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);        int ans = 0x3f3f3f3f, l = 0, r = 0, sum = 0;        while(true){            while(r < n && sum < s) sum += arr[r++];            if(sum < s) break;            ans = min(ans, r - l);            sum -= arr[l++];        }        if(ans > n) ans = 0;        printf("%d\n", ans);    }    return 0;}

Jessica's Reading Problem

#include 
    
     #include 
     #include 
      
       #include 
       
        using namespace std;const int N = 1000002;int n, arr[N];set
        
          s;map
         
           m;int main(){ while(~scanf("%d", &n)){ s.clear(); m.clear(); for(int i = 0; i < n; ++i){ scanf("%d", &arr[i]); s.insert(arr[i]); } int k = s.size(), l = 0, r = 0, cnt = 0, ans = n; while(true){ while(r < n && cnt < k) if(m[arr[r++]]++ == 0) ++cnt; if(cnt < k) break; ans = min(ans, r - l); if(--m[arr[l++]] == 0) --cnt; } printf("%d\n", ans); } return 0;}

Face The Right Way

#include 
    
     #include 
     
      const int N = 5555;int n, dir[N], flip[N];int main(){    while(~scanf("%d", &n)){        for(int i = 0; i < n; ++i){            char ch;            scanf(" %c", &ch);            if(ch == 'F') dir[i] = 0;            else dir[i] = 1;        }        int ansop = n, ansk = 1;        for(int k = 1; k <= n; ++k){            memset(flip, 0, sizeof(flip));            int op = 0, sum = 0;            for(int i = 0; i + k - 1 < n; ++i){                if((dir[i] + sum) & 1){                    ++op;                    flip[i] = 1;                }                sum += flip[i];                if(i - k + 1 >= 0) sum -= flip[i-k+1];            }            for(int i = n-k+1; i < n; ++i){                if((dir[i] + sum) & 1){                    op = -1;                    break;                }                if(i - k + 1 >= 0) sum -= flip[i-k+1];            }            if(op >= 0 && ansop > op){                ansop = op;                ansk = k;            }        }        printf("%d %d\n", ansk, ansop);    }}

Fliptile

#include 
    
     #include 
     
      const int N = 20, INF = 0x3f3f3f3f;const int dx[] = {0, 0, 0, -1}, dy[] = {1, -1, 0, 0};int n, m, ans[N][N], flip[N][N], origin[N][N];bool check(int x, int y){    int cnt = origin[x][y];    for(int i = 0; i < 4; ++i){        int nx = x + dx[i], ny = y + dy[i];        if(nx >= 0 && nx < n && ny >= 0 && ny < m)            cnt += flip[nx][ny];    }    return cnt & 1;}int solve(){    for(int i = 1; i < n; ++i)        for(int j = 0; j < m; ++j)            if(check(i - 1, j))                flip[i][j] = 1;    for(int j = 0; j < m; ++j)        if(check(n - 1, j))            return 0;    int cnt = 0;    for(int i = 0; i < n; ++i)        for(int j = 0; j < m; ++j)            cnt += flip[i][j];    return cnt;}int main(){    while(~scanf("%d %d", &n, &m)){        for(int i = 0; i < n; ++i)            for(int j = 0; j < m; ++j)                scanf("%d", &origin[i][j]);        int step = INF;        for(int i = 0; i < (1 << m); ++i){            memset(flip, 0, sizeof(flip));            for(int j = 0; j < m; ++j)                flip[0][j] = (i >> j) & 1;            int cnt = solve();            if(cnt != 0 && cnt < step){                step = cnt;                memcpy(ans, flip, sizeof(flip));            }        }        if(step == INF) puts("IMPOSSIBLE");        else{            for(int i = 0; i < n; ++i)                for(int j = 0; j < m; ++j)                    printf("%d%c", ans[i][j], " \n"[j == m - 1]);        }    }    return 0;}

Physics Experiment

#include 
    
     #include 
     
      #include 
      
       using namespace std;const double g = 10.0;const int MAX_N = 111;int N, H, R, T;double ans[MAX_N];double calc(int T){    if(T < 0) return H;    double t = sqrt(2 * H / g), d;    int k = (int)(T / t);    if(k & 1)        d = k * t + t - T;    else        d = T - k * t;    return H - g * d * d / 2;}void solve(){    for(int i = 0; i < N; ++i) ans[i] = calc(T - i);    sort(ans, ans + N);    for(int i = 0; i < N; ++i)        printf("%.2f%c", ans[i] + 2 * R * i / 100.0, i == N - 1 ? '\n' : ' ');}int main(){    int x;    scanf("%d", &x);    while(x--){        scanf("%d %d %d %d", &N, &H, &R, &T);        solve();    }    return 0;}

4 Values whose Sum is 0

#include 
    
     #include 
     
      using namespace std;const int N = 4444;int n, a[N], b[N], c[N], d[N], e[N*N], f[N*N];int main(){    ios::sync_with_stdio(false); cin.tie(0);    while(cin >> n){        for(int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i] >> d[i];        int it = 0;        for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) e[it] = a[i] + b[j], f[it++] = c[i] + d[j];        sort(f, f + it);        int ans = 0;        for(int i = 0; i < it; ++i)            ans += upper_bound(f, f + it, -e[i]) - lower_bound(f, f + it, -e[i]);        cout << ans << endl;    }    return 0;}

River Hopscotch

#include 
    
     #include 
     
      using namespace std;const int N = 55555;int l, n, m, rock[N];bool check(int x){    int last = 0, rm = 0;    for(int i = 0; i < n; ++i){        int cur = last + 1;        while(cur < n && rock[cur] - rock[last] < x) ++rm, ++cur;        last = cur;    }    if(rm > m) return false;    return true;}int main(){    while(~scanf("%d %d %d", &l, &n, &m)){        for(int i = 0; i < n; ++i) scanf("%d", &rock[i]);        rock[n++] = 0; rock[n++] = l;        sort(rock, rock + n);        int lb = 0, rb = l + 1;        while(rb - lb > 1){            int mid = (lb + rb) >> 1;            if(check(mid)) lb = mid;            else rb = mid;        }        printf("%d\n", lb);    }    return 0;}

Monthly Expense

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 123456;int n, m, arr[N];bool check(int x){    int seg = 1, sum = 0;    for(int i = 0; i < n; ++i){        sum += arr[i];        if(sum > x){            sum = arr[i];            ++seg;        }    }    if(seg > m) return true;    return false;}int main(){    while(~scanf("%d %d", &n, &m)){        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);        int lb = *max_element(arr, arr + n), rb = accumulate(arr, arr + n, 0);        while(rb > lb){            int mid = (lb + rb) >> 1;            if(check(mid)) lb = mid + 1;            else rb = mid;        }        printf("%d\n", lb);    }    return 0;}

Drying

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 111111;int n, k, arr[N];int main(){    while(~scanf("%d", &n)){        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);        scanf("%d", &k);        if(k == 1){            printf("%d\n", *max_element(arr, arr + n));            continue;        }        int lb = 0, rb = *max_element(arr, arr + n);        while(rb > lb){            int mid = (lb + rb) >> 1;            long long tot = 0;            for(int i = 0; i < n; ++i){                int t = arr[i] - mid;                if(t <= 0) continue;                tot += ceil(double(t) / (k - 1));            }            if(tot > mid) lb = mid + 1;            else rb = mid;        }        printf("%d\n", rb);    }    return 0;}

Cow Acrobats

#include 
    
     #include 
     
      using namespace std;const int N = 55555;struct Cow{    int w, s;    const bool operator < (const Cow& o) const {        return w + s > o.w + o.s;    }}cow[N];int main(){    int n;    while(~scanf("%d", &n)){        int tot = 0;        for(int i = 0; i < n; ++i){            scanf("%d %d", &cow[i].w, &cow[i].s);            tot += cow[i].w;        }        sort(cow, cow + n);        int risk = -0x3f3f3f3f;        for(int i = 0; i < n; ++i){            tot -= cow[i].w;            risk = max(risk, tot - cow[i].s);        }        printf("%d\n", risk);    }    return 0;}

Dropping tests

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 1111;const double eps = 1e-6;int n, k;double x;struct test {    int a, b;    const bool operator < (const test& o) const {        return a - b * x > o.a - o.b * x;    }} arr[N];bool check(){    sort(arr, arr + n);    double atot = 0, btot = 0;    for(int i = 0; i < n - k; ++i) atot += arr[i].a, btot += arr[i].b;    return atot / btot > x;}int main(){    while(scanf("%d %d", &n, &k), n || k){        for(int i = 0; i < n; ++i) scanf("%d", &arr[i].a);        for(int i = 0; i < n; ++i) scanf("%d", &arr[i].b);        double lb = 0, rb = 1;        while(fabs(rb - lb) > eps){            x = (lb + rb) / 2.0;            if(check()) lb = x;            else rb = x;        }        printf("%.0f\n", lb * 100);    }    return 0;}

K Best

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 111111;const double eps = 1e-6;int n, k;double x;struct jewels {    int w, v, i;    const bool operator < (const jewels& o) const {        return v - x * w > o.v - x * o.w;    }} arr[N];bool check(){    sort(arr, arr + n);    double vtot = 0, wtot = 0;    for(int i = 0; i < k; ++i) vtot += arr[i].v, wtot += arr[i].w;    return vtot / wtot > x;}int main(){    while(~scanf("%d %d", &n, &k)){        for(int i = 0; i < n; ++i) scanf("%d %d", &arr[i].v, &arr[i].w), arr[i].i = i + 1;        double lb = 0, rb = 1e15;        while(fabs(rb - lb) > eps){            x = (lb + rb) / 2.0;            if(check()) lb = x;            else rb = x;        }        vector
        
          ans;        for(int i = 0; i < k; ++i) ans.push_back(arr[i].i);        sort(ans.begin(), ans.end());        for(int i= 0; i < ans.size(); ++i) printf("%d%c", ans[i], " \n"[i == ans.size() - 1]);    }    return 0;}

Median

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 111111;int n, arr[N], c_n_2;bool check(int x){    int cnt = 0;    for(int i = 0; i < n; ++i) cnt += arr + n - lower_bound(arr+i+1, arr+n, x + arr[i]);    return cnt <= (c_n_2 >> 1);}int main(){    while(~scanf("%d", &n)){        c_n_2 = n * (n - 1) >> 1;        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);        sort(arr, arr + n);        int lb = 0, rb = 0x3f3f3f3f, ans = 0;        while(rb - lb > 1){            int mid = (lb + rb) >> 1;            if(check(mid)) rb = mid;            else lb = ans = mid;        }        printf("%d\n", ans);    }    return 0;}

Matrix

#include 
    
     using namespace std;typedef long long ll;ll x, n, m;ll calc(ll x, ll y){ return x * x + 100000 * x + y * y - 100000 * y + x * y; }bool check(ll x){    ll cnt = 0;    for(int j = 1; j <= n; ++j){        int lb = 0, rb = n + 1;        while(rb - lb > 1){            int mid = (lb + rb) >> 1;            if(calc(mid, j) < x) lb = mid;            else rb = mid;        }        cnt += lb;    }    return cnt < m;}int main(){    ios::sync_with_stdio(false); cin.tie(0);    cin >> x;    while(x--){        cin >> n >> m;        ll lb = -100000 * n, rb = n * n + 100000 * n + n * n + n * n;        while(rb - lb > 1){            ll mid = (lb + rb) >> 1;            if(check(mid)) lb = mid;            else rb = mid;        }        cout << lb << endl;    }    return 0;}

Moo University - Financial Aid

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 111111;int n, c, f;struct Cow{    int score, aid, rank;}cow_a[N], cow_s[N];bool cmp_s(const Cow& a, const Cow& b){ return a.score < b.score; }bool cmp_a(const Cow& a, const Cow& b){ return a.aid < b.aid; }int main(){    ios::sync_with_stdio(false);    cin.tie(0);    while(cin >> n >> c >> f){        for(int i = 0; i < c; ++i) cin >> cow_s[i].score >> cow_s[i].aid;        sort(cow_s, cow_s + c, cmp_s);        for(int i = 0; i < c; ++i) cow_s[i].rank = i;        memcpy(cow_a, cow_s, sizeof(Cow) * c);        sort(cow_a, cow_a + c, cmp_a);        int l = 0, r = c, ans = -1, half = n >> 1;        while(r - l > 1){            int mid = (l + r) >> 1;            int left = 0, right = 0, tot = cow_s[mid].aid;            for(int i = 0; i < c; ++i){                if(cow_a[i].rank < mid && tot + cow_a[i].aid <= f && left < half){                    ++left;                    tot += cow_a[i].aid;                }                else if(cow_a[i].rank > mid && tot + cow_a[i].aid <= f && right < half){                    ++right;                    tot += cow_a[i].aid;                }            }            if(left < half && right < half){ ans = -1; break; }            else if(left < half) l = mid;            else if(right < half) r = mid;            else{                ans = cow_s[mid].score;                l = mid;            }        }        cout << ans << endl;    }    return 0;}

Telephone Lines

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef pair
         
           P;const int N = 11111;vector
           g[N];int n, p, k, d[N];int dijkstra(int s, int x){ priority_queue
           
            , greater
           
           > q; q.push(P(s, 0)); memset(d, 0x3f3f3f3f, sizeof(d)); d[s] = 0; while(!q.empty()){ P p = q.top(); q.pop(); int v = p.first; if(d[v] < p.second) continue; for(int i = 0; i < g[v].size(); ++i){ P t = g[v][i]; int k = d[v] + (t.second >= x ? 1 : 0); if(d[t.first] > k){ d[t.first] = k; q.push(P(t.first, k)); } } } return d[n-1];}int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin >> n >> p >> k){ for(int i = 0; i < p; ++i){ int f, t, v; cin >> f >> t >> v; --f; --t; g[f].push_back(P(t, v)); g[t].push_back(P(f, v)); } int l = 0, r = 0x3f3f3f3f; while(r - l > 1){ int mid = (l + r) >> 1; if(dijkstra(0, mid) > k) l = mid; else r = mid; } cout << (l > 1000000 ? -1 : l) << endl; } return 0;}

Garland

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n; double a, h[1111], ans;bool check(double x){    h[1] = x;    for(int i = 2; i < n; ++i){        h[i] = 2 * h[i - 1] + 2 - h[i - 2];        if(h[i] < 0) return false;    }    ans = h[n - 1];    return true;}int main(){    while(cin >> n >> a){        memset(h, 0, sizeof(h));        h[0] = a;        double l = 0, r = 0x3f3f3f3f;        for(int i = 0; i < 1000; ++i){            double mid = (l + r) / 2.0;            if(check(mid)) r = mid;            else l = mid;        }        cout << fixed << setprecision(2) << ans << endl;    }    return 0;}

Sum of Consecutive Prime Numbers

#include 
    
     #include 
     
      using namespace std;const int N = 11111;int n, prime[N], tot; bool isprime[N];void init(){    tot = 0;    memset(isprime, true, sizeof(isprime));    isprime[0] = isprime[1] = false;    for(int i = 2; i < N; ++i){        if(isprime[i]) prime[tot++] = i;        for(int j = 0; j < tot && i * prime[j] < N; ++j){            isprime[i * prime[j]] = false;            if(i % prime[j] == 0) break;        }    }}int main(){    init();    while(cin >> n, n){        int l = 0, r = 0, sum = 0, ans = 0;        while(true){            while(sum < n && r < tot) sum += prime[r++];            if(sum < n) break;            if(sum == n) ++ans;            sum -= prime[l++];        }        cout << ans << endl;    }    return 0;}

Graveyard Design

#include 
    
     #include 
     
      using namespace std;typedef long long ll;vector
      
       
         > vt;int main(){    ll n;    while(~scanf("%I64d", &n)){        vt.clear();        ll l = 1, r = 1, sum = 0;        while(true){            while(sum < n){                sum += r * r;                ++r;            }            if((r-1) * (r-1) > n) break;            if(sum == n) vt.push_back(make_pair(l, r));            sum -= l * l;            ++l;        }        printf("%d\n", vt.size());        for(int i = 0; i < vt.size(); ++i){            pair
        
          p = vt[i];            printf("%I64d", p.second - p.first);            while(p.first < p.second) printf(" %I64d", p.first++);            puts("");        }    }    return 0;}

Bound Found

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 101010;const int INF = 0x3f3f3f3f;int n, t, k, arr[N], ans, ansl, ansr;struct book{    int presum, index;    book(){};    book(int pp, int ii): presum(pp), index(ii) {};    const bool operator < (const book& o) const {        return presum < o.presum;    }} pre[N];int main(){    while(scanf("%d %d", &n, &t)){        pre[0] = book(0, 0);        if(!n && !t) break;        for(int i = 1; i <= n; ++i){            scanf("%d", &arr[i]);            pre[i] = book(pre[i - 1].presum + arr[i], i);        }        sort(pre, pre + n + 1);        while(t--){            scanf("%d", &k);            int l = 0, r = 1, sum = INF, MIN = INF; ans = INF;            while(r <= n){                sum = pre[r].presum - pre[l].presum;                if(abs(sum - k) < MIN){                    MIN = abs(sum - k);                    ans = sum;                    ansl = min(pre[l].index, pre[r].index);                    ansr = max(pre[l].index, pre[r].index);                }                if(sum <= k) ++r;                else ++l;                if(l == r) ++r;            }            printf("%d %d %d\n", ans, ansl + 1, ansr);        }    }    return 0;}

The Water Bowls

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 22;int dir[N], flip[N];int calc(int start){    memset(flip, 0, sizeof(flip));    dir[0] = start;    int ans = 0, sum = 0;    for(int i = 0; i < 20; ++i){        if((dir[i] + sum) & 1){            ++ans;            flip[i] = 1;        }        sum += flip[i];        if(i - 2 >= 0) sum -= flip[i - 2];    }    if((dir[20] + sum) & 1) return 0x3f3f3f3f;    return ans;}int main(){    for(int i = 1; i <= 20; ++i) scanf("%d", &dir[i]);    printf("%d\n", min(calc(0), calc(1)));    return 0;}

Extended Lights Out

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int n = 5, m = 6, cx[] = {-1, 0, 0, 0, 1}, cy[] = {0, -1, 0, 1, 0};int t, tile[11][11], opt[11][11], flip[11][11];int get(int x, int y){    int c = tile[x][y];    for(int i = 0; i < 5; ++i){        int xx = x + cx[i], yy = y + cy[i];        if(0 <= xx && xx < n && 0 <= yy && yy < m)            c += flip[xx][yy];    }    return c & 1;}int calc(){    for(int i = 1; i < n; ++i)        for(int j = 0; j < m; ++j)            if(get(i - 1, j))                flip[i][j] = 1;    for(int j = 0; j < m; ++j)        if(get(n - 1, j))            return -1;    int res = 0;    for(int i = 0; i < n; ++i)        for(int j = 0; j < m; ++j)            res += flip[i][j];    return res;}void solve(){    int res = -1;    for(int i = 0; i < 1 << m; ++i){        memset(flip, 0, sizeof(flip));        for(int j = 0; j < m; ++j)            flip[0][m-j-1] = i >> j & 1;        int num = calc();        if(num >= 0 && (res < 0 || res > num)){            res = num;            memcpy(opt, flip, sizeof(flip));        }    }    for(int i = 0; i < n; ++i)        for(int j = 0; j < m; ++j)            printf("%d%c", opt[i][j], j == m - 1 ? '\n' : ' ');}int main(){    scanf("%d", &t);    for(int x = 1; x <= t; ++x){        printf("PUZZLE #%d\n", x);        for(int i = 0; i < n; ++i)            for(int j = 0; j < m; ++j)                scanf("%d", &tile[i][j]);        solve();    }    return 0;}

Linear world

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 33333;const double eps = 1e-6;struct inhabitant{    double pos;    string name;    const bool operator < (const inhabitant& o) const {        return fabs(pos) < fabs(o.pos);    }} arr[N];int n;double l, v;int main(){    while(scanf("%d", &n), n){        scanf("%lf %lf", &l, &v);        for(int i = 0; i < n; ++i){            char dir, name[333];            scanf(" %c %lf %s", &dir, &arr[i].pos, name);            arr[i].name = string(name);            if(dir == 'n' || dir == 'N') arr[i].pos = -arr[i].pos;        }        sort(arr, arr + n);        double maxd = 0.0; int id = 0; bool right = true;        for(int i = 0; i < n; ++i){            double nd = (arr[i].pos < 0.0 ? 0 : l) - arr[i].pos;            if(nd > maxd){                maxd = nd;                id = i;                right = arr[i].pos > 0.0;            }        }        int cnt = 0;        if(right){            for(int i = id; i < n; ++i) cnt += arr[i].pos < 0.0;            id += cnt;        }        else{            for(int i = id; i >= 0; --i) cnt += arr[i].pos > 0.0;            id -= cnt;        }        printf("%13.2f %s\n", (int)(maxd / v * 100) / 100.0, arr[id].name.c_str());    }    return 0;}

Subset

#include #include 
     
      #include 
      
       using namespace std;typedef long long ll;const int N = 44;ll _abs(const ll& x){ return x >= 0 ? x : -x; }int n; ll arr[N];int main(){    while(scanf("%d", &n), n){        for(int i = 0; i < n; ++i) scanf("%lld", &arr[i]);        map
       
         ma;        pair
        
          ans(_abs(arr[0]), 1);        for(int i = 0; i < (1 << (n >> 1)); ++i){            ll sum = 0; int num = 0;            for(int j = 0; j < (n >> 1); ++j)                if((i >> j) & 1){                    sum += arr[j];                    ++num;                }            if(num == 0) continue;            ans = min(ans, make_pair(_abs(sum), num));            map
         
          ::iterator it = ma.find(sum); if(it == ma.end()) ma[sum] = num; else it->second = min(it->second, num); } for(int i = 0; i < (1 << (n - (n >> 1))); ++i){ ll sum = 0; int num = 0; for(int j = 0; j < (n - (n >> 1)); ++j) if((i >> j) & 1){ sum += arr[j + (n >> 1)]; ++num; } if(num == 0) continue; ans = min(ans, make_pair(_abs(sum), num)); map
          
           ::iterator it = ma.lower_bound(-sum); if(it != ma.end()) ans = min(ans, make_pair(_abs(sum + it->first), num + it->second)); if(it != ma.begin()) --it, ans = min(ans, make_pair(_abs(sum + it->first), num + it->second)); } printf("%lld %d\n", ans.first, ans.second); } return 0;}

Sumsets

#include #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N = 1111, INF = 0x3f3f3f3f;int n, arr[N];struct book{    int val, i, j;    book(){};    book(int vv, int ii, int jj): val(vv), i(ii), j(jj) {};    const bool operator < (const book& o) const {        return val < o.val;    }    const bool operator > (const book& o) const {        return val > o.val;    }    const bool operator != (const book& o) const {        return i != o.i && j != o.j && i != o.j && j != o.i;    }};int main(){    while(scanf("%d", &n), n){        int ans = -INF;        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);        vector
        
          left, right;        for(int i = 0; i < n; ++i) for(int j = i + 1; j < n; ++j) left.push_back(book(arr[i] + arr[j], i, j));        for(int i = 0; i < n; ++i) for(int j = i + 1; j < n; ++j){            right.push_back(book(arr[i] - arr[j], i, j));            right.push_back(book(arr[j] - arr[i], j, i));        }        sort(left.begin(), left.end());        sort(right.begin(), right.end());        for(vector
         
          ::iterator it = left.begin(); it != left.end(); ++it){ vector
          
           ::iterator itl = lower_bound(right.begin(), right.end(), *it); vector
           
            ::iterator itr = upper_bound(itl, right.end(), *it); while(itl != itr){ if(*it != *itl) ans = max(ans, arr[itl->j] + it->val); ++itl; } } if(ans == -INF) puts("no solution"); else printf("%d\n", ans); } return 0;}

Paint Color

#include 
    
     using namespace std;const int N = 1002;const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};int h, w, n, X1[N], X2[N], Y1[N], Y2[N], fild[N<<1][N<<1];int compress(int* x1, int* x2, int W){    vector
     
       xs;    for(int i = 0; i < n; ++i) xs.push_back(x1[i]), xs.push_back(x2[i]);    xs.push_back(0); xs.push_back(W);    sort(xs.begin(), xs.end());    xs.erase(unique(xs.begin(), xs.end()), xs.end());    for(int i = 0; i < n; ++i){        x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();        x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();    }    return xs.size() - 1;}void imos(){    memset(fild, 0, sizeof(fild));    for(int i = 0; i < n; ++i){        ++fild[Y1[i]][X1[i]];        --fild[Y1[i]][X2[i]];        ++fild[Y2[i]][X2[i]];        --fild[Y2[i]][X1[i]];    }    for(int i = 0; i < h; ++i) for(int j = 1; j < w; ++j) fild[i][j] += fild[i][j-1];    for(int i = 1; i < h; ++i) for(int j = 0; j < w; ++j) fild[i][j] += fild[i-1][j];}int bfs(){    int ans = 0;    for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j){        if(fild[i][j]) continue;        ++ans;        queue
      
       
         > q;        q.push(make_pair(i, j));        fild[i][j] = 1;        while(!q.empty()){            int x = q.front().first, y = q.front().second;            q.pop();            for(int d = 0; d < 4; ++d){                int xx = x + dx[d], yy = y + dy[d];                if(xx < 0 || h <= xx || yy < 0 || w <= yy || fild[xx][yy]) continue;                q.push(make_pair(xx, yy));                fild[xx][yy] = 1;            }        }    }    return ans;}int main(){    while(~scanf("%d %d", &w, &h)){        if(w == 0 && h == 0) break;        scanf("%d", &n);        for(int i = 0; i < n; ++i) scanf("%d %d %d %d", &X1[i], &Y1[i], &X2[i], &Y2[i]);        w = compress(X1, X2, w);        h = compress(Y1, Y2, h);        imos();        printf("%d\n", bfs());    }    return 0;}

Asteroids

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 100010;int n, k;vector
       
         G[N<<1];int match[N];bool used[N];bool dfs(int v){    used[v] = true;    for(int i = 0; i < G[v].size(); ++i){        int u = G[v][i], w = match[u];        if(w < 0 || (!used[w] && dfs(w))){            match[u] = v;            match[v] = u;            return true;        }    }    return false;}int bipartite_matching(){    int ans = 0;    memset(match, -1, sizeof(match));    for(int i = 0; i < n; ++i){        if(match[i] < 0){            memset(used, false, sizeof(used));            if(dfs(i)) ++ans;        }    }    return ans;}int main(){    scanf("%d %d", &n, &k);    while(k--){        int x, y;        scanf("%d %d", &x, &y);        G[x-1].push_back(y+n-1);        G[y+n-1].push_back(x-1);    }    n <<= 1;    printf("%d\n", bipartite_matching());    return 0;}

转载于:https://www.cnblogs.com/book-book/p/6041272.html

你可能感兴趣的文章

IBM x3850 RAID5数据恢复方案及过程

查看>>

移动计算领域五大机遇：交通运输优势待挖掘

查看>>

如何把win7 旗舰版升级到sp1最新版本

查看>>