お弁当あたため屋さん
問題説明
ここは電子レンジでお弁当を温めることに特化した工場です。
工場内の冷凍庫に保管されている冷たいお弁当を電子レンジを使って1分間温めるのがお仕事です。
数日後に近くでイベントが開催されるため、イベント当日のお弁当の需要が急増しています。
顧客がお弁当を取りに来る時刻と個数が書かれた予約リストが与えられるので、
顧客をお待たせしないよう、あらかじめ計画的にお弁当を温めておく必要があります。
加熱後のお弁当は顧客が取りに来るまでの間、専用の保温棚で保温する必要があります。
必要な保温棚の数が最小となるようにした場合、その時必要な保温棚の数を解答してください。
- 冷凍庫には十分な数のお弁当が保管されています。
- 工場には3台の電子レンジが設置されています。3台同時に使用することも可能です。
- それぞれの電子レンジでは、お弁当を一つずつ温めることができます。
- 保温棚一つにつき一つのお弁当を入れることができます。
- 作業員は非常に優秀なので、瞬時（0秒）に電子レンジや保温棚にお弁当を出し入れすることができます。
- 保温棚に入れていないお弁当は冷めてしまうので、電子レンジに入れたまま放置したり、作業員が持ち続けてはいけません。
加熱後、すぐ保温棚に移動させる規則となっています。 - ただし、顧客がお弁当を取りに来た時に加熱が完了する場合に限り、電子レンジ内からお弁当を取り出して直接渡しても構いません。
- 予約状況によっては、準備に数日要する場合があります。前日までは、お弁当の需要はないものとして扱ってください。
- 保温棚に入れている間、お弁当は冷めることはありません。いつまでも熱々のお弁当を提供することができます。
入力データは、顧客がお弁当を取りに来る時刻の文字列と個数の配列として、以下の形式で与えられます。
{{"時刻1",個数1},{"時刻2",個数2},…,{"0:00:00",0}}
お弁当の個数が0個の場合は入力データの終端を表します。
顧客数は100以下、お弁当の総数は10000個以下です。
3パターンの入力データがあります。
それぞれに対する答えを求め、カンマ区切りで答えてください。
例題
例題の入力データ コピー コピーされました
※本番データではありません{"12:00:10",2},
{"12:01:03",3},
{"0:00:00",0}
},
{
{"0:04:00",5},
{"0:02:20",12},
{"0:00:00",0}
},
{
{"18:20:54",2},
{"18:21:47",2},
{"18:22:22",2},
{"18:23:18",2},
{"18:23:59",2},
{"18:24:47",2},
{"18:25:07",2},
{"18:25:15",2},
{"0:00:00",0}
}
例題の解答と解説
便宜上、電子レンジ3台をABCと区別して扱います。
(1)
11:59:00 ABで加熱開始
12:00:00 AB加熱終了、保温棚に入れる
12:00:03 ABCで加熱開始
12:00:10 保温棚から2個、顧客に提供
12:01:03 ABCから顧客に直接提供
(2)
前日から作業を始める必要があります。
【前日】
23:58:00 ABCで加熱開始
23:59:00 ABCから取り出し 保温棚に入れる(計3個)
23:59:00 ABCで加熱開始
【当日】
0:00:00 ABCから取り出し 保温棚に入れる(計6個)
0:00:00 ABCで加熱開始
0:01:00 ABCから取り出し 保温棚に入れる(計9個)
0:01:00 ABで加熱開始
0:01:20 Cで加熱開始
0:02:00 ABから取り出し 保温棚に入れる(計11個)
0:02:00 ABで加熱開始
0:02:20 Cから直接顧客に提供
0:02:20 保温棚から11個顧客に提供
0:03:00 ABから取り出し 保温棚に入れる(計2個)
0:03:00 ABCで加熱開始
0:04:00 ABCから直接顧客に提供
0:04:00 保温棚から2個顧客に提供
(3)
電子レンジに入れるタイミングの一例を示します。
A:18:19:07
B:18:19:54
A:18:20:07
C:18:20:07
A:18:21:07
B:18:21:07
C:18:21:07
A:18:22:07
B:18:22:07
C:18:22:07
A:18:23:07
B:18:23:07
C:18:23:07
A:18:24:07
B:18:24:07
C:18:24:07
入力データ コピー コピーされました
{"16:57:53",10},
{"11:21:52",10},
{"14:26:49",10},
{"16:11:30",10},
{"20:37:44",10},
{"13:25:52",10},
{"21:05:24",9},
{"12:27:18",9},
{"15:41:37",9},
{"18:08:20",9},
{"19:59:24",9},
{"15:05:15",9},
{"17:44:12",9},
{"20:08:19",8},
{"17:02:00",8},
{"11:56:58",7},
{"13:02:20",7},
{"19:49:52",7},
{"19:27:31",6},
{"19:44:06",6},
{"13:48:28",6},
{"14:05:33",6},
{"19:42:54",6},
{"19:42:34",6},
{"17:47:07",6},
{"15:32:52",6},
{"18:52:51",5},
{"16:01:50",5},
{"14:05:27",5},
{"14:55:17",4},
{"22:07:14",4},
{"21:48:33",4},
{"17:11:42",4},
{"17:47:25",4},
{"18:51:09",4},
{"16:12:46",3},
{"18:20:01",3},
{"19:50:11",3},
{"15:03:58",3},
{"20:47:42",3},
{"21:13:41",3},
{"21:06:22",3},
{"14:45:19",2},
{"14:57:35",2},
{"16:15:43",2},
{"16:24:17",2},
{"21:06:28",1},
{"20:02:33",1},
{"18:03:45",1},
{"19:48:25",1},
{"0:00:00",0}
},
{
{"18:47:06",19},
{"21:03:27",18},
{"18:11:43",17},
{"20:38:38",17},
{"19:53:08",16},
{"18:36:24",16},
{"18:20:13",16},
{"17:52:23",15},
{"20:23:11",15},
{"18:53:16",14},
{"21:36:49",13},
{"21:11:18",13},
{"20:03:40",11},
{"19:58:34",11},
{"19:10:05",11},
{"21:31:27",9},
{"20:23:38",7},
{"21:12:43",7},
{"21:13:15",6},
{"18:37:16",6},
{"19:44:09",5},
{"18:45:16",5},
{"18:48:23",4},
{"17:00:03",4},
{"21:09:06",3},
{"21:42:46",1},
{"21:12:53",1},
{"17:07:20",1},
{"19:11:06",1},
{"21:08:48",1},
{"12:13:15",20},
{"11:18:38",19},
{"12:15:32",18},
{"12:24:54",17},
{"12:14:23",17},
{"11:39:07",16},
{"11:28:41",15},
{"11:59:55",15},
{"12:27:14",14},
{"11:59:35",13},
{"11:44:39",13},
{"12:27:00",11},
{"12:13:10",11},
{"11:29:24",11},
{"12:16:37",11},
{"11:57:00",10},
{"12:12:26",10},
{"12:17:18",10},
{"11:13:54",9},
{"12:01:54",9},
{"11:39:49",9},
{"11:30:26",9},
{"12:11:01",6},
{"11:34:46",6},
{"11:45:33",5},
{"11:17:41",5},
{"11:36:16",4},
{"11:35:55",2},
{"12:13:42",2},
{"11:43:22",1},
{"7:41:38",10},
{"7:22:04",9},
{"6:37:46",9},
{"6:34:15",9},
{"5:40:15",9},
{"7:58:30",9},
{"7:29:16",8},
{"5:43:50",8},
{"7:05:21",8},
{"8:01:40",8},
{"7:14:17",8},
{"6:16:15",7},
{"6:26:10",7},
{"5:53:24",7},
{"5:54:26",7},
{"7:41:30",7},
{"5:54:35",6},
{"6:45:10",5},
{"8:08:09",5},
{"5:49:26",5},
{"6:28:40",5},
{"6:01:38",5},
{"6:41:28",4},
{"7:53:36",3},
{"6:34:02",2},
{"5:39:48",2},
{"7:36:04",1},
{"5:58:46",1},
{"7:19:23",1},
{"7:43:51",1},
{"0:00:00",0}
},
{
{"0:24:22",99},
{"4:27:30",98},
{"17:01:42",97},
{"7:30:05",96},
{"19:14:25",95},
{"4:50:11",94},
{"1:34:28",94},
{"4:25:59",93},
{"5:20:57",92},
{"12:02:56",92},
{"5:27:56",89},
{"5:40:37",87},
{"8:21:55",87},
{"0:43:22",86},
{"7:29:25",86},
{"19:37:06",85},
{"8:40:09",85},
{"23:20:28",85},
{"20:34:31",84},
{"18:41:55",84},
{"7:20:13",83},
{"11:31:00",82},
{"13:43:26",82},
{"2:52:33",80},
{"2:12:09",78},
{"11:26:34",78},
{"10:23:34",77},
{"3:39:32",77},
{"22:47:08",77},
{"5:49:25",74},
{"4:31:19",73},
{"14:17:22",73},
{"5:34:58",72},
{"10:02:08",68},
{"10:14:25",68},
{"10:35:57",67},
{"23:49:53",65},
{"17:30:17",64},
{"2:14:45",64},
{"22:19:09",63},
{"21:38:33",63},
{"4:23:00",63},
{"5:03:00",63},
{"12:05:16",61},
{"16:10:33",60},
{"11:17:45",59},
{"23:31:30",58},
{"15:20:23",56},
{"11:18:42",56},
{"0:33:55",53},
{"7:33:34",52},
{"2:57:54",50},
{"23:03:12",50},
{"0:50:43",47},
{"8:57:01",46},
{"5:49:59",44},
{"23:39:33",43},
{"19:16:23",42},
{"14:07:53",41},
{"2:13:19",41},
{"22:34:04",40},
{"16:08:56",39},
{"15:17:04",39},
{"10:24:24",39},
{"0:38:03",37},
{"8:50:40",37},
{"7:17:25",31},
{"1:03:58",30},
{"10:44:13",30},
{"17:07:53",28},
{"23:27:51",26},
{"19:15:12",22},
{"3:12:49",22},
{"20:10:54",21},
{"21:31:02",20},
{"9:08:48",19},
{"8:01:41",18},
{"15:58:36",18},
{"3:08:13",16},
{"3:50:32",15},
{"0:24:35",15},
{"6:53:32",14},
{"15:47:06",12},
{"23:57:37",12},
{"2:01:14",11},
{"9:01:14",10},
{"13:06:29",10},
{"5:05:11",10},
{"6:22:05",9},
{"22:47:02",8},
{"8:37:43",7},
{"12:38:21",7},
{"17:28:37",7},
{"2:01:22",6},
{"4:48:02",5},
{"1:24:40",5},
{"13:21:26",5},
{"17:41:20",5},
{"1:14:39",5},
{"0:00:00",0}
}
解答
配点：300点
TOP