AtCoder Beginner Contest 069【A，水，B，水，C，数学，D，暴力】

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≤n,m≤100

---

Input

Input is given from Standard Input in the following format:

n m

Output

Print the number of blocks in K-city.

---

Sample Input 1

Copy

3 4

Sample Output 1

Copy

6

There are six blocks, as shown below:

---

Sample Input 2

Copy

2 2

Sample Output 2

Copy

1

There are one block, as shown below:

---

题目链接：http://abc069.contest.atcoder.jp/tasks/abc069_a

分析：结论就是ans=(a-1)*(b-1)

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline int read()

 {

     int x=,f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 inline void write(int x)

 {

     if(x<)

     {

         putchar('-');

         x=-x;

     }

     if(x>)

     {

         write(x/);

     }

     putchar(x%+'');

 }

 int main()

 {

     int a,b;

     cin>>a>>b;

     cout<<(a-)*(b-)<<endl;

     return ;

 }

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≤|s|≤100 (|s| denotes the length of s.)
s consists of lowercase English letters.

---

Input

Input is given from Standard Input in the following format:

s

Output

Print the abbreviation of s.

---

Sample Input 1

Copy

internationalization

Sample Output 1

Copy

i18n

---

Sample Input 2

Copy

smiles

Sample Output 2

Copy

s4s

---

Sample Input 3

Copy

xyz

Sample Output 3

Copy

x1z

---

题目链接：http://abc069.contest.atcoder.jp/tasks/abc069_b

分析：输出第一个，最后一个就好咯

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline int read()

 {

     int x=,f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 inline void write(int x)

 {

     if(x<)

     {

         putchar('-');

         x=-x;

     }

     if(x>)

     {

         write(x/);

     }

     putchar(x%+'');

 }

 char s[];

 int main()

 {

     cin>>s;

     int len=strlen(s);

     cout<<s[]<<len-<<s[len-]<<endl;

     return ;

 }

C - 4-adjacent

---

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have a sequence of length N, a=(a₁,a₂,…,a_N). Each a_i 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, the product of a_i and a_i+1 is a multiple of 4.

Determine whether Snuke can achieve his objective.

Constraints

2≤N≤10⁵
a_i is an integer.
1≤a_i≤10⁹

---

Input

Input is given from Standard Input in the following format:

N

a1 a2 … aN

Output

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

---

Sample Input 1

Copy

3

1 10 100

Sample Output 1

Copy

Yes

One solution is (1,100,10).

---

Sample Input 2

Copy

4

1 2 3 4

Sample Output 2

Copy

No

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

---

Sample Input 3

Copy

3

1 4 1

Sample Output 3

Copy

Yes

The condition is already satisfied initially.

---

Sample Input 4

Copy

2

1 1

Sample Output 4

Copy

No

---

Sample Input 5

Copy

6

2 7 1 8 2 8

Sample Output 5

Copy

Yes

---

题目链接：http://abc069.contest.atcoder.jp/tasks/arc080_a

分析：统计4的倍数，2的倍数还有不是这两个的倍数的数，然后2个2的倍数等于4的倍数，然后就这样了！

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline int read()

 {

     int x=,f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 inline void write(int x)

 {

     if(x<)

     {

         putchar('-');

         x=-x;

     }

     if(x>)

     {

         write(x/);

     }

     putchar(x%+'');

 }

 int main()

 {

     int n;

     cin>>n;

     int a=,b=,c=;

     for(int i=;i<n;i++)

     {

         ll x;

         x=read();

         if(x%==)

             a++;

         else if(x%==)

             b++;

         else c++;

     }

     if(b>)

         c++;

     if(a+>=c)

         cout<<"Yes"<<endl;

     else

     cout<<"No"<<endl;

     return ;

 }

D - Grid Coloring

---

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, …, N. Here, the following conditions should be satisfied:

For each i (1≤i≤N), there are exactly a_i squares painted in Color i. Here, a₁+a₂+…+a_N=HW.
For each i (1≤i≤N), 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,W≤100
1≤N≤HW
a_i≥1
a₁+a₂+…+a_N=HW

---

Input

Input is given from Standard Input in the following format:

H W

N

a1 a2 … aN

Output

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

c11 … c1W

:

cH1 … cHW

Here, c_ij 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 1

Sample Output 1

Copy

1 1

2 3

Below is an example of an invalid solution:

1 2

3 1

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

---

Sample Input 2

Copy

3 5

5

1 2 3 4 5

Sample Output 2

Copy

1 4 4 4 3

2 5 4 5 3

2 5 5 5 3

---

Sample Input 3

Copy

1 1

1

1

Sample Output 3

Copy

1

---

题目链接：http://abc069.contest.atcoder.jp/tasks/arc080_b

分析：从一个点可以到达其它所有的点，直接来一个水平填充好像就过了

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline int read()

 {

     int x=,f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 inline void write(int x)

 {

     if(x<)

     {

         putchar('-');

         x=-x;

     }

     if(x>)

     {

         write(x/);

     }

     putchar(x%+'');

 }

 int w,h,n;

 int s[][];

 int cnt[];

 int main()

 {

     h=read();

     w=read();

     n=read();

     for(int i=;i<=n;i++)

         cnt[i]=read();

     int k=;

     for(int i=;i<=h;i++)

     {

         if(i%==)

         {

             for(int j=;j<=w;j++)

             {

                 if(cnt[k]==)

                 k++;

                 cnt[k]--;

                 s[i][j]=k;

             }

         }

     else

     {

         for(int j=w;j>;j--)

         {

             if(cnt[k]==)

               k++;

             cnt[k]--;

             s[i][j]=k;

         }

     }

     }

     for(int i=;i<=h;i++)

     {

         for(int j=;j<=w;j++)

             printf("%d ",s[i][j]);

         printf("\n");

     }

     return ;

 }

AtCoder Beginner Contest 069【A，水，B，水，C，数学，D，暴力】的相关教程结束。