A - A to Z String 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A を N 個、B を N 個、…、Z を N 個この順に繋げて得られる文字列の先頭から X 番目の文字を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq X \leq N\times 26
  • 入力は全て整数

入力

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

N X

出力

答えを出力せよ。


入力例 1

1 3

出力例 1

C

得られる文字列は ABCDEFGHIJKLMNOPQRSTUVWXYZ です。先頭から 3 番目の文字は C です。


入力例 2

2 12

出力例 2

F

得られる文字列は AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ です。先頭から 12 番目の文字は F です。

Score : 100 points

Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq X \leq N\times 26
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the answer.


Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.


Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.

B - Median?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。

制約

  • 1 \leq a, b, c \leq 100
  • 入力は全て整数

入力

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

a b c

出力

b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。


入力例 1

5 3 2

出力例 1

Yes

与えられた整数を小さい順に並べると 2, 3, 5 となり、b はこれらの整数の中央値です。


入力例 2

2 5 3

出力例 2

No

b は与えられた整数の中央値ではありません。


入力例 3

100 100 100

出力例 3

Yes

Score : 100 points

Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

  • 1 \leq a, b, c \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b c

Output

If b is the median of the given integers, then print Yes; otherwise, print No.


Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.


Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.


Sample Input 3

100 100 100

Sample Output 3

Yes
C - Foreign Exchange

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

1 から N までの番号がつけられた N 個の国があり、i = 1, 2, \ldots, N について、高橋君は国 i の通貨を A_i 単位持っています。

高橋君は、下記の操作を好きな回数( 0 回でも良い)繰り返します。

  • まず、1 以上 N-1 以下の整数 i を選ぶ。
  • その後、国 i の通貨を S_i 単位以上持っているなら、下記の行動を 1 回行う。
    • 国 i の通貨を S_i 単位だけ支払い、国 (i+1) の通貨を T_i 単位だけ獲得する。

最終的に高橋君が持っている国 N の通貨の単位数としてあり得る最大値を出力してください。

制約

  • 入力される値はすべて整数
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq T_i \leq S_i \leq 10^9

入力

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

出力

答えを出力せよ。


入力例 1

4
5 7 0 3
2 2
4 3
5 2

出力例 1

5

以下の説明では、高橋君が持っている各国の通貨の単位数を、数列 A = (A_1, A_2, A_3, A_4) として表します。はじめ、A = (5, 7, 0, 3) です。

下記の通りに 4 回操作を行うことを考えます。

  • i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (5, 3, 3, 3) となる。
  • i = 1 を選び、国 1 の通貨 2 単位を支払って、国 2 の通貨 2 単位を獲得する。その結果、A = (3, 5, 3, 3) となる。
  • i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (3, 1, 6, 3) となる。
  • i = 3 を選び、国 3 の通貨 5 単位を支払って、国 4 の通貨 2 単位を獲得する。その結果、A = (3, 1, 1, 5) となる。

このとき、最終的に高橋君が持っている国 4 の通貨の単位数は 5 であり、これが考えられる最大値です。


入力例 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

出力例 2

45

Score: 150 points

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

  • First, choose an integer i between 1 and N-1, inclusive.
  • Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
    • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq T_i \leq S_i \leq 10^9

Input

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

Output

Print the answer.


Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

  • Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
  • Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
  • Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
  • Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.


Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45
D - Christmas Trees

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

東西に無限に伸びる道路があり、この道路上のある基準となる地点から東に x\mathrm{\,m} のところにある地点の座標は x と定められています。 特に、基準となる地点から西に x\mathrm{\,m} のところにある地点の座標は -x です。

すぬけ君は今から、座標が A である地点を基点にして M\mathrm{\,m} おきにクリスマスツリーを立てます。 すなわち、座標がある整数 k を用いて A+kM と表されるような地点それぞれにクリスマスツリーを立てます。

高橋君と青木君はそれぞれ座標が L,R\ (L\leq R) である地点に立っています。 高橋君と青木君の間(高橋君と青木君が立っている地点を含む)に立てられるクリスマスツリーの本数を求めてください。

制約

  • -10^{18}\leq A \leq 10^{18}
  • 1\leq M \leq 10^9
  • -10^{18}\leq L\leq R \leq 10^{18}
  • 入力は全て整数

入力

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

A M L R

出力

高橋君と青木君の間(高橋君と青木君が立っている地点を含む)に立てられるクリスマスツリーの本数を出力せよ。


入力例 1

5 3 -1 6

出力例 1

3

すぬけ君は、座標が \dots,-4,-1,2,5,8,11,14\dots である地点にクリスマスツリーを立てます。 これらのうち高橋君と青木君の間にあるのは、座標が -1,2,5 である地点に立てられる 3 本です。


入力例 2

-2 2 1 1

出力例 2

0

高橋君と青木君が同じ地点に立っていることもあります。


入力例 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

出力例 3

273142010859

Score : 250 points

Problem Statement

There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.

Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.

Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).

Constraints

  • -10^{18}\leq A \leq 10^{18}
  • 1\leq M \leq 10^9
  • -10^{18}\leq L\leq R \leq 10^{18}
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

A M L R

Output

Print the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).


Sample Input 1

5 3 -1 6

Sample Output 1

3

Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.


Sample Input 2

-2 2 1 1

Sample Output 2

0

Sometimes, Takahashi and Aoki are standing at the same point.


Sample Input 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

Sample Output 3

273142010859
E - abc285_brutmhyhiizp

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

別世界の AtCoder で開催されている AtCoder Big Contest では、 10^{16} 問の問題が一度に出題されます。
問題の ID は 1 問目から順に A, B, ..., Z, AA, AB, ..., ZZ, AAA, ... と付けられています。

つまり、 ID は以下の順番で付けられています。

  • 長さ 1 の英大文字からなる文字列を辞書順に並べたもの
  • 長さ 2 の英大文字からなる文字列を辞書順に並べたもの
  • 長さ 3 の英大文字からなる文字列を辞書順に並べたもの
  • ...

このコンテストに含まれる問題の ID である文字列 S が与えられるので、それが何問目か答えてください。

制約

  • S は AtCoder Big Contest に含まれる問題の ID として正しい

入力

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

S

出力

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


入力例 1

AB

出力例 1

28

ID が AB である問題は、 AtCoder Big Contest の 28 問目です。


入力例 2

C

出力例 2

3

ID が C である問題は、 AtCoder Big Contest の 3 問目です。


入力例 3

BRUTMHYHIIZP

出力例 3

10000000000000000

ID が BRUTMHYHIIZP である問題は、 AtCoder Big Contest の 10^{16} 問目、すなわち最終問題です。

Score : 300 points

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

  • the strings of length 1 consisting of uppercase English letters, in lexicographical order;
  • the strings of length 2 consisting of uppercase English letters, in lexicographical order;
  • the strings of length 3 consisting of uppercase English letters, in lexicographical order;
  • ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

  • S is a valid ID of a problem given in AtCoder Big Contest.

Input

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

S

Output

Print the answer as an integer.


Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.


Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.


Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

F - Leftover Recipes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

冷蔵庫に N 種類の材料があります。これらを材料 1、\dots、材料 N と呼びます。材料 i は Q_i グラムあります。

あなたは 2 種類の料理を作れます。料理 A は、1 人分を作るのに各材料 i (1 \leq i \leq N) が A_i グラム必要です。料理 B は、1 人分を作るのに各材料 i が B_i グラム必要です。どちらも整数人分しか作れません。

冷蔵庫にある材料のみを使って、最大で合計何人分の料理を作れますか。

制約

  • 1 \leq N \leq 10
  • 1 \leq Q_i \leq 10^6
  • 0 \leq A_i \leq 10^6
  • A_i \geq 1 であるような i が存在する。
  • 0 \leq B_i \leq 10^6
  • B_i \geq 1 であるような i が存在する。
  • 入力値はすべて整数である。

入力

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

N
Q_1 Q_2 \dots Q_N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

最大で合計 S 人分の料理を作れるとして、整数 S を出力せよ。


入力例 1

2
800 300
100 100
200 10

出力例 1

5

この冷蔵庫には、800 グラムの材料 1 と 300 グラムの材料 2 があります。

100 グラムの材料 1 と 100 グラムの材料 2 で料理 A を 1 人分作れ、200 グラムの材料 1 と 10 グラムの材料 2 で料理 B を 1 人分作れます。

料理 A を 2 人分、料理 B を 3 人分作るのに必要な材料 1 の量は 100 \times 2 + 200 \times 3 = 800 グラム、材料 2 の量は 100 \times 2 + 10 \times 3 = 230 グラムで、いずれも冷蔵庫にある量を超えません。このようにして合計 5 人分の料理を作ることができますが、6 人分を作る方法はなく、答えは 5 です。


入力例 2

2
800 300
100 0
0 10

出力例 2

38

800 グラムの材料 1 で料理 A を 8 人分、300 グラムの材料 2 で料理 B を 30 人分、合計 38 人分作れます。


入力例 3

2
800 300
801 300
800 301

出力例 3

0

何も作れません。


入力例 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

出力例 4

222222

Score: 300 points

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

  • 1 \leq N \leq 10
  • 1 \leq Q_i \leq 10^6
  • 0 \leq A_i \leq 10^6
  • There is an i such that A_i \geq 1.
  • 0 \leq B_i \leq 10^6
  • There is an i such that B_i \geq 1.
  • All input values are integers.

Input

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

N
Q_1 Q_2 \dots Q_N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Assuming that you can make a maximum total of S servings of dishes, print the integer S.


Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.


Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.


Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.


Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Sample Output 4

222222
G - LRUD Instructions

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

H 行 W 列のグリッドがあります。上から i 行目、左から j 列目にあるマスをマス (i, j) で表します。
N 個のマス (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N) は壁になっています。

はじめ、高橋君はマス (r_\mathrm{s}, c_\mathrm{s}) にいます。

高橋君に Q 個の指示が与えられます。 i = 1, 2, \ldots, Q について、i 番目の指示は文字 d_i と正整数 l_i の組で表されます。d_i は L 、R 、U 、D のいずれかの文字であり、それぞれ左、右、上、下の方向を表します。

i 番目の指示に対して高橋君は下記の行動を l_i 回繰り返します。

現在いるマスに対して、d_i が表す向きに壁のないマスが隣接しているなら、そのマスに移動する。 そのようなマスが存在しない場合は、何もしない。

i = 1, 2, \ldots, Q について、i 番目までの指示を実行した直後に高橋君がいるマスを出力してください。

制約

  • 2 \leq H, W \leq 10^9
  • 1 \leq r_\mathrm{s} \leq H
  • 1 \leq c_\mathrm{s} \leq W
  • 0 \leq N \leq 2 \times 10^5
  • 1 \leq r_i \leq H
  • 1 \leq c_i \leq W
  • i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
  • すべての i = 1, 2, \ldots, Nについて、(r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i)
  • 1 \leq Q \leq 2 \times 10^5
  • d_i は L 、R 、U 、D のいずれかの文字
  • 1 \leq l_i \leq 10^9
  • d_i 以外の入力値は整数

入力

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

H W r_\mathrm{s} c_\mathrm{s}
N
r_1 c_1
r_2 c_2
\vdots
r_N c_N
Q
d_1 l_1
d_2 l_2
\vdots
d_Q l_Q

出力

Q 行出力せよ。 下記の形式にしたがい、i = 1, 2, \ldots, Q について、i 番目までの指示を実行した直後に高橋君がいるマス (R_i, C_i) を i 行目に出力せよ。

R_1 C_1
R_2 C_2
\vdots
R_Q C_Q

入力例 1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

出力例 1

4 2
3 2
3 1
3 5

与えられるグリッドと高橋君の初期位置は下記の通りです。 ここで、# は壁のマスを、T は高橋君がいるマスを表し、. がその他のマスを表します。

...#.
.#...
.....
...T.
..#..

1 つ目の指示に対して高橋君は、左に 2 マス移動し、高橋君の位置は下記の通り、マス (4, 2) になります。

...#.
.#...
.....
.T...
..#..

2 つ目の指示に対して高橋君は、上に 1 マスに移動した後、次の移動先が壁であるために「何もしない」を 2 回行います。その結果、高橋君の位置は下記の通り、マス (3, 2) になります。

...#.
.#...
.T...
.....
..#..

3 つ目の指示に対して高橋君は、左に 1 マス移動した後、次の移動先となるマスが存在しないために「何もしない」を 1 回行います。その結果、高橋君の位置は下記の通り、マス (3, 1) になります。

...#.
.#...
T....
.....
..#..

4 つ目の指示に対して高橋君は、右に 4 マス移動し、高橋君の位置は下記の通り、マス (3, 5) になります。

...#.
.#...
....T
.....
..#..

入力例 2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

出力例 2

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1

Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
N squares, (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N), have walls.

Takahashi is initially at square (r_\mathrm{s}, c_\mathrm{s}).

Q instructions are given to Takahashi. For i = 1, 2, \ldots, Q, the i-th instruction is represented by a pair of a character d_i and a positive integer l_i. d_i is one of L, R, U, and D, representing the directions of left, right, up, and down, respectively.

Given the i-th direction, Takahashi repeats the following action l_i times:

If a square without a wall is adjacent to the current square in the direction represented by d_i, move to that square; otherwise, do nothing.

For i = 1, 2, \ldots, Q, print the square where Takahashi will be after he follows the first i instructions.

Constraints

  • 2 \leq H, W \leq 10^9
  • 1 \leq r_\mathrm{s} \leq H
  • 1 \leq c_\mathrm{s} \leq W
  • 0 \leq N \leq 2 \times 10^5
  • 1 \leq r_i \leq H
  • 1 \leq c_i \leq W
  • i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
  • (r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i) for all i = 1, 2, \ldots, N.
  • 1 \leq Q \leq 2 \times 10^5
  • d_i is one of the characters L, R, U, and D.
  • 1 \leq l_i \leq 10^9
  • All values in the input other than d_i are integers.

Input

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

H W r_\mathrm{s} c_\mathrm{s}
N
r_1 c_1
r_2 c_2
\vdots
r_N c_N
Q
d_1 l_1
d_2 l_2
\vdots
d_Q l_Q

Output

Print Q lines. For i = 1, 2, \ldots, Q, the i-th line should contain the square (R_i, C_i) where Takahashi will be after he follows the first i instructions, in the following format:

R_1 C_1
R_2 C_2
\vdots
R_Q C_Q

Sample Input 1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

Sample Output 1

4 2
3 2
3 1
3 5

The given grid and the initial position of Takahashi are as follows, where # denotes a square with a wall, T a square where Takahashi is, and . the other squares:

...#.
.#...
.....
...T.
..#..

Given the 1-st instruction, Takahashi moves 2 squares to the left, ending up in square (4, 2) as follows:

...#.
.#...
.....
.T...
..#..

Given the 2-nd instruction, Takahashi first moves 1 square upward, then he "does nothing" twice because the adjacent square in his direction has a wall. As a result, he ends up in square (3, 2) as follows:

...#.
.#...
.T...
.....
..#..

Given the 3-rd instruction, Takahashi first moves 1 square to the left, then he "does nothing" once because there is no square in his direction. As a result, he ends up in square (3, 1) as follows:

...#.
.#...
T....
.....
..#..

Given the 4-th instruction, Takahashi moves 4 squares to the right, ending up in square (3, 5) as follows:

...#.
.#...
....T
.....
..#..

Sample Input 2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

Sample Output 2

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1
H - 7x7x7

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

座標空間上に一辺 7 の立方体を 3 つ、ちょうど 1,2,3 個の立方体に含まれる領域の体積がそれぞれ V_1,V_2,V_3 となるように配置したいです。

3 つの整数 a,b,c に対し、(a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7) で表される立方体領域を C(a,b,c) とおきます。

以下の条件を全て満たすような 9 つの整数 a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3 が存在するか判定し、存在するならば実際に 1 つ求めてください。

  • |a_1|,|b_1|,|c_1|,|a_2|,|b_2|,|c_2|,|a_3|,|b_3|,|c_3| \leq 100
  • C_i = C(a_i,b_i,c_i)\ (i=1,2,3) とおいたとき、
    • C_1,C_2,C_3 のうちちょうど 1 個に含まれる領域の体積は V_1 である。
    • C_1,C_2,C_3 のうちちょうど 2 個に含まれる領域の体積は V_2 である。
    • C_1,C_2,C_3 の全てに含まれる領域の体積は V_3 である。

制約

  • 0\leq V_1,V_2,V_3 \leq 3\times 7^3
  • 入力は全て整数

入力

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

V_1 V_2 V_3

出力

問題文中の条件を全て満たすような 9 つの整数 a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3 が存在しないならば No を出力し、存在するならば以下の形式で出力せよ。 複数存在する場合はそのどれを出力してもよい。

Yes
a_1 b_1 c_1 a_2 b_2 c_2 a_3 b_3 c_3

入力例 1

840 84 7

出力例 1

Yes
0 0 0 0 6 0 6 0 0

(a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3)=(0,0,0,0,6,0,6,0,0) の場合を考えます。

この図は C_1,C_2,C_3 の位置関係を表したもので、それぞれ橙、水色、緑の立方体に対応しています。

このとき、

  • |a_1|,|b_1|,|c_1|,|a_2|,|b_2|,|c_2|,|a_3|,|b_3|,|c_3| は全て 100 以下
  • C_1,C_2,C_3 の全てに含まれる領域は (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7) であり、その体積は (7-6)\times(7-6)\times(7-0)=7
  • C_1,C_2,C_3 のうちちょうど 2 個に含まれる領域は ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y< 6) \land (0\leq z\leq 7)) であり、 その体積は (6-0)\times(7-6)\times(7-0)\times 2=84
  • C_1,C_2,C_3 のうちちょうど 1 個に含まれる領域の体積は 840

であり、条件を全て満たします。

(a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3)=(-10, 0, 0, -10, 0, 6, -10, 6, 1) なども同様に条件を全て満たすため、正当な出力として判定されます。


入力例 2

343 34 3

出力例 2

No

条件を全て満たすような 9 つの整数 a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3 は存在しません。

Score: 475 points

Problem Statement

In a coordinate space, we want to place three cubes with a side length of 7 so that the volumes of the regions contained in exactly one, two, three cube(s) are V_1, V_2, V_3, respectively.

For three integers a, b, c, let C(a,b,c) denote the cubic region represented by (a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7).

Determine whether there are nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 that satisfy all of the following conditions, and find one such tuple if it exists.

  • |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100
  • Let C_i = C(a_i, b_i, c_i)\ (i=1,2,3).
    • The volume of the region contained in exactly one of C_1, C_2, C_3 is V_1.
    • The volume of the region contained in exactly two of C_1, C_2, C_3 is V_2.
    • The volume of the region contained in all of C_1, C_2, C_3 is V_3.

Constraints

  • 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3
  • All input values are integers.

Input

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

V_1 V_2 V_3

Output

If no nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions in the problem statement, print No. Otherwise, print such integers in the following format. If multiple solutions exist, you may print any of them.

Yes
a_1 b_1 c_1 a_2 b_2 c_2 a_3 b_3 c_3

Sample Input 1

840 84 7

Sample Output 1

Yes
0 0 0 0 6 0 6 0 0

Consider the case (a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (0, 0, 0, 0, 6, 0, 6, 0, 0).

The figure represents the positional relationship of C_1, C_2, and C_3, corresponding to the orange, cyan, and green cubes, respectively.

Here,

  • All of |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| are not greater than 100.
  • The region contained in all of C_1, C_2, C_3 is (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7), with a volume of (7-6)\times(7-6)\times(7-0)=7.
  • The region contained in exactly two of C_1, C_2, C_3 is ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y < 6) \land (0\leq z\leq 7)), with a volume of (6-0)\times(7-6)\times(7-0)\times 2=84.
  • The region contained in exactly one of C_1, C_2, C_3 has a volume of 840.

Thus, all conditions are satisfied.

(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (-10, 0, 0, -10, 0, 6, -10, 6, 1) also satisfies all conditions and would be a valid output.


Sample Input 2

343 34 3

Sample Output 2

No

No nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions.

I - Cleaning Robot

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

無限に広がる二次元グリッドのマス (0, 0) に掃除ロボットが置かれています。

このロボットに、4 種類の文字 L 、R 、U 、D からなる文字列で表されたプログラムが与えられます。
ロボットは、与えられたプログラムの各文字を先頭の文字から順に読み、各文字について以下の行動を行います。

  1. ロボットの現在地をマス (x, y) とする
  2. 読んだ文字に応じて以下の通りに移動する:
    • L を読んだとき: マス (x-1, y) に移動する。
    • R を読んだとき: マス (x+1, y) に移動する。
    • U を読んだとき: マス (x, y-1) に移動する。
    • D を読んだとき: マス (x, y+1) に移動する。

L 、R 、U 、D からなる文字列 S が与えられます。 ロボットが実行するプログラムは、文字列 S を K 個連接したものです。

ロボットが一度でも存在したことのあるマス(ロボットの初期位置であるマス (0, 0) を含む)は掃除されます。
ロボットがプログラムの実行を終えた後の時点で、掃除されているマスの個数を出力して下さい。

制約

  • S は L 、R 、U 、D からなる長さ 1 以上 2 \times 10^5 以下の文字列
  • 1 \leq K \leq 10^{12}

入力

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

S
K

出力

ロボットがプログラムの実行を終えた後の時点で、掃除されているマスの個数を出力せよ。


入力例 1

RDRUL
2

出力例 1

7

ロボットが実行するプログラムは RDRULRDRUL です。ロボットは初期位置であるマス (0, 0) からはじめ、
(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0) と移動します。
その後掃除されているマスは、(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1) の 7 個です。


入力例 2

LR
1000000000000

出力例 2

2

入力例 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

出力例 3

219911485785

Score : 500 points

Problem Statement

There is a cleaning robot on the square (0, 0) in an infinite two-dimensional grid.

The robot will be given a program represented as a string consisting of four kind of characters L, R, U, D.
It will read the characters in the program from left to right and perform the following action for each character read.

  1. Let (x, y) be the square where the robot is currently on.
  2. Make the following move according to the character read:
    • if L is read: go to (x-1, y).
    • if R is read: go to (x+1, y).
    • if U is read: go to (x, y-1).
    • if D is read: go to (x, y+1).

You are given a string S consisting of L, R, U, D. The program that will be executed by the robot is the concatenation of K copies of S.

Squares visited by the robot at least once, including the initial position (0, 0), will be cleaned.
Print the number of squares that will be cleaned at the end of the execution of the program.

Constraints

  • S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of L, R, U, D.
  • 1 \leq K \leq 10^{12}

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the number of squares that will be cleaned at the end of the execution of the program.


Sample Input 1

RDRUL
2

Sample Output 1

7

The robot will execute the program RDRULRDRUL. It will start on (0, 0) and travel as follows:
(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0).
In the end, seven squares will get cleaned: (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1).


Sample Input 2

LR
1000000000000

Sample Output 2

2

Sample Input 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

Sample Output 3

219911485785