A - Shuffled Equation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数列 A=(A_1,A_2,A_3) が与えられます。
A の要素を自由に並べ替えた列を B=(B_1,B_2,B_3) とします。
このとき、 B_1 \times B_2 = B_3 を満たすようにできるか判定してください。

制約

  • 入力は全て整数
  • 1 \le A_1,A_2,A_3 \le 100

入力

入力は以下の形式で標準入力から与えられる。

A_1 A_2 A_3

出力

B_1 \times B_2 = B_3 を満たすようにできるなら Yes 、そうでないなら No と出力せよ。


入力例 1

3 15 5

出力例 1

Yes

A=(3,15,5) です。
B=(3,5,15) と並べ替えることで、 B_1 \times B_2 = B_3 を満たすようにできます。


入力例 2

5 3 2

出力例 2

No

B をどのように定めても、 B_1 \times B_2 = B_3 を満たすようにはできません。


入力例 3

3 3 9

出力例 3

Yes

Score : 100 points

Problem Statement

You are given a sequence of integers A = (A_1, A_2, A_3).
Let B = (B_1, B_2, B_3) be any permutation of A.
Determine whether it is possible that B_1 \times B_2 = B_3.

Constraints

  • All input values are integers.
  • 1 \le A_1, A_2, A_3 \le 100

Input

The input is given from Standard Input in the following format:

A_1 A_2 A_3

Output

If it is possible that B_1 \times B_2 = B_3, print Yes; otherwise, print No.


Sample Input 1

3 15 5

Sample Output 1

Yes

Here, A=(3,15,5). By rearranging it as B=(3,5,15), we can satisfy B_1 \times B_2 = B_3.


Sample Input 2

5 3 2

Sample Output 2

No

No permutation of B satisfies B_1 \times B_2 = B_3.

B - 1-2-4 Test

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

3 問の問題からなる試験があり、それぞれの問題の配点は 1 点、2 点、4 点でした。

高橋君、青木君、すぬけ君の 3 人がこの試験を受け、 高橋君は A 点、青木君は B 点を取りました。

すぬけ君は、高橋君と青木君のうち少なくとも一方が解けた問題は解け、 2 人とも解けなかった問題は解けませんでした。

すぬけ君の点数を求めてください。

ただし、この問題の制約下で、すぬけ君の点数は一意に定まる事が証明できます。

制約

  • 0\leq A,B \leq 7
  • A,B は整数

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

すぬけ君の点数を整数で出力せよ。


入力例 1

1 2

出力例 1

3

高橋君は 1 点を取った事から、 1 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。
同様に、青木君は 2 点を取った事から、 2 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。

よって、すぬけ君は 1 点の問題と 2 点の問題を正解し、高橋君と青木君がともに解けなかった 4 点の問題はすぬけ君も解けなかったことになるので、3 点を取ったことがわかります。よって、3 を出力します。


入力例 2

5 3

出力例 2

7

高橋君は 5 点を取った事から、 1 点の問題と 4 点の問題を正解し、 2 点の問題は解けなかったことがわかります。
同様に、青木君は 3 点を取った事から、 1 点の問題と 2 点の問題を正解し、 4 点の問題は解けなかったことがわかります。

よって、3 問すべてについて、高橋君と青木君の少なくとも一方が正解しているため、すぬけ君はすベての問題に正解し、7 点を取ったことがわかります。 よって、7 を出力します。


入力例 3

0 0

出力例 3

0

高橋君と青木君は 2 人ともいずれの問題も解けていません。 よって、すぬけ君もいずれの問題も解けておらず、 0 を出力します。

Score : 100 points

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

  • 0\leq A,B \leq 7
  • A and B are integers.

Input

The input is given from Standard Input in the following format:

A B

Output

Print Snuke's score as an integer.


Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.


Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.


Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

C - Let's Get a Perfect Score

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の参加者が、1 から M までの番号がついた M 問からなるコンテストに参加します。

1 以上 N 以下の整数 i 、1 以上 M 以下の整数 j について、S_i の j 番目の文字が o のとき参加者 i は問題 j を解くことが可能で、S_i の j 番目の文字が x のとき参加者 i は問題 j を解くことが不可能です。

このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M 問全てを解くことが可能であるようなペアの個数を答えてください。

より厳密には、1\leq x < y\leq N を満たす整数の組 (x,y) であって、 1 以上 M 以下の任意の整数 j について、参加者 x か参加者 y の少なくとも一方は問題 j を解くことが可能であるという条件を満たすものの個数を答えてください。

制約

  • N は 2 以上 30 以下の整数
  • M は 1 以上 30 以下の整数
  • S_i は o, x からなる長さ M の文字列

入力

入力は以下の形式で標準入力から与えられる。

N M
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。


入力例 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

出力例 1

5

参加者 1 と 2 のペア、参加者 1 と 3 のペア、参加者 1 と 4 のペア、参加者 1 と 5 のペア、参加者 2 と 3 のペアの 5 個のペアが条件を満たします。

例えば参加者 2 と 4 のペアは、問題 4 が解けないので条件を満たしません。


入力例 2

3 2
ox
xo
xx

出力例 2

1

入力例 3

2 4
xxxx
oxox

出力例 3

0

Score : 200 points

Problem Statement

N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.

For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.

More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.

Constraints

  • N is an integer between 2 and 30, inclusive.
  • M is an integer between 1 and 30, inclusive.
  • S_i is a string of length M consisting of o and x.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the answer.


Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.

On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.


Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0
D - Product Calculator

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は電卓を持っています。電卓には最初 1 が表示されています。
高橋君は電卓に対して N 回操作を行います。
i 回目 (1\leq i\leq N) の操作では、その時点で画面に表示されている数に正の整数 A_i をかけます。
しかし、電卓には K 桁までしか表示できないため、計算結果が (K+1) 桁以上になる場合、代わりに 1 が画面に表示されます。 そうでない場合は正しく計算結果が表示されます。

N 回の操作の後に電卓に表示されている数を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 18
  • 1 \leq A_i < 10^K
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N

出力

N 回の操作の後に電卓に表示されている数を出力せよ。


入力例 1

5 2
7 13 3 2 5

出力例 1

10

今回電卓は 2 桁まで表示することができ、最初 1 が表示されています。これに対して、次のように高橋君は操作を行います。

  • 1 回目の操作で、7 をかけます。1\times 7=7 であり、電卓には 7 が表示されます。
  • 2 回目の操作で、13 をかけます。7\times 13=91 であり、電卓には 91 が表示されます。
  • 3 回目の操作で、3 をかけます。91\times 3=273 であり、3 桁になってしまうため、電卓には 1 が表示されます。
  • 4 回目の操作で、2 をかけます。1\times 2=2 であり、電卓には 2 が表示されます。
  • 5 回目の操作で、5 をかけます。2\times 5=10 であり、電卓には 10 が表示されます。

入力例 2

2 1
2 5

出力例 2

1

Score : 200 points

Problem Statement

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq 18
  • 1 \leq A_i < 10^K
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Output the number shown on the calculator after the N operations.


Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

10

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

  • The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
  • The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
  • The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
  • The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
  • The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

1
E - 1111gal password

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。

  • N 桁の正整数である。
  • X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
    • 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
    • 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1

制約

  • N は整数
  • 2 \le N \le 10^6

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。


入力例 1

4

出力例 1

203

4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。


入力例 2

2

出力例 2

25

入力例 3

1000000

出力例 3

248860093

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

  • X is an N-digit positive integer.
  • Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
    • 1 \le X_i \le 9 for all integers 1 \le i \le N;
    • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

  • N is an integer.
  • 2 \le N \le 10^6

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.


Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.


Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.