L - Next TTPC 3
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
東京工業大学プログラミングコンテストは 1 年に 1 度行われる競技プログラミングのコンテストです。英大文字列 S_1, S_2, S_3, S_4 があり、来年以降、つまり正整数 x に対して x 年後に行われる東京工業大学プログラミングコンテストの略称 T_x は次のようにして決められます。
- T_x は 4 文字の英大文字からなる文字列である
- T_x の i 文字目 (1 \le i \le 4) は S_i の ((x - 1) \bmod |S_i|) + 1 文字目と等しい( |S_i| は文字列 S_i の長さを表す)
正整数 N が与えられます。N 回目に略称が TTPC
となるのは何年後でしょうか?
制約
- 1 \le N \le 10^6
- 1 \le |S_i| \le 10^3\ (1 \le i \le 4)
- N は整数
- S_i は英大文字のみからなる文字列
部分点
- 追加の制約 |S_i| \leq 50\ (1 \le i \le 4) を満たすデータセットに正解した場合は 15 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 S_3 S_4
出力
以下の 2 つの条件を満たす正整数 x を出力せよ。そのような x が存在しない場合、代わりに -1
を出力せよ。
- T_x = {}
TTPC
- T_1, T_2, \dots, T_x の中に文字列
TTPC
は N 回出現する
入力例 1
3 TTPC TLE P AC
出力例 1
34
1 回目に略称が TTPC
となるのは 10 年後、 2 回目に略称が TTPC
となるのは 22 年後、 3 回目に略称が TTPC
となるのは 34 年後なので、答えは 34 です。
入力例 2
670055 TF OITFKONTO GFPPNPWTZP CCZFB
出力例 2
-1
略称が TTPC
となることはありません。
入力例 3
910359 TOKYO TECH PROGRAMMING CONTEST
出力例 3
1401951321