実行時間制限: 2 sec / メモリ制限: 256 MiB
問題文
パンチくんの会社では、ICカードを使って勤怠管理を行っています。パソコンにICカードをピッとタッチすると、出勤時刻や退勤時刻が記録されます。
このシステムでは、休憩時にもICカードをタッチすることで、休憩時間も管理することができます。例えば、
- 時刻300
- 時刻500
- 時刻600
- 時刻800
（単位：分）という打刻データがあった場合、それぞれ
- 出勤
- 休憩開始
- 休憩終了
- 退勤
と判定され、休憩を除いた合計400分が、合計の勤務時間と計算されます。休憩は複数回とることもできます。
パンチくんのとある 1 日の打刻データが与えられるので、その日の最初の出勤から、最後の退勤までの、合計の勤務時間を計算して下さい。ただし、 1 日の打刻データが奇数個ということはありえないので、その場合は”error”（ダブルクオーテーション（”）なし）と出力して下さい。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
- 1 行目には、打刻データの数 N (1 ≦ N ≦ 100) が与えられる。
- 2 行目には、 N 回の打刻時刻 a_i (0 ≦ a_i ≦ 1440) が、順番に空白区切りで与えられる。
- i < j のとき、 a_i < a_j であることが保証されている。
出力
合計の勤務時間を 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
4 300 500 600 800
出力例1
400
問題文の例です。
入力例2
2 0 1440
出力例2
1440
休憩がないこともあります。
こんなブラック企業で働いてはいけません。
入力例3
6 540 600 720 780 960 1020
出力例3
180
休憩を複数回とることもできます。
パンチくん、だいぶさぼっています。
入力例4
3 1 2 3
出力例4
error
打刻回数が奇数回ということはありえません。
実行時間制限: 2 sec / メモリ制限: 256 MiB
問題文
パンチくんは、 7 という数字が大好きです。先日も、ナナにまつわるゲームをリリースし、順調にユーザ数を伸ばしています。
さて、パンチくんは、 7 の倍数に興味をもちました。以下の様なゲームを考えます。
パンチくんとニコルちゃんは、数字の 1〜7 のカードを、十分たくさん持っています。まずパンチくんは、カードをいくつか並べて、ある自然数を作ります。次にニコルちゃんは、カードをいくつか並べて、以下の条件を満たす自然数を作ります。
- ニコルちゃんが作った数字は、パンチくんが作った数字以下である。
- ニコルちゃんが作った数字は、 10 進数表記で、 7 の倍数である。
ニコルちゃんは、何通りの数字を作ることができるでしょうか。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目には、パンチくんが作った自然数 N (1 ≦ N < 1000000000000000000 (10^{18})) が与えられる。
- N の各桁の数値は、 {1, 2, 3, 4, 5, 6, 7} のいずれかであることが保証されている。
部分点
1 ≦ N < 100000 (10^5) を満たすテストケースに正解した場合、部分点として 40 点が与えられる。
出力
ニコルちゃんが作ることのできる数字の個数を、 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
31
出力例1
3
ニコルちゃんが作ることのできる数字は、 7, 14, 21 の 3 つです。 28 は作ることができないことに注意して下さい。
入力例2
7
出力例2
1
入力例3
111
出力例3
8
十分たくさんのカードを持っているので、ニコルちゃんは同じ数字を並べた 77 という数字を作ることも可能です。
入力例4
777777777777777777
出力例4
271402266318408
実行時間制限: 2 sec / メモリ制限: 256 MiB
問題文
ソーシャルゲームを運営するためには、日々のユーザ数の増減を観察することが欠かせません。
ゲーム会社を運営しているパンチくんは、最もユーザが増加した期間に、何人ユーザが増加したかを調べようとしています。
日々のユーザの増減数 a_1, a_2, …, a_N が与えられるので、ユーザ数の増減数が最大となる期間のユーザの増減数を求めて下さい。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
- 1 行目には、調査対象となる期間の日数 N (1 ≦ N ≦ 100000) が与えられる。
- 2 行目には、調査対象となる期間の i 日目のユーザの増減数 a_i (-1000 ≦ a_i ≦ 1000) が与えられる。
部分点
1 ≦ N ≦ 3000 を満たすテストケースに正解した場合、部分点として 40 点が与えられる。
出力
ユーザの増減数が最大となる期間（ 1 日以上）のユーザ増減数を、 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
7 3 -4 2 3 -1 2 -1
出力例1
6
3 日目から 6 日目までの、 (2, 3, -1, 2) の増加数 6 が最大です。
入力例2
3 10 20 30
出力例2
60
全期間が、ユーザの増減数が最大となる期間となります。
入力例3
3 -4 -2 -5
出力例3
-2
出力はマイナスとなることがあります。 出力対象となる期間は 1 日以上であることに注意して下さい。
実行時間制限: 2 sec / メモリ制限: 256 MiB
問題文
パンチくんが運営している会社では、サバイバルゲームが大流行りです。
通常のサバイバルゲームはチームが 2 つですが、パンチくんは普通のゲームに飽きてしまったため、多くのチームで対戦することにしました。
参加人数と、チームの数が与えられるので、チームの分け方が何パターンあるか求めて下さい。
ただし、各参加者は必ずどれか 1 つだけのチームに所属するものとし、また 0 人のチームがあってはならないものとします。
入力
入力は以下の形式で標準入力から与えられる。
N M
- サバイバルゲームに参加する人数 N (2 ≦ N ≦ 1000) と、チームの数 M (2 ≦ M ≦ N) が与えられる。
部分点
M = 2 を満たすテストケースに正解した場合、部分点として 40 点が与えられる。
出力
チームの分け方のパターン数を 1000000007( = 1,000,000,007) で割った余りを出力せよ。出力の末尾には改行をいれること。
入力例1
2 2
出力例1
1
2 人を 2 チームに分ける分け方は、 1 通りしかありません。
入力例2
3 2
出力例2
3
3 人を 2 チームに分ける分け方は、
- { A, B }, { C }
- { A, C }, { B }
- { A }, { B, C }
の 3 通りです。
参加者は互いに区別がつきますが、チームは区別がつかないことに注意して下さい。
{ A, B }, { C }と、{ C }, { A, B } は同じものとしてカウントします。
入力例3
500 2
出力例3
695241506
入力例4
20 10
出力例4
584923236
実行時間制限: 2 sec / メモリ制限: 256 MiB
問題文
幼少のパンチくんは、全部で N 店あるお菓子やさんを巡ろうとしています。
このうちのいくつかの店では、スタンプをカードに押してもらえます。その店のスタンプがあると、さらに別のいくつかの店で、ボーナスのお菓子がもらえるというシステムです。
ただし、パンチくんは一度行った店には 2 回行きたくありません。そのため、例えば
- 店 A のスタンプがあると、店 B でお菓子が 3 個もらえる
- 店 B のスタンプがあると、店 A でお菓子が 2 個もらえる
という 2 つの条件が重なっている場合 、どちらかのお菓子を諦めなければいけません。この場合、後者を諦めて、前者の 3 個のお菓子をもらうのが得です。
パンチくんがもらえるお菓子の最大値はいくらでしょうか。
入力
入力は以下の形式で標準入力から与えられる。
N E a_1 b_1 c_1 a_2 b_2 c_2 : a_E b_E c_E
- 1 行目には、お菓子屋さんの数を表す整数 N (1 ≦ N ≦ 16) と、お菓子をもらえる店舗関係の数を表す整数 E (0 ≦ E ≦ N×N)がスペース区切りで与えられる。
- 2 行目から E 行では、お菓子をもらえる店舗関係の情報が与えられる。
このうち i 行目では、 3 つの整数 a_i (1 ≦ a_i ≦ N), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ 1000) が与えられる。
これらは、「店 a_i のスタンプがあると、店 b_i にて、お菓子が c_i 個もらえる」ということを表している。 - i≠j のとき、 a_i≠a_j または b_i≠b_j であることが保障されている。
部分点
1 ≦ N ≦ 8 を満たすテストケースに正解した場合、部分点として 130 点が与えられる。
出力
パンチくんがもらえるお菓子の最大値を、 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
2 2 1 2 3 2 1 2
出力例1
3
問題文に記載されている例です。
入力例2
4 3 1 2 10 1 3 20 1 4 30
出力例2
60
全てのお菓子をもらうことが出来ます。
入力例3
3 3 1 2 20 2 3 30 3 1 10
出力例3
50
10 個のお菓子を諦めることで、最大値を得ます。
入力例4
16 1 4 4 1000
出力例4
0
同じ店に 2 回行くことはできないので、お菓子はもらえません。また、このスタンプサービスと関係ない店がいくつかあることもあります。
入力例5
4 6 4 1 3 1 3 3 4 2 3 3 4 2 2 3 3 2 2 10
出力例5
12