Time Limit: 2 sec / Memory Limit: 256 MB
問題文
1 から N までの番号がついたスレッドのある掲示板があります。 スレッドは書き込みがあると一番上に来ます。 書き込み前のスレッドは上から順に 1 から N の順に並んでいました。 M 個の書き込みが書き込まれた順で与えられるので、全ての書き込みが終わった後のスレッドの順番を出力してください。
例えば、3 個のスレッドがある掲示板に 2、3、1 の順で書き込みがあると、以下のようになります。
従って、書き込み後のスレッドの順番は 1、3、2 となります。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 a_2 : a_M
- 1 行目には、スレッドの数と書き込みの数を表す 2 つの整数 N, M (1 ≦ N ≦ 10^5, 1 ≦ M ≦ 10^5) が空白区切りで与えられる。
- 続く M 行の i 行目には i 番目に書き込まれたスレッドを表す整数 a_i (1 ≦ a_i ≦ N) が与えられる。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 100, 1 ≦ M ≦ 100 を満たすデータセットに正解した場合は 30 点が与えられる。
出力
全ての書き込みが終わった後のスレッドの番号を上から順に 1 行ずつ出力せよ。
入力例1
3 3 2 3 1
出力例1
1 3 2
1 つめの書き込みの後、スレッドは上から 2、1、3 の順で並んでいる。 2 つめの書き込みの後、スレッドは上から 3、2、1 の順で並んでいる。 3 つめの書き込みの後、スレッドは上から 1、3、2 の順で並んでいる。
入力例2
3 3 1 1 1
出力例2
1 2 3
元から 1 番上にあったスレッド 1 にしか書き込みがなかったので、スレッドの順番は変わらない。
入力例3
10 10 3 1 4 1 5 9 2 6 5 3
出力例3
3 5 6 2 9 1 4 7 8 10
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
アリの高橋くんは凸多角形状の板の上にいます。 高橋くんは向いている方向にまっすぐ歩いていきますが、どの方向を向いているかはわかりません。 高橋くんは板の周囲にたどり着くと落ちてしまいます。 高橋くんの位置と板を構成する凸多角形の頂点の位置が与えられるので、高橋くんが板から落ちるまでに歩く最短の距離を求めてください。位置は全て２次元座標で与えられます。
入力
入力は以下の形式で標準入力から与えられる。
x y N x_1 y_1 x_2 y_2 : x_N y_N
- 1 行目には、高橋くんがいる位置の座標を表す整数 x, y (-100 ≦ x ≦ 100, -100 ≦ y ≦ 100) が空白区切りで与えられる。
- 2 行目には、板を構成する凸多角形の頂点数を表す整数 N (3 ≦ N ≦ 10) が与えられる。
- 3 行目からの N 行には、板の頂点の座標を表す整数 x_i y_i (-100 ≦ x_i ≦ 100, -100 ≦ y_i ≦ 100) が空白区切りで与えられる。ただし、板の頂点は反時計回りの順で与えられる。
- 高橋くんのいる位置は周囲を含まない板の内部である。
- 板は凸多角形であることが保証される。
出力
高橋くんが板から落ちるまでに歩く最短の距離を 1 行に出力せよ。出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。
入力例1
0 0 4 100 100 -100 100 -100 -100 100 -100
出力例1
100
どれかの辺に垂直に歩いて行くと、100 だけ歩いて板から落ちます。
入力例2
10 10 3 0 100 -100 -100 100 -100
出力例2
31.3049516850
入力例3
34 6 7 -43 -65 -23 -99 54 -68 65 92 16 83 -18 43 -39 2
出力例3
25.0284205314
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんは遠足に持って行くおやつを選んでいます。 この遠足には合計で P 円までのおやつを持って行くことができます。 ただし、担任のけんしょう先生はやさしいので、どの 1 つのおやつについても、そのおやつがなければ合計が P 円以下になるのであれば許してくれます。
例えば、100 円まで持って行くことができる時に、値段がそれぞれ 30 円、40 円、50 円のおやつを持って行くと、どの 1 つのおやつを取り除いても合計が 100 円以下になるので許してくれます。 しかし、40 円、50 円、60円のおやつを持って行くと、40 円のおやつがなかったとしても合計は 110 円となり 100 円を超えているので、やさしいけんしょう先生もこれは許してくれません。
高橋くんが持って行きたいおやつは N 種類あり、それぞれに値段と満足度があります。 高橋くんはそれぞれの種類のおやつについて最大でも 1 つしか遠足に持って行きません。 けんしょう先生が許してくれるおやつの選び方のうち、満足度の合計が最も大きくなるように選んだ時の満足度の合計を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N P a_1 b_1 a_2 b_2 : a_N b_N
- 1 行目には、高橋くんが持って行きたいおやつの種類と合計で持っていけるおやつの金額を表す 2 つの整数 N, P (1 ≦ N ≦ 5,000, 1 ≦ P ≦ 5,000) が空白区切りで与えられる。
- 2 行目からの N 行には高橋くんの持って行きたいそれぞれおやつの値段と満足度を表す整数 a_i b_i (1 ≦ a_i ≦ 100, 1 ≦ b_i ≦ 100) が空白区切りで与えられる。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 100, 1 ≦ P ≦ 100 を満たすデータセットに正解した場合は 50 点が与えられる。
出力
けんしょう先生が許してくれるおやつの選び方のうち、満足度の合計が最も大きくなるように選んだ時の満足度の合計を 1 行に出力せよ。
入力例1
4 100 30 50 40 40 50 100 60 80
出力例1
190
1 つ目と 2 つ目と 3 つ目のおやつを選ぶと満足度の合計が 190 となり、これがけんしょう先生が許してくれる選び方の中で最大である。
入力例2
5 100 40 10 30 50 60 80 20 40 20 70
出力例2
200
入力例3
10 654 76 54 62 19 8 5 29 75 28 4 76 16 96 24 79 30 20 64 23 56
出力例3
347
この入力は部分点に含まれない。
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
4 つの整数 X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31}) が与えられます。ただし、P は素数です。 X^i (A ≦ i ≦ B) を P で割った余りの最小値を求めてください。
この問題の入力は得点に影響しない入力例 1 を除いて、このC++プログラムを用いて生成しました。擬似乱数生成器の初期化に用いられるプログラムの第 1 引数は 1 以上 10,000 以下の整数を用いました。このファイルの i 行目 (1 ≦ i ≦ 10,000) は、入力生成プログラムの第 1 引数が i であるときの出力と一致します。すなわち、与えられるテストケースは入力例 1 を除いて、このファイルのいずれかの行と一致します。
入力
入力は以下の形式で標準入力から与えられる。
X P A B
- 1 行目には、4 つの整数 X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31}) が空白区切りで与えられる。ただし、P は素数である。
出力
X^i (A ≦ i ≦ B) を P で割った余りの最小値を 1 行に出力せよ。
入力例1
2 11 3 9
出力例1
3
X^i (A ≦ i ≦ B) を P で割った余りは 8, 5, 10, 9, 7, 3, 6 であるので、最小値は 3 である。 この入力は入力生成プログラムを用いて作られたものではないので、得られる得点に影響しない。
入力例2
15 7159 12 12818
出力例2
1
この入力は入力生成プログラムの第 1 引数に 1 を与えて生成した。
入力例3
1400884 50141599 4 458568
出力例3
114
この入力は入力生成プログラムの第 1 引数に 3 を与えて生成した。
入力例4
1591755 291456379 215 1223
出力例4
96324
この入力は入力生成プログラムの第 1 引数に 25 を与えて生成した。