Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 A 行、横 B 列のマスからなるタイルを縦 N 行、横 N 列に並べてできた、縦 (A\times N) 行、横 (B\times N) 列のマス目 X があります。
1\leq i,j \leq N について、上から i 行目、左から j 列目のタイルをタイル (i,j) とします。
X の各マスは以下のように塗られています。
- 各タイルは白いタイルまたは黒いタイルである。
- 白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
- タイル (1,1) は白いタイルである。
- 辺で隣接する 2 つのタイルは異なる色のタイルである。ただし、タイル (a,b) とタイル (c,d) が辺で隣接するとは、|a-c|+|b-d|=1 ( |x| を x の絶対値とする)であることを言う。
マス目 X を出力の形式に従って出力してください。
制約
- 1 \leq N,A,B \leq 10
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
次の条件をみたす (A\times N) 個の文字列 S_1,\ldots,S_{A\times N} を改行区切りで出力せよ。
- S_1,\ldots,S_{A\times N} はそれぞれ長さ (B\times N) の
.または#からなる文字列である。 - 各 i,j (1 \leq i \leq A\times N,1 \leq j \leq B\times N) に対し、マス目 X の上から i 行目かつ左から j 列目のマスが白で塗られているならば S_i の j 文字目は
.であり、黒く塗られているならば#である。
入力例 1
4 3 2
出力例 1
..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##.. ..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##..
入力例 2
5 1 5
出力例 2
.....#####.....#####..... #####.....#####.....##### .....#####.....#####..... #####.....#####.....##### .....#####.....#####.....
入力例 3
4 4 1
出力例 3
.#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#. .#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#.
入力例 4
1 4 4
出力例 4
.... .... .... ....
Score : 200 points
Problem Statement
Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.
Each square of X is painted as follows.
- Each tile is either a white tile or a black tile.
- Every square in a white tile is painted white; every square in a black tile is painted black.
- Tile (1,1) is a white tile.
- Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).
Print the grid X in the format specified in the Output section.
Constraints
- 1 \leq N,A,B \leq 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print (A\times N) strings S_1,\ldots,S_{A\times N} that satisfy the following condition, with newlines in between.
- Each of S_1,\ldots,S_{A\times N} is a string of length (B\times N) consisting of
.and#. - For each i and j (1 \leq i \leq A\times N,1 \leq j \leq B\times N), the j-th character of S_i is
.if the square at the i-th row from the top and j-th column from the left in grid X is painted white; the character is#if the square is painted black.
Sample Input 1
4 3 2
Sample Output 1
..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##.. ..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##..
Sample Input 2
5 1 5
Sample Output 2
.....#####.....#####..... #####.....#####.....##### .....#####.....#####..... #####.....#####.....##### .....#####.....#####.....
Sample Input 3
4 4 1
Sample Output 3
.#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#. .#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#.
Sample Input 4
1 4 4
Sample Output 4
.... .... .... ....
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。
注記
K 進法表記については、Wikipedia「位取り記数法」 を参照してください。
制約
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A,B は K 進法表記で与えられる
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
答えを出力せよ。
入力例 1
2 1011 10100
出力例 1
220
2 進法表記の 1011 を 、10 進法表記すると 11 です。
2 進法表記の 10100 を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。
入力例 2
7 123 456
出力例 2
15642
7 進法表記の 123 を 、10 進法表記すると 66 です。
7 進法表記の 456 を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。
Score : 200 points
Problem Statement
You are given integers A and B, in base K.
Print A \times B in decimal.
Notes
For base-K representation, see Wikipedia's article on Positional notation.
Constraints
- 2 \leq K \leq 10
- 1 \leq A,B \leq 10^5
- A and B are in base-K representation.
Input
Input is given from Standard Input in the following format:
K A B
Output
Print the answer.
Sample Input 1
2 1011 10100
Sample Output 1
220
1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.
Sample Input 2
7 123 456
Sample Output 2
15642
123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
H 行 W 列のマス目の上に 0 個以上のセンサが配置されています。上から i 行目、左から j 列目のマス目を (i, j) と表記します。
センサが配置されているマス目の情報は長さ W の文字列 S_1, S_2, \ldots, S_H によって与えられ、S_i の j 文字目が # のとき、またそのときに限り (i, j) にセンサが配置されています。
このセンサは上下左右斜めに隣接しているマス目に存在する他のセンサと連動し、一つのセンサとして動作します。
ただし、マス目 (x, y) と (x', y') が上下左右斜めに隣接しているとは、\max(|x-x'|,|y-y'|) = 1 であることを指します。
また、センサ A とセンサ B が連動し、センサ A とセンサ C が連動しているとき、センサ B とセンサ C も連動することに注意してください。
連動するセンサを一つのセンサと見なしたとき、このマス目の上にあるセンサの個数を求めてください。
制約
- 1 \leq H, W \leq 1000
- H, W は整数
- S_i は各文字が
#または.である長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
答えを出力せよ。
入力例 1
5 6 .##... ...#.. ....## #.#... ..#...
出力例 1
3
連動しているセンサを一つのセンサと見なしたとき、
- (1,2),(1,3),(2,4),(3,5),(3,6) にあるセンサが連動したもの
- (4,1) にあるセンサ
- (4,3),(5,3) にあるセンサが連動したもの
の 3 つのセンサが存在します。
入力例 2
3 3 #.# .#. #.#
出力例 2
1
入力例 3
4 2 .. .. .. ..
出力例 3
0
入力例 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
出力例 4
7
Score : 300 points
Problem Statement
There are zero or more sensors placed on a grid of H rows and W columns. Let (i, j) denote the square in the i-th row from the top and the j-th column from the left.
Whether each square contains a sensor is given by the strings S_1, S_2, \ldots, S_H, each of length W. (i, j) contains a sensor if and only if the j-th character of S_i is #.
These sensors interact with other sensors in the squares horizontally, vertically, or diagonally adjacent to them and operate as one sensor.
Here, a cell (x, y) and a cell (x', y') are said to be horizontally, vertically, or diagonally adjacent if and only if \max(|x-x'|,|y-y'|) = 1.
Note that if sensor A interacts with sensor B and sensor A interacts with sensor C, then sensor B and sensor C also interact.
Considering the interacting sensors as one sensor, find the number of sensors on this grid.
Constraints
- 1 \leq H, W \leq 1000
- H and W are integers.
- S_i is a string of length W where each character is
#or..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the answer.
Sample Input 1
5 6 .##... ...#.. ....## #.#... ..#...
Sample Output 1
3
When considering the interacting sensors as one sensor, the following three sensors exist:
- The interacting sensors at (1,2),(1,3),(2,4),(3,5),(3,6)
- The sensor at (4,1)
- The interacting sensors at (4,3),(5,3)
Sample Input 2
3 3 #.# .#. #.#
Sample Output 2
1
Sample Input 3
4 2 .. .. .. ..
Sample Output 3
0
Sample Input 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
Sample Output 4
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英小文字のみからなる長さ N の文字列 S が与えられます。
S の文字を並び替えて得られる文字列（S 自身を含む）であって、長さ K の回文を部分文字列として 含まない ものの個数を求めてください。
ただし、長さ N の文字列 T が「長さ K の回文を部分文字列として含む」とは、
ある (N-K) 以下の非負整数 i が存在して、1 以上 K 以下の任意の整数 j について T_{i+j}=T_{i+K+1-j} が成り立つことをいいます。
ここで、T_k は文字列 T の k 文字目を表すものとします。
制約
- 2\leq K \leq N \leq 10
- N,K は整数
- S は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
S の文字を並び替えて得られる文字列であって、長さ K の回文を部分文字列として含まないものの個数を出力せよ。
入力例 1
3 2 aab
出力例 1
1
aab を並び替えて得られる文字列は aab, aba, baa の 3 つであり、このうち aab および baa は長さ 2 の回文 aa を部分文字列として含んでいます。
よって、条件をみたす文字列は aba のみであり、1 を出力します。
入力例 2
5 3 zzyyx
出力例 2
16
zzyyx を並べて得られる文字列は 30 個ありますが、そのうち長さ 3 の回文を含まないようなものは 16 個です。よって、16 を出力します。
入力例 3
10 5 abcwxyzyxw
出力例 3
440640
Score : 300 points
Problem Statement
You are given a string S of length N consisting only of lowercase English letters.
Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.
Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.
Constraints
- 2 \leq K \leq N \leq 10
- N and K are integers.
- S is a string of length N consisting only of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the number of strings obtained by permuting S that do not contain a palindrome of length K as a substring.
Sample Input 1
3 2 aab
Sample Output 1
1
The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.
Sample Input 2
5 3 zzyyx
Sample Output 2
16
There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.
Sample Input 3
10 5 abcwxyzyxw
Sample Output 3
440640
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
1 以上 N 以下の整数であって、A の倍数でも B の倍数でもないものの総和を求めてください。
制約
- 1 \leq N, A,B \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
答えを出力せよ。
入力例 1
10 3 5
出力例 1
22
1 以上 10 以下の整数で 3 の倍数でも 5 の倍数でもないのは 1,2,4,7,8 です。それらの総和は 1+2+4+7+8 =22 です。
入力例 2
1000000000 314 159
出力例 2
495273003954006262
Score : 400 points
Problem Statement
Find the sum of integers between 1 and N (inclusive) that are not multiples of A or B.
Constraints
- 1 \leq N, A,B \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print the answer.
Sample Input 1
10 3 5
Sample Output 1
22
The integers between 1 and 10 (inclusive) that are not multiples of 3 or 5 are 1,2,4,7, and 8, whose sum is 1+2+4+7+8 =22.
Sample Input 2
1000000000 314 159
Sample Output 2
495273003954006262