新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
Special Judge
問題 
あなたのチームは国際企業である解析的計算原理(Analytical Calculation Maxims; 略称ACM)に雇われた。毎年 ACM はさまざまな種類の世論調査を作成し、行なっている。調査そのものは非常にシンプルな形式をしており、質問の一覧とそれぞれの質問に対する回答の一覧とからなる。この調査は全地球規模で行われ、各地の調査員が調査対象の人々に質問をして回っている。調査に対するすべての回答は国際計算処理センター(International Computation and Processing Center; 略称ICPC)に集められた後、その回答データは高賃金の専門家たちのチームによって分析され、互いの相関関係などに基づいて整理される。それぞれの調査に対する回答データは多くの回答からなっており、ひとつの回答は1行で表されている。それぞれの行は調査を受けた人ひとりに対応しており、ある人のその調査で行われたすべての質問に対する回答を表している。
あなたのチームは回答データ分析の最初のステップを自動化するために雇われたのだが、その最初のステップは興味のある2つの質問のペアについて、それに対する回答の相関関係を示すような表を作るというものである。その表のもっとも単純な形として、それぞれの行が1つめの質問に対するすべてのありうる回答に対応しており、それぞれの列が2つめの質問に対するすべてのありうる回答に対応しているというものがある。表のそれぞれのセルには、回答データにおいて2つの質問に対してそのセルに対応するような回答をしている行の個数が書かれている。
しかし、あなたたちの仕事はそこまで簡単ではない。というのも単に上に述べたような単純な表を作るだけでなく、それぞれの行やそれぞれの列に書かれている数値の合計値も求める必要があり、その情報をもとの単純な表に新たな行と列をひとつずつ追加することで記載しなければならないからである。さらにやらなければならない仕事はそれだけではなく、それぞれの行とそれぞれの列に対して回答の割合の分布も調べなければならない。ある行に対する回答の割合の分布はその行のすべてのセルに書く必要があり、あるセルに追加で書かれる数はそのセルに書かれている数がその行全体の合計値に対して何パーセントであるかを表す必要がある。ある行の合計値が0である場合にも追加でセルに記入をする必要があり、その場合には割合の分布が未定義であることを示す記号を記入する。列に対する割合の分布も行のそれと同様にして考える。したがって最終的にあなたたちが作らねばならない表においてはそれぞれのセルは3つの値(もともとの値、行に対する割合、列に対する割合)が書かれている必要がある。合計値を示している追加の行や列に対しても割合を計算する必要があるということに注意してほしい。たとえば、すべての行においてその行の合計値を表している列の「行に対する割合」は常に 100% になる。ただし、その行の合計値が 0 である場合に限っては割合の分布が未定義であることを示す記号を記入する必要がある。またその行の合計値を表す列の「列に対する割合」は表全体の数値の合計値(これは表の最後の行の最後の列に書かれることになる値である)に対するその行の割合が書かれる。
すべての割合は出力時には整数に丸める必要がある。小数点以下が出てしまう場合、その数字は切り捨てても切り上げても構わない。ただし切り捨てか切り上げの選択は、すべての行に対してその行の合計値が書かれているものを除くすべてのセルに書かれている「行に対する割合」の和が 100% となるように行わなければならず、同じようにすべての列に対してその列の合計値が書かれているものを除くすべてのセルに書かれている「列に対する割合」の和が 100% となるように行わなければならない。ただしある行やある列の割合の分布が未定義である場合には和が 100% になっている必要はない。このような条件を満たすような切り捨て切り上げの選択方法はたくさんあるが、条件さえ満たしていればどのように切り捨て切り上げを行なってもよい。
入力
入力は3つのセクションに分かれている。3つのセクションはそれぞれ「調査の内容」「調査の結果」「作るべき表の内容」である。
入力の最初の行には調査の名前が書かれている。この名前は高々 100 文字である。続く行からは調査に含まれるすべての質問の内容が書かれている。それぞれの質問の最初の行には 3 文字の英大文字と数字のみからなる文字列が書かれており、これはその質問のコードを表す。コードの後にひとつの半角空白が置かれており、それに続いて質問の名前が書かれている。この名前は高々 80 文字である。質問のコードと名前を表す行に続く行からは、その質問に対してありうるすべての回答が書かれている。これらの行は1行につきひとつの回答の種類を表している。回答の種類を表す行はひとつの半角空白から始まり、その後に回答のコードを表す 1 文字が書かれている。回答コードは英大文字、数字、あるいは '.', '*', '@' のいずれかである。その回答コードの後にひとつの半角空白が置かれており、それに続いて回答の内容が書かれている。この内容は高々 40 文字である。質問のリストの終了は '#' 一文字からなる行によって示されている。ある質問についてその質問に対するすべての回答コードは重複せず、入力データにおいてすべての質問コードは重複しない。入力には 2 個以上 10 個以下の質問が書かれており、それぞれの質問に対して 2 個以上 100 個以下の回答が書かれている。
入力の次の行からは調査の結果が書かれている。それぞれの行には調査の質問に対する回答がそれぞれ1文字で書かれている。回答する質問の順番は入力に現れる順であり、それぞれの回答は入力で示された 1 文字の回答コードによって表されている。すべての回答は区切りなしでひとつなぎの文字列として与えられる。このセクションの終了は '#' 一文字からなる行によって示されている。入力には 1 個以上 10000 個以下の回答が合計で書かれている(回答の個数は入力の行数と各行に書かれている文字数の積である)。
入力の次の行からは作るべき表の内容が書かれている。それぞれの行に作るべき表の内容が 1 つ書かれている。その行にはまず第1の質問の質問コードが書かれており、それに続いてひとつの半角空白が置かれている。その後に第1のコードとは異なる第2の質問の質問コードが書かれている。さらにその後にひとつの半角空白が置かれており、続いて作るべき表の名前が書かれている。この名前は高々 100 文字である。このセクションの終了は '#' 一文字からなる行によって示されている。入力には高々 100 個の作るべき表の内容が書かれている。
入力データにおいて、末尾に空白がついているような行は存在しない。すべての「名前」は空白で始まったり空白で終わったりはしないが、空白を含むことはありうる。
出力
それぞれの作るべき表の内容に対し、その内容が入力データに現れる順に表を出力せよ。表の最初の行には調査の名前が書かれていなければならず、その後にひとつの半角空白、ひとつの '-' (ダッシュ)の文字、さらにひとつの半角空白、そして表の名前が続いている必要がある。次の行からは表に載る第1の質問の内容を出力する必要がある。その後に表に載る第2の質問の内容を出力する必要がある。質問の内容はいずれも入力データにおけるそれと全く同じ書式で出力しなければならない。その後に空行をひとつ出力し、それに続いて表の中身を出力する必要がある。
表の中身は 1+3*(N1+1) 行からなり、それぞれの行はちょうど 6*(N2+2) 文字からなる。ここで N1 は第1の質問に対してありうる回答の個数である、 N2 は第2の質問に対してありうる回答の個数である。表の最初の行は列の内容を表すヘッダであり、表は合計で N1+1 個の行からなる。表のそれぞれの行は出力においては 3 行ぶんの出力となる。表の最初の N1 行は、それぞれ第1の質問に対する回答に対応しており、この回答の並ぶ順番は入力データに現れる順である。そして表の最後の 1 行はそれぞれの列の合計値を表すものである。また、表は N2+2 個の列からなり、それぞれの列はちょうど 6 文字ぶんの幅がある。最初の列は行の内容を表すヘッダであり、続く N2 行はそれぞれ第2の質問に対する回答に対応しており、この回答の並ぶ順番は入力データに現れる順である。そして表の最後の 1 列はそれぞれの行の合計値を表すものである。表にかかれるすべての情報は、行や列のヘッダも含めすべて右揃えであり、余った左側の部分は各列がちょうど6文字になるように半角空白で埋めなければならない。
列の内容を表す1行のヘッダにおいて、最初の列は空である。その行の続く N2 列はそれぞれ第2の質問のコードのあとにひとつの ':' (コロン)の文字、続いて対応する 1 文字の回答コードが書かれている必要がある。ヘッダの最後の列には "TOTAL" (引用符は除く)という文字列が書かれていなければならない。行の内容を表す N1 個の、それぞれ 3 行のヘッダにおいて、その最初の行にはそれぞれ第1の質問のコードのあとにひとつの ':' (コロン)の文字、続いて対応する 1 文字の回答コードが書かれている必要がある。ヘッダの最後の 3 行のうちの最初の行には "TOTAL" (引用符は除く)という文字列が書かれていなければならない。それぞれの 3 行のヘッダにおける余った 2 行は空白で埋めなければならない。
ヘッダではないほかのすべての表のセルには計算した値が書かれていなければならない。それぞれのセルの最初の行には、そのセルに対応した回答の個数が書かれている必要がある。2行目には適切に整数に丸められた「行に対する割合」が、末尾に文字 '%' (パーセント)を補って書かれているか、あるいはその行の割合が未定義な場合には '-' (ダッシュ)の文字だけが書かれていなければならない。3行目には「列に対する割合」を2行目と同じ書式で出力する必要がある。また、出力におけるそれぞれの表は空行ひとつで区切らねばならない。
入力例
New Year Phone Survey for ACM ICPC Q01 Hello! H Hello! Y Yes! * Uhm... . (silence) @ (other) Q02 How are you? H Hello! Y Yes! F Fine! Q Who are you? @ (other) BYE Happy New Year! Y You too. * (censored) @ (other) . (hang up) # .@. HH@ .@. YFY HQ* H@. YYY .H@ HFY HH@ # Q01 Q02 Health vs greeting style Q02 BYE Politeness matrix #
出力例
New Year Phone Survey for ACM ICPC - Health vs greeting style Q01 Hello! H Hello! Y Yes! * Uhm... . (silence) @ (other) Q02 How are you? H Hello! Y Yes! F Fine! Q Who are you? @ (other)
Q02:H Q02:Y Q02:F Q02:Q Q02:@ TOTAL
Q01:H 2 0 1 1 1 5
40% 0% 20% 20% 20% 100%
66% 0% 50% 100% 33% 50%
Q01:Y 0 1 1 0 0 2
0% 50% 50% 0% 0% 100%
0% 100% 50% 0% 0% 20%
Q01:* 0 0 0 0 0 0
- - - - - -
0% 0% 0% 0% 0% 0%
Q01:. 1 0 0 0 2 3
33% 0% 0% 0% 67% 100%
34% 0% 0% 0% 67% 30%
Q01:@ 0 0 0 0 0 0
- - - - - -
0% 0% 0% 0% 0% 0%
TOTAL 3 1 2 1 3 10
30% 10% 20% 10% 30% 100%
100% 100% 100% 100% 100% 100%
New Year Phone Survey for ACM ICPC - Politeness matrix Q02 How are you? H Hello! Y Yes! F Fine! Q Who are you? @ (other) BYE Happy New Year! Y You too. * (censored) @ (other) . (hang up)
BYE:Y BYE:* BYE:@ BYE:. TOTAL
Q02:H 0 0 3 0 3
0% 0% 100% 0% 100%
0% 0% 100% 0% 30%
Q02:Y 1 0 0 0 1
100% 0% 0% 0% 100%
33% 0% 0% 0% 10%
Q02:F 2 0 0 0 2
100% 0% 0% 0% 100%
67% 0% 0% 0% 20%
Q02:Q 0 1 0 0 1
0% 100% 0% 0% 100%
0% 100% 0% 0% 10%
Q02:@ 0 0 0 3 3
0% 0% 0% 100% 100%
0% 0% 0% 100% 30%
TOTAL 3 1 3 3 10
30% 10% 30% 30% 100%
100% 100% 100% 100% 100%
出典
Northeastern Europe 2001
