Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんが運営しているゲームでは、名前を回文にすることが流行っています。名前を表す文字列が与えられるので、回文かどうかを判定してください。なお、回文とは前から読んでも後ろから読んでも同じとなる文字列のことです。
入力
入力は以下の形式で標準入力から与えられる。
Name
- 1 行目には、名前を表す文字列 Name が与えられる。
- Name の長さは 100 文字以下で、含まれる文字は全て小文字アルファベットであることが保証されている。
出力
名前が回文なら YES を、名前が回文でないなら NO を出力せよ。出力の末尾には改行をつけること。
入力例1
awawa
出力例1
YES
入力例2
chokudai
出力例2
NO
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、1 つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。10 マス × 10 マスのこの島国の地図が与えられるので、1 マスを埋め立てた時に 1 つの島にできるか判定してください。ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。
入力
入力は以下の形式で標準入力から与えられる。
A_{1,1}A_{1,2}...A_{1,10}
A_{2,1}A_{2,2}...A_{2,10}
:
A_{10,1}A_{10,2}...A_{10,10}
- 島国の地図が 10 行にわたって与えられる。
- 各行は 10 文字からなり、
oは陸地を、xは海を表す。 - 少なくとも 1 マスは陸地があることが保証される。
- 少なくとも 1 マスは海があることが保証される。
出力
海を 1 マスだけ陸地にすることで全体を 1 つの島にできるなら YES 、できないなら NO を出力せよ。出力の末尾には改行をつけること。ただし、元から 1 つの島だった場合も YES を出力せよ。
入力例1
xxxxxxxxxx xoooooooxx xxoooooxxx xxxoooxxxx xxxxoxxxxx xxxxxxxxxx xxxxoxxxxx xxxoooxxxx xxoooooxxx xxxxxxxxxx
出力例1
YES
赤く囲ったマスを埋め立てることで 1 つの島にできます。
入力例2
xxxxxxxxxx xoooooooxx xxoooooxxx xxxoooxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxoooxxxx xxoooooxxx xxxxxxxxxx
出力例2
NO
入力例3
xxxxoxxxxx xxxxoxxxxx xxxxoxxxxx xxxxoxxxxx ooooxooooo xxxxoxxxxx xxxxoxxxxx xxxxoxxxxx xxxxoxxxxx xxxxoxxxxx
出力例3
YES
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
全て高さの違う N 個の積み木が 1 列に並べられています。隣り合う 2 個の積み木を並べ替える操作を何回か行って、一番高い積み木から順に左右へ低くなっていくようにする時、必要な最小の交換回数を求めてください。すなわち、並べ替えた後の i 番目の積み木の高さを Ai とし、一番高い積み木の位置を T としたとき、
- A1 < A2 < ... < AT > ... > AN-1 > AN
入力
入力は以下の形式で標準入力から与えられる。
N B1 B2 ... BN
- 1 行目には、積み木の数 N (1≦N≦10^5) がスペース区切りで与えられる。
- 2 行目には、積み木の高さ Bi (1≦Bi≦N) が最初に並べられている順に与えられる。
- ただし、積み木の高さは全て異なる。すなわち、Bi≠Bj (i≠j) が成り立つ。
出力
並べ替えるのに必要な最小の交換回数を出力せよ。出力の末尾には改行をつけること。
部分点
この問題には 2 つのデータセットがあり、データセット毎に部分点が設定されている。
- N≦100 を満たすデータセット 1 に正解した場合は 30 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 70 点が与えられる。
入力例1
4 2 4 1 3
出力例1
1
以下のように 1 回で並べ替えられます。
入力例2
5 2 4 1 3 5
出力例2
3
3 回で並べ替える一例を示します。
入力例3
6 1 2 4 3 5 6
出力例3
1
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんはゲームにはまっています。このゲームではいくつかのアイテムの組み合わせを満たすと経験値が得られます。アイテムの値段と、アイテムの組み合わせによって得られる経験値の一覧が与えられるので、買うアイテムを上手く選んで「得られた経験値 ÷ 使ったお金」を最大にしてください。ただし、アイテムは 1 種類以上買うこととし、1 種類につき 1 個だけ持っておけば経験値が得られます。
入力
入力は以下の形式で標準入力から与えられる。
N M S1 S2 ... SN T1 T2 ... TM K1 A1,1 A1,2 ... A1,K1 K2 A2,1 A2,2 ... A2,K2 : KN AN,1 AN,2 ... AN,KN
- 1 行目には、経験値をもらえる組み合わせの数 N (1≦N≦100) とアイテムの種類数 M (1≦M≦100) がスペース区切りで与えられる。
- 2 行目には、もらえる経験値の大きさ Si (1≦Si≦100) が与えられる。
- 3 行目には、アイテムの値段 Ti (1≦Ti≦100) が与えられる。
- 4 行目からの N 行では、経験値をもらえる組み合わせに含まれるアイテムの種類数 Ki (1≦Ki≦10) と、アイテムの番号を表す Ki 個の整数 Ai,j (1≦Ai,j≦M, Ai,j<Ai,j+1) がスペース区切りで 1 行ずつ与えられる。
出力
「得られた経験値 ÷ 使ったお金」の最大値を出力せよ。絶対誤差、または、相対誤差が 10−4 以下であれば許容される。出力の末尾には改行をつけること。
部分点
この問題には 2 つのデータセットがあり、データセット毎に部分点が設定されている。
- N≦10 を満たすデータセット 1 に正解した場合は 50 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 50 点が与えられる。
入力例1
3 4 4 3 2 4 2 1 10 2 1 2 2 1 3 3 2 3 4
出力例1
1
アイテム 1 、アイテム 2 、アイテム 3 を買うと、使ったお金は 7で、経験値が 4+3=7 得られます。
入力例2
5 5 7 1 3 6 6 6 3 2 6 5 1 2 2 2 3 4 1 2 4 5 2 2 4 2 2 3
出力例2
2.8