実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は実験室で細菌を観察しています。 1 日目の細菌の数は A 匹で、細菌の数は 1 日ごとにちょうど 2 倍になります。
1 日目から N 日目までの各日の細菌の数を、順番に出力してください。
制約
- 1 \leq N \leq 30
- 1 \leq A \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A
- 1 行目には、日数 N と 1 日目の細菌の数 A がスペース区切りで与えられる。
出力
N 行出力せよ。 i 行目には i 日目の細菌の数を出力せよ。
入力例 1
4 3
出力例 1
3 6 12 24
入力例 2
1 100
出力例 2
100
入力例 3
5 1
出力例 3
1 2 4 8 16
入力例 4
1 461300020
出力例 4
461300020
入力例 5
2 1000000000
出力例 5
1000000000 2000000000
Score : 200 pts
Problem Statement
Takahashi is observing bacteria in a laboratory. On day 1, there are A bacteria, and the number of bacteria exactly doubles every day.
Print the number of bacteria on each day from day 1 through day N, in order.
Constraints
- 1 \leq N \leq 30
- 1 \leq A \leq 10^9
- All input values are integers.
Input
The input is given from standard input in the following format:
N A
- The first line contains the number of days N and the number of bacteria on day 1, A, separated by a space.
Output
Print N lines. The i-th line should contain the number of bacteria on day i.
Sample Input 1
4 3
Sample Output 1
3 6 12 24
Sample Input 2
1 100
Sample Output 2
100
Sample Input 3
5 1
Sample Output 3
1 2 4 8 16
Sample Input 4
1 461300020
Sample Output 4
461300020
Sample Input 5
2 1000000000
Sample Output 5
1000000000 2000000000
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君の花園は縦 H 行、横 W 列のマス目でできています。花園の様子は H 個の文字列 S_1, S_2, \ldots, S_H で表され、 S_i の j 文字目は上から i 行目、左から j 列目のマスの様子です。 F は花が咲いていることを、 . は何も咲いていないことを表します。
花が最も多く咲いている列は左から何列目かを求めてください。そのような列が複数ある場合は、そのうち最も左の列を答えてください。
制約
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- S_i は
Fと.のみからなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
- 1 行目には、花園の行数 H と列数 W がスペース区切りで与えられる。
- 2 行目から H 行にわたり、 1 + i 行目には上から i 行目の様子を表す文字列 S_i が与えられる。
出力
花が最も多く咲いている列が左から何列目かを 1 行で出力せよ。複数ある場合は最も左の列を出力せよ。
入力例 1
3 4 F.F. ..F. F.FF
出力例 1
3
入力例 2
1 3 ..F
出力例 2
3
入力例 3
2 2 F. F.
出力例 3
1
入力例 4
4 7 ..FF..F ....F.F .FF..F. .F..FFF
出力例 4
7
入力例 5
5 3 .F. ..F .FF FF. .FF
出力例 5
2
Score : 233 pts
Problem Statement
Takahashi's flower garden consists of a grid with H rows and W columns. The state of the garden is represented by H strings S_1, S_2, \ldots, S_H, where the j-th character of S_i describes the cell in the i-th row from the top and the j-th column from the left. F means a flower is blooming, and . means nothing is blooming there.
Find the column number (from the left) in which the most flowers are blooming. If there are multiple such columns, answer the leftmost one.
Constraints
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- S_i is a string of length W consisting only of
Fand..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
- The first line contains the number of rows H and the number of columns W of the garden, separated by a space.
- For the next H lines starting from the second line, the (1 + i)-th line contains the string S_i representing the state of the i-th row from the top.
Output
Print, in a single line, the column number (from the left) in which the most flowers are blooming. If there are multiple such columns, print the leftmost one.
Sample Input 1
3 4 F.F. ..F. F.FF
Sample Output 1
3
Sample Input 2
1 3 ..F
Sample Output 2
3
Sample Input 3
2 2 F. F.
Sample Output 3
1
Sample Input 4
4 7 ..FF..F ....F.F .FF..F. .F..FFF
Sample Output 4
7
Sample Input 5
5 3 .F. ..F .FF FF. .FF
Sample Output 5
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は山岳部の部長として、ハイキングコースの調査を行っています。
調査対象のコースには N 個のチェックポイントが一列に並んでおり、各チェックポイント i(1 \leq i \leq N)には標高 H_i が記録されています。高橋君は特に「谷」に注目しています。
チェックポイント i(2 \leq i \leq N - 1)が 谷 であるとは、そのチェックポイントの標高が両隣のチェックポイントの標高よりも真に小さい、すなわち H_{i-1} > H_i かつ H_i < H_{i+1} を満たすことを指します。チェックポイント 1 は左隣が、チェックポイント N は右隣が存在しないため、谷にはなりません。
ここで、あるチェックポイントが谷であるかどうかは、列全体における両隣との標高の比較のみで決まります。後述するクエリで指定される区間の端点とは無関係であることに注意してください。
青木君は山岳部の顧問であり、コースのいくつかの区間について谷の個数を調べるよう高橋君に依頼しました。具体的には、Q 個のクエリが与えられ、各クエリでは整数の組 (L_j, R_j) によって区間が指定されます。
各クエリでは、L_j < i < R_j を満たすチェックポイント i(すなわちチェックポイント L_j + 1, L_j + 2, \ldots, R_j - 1)のうち、谷であるものの個数を求めてください。R_j - L_j = 1 の場合、該当するチェックポイントは存在しないため、答えは 0 です。
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
- 入力はすべて整数
入力
N Q H_1 H_2 \ldots H_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 1 行目には、チェックポイントの数を表す N と、クエリの数を表す Q が、スペース区切りで与えられる。
- 2 行目には、各チェックポイントの標高を表す H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
- 3 行目から Q 行では、各クエリの区間が与えられる。
- 2 + j 行目では、j 番目のクエリの区間の左端 L_j と右端 R_j が、スペース区切りで与えられる。
出力
Q 行出力せよ。j 行目には、j 番目のクエリに対する答え、すなわちチェックポイント L_j + 1 から R_j - 1 までの中に存在する谷の個数を出力せよ。
入力例 1
7 4 3 1 4 1 5 1 3 1 7 1 4 3 6 1 2
出力例 1
3 1 1 0
入力例 2
10 5 5 2 8 3 7 1 9 4 6 2 1 10 3 7 5 9 1 3 7 10
出力例 2
4 2 2 1 1
入力例 3
15 6 10 5 5 8 3 9 2 6 2 7 1 4 1 8 6 1 15 1 8 4 10 6 14 10 15 2 3
出力例 3
5 2 3 4 2 0
Score : 333 pts
Problem Statement
Takahashi, as the captain of the mountaineering club, is conducting a survey of hiking courses.
The course under investigation has N checkpoints arranged in a line, and each checkpoint i (1 \leq i \leq N) has a recorded elevation H_i. Takahashi is particularly interested in "valleys."
A checkpoint i (2 \leq i \leq N - 1) is a valley if its elevation is strictly less than the elevations of both adjacent checkpoints, that is, H_{i-1} > H_i and H_i < H_{i+1}. Checkpoint 1 has no left neighbor and checkpoint N has no right neighbor, so neither can be a valley.
Note that whether a checkpoint is a valley is determined solely by comparing its elevation with its two neighbors in the entire sequence. This is independent of the endpoints of the interval specified in the queries described below.
Aoki, the advisor of the mountaineering club, has asked Takahashi to count the number of valleys in several intervals of the course. Specifically, Q queries are given, and each query specifies an interval by a pair of integers (L_j, R_j).
For each query, find the number of valleys among the checkpoints i satisfying L_j < i < R_j (that is, checkpoints L_j + 1, L_j + 2, \ldots, R_j - 1). If R_j - L_j = 1, there are no such checkpoints, so the answer is 0.
Constraints
- 3 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
- All inputs are integers
Input
N Q H_1 H_2 \ldots H_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- The first line contains N, the number of checkpoints, and Q, the number of queries, separated by a space.
- The second line contains the elevations of each checkpoint H_1, H_2, \ldots, H_N, separated by spaces.
- The following Q lines give the interval for each query.
- The (2 + j)-th line contains the left endpoint L_j and the right endpoint R_j of the j-th query, separated by a space.
Output
Print Q lines. The j-th line should contain the answer to the j-th query, that is, the number of valleys among checkpoints from L_j + 1 to R_j - 1.
Sample Input 1
7 4 3 1 4 1 5 1 3 1 7 1 4 3 6 1 2
Sample Output 1
3 1 1 0
Sample Input 2
10 5 5 2 8 3 7 1 9 4 6 2 1 10 3 7 5 9 1 3 7 10
Sample Output 2
4 2 2 1 1
Sample Input 3
15 6 10 5 5 8 3 9 2 6 2 7 1 4 1 8 6 1 15 1 8 4 10 6 14 10 15 2 3
Sample Output 3
5 2 3 4 2 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君が経営する店では、N 台のパソコンが販売されています。パソコンには 1 から N までの番号が付けられており、パソコン i (1 \le i \le N) の性能は A_i、価格は B_i 円です。
今日、店に M 人の客がやってきました。客には 1 から M までの番号が付けられており、客 j (1 \le j \le M) は性能が C_j 以上であるパソコンを 1 台購入したいと考えています。客には予算の上限がなく、性能が C_j 以上であれば価格に関わらず購入します。
高橋君は、M 人の客全員に相異なるパソコンを 1 台ずつ販売したいと考えています。すなわち、客 j に販売するパソコンの番号を P_j (1 \le P_j \le N) とするとき、以下の条件をすべて満たす必要があります。
- すべての j (1 \le j \le M) について、A_{P_j} \ge C_j である。
- すべての j, k (1 \le j < k \le M) について、P_j \neq P_k である(同じパソコンを複数の客に販売することはできない)。
M 人全員に条件を満たすようにパソコンを販売できるか判定し、販売できる場合は高橋君が得られる売上金額(販売した M 台のパソコンの価格の総和 \sum_{j=1}^M B_{P_j})の最大値を求めてください。全員に販売できない場合は、代わりに -1 を出力してください。
制約
- 1 \le N \le 10^5
- 1 \le M \le 10^5
- 1 \le A_i \le 10^9
- 1 \le B_i \le 10^9
- 1 \le C_j \le 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_N B_N C_1 C_2 \dots C_M
出力
M 人全員にパソコンを販売できる場合は、得られる売上金額の最大値を 1 行で出力せよ。全員に販売できない場合は、代わりに -1 を出力せよ。
入力例 1
4 2 3 200 5 100 7 150 2 300 3 5
出力例 1
350
入力例 2
3 3 10 100 5 200 3 300 6 8 4
出力例 2
-1
入力例 3
8 5 10 500000000 20 800000000 15 300000000 30 1000000000 25 700000000 5 900000000 12 400000000 18 600000000 5 10 12 15 20
出力例 3
4000000000
入力例 4
15 8 142 851 684 394 912 628 415 972 321 445 789 123 555 890 234 678 876 543 654 321 987 876 123 999 456 234 789 765 345 888 150 300 450 600 750 800 900 950
出力例 4
5956
入力例 5
1 1 1000000000 1000000000 1000000000
出力例 5
1000000000
Score : 400 pts
Problem Statement
In a store managed by Takahashi, N computers are for sale. The computers are numbered 1 to N, and computer i (1 \le i \le N) has a performance of A_i and a price of B_i yen.
Today, M customers came to the store. The customers are numbered 1 to M, and customer j (1 \le j \le M) wants to buy one computer with a performance of at least C_j. The customers have no budget limit and will purchase a computer regardless of its price as long as its performance is at least C_j.
Takahashi wants to sell a distinct computer to each of the M customers. That is, if P_j (1 \le P_j \le N) is the number of the computer sold to customer j, the following conditions must all be satisfied:
- A_{P_j} \ge C_j for all j (1 \le j \le M).
- P_j \neq P_k for all j, k (1 \le j < k \le M) (the same computer cannot be sold to multiple customers).
Determine whether it is possible to sell computers to all M customers satisfying the conditions. If it is possible, find the maximum total revenue Takahashi can earn (the sum of the prices of the M sold computers, \sum_{j=1}^M B_{P_j}). If it is impossible to sell to all customers, output -1 instead.
Constraints
- 1 \le N \le 10^5
- 1 \le M \le 10^5
- 1 \le A_i \le 10^9
- 1 \le B_i \le 10^9
- 1 \le C_j \le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_N B_N C_1 C_2 \dots C_M
Output
If it is possible to sell computers to all M customers, print the maximum total revenue in a single line. Otherwise, print -1.
Sample Input 1
4 2 3 200 5 100 7 150 2 300 3 5
Sample Output 1
350
Sample Input 2
3 3 10 100 5 200 3 300 6 8 4
Sample Output 2
-1
Sample Input 3
8 5 10 500000000 20 800000000 15 300000000 30 1000000000 25 700000000 5 900000000 12 400000000 18 600000000 5 10 12 15 20
Sample Output 3
4000000000
Sample Input 4
15 8 142 851 684 394 912 628 415 972 321 445 789 123 555 890 234 678 876 543 654 321 987 876 123 999 456 234 789 765 345 888 150 300 450 600 750 800 900 950
Sample Output 4
5956
Sample Input 5
1 1 1000000000 1000000000 1000000000
Sample Output 5
1000000000
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
AtCoder王国には、1 から N までの番号が付けられた N 個の都市と、都市間を結ぶ M 本の鉄道路線があります。すべての路線は双方向に運行しており、移動する向きによって運賃や所要時間は変わりません。
高橋君と青木君の 2 人は、都市 1 から都市 N へ旅行しようとしています。2 人は常に一緒に行動し、財布を 1 つにしており、所持金は 2 人合わせて K 円です。
i 番目 (1 \leq i \leq M) の路線は都市 U_i と都市 V_i を結んでおり、普通列車と特急列車の 2 種類の列車が運行されています。
2 人がこの路線を利用する際は、利用するたびに以下のいずれか一方の列車を独立に選んで 2 人で乗車します。
- 普通列車:運賃は 1 人あたり A_i 円(2 人分で計 2A_i 円)、所要時間は S_i 分
- 特急列車:運賃は 1 人あたり B_i 円(2 人分で計 2B_i 円)、所要時間は T_i 分
なお、A_i と B_i、S_i と T_i の大小関係に制限はなく、特急列車より普通列車の方が運賃が高い場合や、所要時間が短い場合もあります。
2 人は同じ都市や路線を何度でも通過できます。また、都市での乗り換え時間や待ち時間は無視できます。
都市 1 から都市 N まで移動するとき、2 人が支払う運賃の総額が所持金 K 円以下となる移動方法について、所要時間の総和の最小値を求めてください。
制約
- 2 \leq N \leq 200
- 1 \leq M \leq 500
- 0 \leq K \leq 1000
- 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
- U_i \neq V_i (1 \leq i \leq M)
- 同じ都市の組を結ぶ路線が複数存在することもある。
- 1 \leq A_i, B_i \leq 1000 (1 \leq i \leq M)
- 1 \leq S_i, T_i \leq 10^9 (1 \leq i \leq M)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K U_1 V_1 A_1 B_1 S_1 T_1 U_2 V_2 A_2 B_2 S_2 T_2 : U_M V_M A_M B_M S_M T_M
出力
2 人が支払う運賃の総額が K 円以下で都市 1 から都市 N へ移動する際にかかる所要時間の総和の最小値を 1 行で出力してください。
ただし、運賃の総額が K 円以下で都市 N に到達する方法が存在しない場合は、代わりに -1 を出力してください。
入力例 1
3 3 20 1 2 3 5 10 5 2 3 4 6 12 6 1 3 8 12 30 8
出力例 1
16
入力例 2
4 3 15 1 2 3 5 10 4 2 3 3 6 12 5 3 4 3 4 8 3
出力例 2
-1
入力例 3
6 8 80 1 2 10 5 15 35 1 2 8 12 25 10 1 3 15 25 40 18 2 4 6 10 20 8 3 4 12 18 22 11 3 5 7 14 30 12 4 6 9 15 18 7 5 6 11 20 25 9
出力例 3
25
入力例 4
12 18 300 1 2 15 30 800000000 350000000 1 3 20 45 600000000 250000000 2 4 12 25 500000000 200000000 3 4 10 20 400000000 180000000 2 5 25 50 700000000 300000000 3 6 18 35 550000000 220000000 4 7 14 28 450000000 190000000 5 7 22 40 650000000 280000000 6 8 16 32 480000000 210000000 7 9 15 30 520000000 230000000 8 9 12 24 380000000 160000000 5 10 30 60 900000000 400000000 7 10 20 42 620000000 270000000 8 11 18 36 580000000 240000000 9 11 14 28 440000000 190000000 10 12 25 50 750000000 320000000 11 12 22 45 680000000 290000000 4 8 28 55 850000000 360000000
出力例 4
1760000000
入力例 5
2 1 2 1 2 1 2 10 5
出力例 5
10
Score : 433 pts
Problem Statement
The Kingdom of AtCoder has N cities numbered 1 to N, and M railway lines connecting cities. All lines operate bidirectionally, and the fare and travel time do not depend on the direction of travel.
Takahashi and Aoki are planning to travel from City 1 to City N. The two always travel together, share a single wallet, and have a total of K yen between them.
The i-th line (1 \leq i \leq M) connects City U_i and City V_i, and two types of trains operate on it: local trains and express trains.
Each time the two use this line, they can independently choose one of the following train types to take together:
- Local train: Fare is A_i yen per person (a total of 2A_i yen for both), and travel time is S_i minutes.
- Express train: Fare is B_i yen per person (a total of 2B_i yen for both), and travel time is T_i minutes.
There are no restrictions on the relative sizes of A_i and B_i, or S_i and T_i; a local train may be more expensive or faster than an express train.
They may visit the same city or pass through the same line multiple times. Also, transfer and waiting times at cities can be ignored.
Find the minimum possible total travel time to travel from City 1 to City N such that the total fare paid by the two does not exceed their funds of K yen.
Constraints
- 2 \leq N \leq 200
- 1 \leq M \leq 500
- 0 \leq K \leq 1000
- 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
- U_i \neq V_i (1 \leq i \leq M)
- There may be multiple lines connecting the same pair of cities.
- 1 \leq A_i, B_i \leq 1000 (1 \leq i \leq M)
- 1 \leq S_i, T_i \leq 10^9 (1 \leq i \leq M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K U_1 V_1 A_1 B_1 S_1 T_1 U_2 V_2 A_2 B_2 S_2 T_2 : U_M V_M A_M B_M S_M T_M
Output
Print the minimum possible total travel time to travel from City 1 to City N with a total fare of at most K yen in a single line.
If it is impossible to reach City N with a total fare of at most K yen, print -1 instead.
Sample Input 1
3 3 20 1 2 3 5 10 5 2 3 4 6 12 6 1 3 8 12 30 8
Sample Output 1
16
Sample Input 2
4 3 15 1 2 3 5 10 4 2 3 3 6 12 5 3 4 3 4 8 3
Sample Output 2
-1
Sample Input 3
6 8 80 1 2 10 5 15 35 1 2 8 12 25 10 1 3 15 25 40 18 2 4 6 10 20 8 3 4 12 18 22 11 3 5 7 14 30 12 4 6 9 15 18 7 5 6 11 20 25 9
Sample Output 3
25
Sample Input 4
12 18 300 1 2 15 30 800000000 350000000 1 3 20 45 600000000 250000000 2 4 12 25 500000000 200000000 3 4 10 20 400000000 180000000 2 5 25 50 700000000 300000000 3 6 18 35 550000000 220000000 4 7 14 28 450000000 190000000 5 7 22 40 650000000 280000000 6 8 16 32 480000000 210000000 7 9 15 30 520000000 230000000 8 9 12 24 380000000 160000000 5 10 30 60 900000000 400000000 7 10 20 42 620000000 270000000 8 11 18 36 580000000 240000000 9 11 14 28 440000000 190000000 10 12 25 50 750000000 320000000 11 12 22 45 680000000 290000000 4 8 28 55 850000000 360000000
Sample Output 4
1760000000
Sample Input 5
2 1 2 1 2 1 2 10 5
Sample Output 5
10