A – K-City

Time limit : 2sec / Memory limit : 256MB

Score : 100 points

Problem Statement

In K-city, there are n streets running east-west, and m streets running north-south. Each street running east-west and each street running north-south cross each other. We will call the smallest area that is surrounded by four streets a block. How many blocks there are in K-city?

Constraints

  • 2 or less n, m, 100 or less

Input

Input is given from Standard Input in the following format:

n m
Copy the code

Output

Print the number of blocks in K-city.

Sample Input 1

Copy

3, 4,Copy the code

Sample Output 1

Copy

6
Copy the code

There are six blocks, as shown below:

Sample Input 2

Copy

2 2
Copy the code

Sample Output 2

Copy

1
Copy the code

There are one block, as shown below:

Title links: abc069. Contest. Atcoder. Jp/tasks/abc06…

Ans =(a-1)*(b-1)

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline int read() 5 { 6 int x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 inline void write(int x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9) 29 { 30 write(x/10); 31 } 32 putchar(x%10+'0'); 33 } 34 int main() 35 { 36 int a,b; 37 cin>>a>>b; 38 cout<<(a-1)*(b-1)<<endl; 39 return 0; 40}Copy the code

B – i18n

Time limit : 2sec / Memory limit : 256MB

Score : 200 points

Problem Statement

The word internationalization is sometimes abbreviated to i18n. This comes from the fact that there are 18 letters between the first i and the last n.

You are given a string s of length at least 3 consisting of lowercase English letters. Abbreviate s in the same way.

Constraints

  • 3 or less | s | 100 or less (|s| denotes the length of s.).
  • s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
Copy the code

Output

Print the abbreviation of s.

Sample Input 1

Copy

internationalization
Copy the code

Sample Output 1

Copy

i18n
Copy the code

Sample Input 2

Copy

smiles
Copy the code

Sample Output 2

Copy

s4s
Copy the code

Sample Input 3

Copy

xyz
Copy the code

Sample Output 3

Copy

x1z
Copy the code

Title links: abc069. Contest. Atcoder. Jp/tasks/abc06…

Analysis: Output the first one, the last one is good

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline int read() 5 { 6 int x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 inline void write(int x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9) 29 { 30 write(x/10); 31 } 32 putchar(x%10+'0'); 33 } 34 char s[105]; 35 int main() 36 { 37 cin>>s; 38 int len=strlen(s); 39 cout<<s[0]<<len-2<<s[len-1]<<endl; 40 return 0; 41}Copy the code

C – 4-adjacent

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have a sequence of length N, a=(a1,a2… ,aN). Each ai is a positive integer.

Snuke’s objective is to permute the element in a so that the following condition is satisfied:

  • For each 1 I N - 1 or less or less, the product of ai and ai+1 is a multiple of 4.

Determine whether Snuke can achieve his objective.

Constraints

  • 2 N acuities were 105 or less
  • ai is an integer.
  • 1 ai or less 109 or less

Input

Input is given from Standard Input in the following format:

N a1, a2... aNCopy the code

Output

If Snuke can achieve his objective, print Yes; otherwise, print No.

Sample Input 1

Copy

3 1 to 10, 100Copy the code

Sample Output 1

Copy

Yes
Copy the code

One solution is (1,100,10).

Sample Input 2

Copy

4, 1, 2, 3, 4Copy the code

Sample Output 2

Copy

No
Copy the code

It is impossible to permute a so that the condition is satisfied.

Sample Input 3

Copy

3 1 April 1Copy the code

Sample Output 3

Copy

Yes
Copy the code

The condition is already satisfied initially.

Sample Input 4

Copy

2
1 1
Copy the code

Sample Output 4

Copy

No
Copy the code

Sample Input 5

Copy

6, 2, 7, 1, 8, 2, 8Copy the code

Sample Output 5

Copy

Yes
Copy the code

Title links: abc069. Contest. Atcoder. Jp/tasks/arc08…

Analysis: count multiples of 4, multiples of 2 and other multiples of these two, and then two multiples of 2 equal multiples of 4, and that’s it!

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline int read() 5 { 6 int x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 inline void write(int x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9) 29 { 30 write(x/10); 31 } 32 putchar(x%10+'0'); 33 } 34 int main() 35 { 36 int n; 37 cin>>n; 38 int a=0,b=0,c=0; 39 for(int i=0; i<n; i++) 40 { 41 ll x; 42 x=read(); 43 if(x%4==0) 44 a++; 45 else if(x%2==0) 46 b++; 47 else c++; 48 } 49 if(b>0) 50 c++; 51 if(a+1>=c) 52 cout<<"Yes"<<endl; 53 else 54 cout<<"No"<<endl; 55 return 0; 56}Copy the code

D – Grid Coloring

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

Snuke is painting these squares in colors 1, 2,… , N. Here, the following conditions should be satisfied:

  • For each i (1 I N or less or less), there are exactly ai squares painted in Color i. Here, A1 + a2 +... +aN=HW.
  • For each i (1 I N or less or less), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.

Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.

Constraints

  • 1 H or less, W 100 or less
  • 1 N HW or less or less
  • Ai 1 or more
  • A1 + a2 +... +aN=HW

Input

Input is given from Standard Input in the following format:

H W N A1 A2... aNCopy the code

Output

Print one way to paint the squares that satisfies the conditions. Output in the following format:

C11... C1W: cH1... cHWCopy the code

Here, cij is the color of the square at the i-th row from the top and j-th column from the left.

Sample Input 1

Copy

2, 2, 3, 2, 1, 1Copy the code

Sample Output 1

Copy

1 1
2 3
Copy the code

Below is an example of an invalid solution:

1 2
3 1
Copy the code

This is because the squares painted in Color 1 are not 4-connected.

Sample Input 2

Copy

3, 5, 5, 1, 2, 3, 4, 5Copy the code

Sample Output 2

Copy

4. I'm sorryCopy the code

Sample Input 3

Copy

1 1
1
1
Copy the code

Sample Output 3

Copy

1
Copy the code

Title links: abc069. Contest. Atcoder. Jp/tasks/arc08…

Analysis: from one point to all other points, a straight horizontal fill seems too much

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline int read() 5 { 6 int x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 inline void write(int x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9) 29 { 30 write(x/10); 31 } 32 putchar(x%10+'0'); 33 } 34 int w,h,n; 35 int s[105][105]; 36 int cnt[10005]; 37 int main() 38 { 39 h=read(); 40 w=read(); 41 n=read(); 42 for(int i=1; i<=n; i++) 43 cnt[i]=read(); 44 int k=1; 45 for(int i=1; i<=h; i++) 46 { 47 if(i%2==1) 48 { 49 for(int j=1; j<=w; j++) 50 { 51 if(cnt[k]==0) 52 k++; 53 cnt[k]--; 54 s[i][j]=k; 55 } 56 } 57 else 58 { 59 for(int j=w; j>0; j--) 60 { 61 if(cnt[k]==0) 62 k++; 63 cnt[k]--; 64 s[i][j]=k; 65 } 66 } 67 } 68 for(int i=1; i<=h; i++) 69 { 70 for(int j=1; j<=w; j++) 71 printf("%d ",s[i][j]); 72 printf("\n"); 73 } 74 return 0; 75}Copy the code