2012年5月16日水曜日

GCJ2012 Round 1C Problem C. 問題紹介

Google Code Jam 2012 Round 1C
Problem C. Box Factory 問題紹介

工場の組み立てラインが2つあります。一方は箱を、もう一方は箱に入れるおもちゃを作っています。(ベルトコンベアーをイメージすればよいかなと)

箱もおもちゃもいくつかの種類を作っていて、箱に同じ種類のおもちゃを入れて出荷します。違う種類の箱とおもちゃの組み合せの場合は、箱を捨てて次の箱にするか、おもちゃを捨てて次のおもちゃにします。(問題文では You can always throw out と言っているので同じ種類の箱やおもちゃを捨ててもかまいません)
箱もおもちゃも、ラインで作られる順に使うことしかできません。
最大いくつの箱&おもちゃペアを出荷できるでしょう、、という問題です。

例(Sample 2つめの場合):
箱:①①①①①②②②②②②①①①①①
おもちゃ:①①①①①②②②①①①①①②②②
⇒ ①①①①① を作ったあと おもちゃ を捨てて  を作ります。その後 箱 も捨てて  を作り、おもちゃ を捨てて残りの  を作ることで20個出荷することができます。

例(Sample 3つめの場合):
箱:①①①①①②②
おもちゃ:①①①①①②②②②②②①①①①①②②②②②②①①①①①
⇒ ①①①①① を作ったあと、こちらは 箱 を捨てます。②② 、  を作って残りの 箱②②②②②②①①①①① を捨てて 21個出荷することができます。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行には2つの整数 NM が書かれています。
続く行には 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 ≤ NM ≤ 100
  • 1 ≤ aibi ≤ 1016 (一度に流れてくる箱・おもちゃは最大1016個(超たくさん))
  • 1 ≤ AiBi ≤ 100 (箱もおもちゃも最大100種類(順番とは限らない))

解き方はいずれ記事にします。
解いたコードはこちらにあります。

0 件のコメント:

コメントを投稿