No.1545 [Cherry 2nd Tune N] Anthem
タグ : / 解いたユーザー数 52
作問者 : Kazun / テスター : Kanten4205
お知らせ
ジャッジの結果がQLE
だった場合, 問題のミスまたはジャッジのミスが考えられます. ご報告をお願いします.
問題文
あなたは今, 曲を作ろうとしている. この曲の使われるフレーズの候補は
- 曲の最初はフレーズ
, 最後はフレーズ でなくてはならない. - 曲に使われるフレーズの個数は最初の
と最後の も含めて 個以上でなくてはならない. ただし, 同じフレーズを複数回用いている場合はその回数分カウントする. - 曲に使われているフレーズの個数を
とし, 番目のフレーズを とする. このとき, 全ての に対して, となる が存在しなければならない.
上記の条件を全て満たすようにフレーズを組み立て, 曲を作ることは可能か? また, 可能ならば条件を満たすような曲について, 所要時間の総和の最小値を求め, それを達成する曲を1つ作れ. ここで, 所要時間とは, 各フレーズを歌うのに要する時間と, あるフレーズの歌い終わりから歌い始めに要する時間それぞれの総和である.
制約
ならば,- 以下の条件のうち, 少なくとも1つを満たしている. (2021/06/11 22:37 訂正 (一方→1つ))
- [A]
- [B]
- [C]
- [A]
入力
入力は以下の形式で標準入力から与えられる.出力
条件を満たすように曲を作ることが可能である場合, 1行目に Possible
と出力し, 所要時間が最小であるような曲を2行目以降から以下のようにして出力せよ:
最短時間が
このとき, 以下を満たしていなければならない.
に対して, なる が存在する.
もし, 不可能ならば,Impossible
と出力せよ. なお, 適する曲の作り方が複数考えられる場合, どれを出力しても良い.
最後に改行を忘れないこと.
サンプル
サンプル1
入力
3 1 3 3 5 7 6 5 1 1 2 1 2 1 1 3 3 2 3 4 3 3 1
出力
Possible 21 3 1 3 3
フレーズ
- フレーズ
を歌うのに 秒かかる. - フレーズ
の歌い終わりから, フレーズ の歌い始めには 秒かかる. - フレーズ
を歌うのに 秒かかる. - フレーズ
の歌い終わりから, フレーズ の歌い始めには 秒かかる. - フレーズ
を歌うのに 秒かかる.
Possible 21 3 1 1 3
サンプル2
入力
4 1 4 5 1 2 3 400 3 1 2 10 2 3 100 3 4 1000
出力
Impossible
サンプル3
入力
6 3 2 1 3 3 3 3 3 3 6 3 2 1000000000 3 1 1 1 6 1 6 4 1 4 5 1 5 2 1
出力
Possible 23 6 3 1 6 4 5 2
フレーズ数が少ないことが曲の時間が短いことになるとは限らない.
サンプル4
入力
1 1 1 11 1 1 1 1 1
出力
Possible 21 11 1 1 1 1 1 1 1 1 1 1 1
このサンプルは [B], [C] は満たすが, [A] を満たさない.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。