Problem C. Box Factory 問題紹介
工場の組み立てラインが2つあります。一方は箱を、もう一方は箱に入れるおもちゃを作っています。(ベルトコンベアーをイメージすればよいかなと)
箱もおもちゃもいくつかの種類を作っていて、箱に同じ種類のおもちゃを入れて出荷します。違う種類の箱とおもちゃの組み合せの場合は、箱を捨てて次の箱にするか、おもちゃを捨てて次のおもちゃにします。(問題文では You can always throw out と言っているので同じ種類の箱やおもちゃを捨ててもかまいません)
箱もおもちゃも、ラインで作られる順に使うことしかできません。
最大いくつの箱&おもちゃペアを出荷できるでしょう、、という問題です。
例(Sample 3つめの場合):
箱:①①①①①①①①①①②②②②②②①①①①①①①①①①
最大いくつの箱&おもちゃペアを出荷できるでしょう、、という問題です。
例(Sample 2つめの場合):
箱:①①①①①①①①①①②②②②②②①①①①①①①①①①
箱:①①①①①①①①①①②②②②②②①①①①①①①①①①
おもちゃ:①①①①①②②②①①①①①①①①①①②②②①①①①①
⇒ ①①①①① を作ったあと おもちゃ②②② を捨てて ①①①①① を作ります。その後 箱②②②②②② も捨てて ①①①①① を作り、おもちゃ②②② を捨てて残りの ①①①①① を作ることで20個出荷することができます。
箱:①①①①①①①①①①②②②②②②①①①①①①①①①①
おもちゃ:①①①①①②②②②②②①①①①①①①①①①②②②②②②①①①①①
⇒ ①①①①① を作ったあと、こちらは 箱①①①①① を捨てます。②②②②②② 、 ①①①①①①①①①① を作って残りの 箱②②②②②②①①①①① を捨てて 21個出荷することができます。
入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行には2つの整数 N と M が書かれています。
続く行には a1 A1 a2 A2 ... aN AN という具合に 2×N 個の整数が書かれており、これは「種類 A1 の箱 a1 個、次に種類 A2 の箱 a2 個…」が流れてくることを示しています。
問題の3行目は同様に b1 B1 b2 B2 ... bM BM としておもちゃの生産数が示されています。(「種類 B1 のおもちゃ b1 個、次に種類 B2 のおもちゃ b2 個…」)
データ制限:
解き方はいずれ記事にします。
解いたコードはこちらにあります。
入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行には2つの整数 N と M が書かれています。
続く行には a1 A1 a2 A2 ... aN AN という具合に 2×N 個の整数が書かれており、これは「種類 A1 の箱 a1 個、次に種類 A2 の箱 a2 個…」が流れてくることを示しています。
問題の3行目は同様に b1 B1 b2 B2 ... bM BM としておもちゃの生産数が示されています。(「種類 B1 のおもちゃ b1 個、次に種類 B2 のおもちゃ b2 個…」)
データ制限:
- 1 ≤ T ≤ 100 (問題数100問)
- Small input の場合:1 ≤ N ≤ 3、1 ≤ M ≤ 100
Large input の場合:1 ≤ N、M ≤ 100 - 1 ≤ ai、bi ≤ 1016 (一度に流れてくる箱・おもちゃは最大1016個(超たくさん))
- 1 ≤ Ai、Bi ≤ 100 (箱もおもちゃも最大100種類(順番とは限らない))
解き方はいずれ記事にします。
解いたコードはこちらにあります。
0 件のコメント:
コメントを投稿