Testing Round #2

Codeforces

A

問題

単位がcmで長さが与えられるのでfeetとinchに直せ。
3cm = 1inch, 1feet=12inch, inchは近い整数に丸められる。

解法

やるだけ。n=35がやばいので自分含め大量Hackされていた。

ソース

int main() {
  int n;
  cin >> n;
  int feet =  n / 36;
  int inch = ((n%36)+1)/3;
  if (inch == 12) {
    feet++;
    inch = 0;
  }
  cout << feet << " " << inch << endl;
}

B

問題

XMLっぽい入力が与えられるのでインデントして表示せよ。

解法

<*>が来たらネスト数を１増やし、が来たらネスト数を１減らす。
ネスト数に応じてスペースを表示してから<*>ないしを表示する。

ソース

int main() {
  string s;
  cin >> s;
  int nest = 0;
  int start = 0;
  REP(i, s.size()) {
    if (s[i]=='<') start = i;
    else if (s[i]=='>') {
      string hoge = s.substr(start, i-start+1);
      if (hoge[1] == '/') nest--;
      cout << string(nest*2, ' ') << hoge << endl;
      if (hoge[1] != '/') nest++;
    }
  }
}

C

問題

n人いるホビットをパーティに招待する。
・どの２日をとってきても２日とも招待されているホビットが１人はいる。
・どの３日をとってきても３かとも招待されているホビットが１人もいない。
という制約を満たしながらパーティを出来るだけ長い日数開催する時、その日数と招待の仕方を示せ。

解法

サンプルから分かる通りn=3~5のときは3日しか開けない。
n=6の時を考えると、
1 2 3
1 4 5
2 4 6
3 5 6
とすれば４日開く事が出来る。
これをどのように考えたかを説明する。
まず、１日目は
1 2 3
を招待する。
制約を満たすためには２〜４日目に1, 2, 3それぞれ１人ずつ招待しなければいけないので、
1 2 3
1 * *
2 * *
3 * *
とする必要がある。次に２日目は、2,3は招待できないので、
1 2 3
1 4 5
2 * *
3 * *
となる。上と同様に、３〜４日目に4, 5それぞれ１人ずつ招待しなければいけないので、
1 2 3
1 4 5
2 4 *
3 5 *
となる。同様に、
1 2 3
1 4 5
2 4 6
3 5 6
となり、n=6の場合の答えが得られる。
５日開くには、同様な作成方法を考えることで、
1 2 3 4
1 5 6 7
2 5 8 9
3 6 8 10
4 7 9 10
とする必要がある。
3人、6人、10人、・・・というときに１日開催できる日が増えることが分かる。
この数列（i*(i+1)/2）を先に生成しておき、何日開催できるか求めた上で、上の作成方法をすればよい。

ソース

int main() {
  vector<int> v;
  REP(i, 200) {
    v.push_back(i*(i+1)/2);
  }
  int n;
  cin >> n;
  int day = upper_bound(ALL(v), n)-v.begin();
  cout << day << endl;
  int table[day][day-1];
  int cnt = 1;
  for (int i=0; i<day; ++i) {
    for (int j=i; j<day-1; ++j) {
      table[i][j] = cnt;
      table[j+1][i] = cnt;
      cnt++;
    }
  }
  REP(i, day) {
    REP(j, day-1) {
      if (j) cout << " ";
      cout << table[i][j];
    }
    cout << endl;
  }
}