Time Limit: 2 sec / Memory Limit: 256 MB
問題文
青木君は整数 a で割り切れる数が好きです。 高橋君は整数 b で割り切れる数が好きです。
n 以上の整数で、青木君と高橋君の両方が好きな最小の数を答えてください。
入力
入力は以下の形式で標準入力から与えられる。
a b n
- 1 行目には、整数 a (1≦a≦100) が与えられる。
- 2 行目には、整数 b (1≦b≦100) が与えられる。
- 3 行目には、整数 n (1≦n≦20,000) が与えられる。
出力
出力は以下の形式で標準出力に行うこと。
1 行目に、n 以上の整数で青木君と高橋君の両方が好きな数の最小値を出力せよ。末尾の改行を忘れないこと。
入力例1
2 3 8
出力例1
12
12 は 8 以上の整数のうち、 2 と 3 で割り切れるものの最小値です。
入力例2
2 2 2
出力例2
2
入力例3
12 8 25
出力例3
48
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の会社には、秘密の金庫があります。この金庫にはパスワードをかけているのですが、高橋君はそのパスワードを忘れてしまいました。 しかし、幸運なことに、手元にはパスワードのヒントが以下のように書かれていました。
- パスワードは、この紙に書かれている文字列 s の長さ k の部分文字列(※)のどれかである。
高橋君は、ありうるパスワードを全部試せば金庫を開けられる！と喜びました。 しかし、文字列 s はとても長い可能性があるし、しかも同じ部分文字列が複数個文字列 s 中に存在する可能性もあります。明らかに、重複したパスワードを繰り返し試す必要はありません。 そこで、手動で全てのパスワードを試す前に、試す必要がある異なるパスワードの数がいくつあるかを数えることにしました。
あなたの仕事は、文字列 s の内容が与えられるので、試す必要がある異なるパスワードの数がいくつあるかを高橋君に教えてあげることです。
(※)文字列 s の「部分文字列」とは、文字列 s に含まれるある区間を取り出した文字列のことです。
例えば、abc の部分文字列として a,b,c,ab,bc,abc などが挙げられます。
ac や ba などは部分文字列ではないことに注意してください。
入力
入力は以下の形式で標準入力から与えられる。
s k
- 1 行目には、ヒントの紙に書かれている文字列 s (1≦|s|≦300) が与えられる。s は英小文字(
a-z)のみから成る。|s| は文字列 s の長さを表す。 - 2 行目には、パスワードとしてありうる整数 k (1≦k≦300) が与えられる。 k は |s| よりも大きいことがある。
出力
出力は以下の形式で標準出力に行うこと。
1 行目に、パスワードとして考えられる文字列の数を出力せよ。末尾の改行を忘れないこと。
入力例1
abcabc 2
出力例1
3
パスワードとしてありうる部分文字列の集合は、{ab,bc,ca} です。
入力例2
aaaaa 1
出力例2
1
パスワードとしてありえる部分文字列は、a のみです。
入力例3
hello 10
出力例3
0
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
長さ N の非負整数列 S={s_1,s_2,...,s_N} と整数 K があります。 あなたの仕事は、以下の条件を満たす S の 連続する 部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないといけません。
- その部分列に含まれる全ての要素の値の積は、K 以下である。
もし条件を満たす部分列が一つも存在しないときは、0 を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
N K s_1 s_2 : s_N
- 1 行目には、数列の長さを表す整数 N (1≦N≦10^5) と問題文中の整数 K (0≦K≦10^9) が空白区切りで与えられる。
- 2 行目からの N 行には、数列の各要素の値が与えられる。そのうち i(1≦i≦N) 行目には、s_i (0≦s_i≦10^9) が書かれている。
部分点
この問題には部分点が設定されている。満点は 100 点である。
- N≦1000 を満たすデータセット 1 に正解した場合は、20 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合、上記の点数に加え 80 点が与えられる。
出力
出力は以下の形式で標準出力に行うこと。
1 行目に、含まれる全ての要素の値の積が K 以下となる連続する部分列のうち最長のものの長さを出力せよ。もし条件を満たす部分列が一つも存在しないときは、0 を出力せよ。末尾の改行を忘れないこと。
入力例1
7 6 4 3 1 1 2 10 2
出力例1
4
部分列 S[2..5]=s_2,s_3,s_4,s_5 を選ぶと、積は 3×1×1×2=6 となり、K 以下になります。
入力例2
6 10 10 10 10 10 0 10
出力例2
6
入力例3
6 9 10 10 10 10 10 10
出力例3
0
入力例4
4 0 1 2 3 4
出力例4
0
Time Limit: 2 sec / Memory Limit: 512 MB
問題文
0/1ナップサック問題を解いてください。0/1ナップサック問題とは以下のような問題のことです。
- N 個の荷物があり、i (1≦i≦N) 番目の荷物には価値 v_i と重さ w_i が割り当てられている。
- 許容重量 W のナップサックが1つある。
- 重さの和が W 以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。
入力
入力は以下の形式で標準入力から与えられる。
N W v_1 w_1 v_2 w_2 : v_N w_N
- 1 行目には、荷物の数を表す整数 N (1≦N≦200) とナップサックの許容重量を表す整数 W(1≦W≦10^9) が空白区切りで与えられる。
- 2 行目からの N 行には、各荷物の情報が与えられる。そのうち i(1≦i≦N) 行目には、i 番目の荷物の価値を表す整数 v_i (1≦v_i≦10^9) と重さを表す整数 w_i (1≦w_i≦10^9) が空白区切りで与えられる。
- 「N≦30」、「全てのi(1≦i≦N) について 1≦w_i≦1000」、「全てのi(1≦i≦N) について 1≦v_i≦1000」という 3 つの条件のうち少なくとも1つの条件が成り立つ。
部分点
この問題には部分点が設定されている。満点は 100 点である。
- N≦30 を満たすデータセット 1 に正解した場合は、34 点が与えられる。
- N≦200 かつ全ての i(1≦i≦N) について 1≦w_i≦1000 を満たすデータセット 2 に正解した場合は、上記の点数とは別に 33 点が与えられる。
- N≦200 かつ全ての i(1≦i≦N) について 1≦v_i≦1000 を満たすデータセット 3 に正解した場合は、上記の点数とは別に 33 点が与えられる。
出力
出力は以下の形式で標準出力に行うこと。
1 行目に、達成できる最大の合計価値を出力せよ。末尾の改行を忘れないこと。
入力例1
3 10 15 9 10 6 6 4
出力例1
16
2 番目と 3 番目のアイテムを選ぶと、合計の重みが 10 で価値が 16 となり、最大価値を達成できます。 この入出力例は、データセット 1,2,3 の制約を満たしているため、全てのデータセットの採点に用いられます。
入力例2
30 499887702 128990795 137274936 575374246 989051853 471048785 85168425 640066776 856699603 819841327 611065509 704171581 22345022 536108301 678298936 119980848 616908153 117241527 28801762 325850062 478675378 623319578 706900574 998395208 738510039 475707585 135746508 863910036 599020879 340559411 738084616 122579234 545330137 696368935 86797589 665665204 592749599 958833732 401229830 371084424 523386474 463433600 5310725 210508742 907821957 685281136 565237085 619500108 730556272 88215377 310581512 558193168 136966252 475268130 132739489 303022740 12425915 122379996 137199296 304092766 23505143
出力例2
3673016420
この入出力例は、データセット 1 の制約のみ満たしているため、データセット 2,3 の採点には用いられません。
入力例3
10 2921 981421680 325 515936168 845 17309336 371 788067075 112 104855562 96 494541604 960 32007355 161 772339969 581 55112800 248 98577050 22
出力例3
3657162058
この入出力例は、データセット 3 の制約を満たしていないため、データセット 3 の採点には用いられません。
入力例4
10 936447862 854 810169801 691 957981784 294 687140254 333 932608409 832 42367415 642 727293784 139 870916042 101 685539955 853 243593312 369 977358410
出力例4
1686
この入出力例は、データセット 2 の制約を満たしていないため、データセット 2 の採点には用いられません。