Codeforce 915 A、B、C

A. Garden
【题意】
选择一个桶可以以最少的小时浇满花园,花园不能重复浇.

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=200;
int n,k;
int min_bucket_fill;

int main(){
    while(cin>>n>>k){
        min_bucket_fill=0x3f3f3f3f;
        for(int i=0;i<n;++i){
            int a;
            cin>>a;
            if(k%a==0)min_bucket_fill=min(k/a,min_bucket_fill);
        }
        printf("%d\n",min_bucket_fill);
    }
    return 0;
}

B. Browser
【题意】
给定初始位置,需要使用的页面区间【l,r】,问,从初始位置开始,到关闭所有非区间内标签最少需要多少次点击鼠标.关闭页面也需要点击一次.

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int n,pos,l,r;
int main(){
    while(cin>>n>>pos>>l>>r){
        if(l==1&&r==n){printf("0\n");continue;}
        int ans=0;
        ans=abs(min(abs(pos-l),abs(pos-r))+2+r-l);
        if(l==1)ans=abs(pos-r)+1;
        if(r==n)ans=abs(pos-l)+1;
        printf("%d\n",ans);
    }
    return 0;
}

C. Permute Digits
【题意】
给定a,b.对a进行任意排列,得到小于等于b且大于等于a的c.问这个c最大是多少.
Tip:
注意a,b取值范围是1e18
string数字无法比较大小.

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

long long str_2_num(string str){
    long long reg=0;
    int len=str.size();
    for(int i=0;i<len;++i){
        reg*=10;
        reg+=(str[i]-'0');
    }
    return reg;
}

int main(){
    string a,b;
    string ans;
    while(cin>>a>>b){
        int len=a.size();
        sort(a.begin(),a.end());
        for(int i=0;i<len;++i){
            for(int j=i;j<len;++j){
                string tmp=a;
                swap(tmp[i],tmp[j]);
                sort(tmp.begin()+i+1,tmp.end());
                if(str_2_num(tmp)<=str_2_num(b)&&str_2_num(tmp)>=str_2_num(a))swap(a[i],a[j]);
            }
        }
        cout<<a<<endl;
    }
    return 0;
}

Codeforce 1B Spreadsheet

题意:
26进制的转换,需要注意的是,A <=> 0.所以处理的时候需要注意一下10禁止转26进制的时候是 以(num-1)作为当前数.

另外就是 10转26进制直接从0开始依次*26即可.以及 sscanf() 和 %[A-Z]的用法.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stack>
using namespace std;
const int MAXN=100;
int N;
char Q[MAXN];
//10进制转26进制
void solveToAlpha(){
    stack<char> ans;
    int a,num;
    sscanf(Q,"R%dC%d",&a,&num);
    int i;
    for(i=0;num>0;i++){
        char c=(num-1)%26+'A';
        ans.push(c);
        num=(num-1)/26;
    }
    while(!ans.empty()){
        printf("%c",ans.top());
        ans.pop();
    }
    printf("%d\n",a);
}
//26进制转10进制
void solveToNum(){
    int a;
    char b[MAXN];
    sscanf(Q,"%[A-Z]%d",b,&a);
    long long ans=0;
    int len=strlen(b);
    for(int i=0;i<len;++i){
        ans*=26;
        ans=ans+b[i]-'A'+1;
    }
    printf("R%dC%lld\n",a,ans);
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%s",Q);
        int a,b;
        //sscanf()
        if(sscanf(Q,"R%dC%d",&a,&b)==2){
            solveToAlpha();
        }else{
            solveToNum();
        }
    }
    return 0;
}

Codeforce 1A Theatre Square

题意:
给你一个N*M的矩阵,和a*a的陶瓷,陶瓷不允许被破坏,问最少需要多少陶瓷能铺满矩阵.

#include<cstdio>
#include<iostream>
#include<algorithm>
#define EPS 1e-9
using namespace std;

int n,m,a;

long long up_bound(double s){
    long long ans=s;
    if(s-ans>EPS){
        ans++;
    }
    return ans;
}

int main(){
    while(scanf("%d %d %d",&n,&m,&a)!=EOF){
        long long row = up_bound(1.0*m/a);
        long long column = up_bound(1.0*n/a);
        long long ans=row*column;
        printf("%lld\n",ans);
    }
    return 0;
}

Educational Codeforces Round 25 B

 【题目】

B. Five-In-a-Row

time limit: per test1 second
memory limit: per test256megabytes
input: standard input
output: standard output

Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it’s Alice’s turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.

Input

You are given matrix 10 × 10 (10 lines of 10 characters each) with capital Latin letters ‘X’ being a cross, letters ‘O’ being a nought and ‘.’ being an empty cell. The number of ‘X’ cells is equal to the number of ‘O’ cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.

Output

Print ‘YES’ if it’s possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print ‘NO’.

Examples
Input
XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........
Output
YES
Input
XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........
Output

NO

Link: http://codeforces.com/contest/825/problem/B
【题意】
X是否能在一步以内连成五子.可以则赢.

【题解】

数据量不大,枚举八个方向即可,注意,每次只能往一个方向走,不能拐弯.而且必须枚举八方向,不能只枚举向下的几个方向.
如果找到第一个五子,则往后就不需要计算了.

【Sourcr Code】
github: Educational Codeforces Round 25 B.cpp

#include<bits/stdc++.h>
using namespace std;
char mp[11][11];
bool re;
int d[8][3]={{0,1},{1,0},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};

bool check(int x,int i,int y,int j){
    if(x+i>=0&&x+i<10&&y+j>=0&&y+j<=10)
        return true;
    else return false;
}

void dfs(int x,int y,int win,int ct,int dir){
 //   if(dir==3)
 //       printf("(%d,%d):%d %d\n",x,y,win,dir);
    if(win==5 || re){re=true;return;}
    int i=d[dir][0],j=d[dir][1];
    if(check(x,i,y,j)){
        if(mp[x+i][y+j]=='X') dfs(x+i,y+j,win+1,ct,dir);
        if(mp[x+i][y+j]=='.' && ct==0) dfs(x+i,y+j,win+1,1,dir);
    }
}

int main(){
    re=false;
    for(int i=0;i<10;++i)
        gets(mp[i]);
    for(int i=0;i<10;++i){
        if(re)break;
        for(int j=0;j<10;++j){
            if(mp[i][j]=='X'){
                for(int k=0;k<8;++k){
                    dfs(i,j,1,0,k);
                    if(re)break;
                }
                if(re)break;
            }
        }
    }
    if(re)printf("YES\n");
    else printf("NO\n");
    return 0;
}

/**
....X.....
...X.OOOO.
..X.......
.X........
..........
..........
..........
..........
..........
..........
**/

Educational Codeforces Round 25 A

【题目以及连接】

A. Binary Protocol

time limit per test:1 second
memory limit per test:256 megabytes
input: standard input
output: standard output

Polycarp has just invented a new binary protocol for data transmission. He is encoding positive integer decimal number to binary string using following algorithm:

  • Each digit is represented with number of ‘1’ characters equal to the value of that digit (for 0 it is zero ones).
  • Digits are written one by one in order corresponding to number and separated by single ‘0’ character.

Though Polycarp learnt how to encode the numbers, he has no idea how to decode them back. Help him calculate the decoded number.

Input

The first line contains one integer number n (1 ≤ n ≤ 89) — length of the string s.

The second line contains string s — sequence of ‘0’ and ‘1’ characters, number in its encoded format. It is guaranteed that the number corresponding to the string is positive and doesn’t exceed 109. The string always starts with ‘1’.

Output

Print the decoded number.

Examples
Input
3
111
Output
3
Input
9
110011101
Output

2031

Link: Codeforce Educational Codeforces Round 25 A

【题意】
给出一串二进制字符串,翻译成原来的数字.规则为数字间以单独的0为分隔符.多余的0当做一个0输出,最后有几个0输出几个0.
(后面那个意思蒙出来的,英语渣,有点没搞懂最后一个条件是为什么).
【题解】
逐位记录即可.
【Source Code】
github:Educational Codeforces Round 25 A.cpp
–忽然发现–原来链接中有空格使用%20处理的.但是空格多了,复制的时候不会复制上%20..要手敲

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        char digit,pre='0';
        int cnt=0;
        for(int i=0;i<n;++i){ 
            cin>>digit;
            if(digit=='1') cnt++;
            if(digit=='0') {printf("%d",cnt);cnt=0;}
        }
        if(digit=='1') printf("%d",cnt);
        if(digit=='0') printf("0");
        printf("\n");
    }
    return 0;
}

Codeforces 232A Cycles

【类型】

思路,逻辑题.

【参考】

WannaFlyUnion

【题解】

每次加入一个点时让他先于点1相连,贡献为0,然后与点2相连,贡献为1,与三相连,贡献为2…依此类推.

【Code】

#include <iostream>
using namespace std;
const int MAXN=111;
int mapp[MAXN][MAXN];
int main(){
    int n;
    cin>>n;
    int l=2;
    int ant=0;
    mapp[1][2]=mapp[2][1]=1;
    for(int i=3;i<=100;++i){
        l=max(l,i);
        mapp[i][1]=mapp[1][i]=1;
        //都与点1相连
        for(int j=2;j<i;++j){
            mapp[i][j]=mapp[j][i]=1;
            //比如4个点,2和4连贡献了一个,3和4连贡献了两个…
            ant+=j-1;
            if(ant==n)
                break;
            else if(ant>n){
                ant-=j-1;
                mapp[i][j]=mapp[j][i]=0;
                break;
            }
        }
        if(ant==n)
            break;
    }
    printf(“%d\n”,l);
    for (int i = 1 ; i <= l ; i++)  
    {  
        for (int j = 1 ; j < l ; j++)  
            printf (“%d”,mapp[i][j]);  
        printf (“%d\n”,mapp[i][l]);  
    }  
    return 0;
}