AtCoder Weekday Contest 0195 Beta

A - Collecting Cards

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 166 点

問題文

高橋君はカードゲームのデッキを組んでいます。デッキには N 種類のカードが必要で、 i 種類目のカードはちょうど A_i 枚必要です。高橋君は現在、 i 種類目のカードを B_i 枚持っています。

各種類について、あと何枚買えば必要な枚数が揃うかを求めてください。すでに必要な枚数以上持っている場合は 0 を出力してください。

制約

1 \leq N \leq 100
1 \leq A_i \leq 1000
0 \leq B_i \leq 1000
入力はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、カードの種類数 N が与えられる。
2 行目から N 行にわたり、 1 + i 行目には i 種類目のカードの必要枚数 A_i と現在の枚数 B_i がスペース区切りで与えられる。

出力

N 行出力せよ。 i 行目には i 種類目のカードをあと何枚買えばよいかを出力せよ。

入力例 1

出力例 1

3
0
3

入力例 2

1
10 3

出力例 2

入力例 3

2
5 5
7 2

出力例 3

0
5

入力例 4

2
1 0
2 1

出力例 4

1
1

入力例 5

2
5 0
7 2

出力例 5

5
5

Score : 166 pts

Problem Statement

Takahashi is building a deck for a card game. The deck requires N types of cards, and exactly A_i cards of the i-th type are needed. Takahashi currently has B_i cards of the i-th type.

For each type, determine how many more cards he needs to buy to have the required number. If he already has at least the required number, print 0.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 1000
0 \leq B_i \leq 1000
All input values are integers.

Input

The input is given from standard input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains N, the number of card types.
For each of the following N lines, the (1+i)-th line contains the required number A_i and current number B_i of cards of the i-th type, separated by a space.

Output

Print N lines. On the i-th line, print how many more cards of the i-th type Takahashi needs to buy.

Sample Input 1

Sample Output 1

3
0
3

Sample Input 2

1
10 3

Sample Output 2

Sample Input 3

2
5 5
7 2

Sample Output 3

0
5

Sample Input 4

2
1 0
2 1

Sample Output 4

1
1

Sample Input 5

2
5 0
7 2

Sample Output 5

5
5

B - New Snowfall Records

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君の町では N 日間、毎朝の積雪量を記録しました。 i 日目の積雪量は A_i センチメートルでした。

i 日目の積雪量が、それより前のすべての日の積雪量より大きいとき、 i 日目は「新記録の日」です。 1 日目は必ず新記録の日とします。

各日について、新記録の日なら o 、そうでなければ x として、 1 日目から順に並べた長さ N の文字列を出力してください。

制約

1 \leq N \leq 100
0 \leq A_i \leq 1000
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

1 行目には、日数 N が与えられる。
2 行目には、各日の積雪量 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

長さ N の文字列を 1 行で出力せよ。

入力例 1

5
3 5 2 1 8

出力例 1

ooxxo

入力例 2

3
1 2 3

出力例 2

ooo

入力例 3

4
5 3 2 0

出力例 3

oxxx

入力例 4

4
5 1000 2 0

出力例 4

ooxx

入力例 5

1
1

出力例 5

Score : 233 pts

Problem Statement

In Takahashi's town, the snowfall depth was recorded every morning for N days. The snowfall on day i was A_i centimeters.

When the snowfall on day i is greater than the snowfall on every earlier day, day i is called a "new-record day". Day 1 is always a new-record day.

For each day, let o denote a new-record day and x otherwise. Print the string of length N obtained by arranging these characters in order from day 1.

Constraints

1 \leq N \leq 100
0 \leq A_i \leq 1000
All input values are integers.

Input

The input is given from standard input in the following format:

N
A_1 A_2 \ldots A_N

The first line contains the number of days N.
The second line contains the snowfall amounts A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print a single line containing a string of length N.

Sample Input 1

5
3 5 2 1 8

Sample Output 1

ooxxo

Sample Input 2

3
1 2 3

Sample Output 2

ooo

Sample Input 3

4
5 3 2 0

Sample Output 3

oxxx

Sample Input 4

4
5 1000 2 0

Sample Output 4

ooxx

Sample Input 5

1
1

Sample Output 5

C - Switches and Light Bulbs

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 H 行、横 W 列のマス目があります。上から i 行目、左から j 列目にあるマスをマス (i, j) と呼びます。

各マスには電球とスイッチが 1 つずつ設置されています。

各マスの電球の初期状態は、長さ W の文字列 S_1, S_2, \dots, S_H によって与えられます。マス (i, j) にある電球は、S_i の j 文字目が 0 のとき消灯、1 のとき点灯しています。

マス (i, j) にあるスイッチを押すと、マス (i, j) およびそのマスと上下左右に隣接するマス（存在するなら）にあるすべての電球の状態が反転します（すなわち、点灯している電球は消灯し、消灯している電球は点灯します）。

高橋君は合計で Q 回、スイッチを押す操作を行います。k 回目 (1 \leq k \leq Q) の操作では、マス (R_k, C_k) にあるスイッチを押します。なお、複数回の操作で同じマスのスイッチが押されることもあります。

すべての操作が終了した後の、各マスの電球の状態を求めてください。

制約

1 \leq H \leq 2 \times 10^4
1 \leq W
H \times W \leq 10^6
S_i は 0 および 1 のみからなる長さ W の文字列 (1 \leq i \leq H)
1 \leq Q \leq 10^5
1 \leq R_k \leq H (1 \leq k \leq Q)
1 \leq C_k \leq W (1 \leq k \leq Q)
H, W, Q, R_k, C_k は整数

入力

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

H W
S_1
S_2
\vdots
S_H
Q
R_1 C_1
R_2 C_2
\vdots
R_Q C_Q

出力

すべての操作が終了した後の各マスの電球の状態を H 行で出力せよ。

i 行目 (1 \leq i \leq H) には、長さ W の文字列を出力せよ。この文字列の j 文字目 (1 \leq j \leq W) は、すべての操作が終了した後のマス (i, j) の電球が消灯しているならば 0、点灯しているならば 1 とせよ。

入力例 1

出力例 1

010
111
010

入力例 2

出力例 2

011
110

入力例 3

出力例 3

入力例 4

8 12
101001101001
010110010110
110011001100
001100110011
100100100100
011011011011
111000111000
000111000111
15
1 1
8 12
4 6
5 7
2 10
7 3
1 12
8 1
3 5
6 8
4 6
5 7
3 3
6 10
8 8

出力例 4

011001101110
111100011001
101000001000
000110110011
100100110000
010011101101
000100111101
111111111100

入力例 5

出力例 5

Score : 300 pts

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell contains one light bulb and one switch.

The initial states of the light bulbs in each cell are given by H strings S_1, S_2, \dots, S_H of length W. The light bulb at cell (i, j) is off if the j-th character of S_i is 0, and on if it is 1.

When the switch at cell (i, j) is pressed, the states of the light bulbs at cell (i, j) and all cells adjacent to it vertically or horizontally (if they exist) are toggled (that is, an on bulb is turned off, and an off bulb is turned on).

Takahashi will perform the operation of pressing a switch a total of Q times. In the k-th operation (1 \leq k \leq Q), he presses the switch at cell (R_k, C_k). Note that the switch in the same cell may be pressed multiple times across different operations.

Find the state of the light bulb in each cell after all operations are completed.

Constraints

1 \leq H \leq 2 \times 10^4
1 \leq W
H \times W \leq 10^6
S_i is a string of length W consisting of 0 and 1 (1 \leq i \leq H).
1 \leq Q \leq 10^5
1 \leq R_k \leq H (1 \leq k \leq Q)
1 \leq C_k \leq W (1 \leq k \leq Q)
H, W, Q, R_k, and C_k are integers.

Input

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

H W
S_1
S_2
\vdots
S_H
Q
R_1 C_1
R_2 C_2
\vdots
R_Q C_Q

Output

Print the states of the light bulbs in each cell after all operations are completed in H lines.

The i-th line (1 \leq i \leq H) should contain a string of length W, where the j-th character (1 \leq j \leq W) is 0 if the light bulb at cell (i, j) is off after all operations, and 1 if it is on.

Sample Input 1

Sample Output 1

010
111
010

Sample Input 2

Sample Output 2

011
110

Sample Input 3

Sample Output 3

Sample Input 4

8 12
101001101001
010110010110
110011001100
001100110011
100100100100
011011011011
111000111000
000111000111
15
1 1
8 12
4 6
5 7
2 10
7 3
1 12
8 1
3 5
6 8
4 6
5 7
3 3
6 10
8 8

Sample Output 4

011001101110
111100011001
101000001000
000110110011
100100110000
010011101101
000100111101
111111111100

Sample Input 5

Sample Output 5

D - Stamp Rally

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、一直線のコースで行われるスタンプラリーに参加しています。

コース上には N 箇所のチェックポイントがあり、スタート側から順にチェックポイント 1, 2, \dots, N と番号が付けられています。

チェックポイントで押すことができるスタンプは全部で 7 種類あり、1 以上 7 以下の整数で表されます。チェックポイント i (1 \le i \le N) を訪れると、種類 C_i のスタンプを 1 つ押すことができます。

高橋君は、連続する区間のチェックポイントを訪れて全 7 種類のスタンプをすべて集めたいと考えています。

形式的には、1 \le l \le r \le N を満たす整数の組 (l, r) であって、チェックポイント l, l+1, \dots, r を順に訪れたときに押せるスタンプの中に種類 1 から種類 7 までのスタンプがすべて含まれる（すなわち、集合 \{C_l, C_{l+1}, \dots, C_r\} が \{1, 2, 3, 4, 5, 6, 7\} と一致する）ものの総数を求めてください。

制約

1 \le N \le 10^6
1 \le C_i \le 7 (1 \le i \le N)
入力はすべて整数

入力

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

N
C_1 C_2 \dots C_N

出力

条件を満たす組 (l, r) の総数を 1 行に出力してください。

なお、答えは 32 bit 整数型に収まらない場合があることに注意してください。

入力例 1

8
1 2 3 4 5 6 7 1

出力例 1

入力例 2

9
1 2 3 4 5 6 1 2 3

出力例 2

入力例 3

24
3 7 1 2 4 5 6 2 3 1 7 4 5 6 6 5 4 3 2 1 7 1 2 3

出力例 3

入力例 4

70
3 1 4 1 5 7 2 6 5 3 5 7 1 2 4 6 3 2 7 1 5 4 6 2 3 7 1 4 5 6 1 2 3 4 5 6 7 7 6 5 4 3 2 1 1 3 5 7 2 4 6 2 4 6 1 3 5 7 7 5 3 1 6 4 2 1 2 3 4 5

出力例 4

入力例 5

1
1

出力例 5

Score : 366 pts

Problem Statement

Takahashi is participating in a stamp rally held on a straight course.

There are N checkpoints along the course, numbered 1, 2, \dots, N in order from the start.

There are 7 types of stamps that can be collected at the checkpoints, represented by integers from 1 through 7. When visiting checkpoint i (1 \le i \le N), one can collect one stamp of type C_i.

Takahashi wants to collect all 7 types of stamps by visiting a contiguous range of checkpoints.

Formally, find the number of pairs of integers (l, r) satisfying 1 \le l \le r \le N such that the stamps collected when visiting checkpoints l, l+1, \dots, r in order contain all stamp types from 1 through 7 (that is, the set \{C_l, C_{l+1}, \dots, C_r\} equals \{1, 2, 3, 4, 5, 6, 7\}).

Constraints

1 \le N \le 10^6
1 \le C_i \le 7 (1 \le i \le N)
All input values are integers.

Input

The input is given in the following format:

N
C_1 C_2 \dots C_N

Output

Print the total number of pairs (l, r) that satisfy the condition in a single line.

Note that the answer may not fit in a 32-bit integer.

Sample Input 1

8
1 2 3 4 5 6 7 1

Sample Output 1

Sample Input 2

9
1 2 3 4 5 6 1 2 3

Sample Output 2

Sample Input 3

24
3 7 1 2 4 5 6 2 3 1 7 4 5 6 6 5 4 3 2 1 7 1 2 3

Sample Output 3

Sample Input 4

70
3 1 4 1 5 7 2 6 5 3 5 7 1 2 4 6 3 2 7 1 5 4 6 2 3 7 1 4 5 6 1 2 3 4 5 6 7 7 6 5 4 3 2 1 1 3 5 7 2 4 6 2 4 6 1 3 5 7 7 5 3 1 6 4 2 1 2 3 4 5

Sample Output 4

Sample Input 5

1
1

Sample Output 5

E - Choosing Pairs

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

ある部活動には、1 から N までの番号が付けられた N 人の部員が所属しています。部員 i (1 \le i \le N) の技術力は A_i、体力は B_i です。

高橋君は、今度開催される大会に向けて部員の中から 2 人のペアを 1 組選ぼうとしています。

大会で勝ち抜くためには、選んだ 2 人の技術力の合計が X 以上、かつ体力の合計が Y 以上である必要があります。

1 \le i < j \le N を満たす整数の組 (i, j) のうち、部員 i と部員 j を選んだときにこの条件を満たす（すなわち A_i + A_j \ge X かつ B_i + B_j \ge Y を満たす）ものの個数を求めてください。

制約

2 \le N \le 10^5
1 \le X, Y \le 2 \times 10^9
1 \le A_i, B_i \le 10^9 (1 \le i \le N)
入力はすべて整数

入力

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

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

条件を満たす組 (i, j) の個数を 1 行に出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

20 100000 100000
45000 55000
62000 39000
21000 84000
78000 23000
35000 69000
51000 50000
89000 12000
14000 91000
68000 42000
41000 64000
66000 35000
31000 76000
54000 47000
83000 19000
27000 81000
49000 52000
72000 30000
18000 88000
60000 43000
33000 71000

出力例 4

入力例 5

2 2000000000 2000000000
1000000000 1000000000
1000000000 1000000000

出力例 5

Score : 466 pts

Problem Statement

A club has N members, numbered 1 to N. Member i (1 \le i \le N) has a technical skill of A_i and a physical strength of B_i.

Takahashi wants to select a pair of 2 members from the club for an upcoming tournament.

To win in the tournament, the sum of the technical skills of the chosen 2 members must be at least X, and the sum of their physical strengths must be at least Y.

Find the number of pairs of integers (i, j) satisfying 1 \le i < j \le N such that choosing member i and member j satisfies this condition (that is, A_i + A_j \ge X and B_i + B_j \ge Y).

Constraints

2 \le N \le 10^5
1 \le X, Y \le 2 \times 10^9
1 \le A_i, B_i \le 10^9 (1 \le i \le N)
All input values are integers.

Input

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

N X Y
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the number of pairs (i, j) satisfying the condition in a single line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

20 100000 100000
45000 55000
62000 39000
21000 84000
78000 23000
35000 69000
51000 50000
89000 12000
14000 91000
68000 42000
41000 64000
66000 35000
31000 76000
54000 47000
83000 19000
27000 81000
49000 52000
72000 30000
18000 88000
60000 43000
33000 71000

Sample Output 4

Sample Input 5

2 2000000000 2000000000
1000000000 1000000000
1000000000 1000000000