Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はブラウザでネットサーフィンをするのが大好きです。
しかし、タブを開きすぎる癖があるので、よくブラウザがクラッシュします。
高橋君が使っているブラウザは開かれているタブが L 個を超えるとクラッシュします。
ブラウザはクラッシュすると自動で再起動して、1 個のタブが開いている状態になります。
初め、高橋君のブラウザは 1 個のタブが開かれている状態です。
そのあとの高橋君の「新しいタブを開く」と「タブを閉じる」の履歴が与えられるので、高橋君が何回ブラウザをクラッシュさせるかを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N L S
- 1 行目には高橋君が行った行動の個数を表す整数 N(1 ≦ N ≦ 10^5) とブラウザがクラッシュする基準を表す整数 L(1 ≦ L ≦ 10^5) が空白区切りで与えられる。
- 2 行目には高橋君の行動の履歴を表す
+と-のみからなる N 文字の文字列 S が与えられる。 - S は高橋君の行動を時系列順にならべたものであり、
+は新しいタブを開くことを、-はあるタブを閉じることを表す。 - タブが 1 個のときにタブを閉じることは無い。
出力
高橋君がブラウザをクラッシュさせる回数を表す整数を 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
6 2 +++-++
出力例1
2
- 最初のタブの個数は 1 個です。
- 1 回目の操作が終わったあとのタブの個数は 2 個です。
- 2 回目の操作が終わるとタブが 3 個になりますが L より大きいのでブラウザはクラッシュして、タブは 1 個になります。
- 3 回目の操作が終わったあとのタブの個数は 2 個です。
- 4 回目の操作が終わったあとのタブの個数は 1 個です。
- 5 回目の操作が終わったあとのタブの個数は 2 個です。
- 6 回目の操作が終わるとタブが 3 個になりますが L より大きいのでブラウザはクラッシュして、タブは 1 個になります。
よって合計で 2 回、ブラウザはクラッシュします。
入力例2
20 20 ++-+-+++--+++++-++++
出力例2
0
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
座標平面上に N 個の点があります。
これらの点は全て、x 座標 と y 座標の値が共に整数です。つまり格子点上にあります。
そのうえ、これらの点は全て、ある点 P とのマンハッタン距離が同じであることがわかっています。ここで、マンハッタン距離とは、 2 つの点の座標がそれぞれ (a, b), (c, d) であるとき、 | a-c | + | b-d | で計算される距離のことです。
そして、点 P も格子点上にあります。
点 P としてあり得る点を 1 つ挙げてください。
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 : x_N y_N
- 1 行目には点の個数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の点の座標を表す 2 つの整数 x_i, y_i(-10^9 ≦ x_i, y_i ≦ 10^9)が与えられる。
- i ≠ j ならば (x_i, y_i) ≠ (x_j, y_j) が成り立つ。
- N 個の点は必ずある点からのマンハッタン距離が等しい。
出力
点 P としてあり得る点の x 座標の値 Pxと y 座標の値 Py を順に空白区切りで1行に出力せよ。
このとき -10^9 ≦ Px, Py ≦ 10^9 が成り立ってなければならない(そのような解が存在することは保証される)。
出力の末尾に改行を入れること。
入力例1
3 1 2 3 4 2 5
出力例1
2 3
与えられた点は全て点 (2, 3) からのマンハッタン距離が 2 です。
入力例2
3 0 1 1 0 -1 0
出力例2
0 -2016
y ≦ 0 であるような点 (0, y) は全て、点 P としての条件を満たします。 この場合 -10^9 ≦ y であるかぎり、どれを出力しても構いません。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋語には N 種類の文字があります。
この問題では便宜上、各文字に辞書順で小さい順に 1 ～ N の整数を割り振って扱うことにします。
高橋語の単語は全て N 文字からなり、N 種類の文字が全てちょうど 1 個ずつ含まれます。 また、そのような文字列は全て高橋語の単語です。
つまり、高橋語の単語は N! 個あります。
ある N 以下の正の整数 K が与えられるので、高橋語の単語の中で辞書順で小さい方から N! ÷ K 番目の単語を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K
- 1 行目には 2 つの整数 N, K(1 ≦ K ≦ N ≦ 10^5) が空白区切りで与えられます。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 20 を満たすデータセットに正解した場合は 30 点が与えられる。
- 1 ≦ N ≦ 10^5 を満たすデータセットに正解した場合はさらに 70 点が与えられる。合計で100点となる。
出力
出力は N 行からなる。 i 行目には高橋語の単語の中で辞書順で小さい方から N! ÷ K 番目の単語の i 文字目の文字に対応する整数を出力せよ。 出力の末尾に改行を入れること。
入力例1
4 3
出力例1
2 1 4 3
1,2,3,4 の並び替えのうち、辞書順で小さい方から 4! ÷ 3 = 8 番目の文字を出力しなければなりません。 高橋語の単語のうち辞書順で小さい方から順に 8 個を列挙すると
1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
2, 1, 3, 4
2, 1, 4, 3
となります。よって 2, 1, 4, 3が求めるべき単語です。
入力例2
11 7
出力例2
2 7 9 5 4 11 10 8 6 3 1
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
縦に N 行、横に N 列の方眼紙があります。
この方眼紙上の最も左上のマスから下に X マス、右に Y マス進んだところにあるマスをマス (X, Y) と呼ぶことにします。 つまり、最も左上のマスはマス (0, 0) 、右下のマスはマス (N-1, N-1) になります。
初め、全てのマスには整数 0 が書き込まれています。
この方眼紙に Q 回のクエリ操作を行うことを考えます。 クエリ操作は 3 種類あり以下のとおりです。
1 A B C: A ≦ X+Y ≦ B となる全てのマス (X, Y) にかかれている整数に C を加える。0 ≦ A ≦ B ≦ 2N-2, -10^5 ≦ C ≦ 10^5 を満たすことが保証される。2 A B C: A ≦ X-Y ≦ B となる全てのマス (X, Y) にかかれている整数に C を加える。1-N ≦ A ≦ B ≦ N-1, -10^5 ≦ C ≦ 10^5 を満たすことが保証される。3 A B C D: A ≦ X ≦ B かつ C ≦ Y ≦ D となる全てのマス (X,Y) の中の最大値 M と、その範囲の中に M が書かれたマスがいくつあるか求める。0 ≦ A ≦ B ≦ N-1, 0 ≦ C ≦ D ≦ N-1 を満たすことが保証される。
このようなクエリを順番に処理するプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
N Q Query_1 Query_2 : Query_Q
- 1 行目には方眼紙の大きさを表す整数 N(1 ≦ N ≦ 5,000) とクエリの個数を表す整数 Q(1 ≦ Q ≦ 5,000)が空白区切りで与えられる。
- 2 行目からの Q 行の内 i 行目には i 番目のクエリが与えられる。クエリの形式は問題文中で与えたとおりである。
- 3 種類目のクエリは 1 個以上与えられる。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 50を満たすデータセットに正解した場合は 10 点が与えられる。
- 1 ≦ N ≦ 500を満たすデータセットに正解した場合はさらに 20 点が与えられる。合計で30点となる。
- 1 ≦ N ≦ 5,000 を満たすデータセットに正解した場合はさらに 70 点が与えられる。合計で100点となる。
出力
出力の行数は 3 種類目のクエリの個数と等しくなる。 i 行目には i 番目の 3 種類目のクエリの答えを出力せよ。 範囲の中の最大値を M、その個数を C とすると M, C をこの順で空白区切りで出力せよ。 出力の末尾に改行を入れること。
入力例1の説明にミスがあったため、正しいものに差し替えました（21:51）
入力例1
4 4 1 1 4 2 3 0 1 2 3 2 -2 1 3 3 0 3 1 3
出力例1
2 4 5 7
1 番目のクエリを処理した後の方眼紙の様子は以下の様になります。
2 番目のクエリの範囲は以下の様な範囲です。
よって最大値は 2、 個数は 4 個になります。
3 番目のクエリを処理した後の方眼紙の様子は以下の様になります。
4 番目のクエリの範囲は以下の様な範囲です。
よって最大値は 5、 個数は 7 個になります。
入力例2
50 20 2 5 40 6 1 69 94 5 3 8 39 31 32 2 -29 -21 -10 2 20 43 3 2 -37 36 -10 2 -18 45 5 2 30 39 -2 3 0 1 19 33 3 27 47 0 43 3 0 1 28 39 1 90 97 0 2 -46 31 7 1 81 81 4 1 11 54 3 3 10 29 26 30 1 39 45 3 1 70 97 -4 3 24 46 14 34 3 1 18 48 48
出力例2
11 5 -5 1 14 8 0 3 5 82 16 2 10 5