Time Limit: 2 sec / Memory Limit: 256 MB
問題文
すべての桁の数字が同じであるような正の整数を ゾロ目数 と呼ぶことにします。小さい方から N 番目のゾロ目数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目には、整数 N (1≦N≦50) が与えられる。
出力
小さい方から N 番目のゾロ目数を出力せよ。出力の末尾には改行を入れること。
入力例1
1
出力例1
1
入力例2
11
出力例2
22
ゾロ目数を小さい方から列挙すると、1，2，3，4，5，6，7，8，9，11，22，... となります。
入力例3
50
出力例3
555555
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君と青木君は N 個の石からなる石の山を使って石取りゲームをすることにしました。ゲームのルールは以下の通りです。
- プレイヤーは交互に 1 個以上の石を山から取る。
- 最後の石を取ったプレイヤーの勝利である。
先手の高橋君は一度に最大 A 個までの石を取ることが可能であり、後手の青木君は一度に最大 B 個までの石を取ることが可能です。
2 人が最適に行動したとき勝利するプレイヤーがどちらか判定するのがあなたの仕事です。
入力
入力は以下の形式で標準入力から与えられる。
N A B
- 1 行目に石の数を表す整数 N (1≦N≦10^{9}) が与えられる。
- 2 行目に高橋君と青木君が一度に山から取れる石の最大個数を表す 2 つの整数 A,B (1≦A,B≦10^{9}) が空白区切りで与えられる。
部分点
この問題には部分点が設定されている。
- A = B を満たすデータセットに正解した場合は 40 点が与えられる。
- A ≠ B を満たすデータセットに正解した場合は 60 点が与えられる。
- 上記の 2 つのデータセット両方に正解することにより合計 100 点が得られる。
出力
先手の高橋君が勝つ場合は Takahashi を、後手の青木君が勝つ場合は Aoki を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例 1
5 3 3
出力例 1
Takahashi
- 先手の高橋君が 1 個の石を取ることで、後手の青木君がどのように石を取っても勝つことが可能です。
- このケースは A = B の制約を満たします。
入力例 2
4 3 3
出力例 2
Aoki
- 先手の高橋君がどのように石を取っても、勝つことは不可能です。
- このケースは A = B の制約を満たします。
入力例 3
5 3 2
出力例 3
Takahashi
- 先手の高橋君が 2 個の石を取ることで、後手の青木君がどのように石を取っても勝つことが可能です。
- このケースは A ≠ B の制約を満たします。
入力例 4
1000000000 1000000000 1
出力例 4
Takahashi
- 先手の高橋君が 1,000,000,000 個の石を取ることで勝つことが可能です。
- このケースは A ≠ B の制約を満たします。
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
高橋君と青木君は合コンを企画しました。 2 人は N 人の男性と、 M 人の女性を集めることに成功しました。男性には 1 から N の、女性には 1 から M の番号がそれぞれ割り当てられています。企画者である高橋君と青木君の目的はこの合コンで成立するカップルの数を最大化することです。 ここで、カップルとは 1 組の男女のことです。また、それぞれの人は 2 つ以上のカップルに含まれていてはいけません。
i (1≦i≦N) 番の男性は年収が A_i 円であり、年収が B_i 円以上の女性とカップルになりたいと考えています。 j (1≦j≦M) 番の女性は年収が C_j 円であり、年収が D_j 円以上の男性とカップルになりたいと考えています。
高橋君と青木君は i 番の男性と j 番の女性の要求が同時に満たされるとき、すなわち B_i≦C_j かつ D_j≦A_i が満たされるとき、 i 番目の男性と j 番目の女性によるカップルを成立させることが可能です。
この合コンで成立させることができるカップルの数の最大値を調べるのがあなたの仕事です。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 : A_N B_N C_1 D_1 C_2 D_2 : C_M D_M
- 1 行目に男女の数を表す 2 つの整数 N,M (1≦N,M≦150,000) が与えられる。
- 2 行目からの N 行のうち i (1≦i≦N) 行目には、i 番の男性の年収と相手に要求する年収を表す 2 つの整数 A_i,B_i (1≦A_i,B_i≦10^9) が空白区切りで与えられる。
- 2+N 行目からの M 行のうち j (1≦j≦M) 行目には、j 番の女性の年収と相手に要求する年収を表す 2 つの整数 C_j,D_j (1≦C_j,D_j≦10^9) が空白区切りで与えられる。
部分点
この問題には部分点が設定されている。
- 任意の i,j (1≦i≦N,1≦j≦M) において B_i≦C_j を満たすデータセットに正解した場合は 30 点が与えられる。
出力
この合コンで成立させることができるカップルの数の最大値を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例 1
3 3 3 5 2 4 4 5 3 1 6 2 5 3
出力例 1
2
- 1 番の男性と 2 番の女性のカップル、 2 番の男性と 3 番の女性のカップルを成立させたときが、成立するカップルの数が最大になる場合の 1 つであり、成立するカップルの数は 2 です。
- それぞれの人について、複数のカップルに含まれてはならないことに注意してください。
- このケースは男性の要求する年収より女性の年収が小さい場合が存在するため、部分点の追加制約を満たしません。
入力例 2
3 4 4 1 2 1 7 1 5 3 12 1 1 10 8 5
出力例 2
3
- 1 番の男性と 1 番の女性の、 2 番の男性と 2 番の女性の、 3番の男性と 4番の女性のカップルを成立させたときが、成立するカップルの数が最大になる場合であり、その数は 3 です。
- このケースは部分点の追加制約を満たします。
入力例 3
5 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 3
1
- このケースは部分点の追加制約を満たします。
入力例 4
1 1 1 1 1 2
出力例 4
0
- 成立するカップルの数が 0 の場合もあることに注意してください。
- このケースは部分点の追加制約を満たします。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
H 行、W 列のマス目があります。第 i (0≦i≦H-1) 行、第 j (0≦j≦W-1) 列のマスを (i,\ j) と表します。
最初、マス (0,\ 0) にうさぎがいます。うさぎは以下の操作を繰り返します。
- 今いるマスに色が塗られていれば、操作を終了する。
- 今いるマスに色が塗られていなければ、今いるマスに色を塗り、今いるマス (i,\ j) から ((i+1)\ {\rm mod}\ H,\ j) または (i,\ (j+1)\ {\rm mod}\ W) へ移動する。
うさぎがすべてのマスに色を塗った後、マス (0,\ 0) で操作を終了するような方法は何通りでしょうか？ 10^9+7 で割った余りを求めてください。
ただし、うさぎの辿った経路が異なるとき、またそのときのみ、2 つの方法は異なるものとします。
入力
入力は以下の形式で標準入力から与えられる。
H W
- 1 行目には、マス目の行数 H (2≦H≦10^6) と列数 W (2≦W≦10^6) が空白区切りで与えられる。
出力
答えを 10^9+7 で割った余りを出力せよ。出力の末尾には改行を入れること。
入力例1
2 2
出力例1
2
図の 2 通りです。
入力例2
6 3
出力例2
3
入力例3
3 4
出力例3
0
入力例4
10 10
出力例4
260
入力例5
200 300
出力例5
551887980
答えを 10^9+7 で割った余りを出力してください。