بررسی سوالات مسابقه ZOJ Monthly Contest, Feburary 2009

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
 
int board[7][7], m, n, t;
int result;
 
void bt( int idx, int diff ) {
    if( idx == n ) 
        result = min( result, abs( diff ) );
    else {
        for( int i = 0; i < m - 1; i ++ ) {
            int a = board[idx][ i ];
            int b = board[idx][ m - 1 ] - a;
            bt( idx + 1, diff + b - a );
        }
    }
}
 
int main() {
    while( cin >> n >> m ) {
        for( int i = 0; i < n; i ++ )
            for( int j = 0; j < m; j ++ ) {
                cin >> board[i][j];
                if( j > 0 )
                    board[i][j] += board[i][j - 1];
            }
        cin >> t;
        result = 0x7fffffff;
        bt( 0, 0 );
        if( result <= t ) 
            cout << result << endl;
        else
            cout << "You'd better buy another one!" << endl;
    }
    return 0;
}

double L = 0, R = 1e9;
while( L < R - 1e-6 ) 
	if( check( (L + R) * 0.5 ) )
		 R = (L + R) * 0.5;
	else
		 L = (L + R) * 0.5;
cout.precision(10);
cout.setf(ios::fixed | ios::showpoint);
cout << L << endl;

bool mark[10];
 
bool bt( int idx, double xa, double xb, double ya, double yb, double r ) {
    if( xb < xa || yb < ya )
        return false;
    if( idx == n )
        return true;
    for( int i = 0; i < n; i ++ )
        if( !mark[i] ) {
            mark[i] = true;
            if( bt( idx + 1, 
                    max(xa, x[i] - max(0., r - idx * t) * vx) , 
                    min(xb, x[i] + max(0., r - idx * t) * vx) ,
                    max(ya, y[i] - max(0., r - idx * t) * vy) , 
                    min(yb, y[i] + max(0., r - idx * t) * vy) , r) )
                return true;
            mark[i] = false;
        }
    return false;
}
 
bool check( double r ) {
    memset( mark, 0, sizeof mark );
    return bt( 0, -1e10, 1e10, -1e10, 1e10, r );
}

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 300;
 
int n, m, rel[N][N], mat[N][N], a, b, arr[N];
 
int main() {
    while( scanf("%d %d", &n, &m) == 2 ) {
        memset( rel, 0, sizeof rel );
        for( int i = 0; i < m; i ++ ) {
            scanf("%d %d", &a, &b);
            rel[a][b] = rel[b][a] = true;
        }
        for( int i = 0; i < n; i ++ )
            scanf("%d", &arr[i]);
        for( int i = n-1; i >= 0; i -- )
            for( int j = i; j < n; j ++ )
                if( i == j )
                    mat[i][j] = 1;
                else {
                    mat[i][j] = 1 + mat[i+1][j];
                    for( int k = i + 1; k <= j; k ++ ) {
                        if( k < j ) mat[i][j] = min( mat[i][j], mat[i][k] + mat[k + 1][j] );
                        if( rel[arr[i]][arr[k]] ) 
                            if( k == i + 1 || mat[i+1][k-1] == 0 ){
                                int t = 0;
                                if( k < j )
                                    t += mat[k+1][j];
                                mat[i][j] = min( mat[i][j], t );
                            }
                    }
                }
        printf("%d\n", n - mat[0][n-1]);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N = 501;
 
int dp[N];
int n, m;
bool mat[N][N];
 
int main() {
    dp[0] = 0;
    dp[1] = 1;
    for( int i = 2; i < N; i ++ ) {
        dp[i] = 0;
        for( int j = 0; j < i-1; j ++ ) {
            int t = min(dp[j] + dp[i-j-1], dp[j+1] + dp[i-j-2]);
            dp[i] = max(dp[i], t);
        }
    }
    while( scanf("%d %d", &n, &m) == 2 ) {
        memset(mat, 0, sizeof mat);
        for( int i = 0; i < m; i ++ ) {
            int a, b;
            scanf("%d %d", &a, &b);
            mat[a][b] = mat[b][a] = true;
        }
        int cnt = 1, result = 0;
        for( int i = 1; i < n; i ++ ) 
            if( mat[i-1][i] )
                cnt ++;
            else {
                result += dp[cnt];
                cnt = 1;
            }
        result += dp[cnt];
        printf("%d\n", result);
    }
    return 0;
}

for( n = 1; n < N; n ++ ) 
	for( idx = 0; idx < n; idx ++ ) {
		 memset( mat, -1, sizeof mat );
		 result += solve( N-1, eq, eq ) * 1. / n;
	}

cout << result / (b - a + 1) << endl;

enum {
    eq = 0,
    le = 1,
    gr = 2
};

int solve( int s, int c1, int c2 ) {
    if( c1 == le || c2 == gr )
        return 0;
    if( s == -1 ) {
        return 1;
    }
    int& result = mat[s][c1][c2];
    if( result == -1 ) {
        result = 0;
        if( s != idx && s != n - 1 )
            result += solve( s - 1, update(sa, s, c1, 0), update(sb, s, c2, 0) );
        if( s < n )
            result += solve( s - 1, update(sa, s, c1, 1), update(sb, s, c2, 1) );
    }
    return result;
}

int update( string& s, int idx, int pre_c, int bit ) {
    if( pre_c != eq )
        return pre_c;
    if( bit > s[idx] - '0' )
        return gr;
    else if( bit < s[idx] - '0' )
        return le;
    else
        return eq;
}

#include <iostream>
using namespace std;
 
int n, x, y;
 
int main() {
    while( cin >> n >> x >> y )
        cout << n - 1 << endl;
    return 0;
}

const int invalid = 0x7fffffff;

void add_inf( vector<int>& v, int price, int value ) {
    for( int i = 0; i + price < v.size(); i ++ )
        if( v[i] != invalid )
            if( v[i + price] == invalid || v[i + price] < v[i] + value )
                v[i + price] = v[i] + value;
}

void add_one( vector<int>& v, int price, int value ) {
    for( int i = (int)v.size() - 1 - price; i >= 0; i -- )
        if( v[i] != invalid )
            if( v[i + price] == invalid || v[i + price] < v[i] + value )
                v[i + price] = v[i] + value;
}

void add_k( vector<int>& v, int price, int value, int k ) {
    for( int i = 1; i <= k; i *= 2 ) {
        add_one( v, price * i, value * i );
        k -= i;
    }
    if( k > 0 )
        add_one( v, price * k, value * k );
}

void add( vector<int>& v, int idx ) {
    if( k[idx] == 0 )
        add_inf( v, p[idx], e[idx] );
    else
        add_k( v, p[idx], e[idx], k[idx] );
}

void merge( vector<int>& va, vector<int>& vb ) {
    for( int i = 0; i < va.size(); i ++ )
        if( vb[i] != invalid )
            if( va[i] == invalid || va[i] < vb[i] )
                va[i] = vb[i];
}

int main() {
    while( cin >> n >> d ) {
        for( int i = 0; i < n; i ++ )
            cin >> k[i] >> e[i] >> p[i];
        cin >> g;
        vector<int> result(d+1, invalid);
        result[0] = 0;
        string s; 
        getline( cin, s );
        memset(marked, 0, sizeof marked);
        for( int i = 0; i < g; i ++ ) {
            getline( cin, s );
            istringstream hin( s );
            vector<int> tresult = result;
            while( hin >> a ) {
                vector<int> v = tresult;
                add(v, a-1);
                merge(result, v);
                marked[a-1] = true;
            }
        }
        for( int i = 0; i < n; i ++ )
            if( !marked[i] )
                add( result, i );
        if( result[d] != invalid && result[d] >= 0 )
            cout << result[d] << endl;
        else
            cout << "i'm sorry..." << endl;
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int N = 202;
const int inf = 0x7fffffff;
 
int cap[N][N], flow[N][N];
int adj[N][N], adjc[N];
int par[N], q[N], qc;
 
int m, n, a, b, s;
 
int boy( int x ) { return x; }
int girl( int x ) { return m + x; }
int src( ) { return m + n; }
int trg( ) { return m + n + 1; }
 
void add( int a, int b ) {
    adj[a][adjc[a]++] = b;
    adj[b][adjc[b]++] = a;
}
 
int maxflow( int n, int s, int t ) {
    int result = 0;
    memset( flow, 0, sizeof flow );
    while( true ) {
        memset( par, -1, sizeof par );
        qc = 1;
        par[s] = -2, q[0] = s;
        for( int i = 0; i < qc; i ++ ) {
            int u = q[i];
            for( int j = 0; j < adjc[u]; j ++ ) {
                int v = adj[u][j];
                if( cap[u][v] > flow[u][v] && par[v] == -1 ) {
                    q[qc++] = v;
                    par[v] = u;
                }
            }
        }
        if( par[t] == -1 )
            break;
        int add = inf;
        int u = t;
        while( u != s ) {
            int v = par[u];
            add = min( add, cap[v][u] - flow[v][u] );
            u = v;
        }
        result += add;
        u = t;
        while( u != s ) {
            int v = par[u];
            flow[v][u] += add;
            flow[u][v] -= add;
            u = v;
        }
    }
    return result;
}
 
int solve( vector<int>& vb, vector<int>& vg ) {
    maxflow( m + n + 2, src(), trg() );
    int result = 0;
    for( int i = 0; i < m; i ++ )
        if( par[boy(i)] != -1 ) {
            vb.push_back( i + 1 );
            result += cap[src()][boy(i)];
        }
    for( int i = 0; i < n; i ++ )
        if( par[girl(i)] == -1 ) {
            vg.push_back( i + 1 );
            result += cap[girl(i)][trg()];
        }
    return result;
}
 
int main() {
    bool f = true;
    while( scanf("%d %d %d", &m, &n, &s) == 3 ) {
        if( !f )
            printf("\n");
        f = false;
        memset( adjc, 0, sizeof adjc );
        memset( cap, 0, sizeof cap );
        for( int i = 0; i < m; i ++ ) {
            scanf( "%d", &cap[src()][boy(i)] );
            adj[src()][i] = boy(i);
            add( src(), i );
        }
        for( int i = 0; i < n; i ++ ) {
            scanf( "%d", &cap[girl(i)][trg()] );
            add( girl(i), trg() );
        }
        for( int i = 0; i < s; i ++ ) {
            scanf( "%d %d", &a, &b );
            cap[boy(a-1)][girl(b-1)] = inf;
            add( boy(a-1), girl(b-1) );
        }
        std::vector<int> vboy, vgirl;
        int max_love = solve( vboy, vgirl );
        printf( "%d %d %d\n", max_love, vboy.size(), vgirl.size() );
        for( int i = 0; i < vboy.size(); i ++ ) {
            if( i )
                printf(" ");
            printf("%d", vboy[i]);
        }
        printf("\n");
        for( int i = 0; i < vgirl.size(); i ++ ) {
            if( i )
                printf(" ");
            printf("%d", vgirl[i]);
        }
        printf("\n");
    }
    return 0;
}

#include <cstdio>
#include <cstring>
 
int mat[101][101], n, m, a, b, c, d, hotels[100];
 
int main() {
    while( scanf("%d %d", &n, &c) == 2 ) {
        for( int i = 0; i < c; i ++ )
            scanf("%d", &hotels[i]);
        scanf("%d", &m);
        memset( mat, 0, sizeof mat );
        for( int i = 0; i < m; i ++ ) {
            scanf("%d %d %d", &a, &b, &d);
            if( mat[a][b] == 0 || mat[a][b] > d ) mat[a][b] = d;
        }
        for( int k = 1; k <= n; k ++ )
            for( int i = 1; i <= n; i ++ )
                for( int j = 1; j <= n; j ++ )
                    if( mat[i][k] && mat[k][j] )
                        if( mat[i][j] == 0 || mat[i][j] > mat[i][k] + mat[k][j] )
                            mat[i][j] = mat[i][k] + mat[k][j];
        int result = -1;
        for( int i = 0; i < c; i ++ ) {
            int dist = mat[hotels[i]][hotels[i]];
            if( dist != 0 )
                if( result == -1 || dist < mat[hotels[result]][hotels[result]] )
                    result = i;
        }
        if( result == -1 )
            printf("I will nerver go to that city!\n");
        else
            printf("%d\n", hotels[result]);
    }
    return 0;
}