2016-2017 ACM Central Region of Russia Quarterfinal Programming Contest

A. Fried Fish

题意：有N条鱼，有一个同时可以煎k条鱼的锅，鱼两个面都要煎；

分析：k*2个面要煎，是否有一种方式可以让锅没有空闲，当时我举了几个例子，确实可以找到，没有证明，注意n<k的情况

#include 
    
     #include 
     
      #include 
      
       using namespace std;int main(){    freopen("INPUT.TXT","r",stdin);    freopen("OUTPUT.TXT","w",stdout);    int x,y;    while(scanf("%d%d",&x,&y)!= EOF)    {        if(2*x<=y)        printf("2\n");        else        {            if((2*x)%y==0)            printf("%d\n",(2*x)/y);            else            printf("%d\n",(2*x)/y+1);        }    }    return 0;}
      
     
    

B. Hanoi tower

题意：用给出的汉诺塔算法，求出第一次相同时的步数；

分析：

网上有一个公式：先求出n层从A到B的步数：d(n)=d(n-1)*2+1

然后：ans(n)= d(n/3*2-1)+d(n/3-1)+1

勉强这个方案可以看懂，的确要比ans(n)=d(n/32)+d(n/3)或者 2d(n/3) 要小，

但是，最后有一个特判，不是很懂；

回到原题，直接根据给出的算法，打表求解，前几项分别是:

2 9 38 135 542 2079

直接给出公式把：强烈推荐python 写大整数

a = [0]*105#print aa[1] = 2a[2] = 9deta = 97for i in range(3,103):    if i%2==1:        a[i] = a[i-1]*4+2    else:        a[i] = a[i-1]+deta        deta = 16*deta - 15cin = open("input.txt","r")cout = open("output.txt","w")n = int(int(cin.read())/3)cout.write(str(a[n]))

打表程序：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long ll;int k;int ans;int num[3];void hanoi(char x,char y,char z,int n) { if(n>0) { hanoi(x,z,y,n-1); printf("------->%d: %d%d%d\n",k++,--num[x-'a'],++num[y-'a'],num[z-'a']); //k++; //num[x-'a']--; //num[y-'a']++; //if(num[x-'a']==num[y-'a']&&num[y-'a']==num[z-'a']) { // ans = k; //return ; //} hanoi(z,y,x,n-1); }}int main(){ freopen("output.txt","w",stdout); int n; scanf("%d",&n); k = 1; num[0] = n; hanoi('a','b','c',n); printf("%d\n",ans); return 0;}
           
          
         
        
       
      
     
    

D. Weather Station

题意：有8个方向，给出一个字符串，求这个字符串可能是几种方案合成的

分析：乘法原理，d(i) 是前 i 项字符的方案数，当i+1 个字符串可能模棱两可，那么这里就有两种可能，于是：d(i+1)= d(i)*2

#include 
    
     using namespace std;const int maxn = 100000 + 5;char str[maxn];const int MOD = 1000000000+7;int main(){        freopen("input.txt","r",stdin);    freopen("output.txt","w",stdout);    scanf("%s",str);    int len = strlen(str);    int ans = 1;    for(int i=0;i
    

E. Cupcakes

题意：有n个学生，来排队吃蛋糕k个，领完后又到队列后面可以继续吃，每个学生最多能吃a_i个，有一个大胃王，每次都吃完a_i，现在大家想让他吃的时候恰好没有蛋糕了，求是不是可能；

分析：贪心极端情况，当轮到大胃王吃的时候，如果，前面的人最少，最多能吃[l,r]个，k在个区间，于是就可以做到；

#include 
    
     using namespace std;const int maxn = 100000+5;long long a[maxn];int main(){    freopen("input.txt","r",stdin);    freopen("output.txt","w",stdout);    int n;    long long k;    scanf("%d%lld",&n,&k);    long long x = 0;    int flag = -1;    for(int i=0;i
     
      x) {            flag = i;            x = max(x,a[i]);        }    }    long long l = 0,r=0;    for(int i=0;i
      
       =k) {        puts("YES");        return 0;    }    while(l<=r) {        l+=x;        r+=x;        for(int i=flag+1;i
       
        =k) {            puts("YES");            return 0;        }        else if(l>k)            break;    }    puts("KEK");    return 0;}
       
      
     
    

G. Sphenic numbers

题意：一个数是否是三个素数的乘积

分析：直接质因数分解

#include
    
     using namespace std;const int maxn = 10467397 + 105;vector
     
       primes;bool bo[maxn+5];int prime_table() {    int i,j,cnt=0;    bo[0]=bo[1]=true;    for(i=2; i<=sqrt(maxn*1.0); i++)        if(!bo[i]) {            j=i*i;            for(; j<=maxn; j+=i)                bo[j]=true;        }    for(i=0; i<=maxn; i++)        if(!bo[i])            primes.push_back(i);    return primes.size();}bool add_int(int n){    int e = 0;    for(int i = 0; i < primes.size(); i++){        bool f = true;        while(n % primes[i] == 0){            n /= primes[i];            if(f){                f = false;                e++;            }        }        if(n == 1)            return e == 3;    }}int main() {//    freopen("in.txt", "r", stdin);    freopen("input.txt", "r", stdin);    freopen("output.txt", "w", stdout);    int n;    prime_table();    scanf("%d", &n);    puts(add_int(n) ? "YES" : "NO");    return 0;}
     
    

H. Non-random numbers

题意：生成一个n位的随机数，有多少种数，有三条规则：

• 没有前导零
• 第 i 位 不是 i
• n 位

分析：第一位8种，后面9种，再后面10种，不用写大整数.

#include 
    
     using namespace std;int main(){    freopen("input.txt","r",stdin);    freopen("output.txt","w",stdout);    int n;    scanf("%d",&n);    unsigned long long ans = 1;    if(n<=9) {        n--;        ans = 8;        for(int i=0;i
    

J. Architect of Your Own Fortune

题意：有两种票，可以折叠起来拼成一种超级幸运票，求最多能匹配多少张？

分析：最大匹配

#include 
    
     using namespace std;const int maxn = 500+5;struct BPM{    int n,m;    vector
     
       G[maxn];    int left[maxn];    bool T[maxn];    int right[maxn];    bool S[maxn];    void init(int n,int m)    {        this->n = n;        this->m = m;        for(int i=0; i