Educational Codeforces Round 104 問題文和訳

A. Arena / Арена
- 入力
- 出力
- 入出力例
- 注記
B. Cat Cycle / Круговорот котов в квартире
- 入力
- 出力
- 入出力例
- 注記
C. Minimum Ties / Как можно меньше ничьих
- 入力
- 出力
- 入出力例
- 注記
D. Pythagorean Triples / Пифагоровы тройки
- 入力
- 出力
- 入出力例
- 注記
E. Cheap Dinner / Дешевый обед
- 入力
- 出力
- 入出力例
- 注記
F. Ones / Единицы
G. String Counting / Подсчет строк

A. Arena / Арена

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

$n$ 人のヒーローがアリーナで互いに戦います。初期状態では $i$ 番目のヒーローのレベルは $a_i$ です。

毎分、相異なる2人のヒーローの戦いが起こります。これらのヒーローは自由に選ぶことができます(直前の1分間に戦っていたのと同じ2人のヒーローを選ぶこともできます)。

同じレベルのヒーローが戦ったとき、どちらもその戦いに勝利することはありません。異なるレベルのヒーローが戦ったとき、レベルの高い方のヒーローが勝ち、そのヒーローのレベルが $1$ 上がります。

トーナメントの勝者は、 $100^{500}$ 戦以上に初めて勝利したのヒーローです(この数の戦いに勝利するヒーローがいなければトーナメントは永遠に続き、勝者は存在しないことになる、ということが起こりえます)。勝者候補とは、トーナメントの勝者となるような一連の試合が存在するヒーローのことです。

$n$ 人のヒーローの内、勝者候補の人数を計算して下さい。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 500)$ が与えられる、 $t$ はテストケースの個数である。

各テストケースは2行からなる。1行目には1つの整数 $n$ $(2 \leq n \leq 100)$ が与えられる、 $n$ はヒーローの人数である。2行目には $n$ 個の整数 $a_1,\,a_2,\, \dots,\,a_n$ $(1 \leq a_i \leq 100)$ が与えられます、 $a_i$ は $i$ 番目のヒーローの初期レベルである。

出力

各テストケースについて単一の整数を出力せよ、その整数は $n$ 人のヒーローの内の勝者候補の人数である。

入出力例

1
0
3

注記

この入出力例の1番目のテストケースでは、勝者候補は1番目のヒーローのみです。

この入出力例の2番目のテストケースでは、ヒーロー同士の戦いでは誰も勝つことはなく、トーナメントは永遠に続き、勝者は存在しません。

B. Cat Cycle / Круговорот котов в квартире

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

2匹の猫A, Bと暮らしているとします。その2匹の猫が普段寝ている $n$ 箇所のお昼寝スポットがあります。

猫は寝るのが好きで、また、これらの場所が好きでなので、1時間ごとに次のように周期的にお昼寝場所を変えています。

猫Aは $n,\,n - 1,\,n - 2,\,\dots,\,3,\,2,\,1,\,n,\,n-1,\,\dots$ という順でお昼寝場所を変える。言い換えれば、最初の1時間はスポット $n$ にいて、それから循環的降順に場所を変えていく。
猫Bは $1,\,2,\,3,\,\dots,\,n - 1,\,n,\,1,\,2,\,\dots$ という順でお昼寝場所を変える。言い換えれば、最初の1時間はスポット $1$ にいて、それから循環的昇順に場所を変えていく。

猫Bの方がずっと若く、AとBは一緒に寝ないという厳しいヒエラルキーが存在します。言い換えれば、両方の猫がスポット $x$ に行きたいとき、Aがこの場所をとり、Bは次の順番の場所に移動します( $x < n$ のときは $x + 1$ へ、 $x = n$ のときは $1$ へ)。猫Bは自身の順番に従い、自分が飛ばしたスポット $x$ へAが去ったあとに戻ることはなく、スポット $x + 2$ などへ移動します。

$k$ 時間目に猫Bはどこいるか計算してください。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、 $t$ はテストケースの個数である。

各テストケースについての唯一の行には2つの整数 $n,\,k$ $(2 \leq n \leq 10^9,$ $1 \leq k \leq 10^9)$ が与えられる、それらはスポットの数 $n$ と時間 $k$ である。

出力

各テストケースについて単一の整数を出力せよ、その整数は $k$ 時間目に猫Bがいるスポットの番号である。

入出力例

注記

1番目と2番目のテストケースでは $n = 2$ であるので、次のようになります。

1時間目: Aはスポット $2$ に、Bは $1$ にいる。
2時間目: Aはスポット $1$ に、Bは $2$ に動く。

$n=3$ の場合、次のようになります。

1時間目: Aはスポット $3$ に、Bは $1$ にいる。
2時間目: Aはスポット $2$ に動く。Bは $1$ から $2$ に動きたいが、占有されているため $3$ に動く。
3時間目: Aはスポット $1$ に動く。Bは $3$ から $1$ に動きたいが、占有されているため $2$ に動く。

6番目のテストケースでは次のようになります。

Aの各時間の位置: $[5,\,4,\,3,\,2,\,1]$
Bの各時間の位置: $[1,\,2,\,4,\,5,\,2]$

C. Minimum Ties / Как можно меньше ничьих

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

サッカー*1の大選手権大会が間もなく行われます! $n$ チームが出場し、各ペアで正確に1試合ずつ対戦します。

試合の結果は次の2つの可能性があります。

試合が引き分けとなり、両チームが $1$ 点を獲得する
一方のチームが試合に勝ち、勝ったチームが $3$ 点を獲得し、負けたチームは $0$ 点を獲得する

チームの得点はプレーした全ての試合で得た点数の合計です。

選手権大会の終わりに全てのチームが同じ点数であるような仮定的状況に興味があります。簡単な例として、全ての試合が引き分けで終わるようなものがありますが、引き分けの数を最小化したいです。

全てのチームが同じ得点であり、引き分けの数が最小であるような状況(各試合の結果を選択)を記述することが課題です。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、 $t$ はテストケースの個数である。

次にテストケースが続く。各テストケースは1行で1つの整数 $n$ $(2 \leq n \leq 100)$ で与えられる、 $n$ はチームの数である。

出力

各テストケースについて試合結果を表す $\displaystyle\frac{n(n-1)}{2}$ 個の整数を次のような順序で出力せよ: 1番目の整数はチーム $1$ 対チーム $2$ の試合、2番目はチーム $1$ 対チーム $3$ で、それから $1$ 対 $3$ 、 $1$ 対 $4$ 、...、 $2$ 対 $3$ 、 $2$ 対 $4$ 、...、 $2$ 対 $n$ と続き、チーム $n - 1$ 対チーム $n$ の試合まで対応させる。

チーム $x$ 対チーム $y$ の試合に対応する整数は $x$ が勝った場合 $1$ 、 $y$ が勝った場合 $-1$ 、引き分けの場合 $0$ とする。

全てのチームの得点が同じで、引き分けの回数が最小でなければならない。最適解が複数存在する場合、そのうちの1つを出力せよ。全てのチームの得点が同じにする方法は常に存在することは示される。

入出力例

2
2
3

0 
1 -1 1

注記

この入出力例の1番目のテストケースでは、試合が引き分けで終了し、両チームが $1$ 点を獲得します。

この入出力例の2番目のテストケースでは、チーム $1$ がチーム $2$ に勝利(チーム $1$ が $3$ 点獲得)し、チーム $1$ がチーム $3$ に敗北(チーム $3$ が $3$ 点獲得)し、チーム $2$ がチーム $3$ に勝利(チーム $2$ が $3$ 点獲得)します。

D. Pythagorean Triples / Пифагоровы тройки

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

Πυθαγόρας*2数とは第1隣辺*3、第2隣辺、斜辺の長さが $a,\,b,\,c$ となるような直角三角形を作れる整数の組 $(a,\,b,\,c)$ のことです。

Вася*4は直角三角形の性質を研究していて、ある3つ組整数がΠυθαγόρας数であるかを判別する公式を使っています。不幸なことに、彼は正確な公式を忘れてしまいました。彼はその公式には2乗が用いられているということだけを覚えていました。そこで、彼は $c = a^2 - b$ という式を考え出しました。

明らかに、これは3整数がΠυθαγόρας数であるかを判別する正しい式ではありません。しかし、驚くことに、 $5 = 3^2 - 4$ であるため、3整数 $(3,\,4,\,5)$ には実際にうまくいきました。つまり、Васяの公式によりΠυθαγόρας数と判別されます。

Васяが正しい公式をみつけ(、そして彼の公式が間違っているとわかっ)たとき、「 $1 \leq a \leq b \leq c \leq n$ である3整数 $(a,\,b,\,c)$ のうち、自分の式と、本当の定義に当てはまるΠυθαγόρας数は何組あるのだろうか?」と彼は疑問に思いました。彼はそのような3つ組を数えるように頼みました。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、 $t$ はテストケースの個数である。

各テストケースは1行で1つの整数 $n$ $(1 \leq n \leq 10^9)$ で与えられる。

出力

各テストケースについて1つの整数を出力せよ、その整数とは、本当の定義とВасяが思いついた式の両者でΠυθαγόρας数となる $1 \leq a \leq b \leq c \leq n$ である3整数 $(a,\,b,\,c)$ の数である。

入出力例

0
1
1

注記

$c = a^2 - b$ を満たす $1 \leq a \leq b \leq c \leq 9$ であるΠυθαγόρας数は $(3,\,4,\,5)$ だけです。そのため、 $n=3$ のときは答えは $0$ 、 $n=6$ (、 $n=9$ )のときは答えは $1$ となります。

E. Cheap Dinner / Дешевый обед

テストごとの時間制限: 4秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力

Иван*5は美味しいディナーを食べたいと思っています。美味しいディナーはファーストコース*6、セカンドコース、ドリンク、デザートから構成されてなければなりません。

Иванの頼めるファーストコースは $n_1$ 種類( $i$ 番目の値段は $a_i$ コイン)、セカンドコースは $n_2$ 種類( $i$ 番目の値段は $b_i$ コイン)、ドリンクは $n_3$ 種類( $i$ 番目の値段は $c_i$ コイン)、デザートは $n_4$ 種類( $i$ 番目の値段は $d_i$ コイン)あります。

相性の悪い料理もあります。ファーストコースとセカンドコースで相性の悪いものが $m_1$ 組、セカンドコースとドリンクで $m_2$ 組、ドリンクとデザートで $m_3$ 組存在します。

Иванは相性のいいファーストコース、セカンドコース、ドリンク、デザートをちょうど1つずつ頼みつつ、ディナーの総費用が可能な限り最小になるようにしたいです。彼がディナーの最安価オプションを見つける手伝いをしてください。

入力

1行目には4つの整数 $n_1,\,n_2,\,n_3,\,n_4$ $(1 \leq n_i \leq 150000)$ が与えられる、 $n_1,\,n_2,\,n_3,\,n_4$ はそれぞれファーストコース、セカンドコース、ドリンク、デザートの種類数である。

次に4行が続く。その1行目には $n_1$ 個の整数 $a_1,\,a_2,\,\dots,\,a_{n_1}$ $(1 \leq a_i \leq 10^8)$ が与えられる、 $a_i$ は $i$ 番目のファーストコースの値段である。次の3行にはセカンドコース、ドリンク、デザートの値段が同じ形式で与えられる $(1 \leq b_i,\,c_i,\,d_i \leq 10^8)$ 。

次の行には1つの整数 $m_1$ $(0 \leq m_1 \leq 200000)$ が与えられる、 $m_1$ はファーストコースとセカンドコースで相性の悪い組の数である。つづく $m_1$ 行のそれぞれには2つの整数 $x_i,\,y_i$ $(1 \leq x_i \leq n_1,$ $1 \leq y_i \leq n_2)$ が与えられる、これはファーストコース $x_i$ とセカンドコース $y_i$ で相性が悪いこと表す。これらの組はすべて異なるものである。

セカンドコースとドリンクで相性の悪い組も同じ形式で与えられる。ドリンクとデザートで相性の悪い組についても同様である $(0 \leq m_1,\,m_2 \leq 200000)$ 。

出力

相性の良いファーストコース、セカンドコース、ドリンク、デザートの組を選ぶことができない場合、 $-1$ を出力せよ。そうでなければ、1つの整数を出力せよ、その整数はディナーの最小総費用である。

入出力例

-1

注記

1つ目の入出力例の最適オプションはファーストコース $2$ 、セカンドコース $1$ 、ドリンク $2$ 、デザート $1$ です。

2つ目の入出力例では、ファーストコースとセカンドコースの唯一の組の相性が悪いため、ディナーを摂ることができません。

F. Ones / Единицы

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

正の(ゼロより大きい)整数 $n$ が与えられます。

$n$ をイチ(数字の'1')のみで構成される整数(負数も可)の和で表さなければなりません。例えば、 $24 = 11 + 11 + 1 + 1,$ $102 = 111 - 11 + 1 + 1$ です。

全ての可能な表現のなかで、イチを使う数が最小のものを見つけなければならない。

入力

1つの整数 $n$ $(1 \leq n \leq 10^{50})$ で与えられる単一行である。

出力

1つの整数 $x$ を出力せよ: $n$ を合計 $x$ 個のイチを用いた整数(負数も可)の和として表す表現が存在するような最小の $x$ である。

入出力例

G. String Counting / Подсчет строк

テストごとの時間制限: 10秒
テストごとのメモリ制限: 1024 MB
入力: 標準入力
出力: 標準出力

$c_1$ 文字の'a'、 $c_2$ 文字の'b'、...、 $c_{26}$ 文字の'z'があります。これらの文字から長さ $n$ の美しい文字列を作りたいです(明らかに $i$ 番目の文字を $c_i$ 回より多く使うことはできません)。各 $c_i$ は $\displaystyle\frac{n}{3}$ より大きいです。

そのなかに $1$ より大きい奇数長の回文連続部分文字列が存在しない場合、その文字列は美しいと呼ばれます。例えば、文字列"abacaba"は美しくありません、というのも $1$ より大きい奇数長の回文部分文字列がいくつかあるからです(例えば、"aca")。他の例としては"abcaa"は美しいです。

作ることができる文字列の数を計算し、答えをmodulo $998244353$ で出力してください。

入力

1行目は1つの整数 $n$ $(3 \leq n \leq 400)$ で与えられる。

2行目は $26$ 個の整数 $c_1,\,c_2,\,\dots,\,c_{26}$ $\displaystyle\left(\frac{n}{3} \leq c_i \leq n\right)$ で与えられる。

出力

1つの整数を出力せよ、その整数は作ることができる文字列の数をmodulo $998244353$ した数である。

入出力例

4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

3
2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 2 2 3 2 2 3 2 2

400
348 322 247 158 209 134 151 267 268 176 214 379 372 291 388 135 147 304 169 149 193 351 380 368 181 340

287489790

*1:footballはアメリカ英語ではアメフトの可能性もありますが、イギリス英語ではサッカーを意味するためどちらの意味をとるか迷いましたが、ロシア語の問題文ではАмериканский футбол(ьный)ではなくфутбол(ьный)となっていたため、サッカーの方で訳しました

*2:古希/pyː.tʰa.ɡó.raːs/、ピタゴラス、ピュタゴラス、Pythagoras(英/paɪˈθæɡ.əɹ.əs/、米/paɪˈθæ.ɡɚ.əs/)

*3:脚などとも呼ばれる

*4:露[ˈvasʲə]、Vasya、Vasja、ヴァーシャ: 男性名Василий([vɐˈsʲilʲɪj]、Vasily、Vasilij、ヴァシーリー)の指小辞語、愛称

*5:露[ɪˈvan]、Ivan、イヴァン、イワン: 聖人ヨハネに由来する名前、John(英)、Jean(仏)、Giovanni(伊)等と同語源

*6:フルコースの1品目のこと、ここでのコースは皿の意