問題一覧 > 通常問題

No.1545 [Cherry 2nd Tune N] Anthem

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 52
作問者 : KazunKazun / テスター : Kanten4205Kanten4205
0 ProblemId : 6142 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-11 22:37:26

お知らせ

ジャッジの結果が QLE だった場合, 問題のミスまたはジャッジのミスが考えられます. ご報告をお願いします.

問題文

あなたは今, 曲を作ろうとしている. この曲の使われるフレーズの候補は N 個であり, それぞれ フレーズ 1,, フレーズ N とする. フレーズ i を歌うのには Xi 秒を要する. ここで, 作ろうとしている曲に関して, 以下の条件を満たしていなければならない.

  • 曲の最初はフレーズ S, 最後はフレーズ T でなくてはならない.
  • 曲に使われるフレーズの個数は最初の S と最後の T も含めて K 個以上でなくてはならない. ただし, 同じフレーズを複数回用いている場合はその回数分カウントする.
  • 曲に使われているフレーズの個数を R とし, k (1kR) 番目のフレーズを Pk とする. このとき, 全ての 1k<R に対して, (Pk,Pk+1)=(Aj,Bj) となる 1jM が存在しなければならない.
そして, 1jM に対して, フレーズ Aj の歌い終わりから, フレーズ Bj の歌い始めには Yj 秒要する.

上記の条件を全て満たすようにフレーズを組み立て, 曲を作ることは可能か? また, 可能ならば条件を満たすような曲について, 所要時間の総和の最小値を求め, それを達成する曲を1つ作れ. ここで, 所要時間とは, 各フレーズを歌うのに要する時間と, あるフレーズの歌い終わりから歌い始めに要する時間それぞれの総和である.

制約

  • 1N105
  • 1S,TN
  • 1K3×104
  • 1Xi109
  • 1Mmin(N2,2×105)
  • 1Aj,BjN
  • jk ならば, (Aj,Bj)(Ak,Bk)
  • 1Yj109
  • 以下の条件のうち, 少なくとも1つを満たしている. (2021/06/11 22:37 訂正 (一方→1つ))
    • [A] 1N105,1K10
    • [B] 1N,K130
    • [C] 1N10,1K3×104

入力

入力は以下の形式で標準入力から与えられる.
N S T K
X1  XN
M
A1 B1 Y1

AM BM YM

出力

条件を満たすように曲を作ることが可能である場合, 1行目に Possible と出力し, 所要時間が最小であるような曲を2行目以降から以下のようにして出力せよ: 最短時間が V で, それを達成するような曲が R 個のフレーズからなり, i 番目のフレーズが Pi であるとき, 以下の形式で出力せよ.

V
R
P1  PR
このとき, 以下を満たしていなければならない.
  • RK
  • 1PiN
  • P1=S,PR=T
  • 1i<R に対して, (Pi,Pi+1)=(Aj,Bj) なる 1jM が存在する.

もし, 不可能ならば,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

フレーズ 1,3,3 という順番で構成される曲はフレーズ数 3 からなる曲であり, 所要時間は以下のように 5+3+6+1+6=21 秒である.

  • フレーズ 1 を歌うのに 5 秒かかる.
  • フレーズ 1 の歌い終わりから, フレーズ 3 の歌い始めには 3 秒かかる.
  • フレーズ 3 を歌うのに 6 秒かかる.
  • フレーズ 3 の歌い終わりから, フレーズ 3 の歌い始めには 1 秒かかる.
  • フレーズ 3 を歌うのに 6 秒かかる.
なお, フレーズ 1,1,3 という順番で構成される曲も条件を満たし, 所要時間も 21 である. よって, 以下のような出力も正解になる.
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

1,2,3,4 とフレーズ数が 4 からなる曲は作れるが, 5 以上にすることは不可能である.

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。