Codeforces Round #318(Div 1) 573A, 573B,573C-白红宇

Codeforces Round #318(Div 1) 573A, 573B,573C

阅读量：5291 次

发布时间：2019-06-14

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

转载请注明出处： ——by fraud

这场的前两题完全是手速题。。。A题写了7分钟，交的时候已经500+了，好在B题出的速度勉强凑活吧，and C题也没有FST

Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are n players (including Limak himself) and right now all of them have bids on the table. i-th of them has bid with size ai dollars.

Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?

Input

First line of input contains an integer n (2 ≤ n ≤ 105), the number of players.

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109) — the bids of players.

Output

Print "Yes" (without the quotes) if players can make their bids become equal, or "No" otherwise.

Sample test(s)

input

4 75 150 75 50

output

Yes

input

3 100 150 250

output

No

Note

In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.

It can be shown that in the second sample test there is no way to make all bids equal.

A题没啥好说的，把因为可以乘2或乘三，那只要看看除了2和3之外，其他的因子是否相同即可

1 //##################### 2 //Author:fraud 3 //Blog: http://www.cnblogs.com/fraud/ 4 //##################### 5 //#pragma comment(linker, "/STACK:102400000,102400000") 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 #include 
            
             13 #include 
             
              14 #include 
              
               15 #include 
               
                16 #include 
                
                 17 #include 
                 
                  18 #include 
                  
                   19 #include 
                   20 #include 
                    
                     21 #include 
                     
                      22 #include 
                      
                       23 #include 
                       
                        24 #include 
                        
                         25 #include 
                         
                          26 using namespace std;27 #define XINF INT_MAX28 #define INF 0x3FFFFFFF29 #define mp(X,Y) make_pair(X,Y)30 #define pb(X) push_back(X)31 #define rep(X,N) for(int X=0;X
                          
                           =L;X--)34 #define clr(A,X) memset(A,X,sizeof(A))35 #define IT iterator36 typedef long long ll;37 typedef pair
                           
                             PII;38 typedef vector
                            
                              VII;39 typedef vector
                             
                               VI;40 int a[100010];41 int main()42 {43 ios::sync_with_stdio(false);44 int n;45 cin>>n;46 rep(i,n){47 cin>>a[i];48 while(a[i]%2==0)a[i]/=2;49 while(a[i]%3==0)a[i]/=3;50 }51 int ff = 0;52 rep(i,n-1)if(a[i]!=a[i+1])ff = 1;53 if(ff)cout<<"No"<

代码君

Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built n towers in a row. The i-th tower is made of hi identical blocks. For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.

Input

The first line contains single integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers h1, h2, ..., hn (1 ≤ hi ≤ 109) — sizes of towers.

Output

Print the number of operations needed to destroy all towers.

Sample test(s)

input

6 2 1 4 6 2 2

output

input

7 3 3 3 1 3 3 3

output

Note

The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.

$\text{[math]}$

After first operation there are four blocks left and only one remains after second operation. This last block is destroyed in third operation.

同样很水，从左到右以及从右到左各扫一遍即可

1 //##################### 2 //Author:fraud 3 //Blog: http://www.cnblogs.com/fraud/ 4 //##################### 5 //#pragma comment(linker, "/STACK:102400000,102400000") 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 #include 
            
             13 #include 
             
              14 #include 
              
               15 #include 
               
                16 #include 
                
                 17 #include 
                 
                  18 #include 
                  
                   19 #include 
                   20 #include 
                    
                     21 #include 
                     
                      22 #include 
                      
                       23 #include 
                       
                        24 #include 
                        
                         25 #include 
                         
                          26 using namespace std;27 #define XINF INT_MAX28 #define INF 0x3FFFFFFF29 #define mp(X,Y) make_pair(X,Y)30 #define pb(X) push_back(X)31 #define rep(X,N) for(int X=0;X
                          
                           =L;X--)34 #define clr(A,X) memset(A,X,sizeof(A))35 #define IT iterator36 typedef long long ll;37 typedef pair
                           
                             PII;38 typedef vector
                            
                              VII;39 typedef vector
                             
                               VI;40 int h[100010];41 int dp[100010];42 int dp2[100010];43 int main()44 {45 ios::sync_with_stdio(false);46 int n;47 cin>>n;48 rep(i,n)cin>>h[i];49 int maxx = 0;50 dp[0] = dp2[n-1] = 1;51 rep2(i,1,n-1)dp[i] = min(h[i],dp[i-1]+1);52 dep(i,n-2,0)dp2[i] = min(h[i],dp2[i+1]+1);53 rep(i,n)dp[i] = min(dp[i],dp2[i]);54 rep(i,n)maxx = max(dp[i],maxx);55 cout<
                              
                               <

代码君

Limak is a little bear who learns to draw. People usually start with houses, fences and flowers but why would bears do it? Limak lives in the forest and he decides to draw a tree.

Recall that tree is a connected graph consisting of n vertices and n - 1 edges.

Limak chose a tree with n vertices. He has infinite strip of paper with two parallel rows of dots. Little bear wants to assign vertices of a tree to some n distinct dots on a paper so that edges would intersect only at their endpoints — drawn tree must be planar. Below you can see one of correct drawings for the first sample test.

$\text{[math]}$

Is it possible for Limak to draw chosen tree?

Input

The first line contains single integer n (1 ≤ n ≤ 105).

Next n - 1 lines contain description of a tree. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) denoting an edge between vertices ai and bi. It's guaranteed that given description forms a tree.

Output

Print "Yes" (without the quotes) if Limak can draw chosen tree. Otherwise, print "No" (without the quotes).

Sample test(s)

input

8 1 2 1 3 1 6 6 4 6 7 6 5 7 8

output

Yes

input

13 1 2 1 3 1 4 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13

output

No

一开始少考虑了一些，然后只是判断儿子不符合的情况，然后还有一些漏考虑的细节。

统计有多少个一定要占一半边的子树，如果超过两个，那就是不符合的。

树形dp，第一次dfs统计好所有子树，第二遍，把根的信息传下来一起考虑就ok了。

1 //##################### 2 //Author:fraud 3 //Blog: http://www.cnblogs.com/fraud/ 4 //##################### 5 //#pragma comment(linker, "/STACK:102400000,102400000") 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 #include 
           
            13 #include 
            
             14 #include 
             
              15 #include 
              
               16 #include 
               
                17 #include 
                
                 18 #include 
                 
                  19 #include 
                  20 #include 
                   
                    21 #include 
                    
                     22 #include 
                     
                      23 #include 
                      
                       24 #include 
                       
                        25 #include 
                        
                         26 using namespace std;27 #define XINF INT_MAX28 #define INF 0x3FFFFFFF29 #define mp(X,Y) make_pair(X,Y)30 #define pb(X) push_back(X)31 #define rep(X,N) for(int X=0;X
                         
                          =L;X--)34 #define clr(A,X) memset(A,X,sizeof(A))35 #define IT iterator36 typedef long long ll;37 typedef pair
                          
                            PII;38 typedef vector
                           
                             VII;39 typedef vector
                            
                              VI;40 vector
                             
                              G[100010];41 int dp[100010];42 int ff = 0;43 void dfs(int u,int fa){44 int num = 0;45 int sz = G[u].size();46 rep(i,sz){47 int v = G[u][i];48 if(v == fa)continue;49 dfs(v,u);50 dp[u] += dp[v];51 num++; 52 }53 if(!dp[u])dp[u] = 1;54 if(dp[u] == 2 && num == 1)dp[u]++;55 }56 void dfs2(int u,int fa,int num){57 int sz = G[u].size();58 int n = 0;59 if(num>2)n++;60 rep(i,sz){61 int v = G[u][i];62 if(v == fa)continue;63 int tmp = 1;64 tmp = max(num+dp[u]-dp[v],tmp);65 if(tmp == 2 && num == 2)tmp = 3;66 dfs2(v,u,tmp);67 if(dp[v]>2)n++;68 }69 if(n>2)ff = 1;70 }71 72 int main()73 {74 ios::sync_with_stdio(false);75 int n;76 cin>>n;77 int u,v;78 rep(i,n-1){79 cin>>u>>v;80 u--;v--;81 G[u].pb(v);82 G[v].pb(u);83 }84 dfs(0,-1);85 dfs2(0,-1,0);86 87 88 if(ff)cout<<"No"<