Codeforces Round #224 (Div. 2)

A. Ksenia and Pan Scales

题意:给出一个字符串,中间用|分割开,再给一个字符串,字符串中的数字要选一下放到左边,剩下的全放右边,使得最后两边字符串等长。

分析:直接模拟。

Codeforces Round #224 (Div. 2)
/****************************************
* File Name: 224a.cpp
* Author: sky0917
* Created Time: 2014年01月17日 23:28:18
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000;

char s[maxn];
int main(){
    while (scanf("%s",s)!=EOF){
        int l = 0; 
        int r = 0;

        int f = 0;
        for (int i=0; s[i]; i++){
            if (s[i] == |) {
                f = 1; 
                continue;
            }
            if (f){
                r++;
            }   
            else{
                l++;
            }
        }
        char str[1000];
        scanf("%s",str);
        int len = strlen(str);
        int t;
        if (l > r) t = l-r;
        else t = r - l;
        
        if (len < t || (len - t)%2 == 1)        {
            printf("Impossible\n");
        }
        else{
            f = 0;
            int j = 0;
            if (l > r){
                f = -1;
                for (int i=0; s[i] != |; i++){
                    printf("%c",s[i]);  
                    f = i;  
                }
                
                for (int i=0; i<(len-t)/2; i++){
                    printf("%c",str[j++]);
                }
                putchar(|);
                for (int i= f+2; s[i]; i++){
                    putchar(s[i]);
                }
                for (int i=0; i<t; i++){
                    putchar(str[j++]);
                }
                for (int i=0; i<(len-t)/2; i++){
                    putchar(str[j++]);
                }
                puts("");
            }
            else{
                f = -1;
                for (int i=0; s[i] != |; i++){
                    printf("%c",s[i]);  
                    f = i;  
                }
                for (int i=0; i<t; i++){
                    putchar(str[j++]);
                }
                for (int i=0; i<(len-t)/2; i++){
                    printf("%c",str[j++]);
                }
                putchar(|);
                for (int i= f+2; s[i]; i++){
                    putchar(s[i]);
                }
                for (int i=0; i<(len-t)/2; i++){
                    putchar(str[j++]);
                }
                puts("");   
            }
        }
    }   
    return 0;
}
View Code

 

B. Number Busters

题意:给出5个数字 a,?b,?w,?x,?c (1?≤?a?≤?2·109,?1?≤?w?≤?1000,?0?≤?b?<?w,?0?<?x?<?w,?1?≤?c?≤?2·109).

        a,b,w,x是第一个人的,c是第二个人的,每次第二个人都将 c - 1 ,第一个人如果 b?≥?x  就执行 b?=?b?-?否则就执行a?=?a?-?1; b?=?w?-?(x?-?b)

        问经过最少多少次之后会出现c <= a

分析:a 和 c 很大,而b 和 w 都比较小,发现经有限次之后b 会变成原来的值,所以考虑找循环节,

        找到一个循环节中经过的次数 ti 和 a  不变的次数 d,那么每经过 ti 次,c就会比a多减 d,

        算出 de = c - a,这个de表示 c 一共要比a多减的次数,先算出经过若干个循环节的次数,de对a

        的余数部分单独计算。

 

Codeforces Round #224 (Div. 2)
/****************************************
* File Name: 224b.cpp
* Author: sky0917
* Created Time: 2014年01月18日  1:03:09
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

long long a, b, w, x, c;
long long de;

long long cal(long long &ad, long long f){

    long long tmp = b;
    long long tot = 0;
    while (1){
        if (ad == de && f){
            return tot;
        }
        if (b >= x){
            ad++;
            b = b - x;
            tot++;
            if (b == tmp){
                return tot;
            }       
        }
        else{
            b = w - (x - b);    
            tot++;
            if (b == tmp){
                return tot;
            }
        }
    }   
}
int main(){
    while (scanf("%I64d %I64d %I64d %I64d %I64d",&a,&b,&w,&x,&c)!=EOF){
        if (c <= a){
            printf("0\n");
            continue;
        }

        de = c - a;
        long long add = 0;
        long long ti = cal(add, 0);
        long long res = 0;
        if (de > add){
            if (de % add != 0){
                res = de / add * ti;
                de = de % add;
            }
            else{
                res = (de - add) / add * ti;
                de = (de - add) % add + add;
            }
        }
        add = 0;
        res += cal(add, 1);     
        printf("%I64d\n",res);
    }
    return 0;
}
View Code

 

C. Arithmetic Progression

题意:给出n 个数字,把这些数字排成有序的一列,然后可以在任何一个位置放上一个数字x,要求使得n+1个数字构成等差数列,问 x 可以是哪些值。

分析:模拟,考虑好特殊的情况。

        当 n = 1 时, 有无数个 x 满足

        当所有数字都一样时

              如果 n = 1, 有无数个 x 满足

          否则 只有一个 x 满足

        当数字不都一样时

      当 n = 2 时,

                       至少有2个满足,一个在最前,一个在最后,如果 中间可以放一个数字的话 就是 有 3个满足

      当 n > 2 时,

                        如果序列中相邻数字的差值超过 2 种, 则有 0 个 x 满足

                        如果序列中相邻的数字的差值是 2 种,分别是 d1, d2

                                       如果 d1 > 1 && d2 > 1 ,那么有 0 种 x 满足

                                       如果 d1 = 1 && d2 > 1, 那么d1 的次数只能出现 1 次,而且 d1是偶数,而且 d1 = d2*2 ,那么就有 3 种 x 满足,否则有 0 种

                                       如果 d1 > 1 && d2 = 1,同上

                                       如果 d1 = 1 && d2 = 1,同上

                        如果序列中相邻的数字的差值是 1 种, 那么有 2 种 x 满足,分别是开头和结尾。

Codeforces Round #224 (Div. 2)
/****************************************
* File Name: 224c.cpp
* Author: sky0917
* Created Time: 2014年01月18日  0:05:12
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;

int a[maxn];
int b[maxn];
int n;
int ans[maxn];
int tp = 0;
int main(){
    while (scanf("%d",&n)!=EOF){
        for (int i=0; i<n; i++){
            scanf("%d",&a[i]);
        }
        if (n == 1){
            printf("-1\n");
            continue;
        }
        sort(a, a+n);
        if (a[0] == a[n-1]){
            printf("1\n");
            printf("%d\n",a[0]);
            continue;
        }
        if (n == 2){
            if ((a[1] - a[0]) % 2 == 0)
                printf("3\n");
            else printf("2\n");

            printf("%d ",a[0] - (a[1]-a[0]));
            if ((a[1] - a[0]) % 2 == 0){
                printf("%d ",(a[1] + a[0]) / 2);
            }
            printf("%d\n",a[1] + (a[1]-a[0]));
            continue;
        }

        int res = 0;
        int d1 = a[1] - a[0];
        int d2 = 0;
        int f1 = 1, f2 = 0;
        for (int i=2; i<n; i++){
            if (a[i] - a[i-1] == d1){
                f1++;   
            }   
            else{
                if (f2 == 0){
                    f2 = 1;
                    d2 = a[i] - a[i-1];
                }
                else{
                    if (a[i] - a[i-1] == d2){
                        f2++;
                    }
                    else{
                        res = -1;
                        printf("0\n");
                        break;
                    }
                }   
            }
        }
        if (res == -1)continue;
        int tp = 0; 
        if (f2 == 0){
            printf("2\n");
            printf("%d %d\n",a[0]-d1,a[n-1]+d1);    
            continue;
        }
        if (f2 == 1){
            if (d1 == d2 * 2 && f1 == 1){
                if (d1 % 2 == 0){
                    printf("1\n");
                    printf("%d\n",a[0] + d1/2);
                }
                else{
                    printf("0\n");
                }
            }   
            else if (d2 == d1 * 2){
                if (d2 % 2 == 0){
                    printf("1\n");
                    for (int i=1; i<n; i++){
                        if (a[i] - a[i-1] == d2){
                            printf("%d\n",a[i] - d2/2);
                            break;
                        }
                    }
                }
                else{
                    printf("0\n");
                }
            }
            else{
                printf("0\n");
            }
            continue;
        }
        if (f2 > 1){
            if (f1 == 1 && d1 == 2*d2 && d1 % 2 == 0){
                printf("1\n");
                printf("%d\n",a[0] + d1/2); 
            }
            else{
                printf("0\n");
            }
        }
    }   
    return 0;
}
View Code

 

D. Ksenia and Pawns

题意:给出类似下面的这种棋盘 grid:

####

#>^#

####

^ v < > 分别表示在那个位置可以走的方向,# 可以放两个棋子,棋子进入该位置后就不能再动,

现在有 2 个 棋子,# 位置可以放 2个棋子,其它位置只能放一个,一开始选定 2 个位置放上这 2 个棋子,然后每次

同时让棋子沿着格子的方向移动,一直到进入# 为止。问两个棋子移动的总次数最多是多少。

分析:如果有环路则总次数无限大,否则如果以最终到达的 # 为根,路径为边,会发现两个棋子的路径是一棵树,问题

       就转化为在一棵树(或一个森林)找两个最长的路径,满足他们在距离叶子相同距离的位置不能有相交,(两条

      路径可以部分重合)

Codeforces Round #224 (Div. 2)
/****************************************
* File Name: 224d.cpp
* Author: sky0917
* Created Time: 2014年01月18日 11:22:46
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2003;
const int INF = 0x1f1f1f1f;

char g[maxn][maxn];
int v[maxn][maxn];
int d[maxn][maxn];
int p[maxn][maxn];
int dir[333];
int n, m;
int f[8] = {-1, 1, 0, 0, 0, 0, -1, 1};
bool flag;
int ma, fa;
inline bool ok(int x, int y){
    return x>=0 && x<n && y>=0 && y<m;  
}
int dfs(int x, int y){

    v[x][y] = 1;
    d[x][y] = INF;
    if (g[x][y] == #){
        d[x][y] = 0;
        return x*m + y;
    }
    int de = dir[g[x][y]];
    int xx = x + f[de];
    int yy = y + f[de+4];
    if (ok(xx, yy)){
        if (v[xx][yy]){ 
            if (d[xx][yy] == INF){
                flag = true;
                return 0;
            }
            else{
                d[x][y] = d[xx][yy] + 1;
                p[x][y] = p[xx][yy];
                if (d[x][y] > ma){
                    fa = p[x][y];
                    ma = d[x][y];
                }
            }
        }
        else{
            p[x][y] = dfs(xx, yy);
            d[x][y] = d[xx][yy] + 1;    
            if (d[x][y] > ma){
                fa = p[x][y];
                ma = d[x][y];
            }
        }
    }
    return p[x][y];
}

int main(){
    
    dir[^] = 0;
    dir[v] = 1;
    dir[<] = 2;
    dir[>] = 3;
    
    while (scanf("%d %d",&n,&m)!=EOF){
        for (int i=0; i<n; i++){
            scanf("%s",g[i]);
        }
        flag = false;
        ma = 0;
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (flag) break;
                if (g[i][j] != # && !v[i][j]){
                     dfs(i, j); 
                }
            }
        }
        if (flag){
            printf("-1\n");
        }
        else{
            if (ma == 0){
                printf("0\n");
                continue;
            }
            int ff = 0;
            for (int i=0; i<n && ff == 0; i++){
                for (int j=0; j<m; j++){
                    if (d[i][j] == ma && p[i][j] != fa){
                        ff = 1;
                        break;  
                    }   
                }
            }   
            if (ff)
                printf("%d\n",ma*2);
            else
                printf("%d\n",ma*2-1);
        }
    }   
    return 0;
}
View Code

Codeforces Round #224 (Div. 2)

上一篇:c89和c99的区别【转】


下一篇:读写INI配置文件