Educational Codeforces Round 84 (Rated for Div. 2)

参加しました。

f:id:coonevo:20200325235339p:plain — 順位表

Sum of Odd Integers
Princesses and Princes
- 問題
  - 問題
  - 入力
  - 出力
- 解説
- 提出
Game with Chips
D - Infini Path
- 問題概要
E - Count The Blocks

Sum of Odd Integers

問題概要

$N$ が $K$ 個の相異なる奇数の和で表すことができますか？

解説

偶奇について考えると、 $N$ と $K$ の偶奇が一致していないと構成できません。また、 $K$ 個の相異なる奇数で作られる最小の和は、 $K^{2}$ なので、 $N$ がそれ未満だと構成できません。結論から言うと、以上二つの条件を潜り抜ければ構成できます。 $1, 3, ..., 2K - 1$ の和が $K^{2}$ であることから、 $K^{2} \le N$ かつ $N \% 2 == K \% 2$ であれば、 $(N-K^{2})\%2 = 0$ なので、 $K$ 個の奇数のうち最大のものに足りない分 $(N-K^{2})$ を足せば、和を $N$ にすることができます。

提出

Princesses and Princes

問題

※ DeepL翻訳に頼ってみました。数式の細かい表現の足りないところは補いました。

ベルランドの王ポリカープLXXXIVには、 $n$ 人の娘たちがいる。近隣の王国に自分の権力を確立するために、彼は、これらの王国の王子たちと娘たちを結婚させたいと考えている。幸運なことに、他の王国にも $n$ 王国がある。

そこで、ポリカルプLXXXIVは、自分の娘を $1$ から $n$ まで、王国を $1$ から $n$ まで列挙した。それぞれの娘のために、娘が結婚したいと思っていた王国の王子たちのリストを編纂した。

ポリカープLXXXIVは非常に忙しいので、彼は貪欲に娘たちのためのカップルを次々と見つける。

最初の娘のために、彼は彼女のリストから最も低い数の王国を取り、彼らの王子に娘を結婚させます。次の娘のために、彼は彼女のリストの中で最も低い番号の王国を取り、その王子はまだ取られていない。もしリストに自由な王子がいなければ、娘は誰とも結婚せず、ポリカルプLXXXIVは次の娘に進む。この処理は、 $n$ 番目の娘の後に終わります。

例えば、4人の娘と王国があるとすると、娘たちが持っているリストはそれぞれ[2,3]、[1,2]、[3,4]、[3]である。

この場合、娘 $1$ は王国 $2$ の王子と結婚し、娘 $2$ は王国 $1$ の王子と結婚し、娘 $3$ は王国 $3$ の王子と結婚します。

実際、結婚の手続きを始める前に、ポリカルプLXXXIVは娘の一人に、ある王子も結婚する価値があると説得する時間を持っている。事実上、彼は娘のリストの中の一つの王国を正確に追加することができることを意味します。この王国は娘のリストに存在してはならないことに注意してください。

ポリカルプLXXXIVは夫婦の数を増やしたいと考えています。

残念ながら、彼には時間がないのは、どの項目を追加するかを決定することです。もし結婚しているカップルの総数を増やす方法がない場合，結婚がすでに最適であることを出力してください．そうでなければ，Polycarp LXXXIVがそれを追加すると夫婦の総数が増加するような項目を見つけてください．

もし，結婚したカップルの総数が増加するように項目を追加する方法が複数あるならば，そのうちのどれかを出力してください．

あなたと私たちの便宜のために、 $t$ 個の独立したテストケースに答えるように求められています。

入力

最初の行には、 $t (1\le t\le 10^{5})$ という単一の整数、つまりテストケースの数が含まれています。

その後、 $t$ 個ののテストケースが続く。

各テストケースの最初の行には、単一の整数 $n (1\le n\le 10^{5})$ - 娘の数と王国の数が含まれています。

次の $n$ 行のそれぞれには、各娘のリストの記述が含まれています。最初の整数 $k (1\le k\le n)$ は、 $i$ 番目の娘のリストの項目数です。その後に続く $k$ 個の別々の整数 $gi_1,gi_2,...,gi_k (1\le gi_j\le n)$ - リストの中の王国のインデックスを順に並べる $(gi_1\lt gi_2\lt ... \lt gi_k )$ 。

全てのテストケースに渡る娘の総数が $10^{5}$ を超えないことが保証されています。

また、すべてのテストケースにおいて、リストに含まれる王国の総数が $10^{5}$ を超えないことが保証されています。

出力

各テストケースについて、それに対する答えを印刷しなさい。

もしPolycarp LXXXIVが彼の娘のリストにいくつかの王国を追加して結婚したカップルの総数を増やすことができるならば，最初の行に "IMPROVE "と印刷してください．二行目には二つの整数-娘のインデックスとポリカープLXXXIVがその娘のリストに追加すべき王国のインデックス-が含まれるべきである。

結婚しているカップルの総数が増加するように項目を追加する方法が複数ある場合，そのうちのどれかを表示してください．

そうでなければ、唯一の行は "OPTIMAL "という単語を含んでいなければなりません。