JOI 2006 問題5

あなたはある機械の製造工場で品質管理の責任者をしている. この機械には, 部品として電源とモーターとケーブルが必要である. 製造工場には電源が a 個, モーターが b 個, ケーブルが c 個あり, それぞれ 1 から a まで, a+1 から a+b まで, a+b+1 から a+b+c までの番号が付いている. 困ったことに, 部品の中に故障しているものがあるかもしれない. 工場ではどの部品が故障していてどの部品が正常であるかを知りたい.

そこで, 工場では次の方法で部品を検査した. 電源とモーターとケーブルを1つずつ持ってきてつなぎ, 動作させてみる. このとき, 3つの部品がすべて正常であるときは正しく動作して「合格」とわかる. 3つの中に故障している部品が1つでも入っているときは正しく動作しないので「不合格」とわかる. (工場で作っている機械はとても精密なので, 故障した部品がまざっているのに偶然正しく動作してしまうなどということは起きないのだ.)

あなたには検査結果のリストが渡される. 検査結果のリストの各行には, 検査に使った電源とモーターとケーブルの番号と, 検査が合格だったか不合格だったかが書かれている.

検査結果のリストが与えられたとき, すべての部品を, 検査結果から確実に故障しているとわかる部品と, 確実に正常とわかる部品と, 検査結果からは故障しているとも正常であるとも決まらない部品に分類するプログラムを作成せよ.

入力ファイルの形式は以下の通りである.

1 行目には 3 個の整数が空白区切りで書かれており, 順に電源の個数 a, モーターの個数 b, ケーブルの個数 c を表す.
2 行目には 1 個の整数が書かれており, 検査結果のリストに含まれる検査の回数 N が書かれている.
続く N 行は検査結果のリストを表す. 各行には, 4 個の整数 i, j, k, r が1つの空白を区切りとして書かれており, 電源 i とモーター j とケーブル k をつないで検査した結果が, 「合格」 (r=1 のとき) か「不合格」 (r=0 のとき) だったことを表す.

a, b, c, N は 1 ≦ a, b, c ≦ 100, 1 ≦ N ≦ 1000 を満たす.

提出する出力ファイルは以下の通りである. 出力ファイルは a+b+c 行からなる.

i 行目 (1 ≦ i ≦ a+b+c):

  • 検査結果から部品 i が故障しているとわかる場合は 0 を出力する.
  • 検査結果から部品 i が正常とわかる場合は 1 を出力する.
  • 検査結果から部品 i が故障しているか正常であるかが決まらない場合は 2 を出力する.

拍子抜けするほど簡単である。

0,1,2のどれかが入る配列を用意する。2で初期化しておくと良い。

rが1であればi,j,kのすべてが1である。まずは、それをすべての場合で確認する。

0の場合はどれか2つが1であればもう1つは0になると言える。

#include <iostream>
using namespace std;
int main() {
 int a, b, c, n, i[1000], j[1000], k[1000], r[1000], e;
 int v[1000] = { 0 };
 while (1) {
  cin >> a >> b >> c;
  if (a == 0 && b == 0 && c == 0) return 0;
  cin >> n;
  for (e = 1; e <= a + b + c; e++) {
   v[e] = 2;
  }
  for (e = 0; e < n; e++) {
   cin >> i[e] >> j[e] >> k[e] >> r[e];
   if (r[e] == 1) {
    v[i[e]] = 1;
    v[j[e]] = 1;
    v[k[e]] = 1;
   }
  }
  for (e = 0; e < n; e++) {
   if (r[e] == 0) {
    if (v[i[e]] == 1 && v[j[e]] == 1) {
     v[k[e]] = 0;
    }
    else if (v[i[e]] == 1 && v[k[e]] == 1) {
     v[j[e]] = 0;
    }
    else if (v[j[e]] == 1 && v[k[e]] == 1) {
     v[i[e]] = 0;
    }
   }
  }
  for (e = 1; e <= a + b + c; e++) {
   cout << v[e] << endl;
  }
 }
 return 0;
}

JOI 2006 問題4

1 から 2n の数が書かれた 2n 枚のカードがあり, 上から 1, 2, 3, ... , 2n の順に積み重なっている.

このカードを, 次の方法を何回か用いて並べ替える.

整数 k でカット
上から k 枚のカードの山 A と 残りのカードの山 B に分けた後, 山 A の上に山 B をのせる.
リフルシャッフル
上から n 枚の山 A と残りの山 B に分け, 上から A の1枚目, B の1枚目, A の2枚目, B の2枚目, …, A の n枚目, B の n枚目, となるようにして, 1 つの山にする.

入力ファイルの指示に従い, カードを並び替えたあとのカードの番号を, 上から順番に出力するプログラムを作成せよ.

  • 1 行目には n (1 ≦ n ≦ 100)が書かれている. すなわちカードの枚数は 2n 枚である.
  • 2 行目には操作の回数 m (1 ≦ m ≦ 1000)が書かれている.
  • 3 行目から m + 2 行目までの m 行には, 0 から 2n-1 までのいずれか 1 つの整数 k が書かれており, カードを並べ替える方法を順に指定している.
    • k = 0 の場合は, リフルシャッフルを行う.
    • 1 ≦ k ≦ 2n-1 の場合は, k でカットを行う.

2n 行からなる出力ファイルを提出せよ. 1 行目には並べ替え終了後の一番上のカードの番号, 2 行目には並べ替え終了後の上から 2 番目のカードの番号というように, i 行目には上から i 番目のカードの番号を出力せよ.

交換後の配列を作り、それを現在の並び方に格納するということをm回繰り返せば良いだろう。

#include <iostream>
#include <vector>
using namespace std;
int main() {
 int a[1000], n,m;//aは現在のカードの状況を格納
 cin >> n;
 for (int i = 1; i <= 2 * n; i++) {
  a[i] = i;//a[1]=1,a[2]=2...
 }
 cin >> m;
 for (int i = 0; i < m; i++) {
  vector<int>v(2 * n + 5);//交換後の状態を格納
  int k, j, now = 1;
  cin >> k;
  if (k == 0) {
   for (j = 1; j <= n; j++) {
    v[now] = a[j];
    now++;
    v[now] = a[j + n];
    now++;
   }
  }
  else {
   for (j = k + 1; j <= 2 * n; j++) {
    v[now] = a[j];
    now++;
   }
   for (j = 1; j <= k; j++) {
    v[now] = a[j];
    now++;
   }
  }
  for (j = 1; j <= 2 * n; j++) {
   a[j] = v[j];//交換後を現在に戻す
  }
 }
 for (int i = 1; i <= 2 * n; i++) {
  cout << a[i] << endl;
 }
 return 0;
}

JOI 2006 問題3

ガイウス・ユリウス・カエサル(Gaius Julius Caesar), 英語読みでジュリアス・シーザー(Julius Caesar)は, 古代ローマの軍人であり政治家である. カエサルは, 秘密の手紙を書くときに, 'A' を 'D' に, 'B' を 'E' に, 'C' を 'F' に, というように3つずらして表記したという記録が残っている.

大文字のアルファベット26文字だけからなる文字列を, カエサルがしたように3文字ずつずらす変換を施し得られた文字列がある. このような文字列を元の文字列に戻すプログラムを作成せよ.

各文字の変換前と変換後の対応は次のようになる.

      変換前    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
      変換後    D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

例えば, この方法で文字列 JOI を変換すると MRL が得られ, この方法で変換された文字列 FURDWLD の元の文字列は CROATIA である.

 

変換後から変換前にすれば良い。文字列を操作するのでstringをincludeする。

この場合、mapという特別な配列を使用すれば一瞬で解ける。

D→Aなので、

v['D']='A'というように考えていけば良い。

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
string s;
cin >> s;//文字を読み込む
map<char, char>m;
m['D'] = 'A';
m['E'] = 'B';
m['F'] = 'C';
m['G'] = 'D';
m['H'] = 'E';
m['I'] = 'F';
m['J'] = 'G';
m['K'] = 'H';
m['L'] = 'I';
m['M'] = 'J';
m['N'] = 'K';
m['O'] = 'L';
m['P'] = 'M';
m['Q'] = 'N';
m['R'] = 'O';
m['S'] = 'P';
m['T'] = 'Q';
m['U'] = 'R';
m['V'] = 'S';
m['W'] = 'T';
m['X'] = 'U';
m['Y'] = 'V';
m['Z'] = 'W';
m['A'] = 'X';
m['B'] = 'Y';
m['C'] = 'Z';
for (int i = 0; i < s.size(); i++) {
s[i] = m[s[i]];//ex)s[i]がDの場合m[D]はAである
}
cout << s << endl;
return 0;
}

JOI 2006 問題2

JOI大学のM教授はプログラミングの授業を担当している. クラスには30人の受講生がいて各受講生には1番から30番までの出席番号がふられている. この授業の課題を28人の学生が提出した. 提出した28人の出席番号から提出していない2人の出席番号を求めるプログラムを作成せよ.

 

配列を30人分用意して、読み込んだ数字の配列の箇所を1にする。

よって0になっている配列の数字を見れば、答えがわかる。

vectorをincludeすると連想配列を生成できる

 

#include <iostream>
#include <vector>
using namespace std;
int main() {
 int a[1000] = { 0 };//読み取ったか判断する配列 0=読み取っていない
 for (int i = 0; i < 28; i++) {
 int num;
 cin >> num;
 a[num] = 1;//読み取った数字の箇所を1にする
 } 
 vector<int>v(5);//答えを格納する配列
 int j = 0;
 for (int i = 1; i <= 30; i++) {
  if (a[i] == 0) {
  v[j] = i;
  j++;
  }//もし0だったら答えである
 }
 cout << v[0] << endl;
 cout << v[1] << endl;
 return 0;
}

 

 

JOI 2006 問題1

JOI高校の2人の生徒 A さんと B さんは, 情報,数学,理科,英語の4教科の試験を受けた. A さんと B さんのこれら4教科の得点が与えられると, Aさんの合計点 S と Bさんの合計点 T のうち大きな方を出力するプログラムを作成せよ. ただし, 同点の場合は S (= T) を出力せよ.

 

足して(+=)SとTの大きい方(max)を出力する

algorithmをincludeすると早くかけそう

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a = 0, b = 0;//合計
for (int i = 0; i < 4; i++) {
int num = 0;
cin >> num;
a += num;
}//4回読み取った数字を足せば良い(A君)
for (int i = 0; i < 4; i++) {
int num = 0;
cin >> num;
b += num;
}//(B君)
printf("%d", max(a, b));
return 0;
}