実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
yahoo 型文字列とは、yah のあとに同じ英小文字が 2 つ連続した文字列を指します。例えば、yahoo, yahhh などは yahoo 型文字列ですが、
yahoy や snuke はそうではありません。
5 文字の英小文字からなる文字列 S が与えられるので、yahoo 型文字列かどうか判定してください。
制約
- |S|=5
- S は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が yahoo 型文字列なら YES を、そうでないなら NO を出力せよ。
入力例 1
yahoo
出力例 1
YES
yahoo は yahoo 型文字列です。
入力例 2
snuke
出力例 2
NO
snuke は yahoo 型文字列ではありません。
入力例 3
yyyyy
出力例 3
NO
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 200 点
問題文
矢風くんはオークションに参加しています。矢風くんの欲しい品物には、現在 X 円の値が付いています。
矢風くんはこの品物に、以下の条件を満たすような Y に対して、Y 円の値段をつけることができます。
- オークションでつける値段として適切である。すなわち、X+1\leq Y である。
- つける金額は細かすぎない。すなわち、Y の 10 進表記の下 K 桁は全て 0 である。
矢風くんがつけることのできる最小の金額を求めてください。
制約
- 1 \leq X \leq 10^9
- 0 \leq K \leq 9
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
X K
出力
矢風くんがつけることのできる最小の金額を出力せよ。
入力例 1
2018 2
出力例 1
2100
2018 円より大きく、下 2 桁が 0 であるような最小の金額は、2100 円です。
入力例 2
888 0
出力例 2
889
X 円より大きい値段をつけなければならないことに注意してください。
入力例 3
100 7
出力例 3
10000000
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 500 点
問題文
高橋君と青木君が取引をします。 はじめ、高橋君の所持金は 0 円です。
高橋君は 1 から N の番号がついた N 個の財宝を持っています。高橋君は青木君に財宝 i を売却すると x_i 円得ることができます。
青木君は 1 から N の番号がついた N 個の商品を販売しています。商品 i は価値 v_i を持ち、価格 c_i 円で販売されています。
取引は以下の手順で行われます。
- 高橋君は財宝を売却するか、商品を購入するかを決める。前者ならば手順 2. へ、後者ならば手順 3. へ進む。
- 高橋君は持っている財宝のうち、最も番号が小さいものを青木君に売却しお金を得る。その後、青木君は商品を 1 つ選び販売を停止する。手順 1. へ戻る。
- 高橋君は販売中の 0 個以上の商品を購入し、取引を終了する。このとき、高橋君は所持金が 0 円未満になるように購入することはできない。
高橋君が購入した商品の価値の総和を得点とします。
高橋君は得点を最大化するように、青木君は得点を最小化するように行動するとき、得点はいくつになりますか？
制約
- 1 \leq N \leq 18
- 1 \leq x_i,c_i,v_i\leq10^{15}
- 与えられる入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
x_{1} ... x_{N}
c_{1} ... c_{N}
v_{1} ... v_{N}
出力
答えを出力せよ。
入力例 1
3 200 1000 1 100 100 300 1000 2000 1000000
出力例 1
1000
- 2 人の動きの一例について説明します。
- 高橋君は財宝の売却を選び、財宝 1 を売却し、200 円を得ます。
- 青木君は商品 2 の販売を停止します。
- 高橋君は財宝の売却を選び、財宝 2 を売却し、1000 円を得ます。
- 青木君は商品 3 の販売を停止します。
- 高橋君は商品の購入を選び、商品 1 を購入し、取引を終了します。
入力例 2
2 1 100 1 100 100 1
出力例 2
0
- 高橋君がどのように行動しても、商品を購入することはできません。
入力例 3
5 100 1 1 1 1 1 1 1 1 1 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000
出力例 3
4000000000000000
入力例 4
18 89 36 77 25 84 49 67 21 78 94 55 50 22 40 44 17 93 11 55 81 89 38 19 65 68 75 66 52 75 93 94 31 73 86 25 79 38 81 44 33 70 20 89 34 13 45 27 88 91 85 36 98 52 93
出力例 4
337
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 800 点
問題文
すぬけ君は黒板に 2 つの異なる整数 X,Y と K 行 K 列のマス目を書きました。 次に、すぬけ君はマス目の i 行 j 列目に整数 A_{i,j} を書きました。
すぬけ君はこれを使って、長さ K の数列 a が以下の条件を満たすとき a を 良い数列 と呼ぶことにしました。
- 条件：1 \leq i,j \leq K を満たすどの (i,j) についても、以下が成立する
- a_i xor a_j xor X あるいは a_i xor a_j xor Y が A_{i,j} と一致する。
- ただし、xor はビットごとの排他的論理和を表す。
すぬけ君は N 個の整数を持っています。i 番目の整数は x_i です。 すぬけ君はこれら N 個の数から K 個を選んで並べて、長さ K の数列を作ることにしました。 すぬけ君が作ることのできる数列のうち、良い数列であるようなものはいくつありますか？ modulo 10^{9} + 7 で求めてください。
ある数列の作り方は複数あるかもしれませんが、最終的に得られる数列として同じであれば区別しないことに注意してください。 詳しくはサンプル 1 も参照してください。
制約
- 1 \leq N \leq 2048
- 1 \leq K \leq {\rm min}(1024,N)
- 0 \leq X,Y,x_i, A_{i,j} < 2048
- X \neq Y
- 与えられる入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K X Y
x_{1} ... x_{N}
A_{1,1} ... A_{1,K}
:
A_{K,1} ... A_{K,K}
出力
答えを出力せよ。
入力例 1
6 3 1 0 0 8 1 2 15 8 1 2 8 2 0 10 8 10 1
出力例 1
2
- 答えとしてありうる数列は (0,2,8) と (1,2,8) の 2 通りです。
- (0,2,8) となるように数を選んで並べる方法は 2 通りありますが、それらは区別しないことに注意してください。
入力例 2
2 2 0 4 0 1 8 16 110 12
出力例 2
0
- どのような数列であっても条件を満たすことはありません。
入力例 3
35 4 11 1 23 2 17 16 22 22 6 0 0 15 16 5 12 21 0 9 17 0 2 26 22 19 6 16 13 7 26 8 22 29 26 13 8 32 14 1 0 15 31 0 11 14 20 5 4 1 17 21 20 27 1
出力例 3
26
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1000 点
問題文
N 頂点の無向単純グラフであって、各頂点の次数が順に D_1,...,D_N であるようなものが存在するかどうか判定してください。 存在しない場合、ある i に対して D_i を 1 だけ増やすことで、そのようなグラフが存在するようにできるかどうかも判定してください。
制約
- 1 \leq N \leq 10^5
- 0 \leq D_i \leq N-1(1\leq i\leq N)
- D_i \leq D_{i+1}(1\leq i\leq N-1)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N D_1 : D_N
出力
各頂点の次数が順に D_1,...,D_N であるようなものが存在する場合、YES を出力せよ。
そうでない場合、ある i に対して D_i を 1 だけ増やすことで、そのようなグラフが存在するようにできるなら、NO を出力せよ。
そうでない場合、ABSOLUTELY NO を出力せよ。
入力例 1
5 1 2 2 3 4
出力例 1
YES
辺集合が {(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)} であるようなグラフが条件を満たします。
入力例 2
7 1 1 1 1 6 6 6
出力例 2
ABSOLUTELY NO
入力例 3
8 1 1 1 2 3 4 4 5
出力例 3
NO