実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
2^n \gt n^2 ですか？
制約
- n は 1 以上 10^9 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
n
出力
2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。
入力例 1
5
出力例 1
Yes
2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。
入力例 2
2
出力例 2
No
n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。
入力例 3
623947744
出力例 3
Yes
Score : 100 points
Problem Statement
Does 2^n \gt n^2 hold?
Constraints
- n is an integer between 1 and 10^9 (inclusive).
Input
Input is given from Standard Input in the following format:
n
Output
If 2^n \gt n^2, print Yes; otherwise, print No.
Sample Input 1
5
Sample Output 1
Yes
Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.
Sample Input 2
2
Sample Output 2
No
For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.
Sample Input 3
623947744
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
上下左右に広がる H 行 W 列のマス目があり、各マスにはコマが置かれているか、何も置かれていないかのどちらかです。
マス目の状態は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H によって表され、
S_i の j 文字目が # のとき上から i 行目かつ左から j 列目のマスにはコマが置かれていることを、
S_i の j 文字目が . のとき上から i 行目かつ左から j 列目のマスには何も置かれていないことを表しています。
マス目上のマスのうち、コマが置かれているようなものの個数を求めてください。
制約
- 1\leq H,W \leq 10
- H,W は整数
- S_i は
#と.のみからなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
コマが置かれているマスの個数を整数で出力せよ。
入力例 1
3 5 #.... ..... .##..
出力例 1
3
- 上から 1 行目かつ左から 1 列目のマス
- 上から 3 行目かつ左から 2 列目のマス
- 上から 3 行目かつ左から 3 列目のマス
の計 3 つのマスにコマが置かれているため、3 を出力します。
入力例 2
1 10 ..........
出力例 2
0
どのマスにもコマは置かれていないため、0 を出力します。
入力例 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
出力例 3
16
Score : 100 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is empty.
How many squares in the grid have pieces on them?
Constraints
- 1\leq H,W \leq 10
- H and W are integers.
- S_i is a string of length W consisting of
#and..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the number of squares with pieces as an integer.
Sample Input 1
3 5 #.... ..... .##..
Sample Output 1
3
The following three squares have pieces on them:
- the square at the 1-st row from the top and 1-st column from the left;
- the square at the 3-rd row from the top and 2-nd column from the left;
- the square at the 3-rd row from the top and 3-rd column from the left.
Thus, 3 should be printed.
Sample Input 2
1 10 ..........
Sample Output 2
0
Since no square has a piece on it, 0 should be printed.
Sample Input 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
Sample Output 3
16
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S,T が与えられるので、 T が S の(連続する)部分文字列かどうか判定してください。
なお、文字列 X に以下の操作を 0 回以上施して文字列 Y が得られる時、またその時に限り Y は X の(連続する)部分文字列であると言います。
- 以下の 2 つの操作から 1 つを選択して、その操作を行う。
- X の先頭の 1 文字を削除する。
- X の末尾の 1 文字を削除する。
例えば tag は voltage の(連続する)部分文字列ですが、 ace は atcoder の(連続する)部分文字列ではありません。
制約
- S,T は英小文字からなる
- 1 \le |S|,|T| \le 100 ( |X| は文字列 X の長さ )
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
T が S の(連続する)部分文字列なら Yes 、そうでないなら No と出力せよ。
入力例 1
voltage tag
出力例 1
Yes
tag は voltage の(連続する)部分文字列です。
入力例 2
atcoder ace
出力例 2
No
ace は atcoder の(連続する)部分文字列ではありません。
入力例 3
gorilla gorillagorillagorilla
出力例 3
No
入力例 4
toyotasystems toyotasystems
出力例 4
Yes
S=T である場合もあります。
Score : 200 points
Problem Statement
You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.
A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.
- Do one of the following.
- Delete the first character in X.
- Delete the last character in X.
For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.
Constraints
- S and T consist of lowercase English letters.
- 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)
Input
The input is given from Standard Input in the following format:
S T
Output
If T is a (contiguous) substring of S, print Yes; otherwise, print No.
Sample Input 1
voltage tag
Sample Output 1
Yes
tag is a (contiguous) substring of voltage.
Sample Input 2
atcoder ace
Sample Output 2
No
ace is not a (contiguous) substring of atcoder.
Sample Input 3
gorilla gorillagorillagorilla
Sample Output 3
No
Sample Input 4
toyotasystems toyotasystems
Sample Output 4
Yes
It is possible that S=T.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
- 縦 9 マス 横 9 マスの領域である
- 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である
- 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である
TaK Code を回転させることはできません。
縦 N マス、横 M マスのグリッドがあります。
グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。
グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
制約
- 9 \leq N,M \leq 100
- N,M は整数である
- S_i は
.および#のみからなる長さ M の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
上から i 行目左から j 列目のマスを左上とする縦 9 マス 横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス 横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が 1 つもないこともあります。
Score : 200 points
Problem Statement
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
- It is a region consisting of nine horizontal rows and nine vertical columns.
- All the 18 cells in the top-left and bottom-right three-by-three regions are black.
- All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
It is not allowed to rotate a TaK Code.
You are given a grid with N horizontal rows and M vertical columns.
The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
Constraints
- 9 \leq N,M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.
Sample Input 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2
1 1
Sample Input 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3
There may be no region that satisfies the conditions of TaK Code.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
xy 平面上に 1 から N までの番号が付いた N 個の点があります。
点 i は座標 (X_i,Y_i) にあり、相異なる 2 点は異なる位置に存在します。
この N 点から 3 点を選ぶとき、選ばれた 3 点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。
制約
- 入力は全て整数である
- 3 \le N \le 300
- -10^9 \le X_i,Y_i \le 10^9
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
出力
答えを整数として出力せよ。
入力例 1
4 0 1 1 3 1 1 -1 -1
出力例 1
3
点を図示すると、以下のようになります。
三角形をなすような点の選び方は、 \{1,2,3\},\{1,3,4\},\{2,3,4\} の 3 つです。
入力例 2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
出力例 2
1124
Score : 300 points
Problem Statement
In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.
Constraints
- All values in input are integers.
- 3 \le N \le 300
- -10^9 \le X_i,Y_i \le 10^9
- (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
Output
Print the answer as an integer.
Sample Input 1
4 0 1 1 3 1 1 -1 -1
Sample Output 1
3
The figure below illustrates the points.
There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.
Sample Input 2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
Sample Output 2
1124