Time Limit: 2 sec / Memory Limit: 256 MB
問題
巨大生物「巨人」の出現によりに住居を追われた人類は、城壁に囲まれた居住区に移り住むことで一時的な安全を得るに至った。 しかしそれから約１００年後、城壁を破壊する程の力を持つ「超大型巨人」の出現により人類は再びの危険に晒されることとなる。 困ったことにこの「超大型巨人」は神出鬼没であり、いつ何時どこに現れるかわからない。
城壁内はいくつかの地区に分かれており、仮にある一つの地区に巨人が侵入してもその地区を封鎖することで他の地域に被害が及ぶのを防ぐことができる。 住人達は万が一城壁内に巨人が侵入した場合に備えて、侵入された地区を通らずに残りの地区間を移動できるような道路網を整備したいと考えた。
あなたの仕事は任意の１地区を通らなくても残りの全地区間を移動できるような道路の最小本数と、そのような道路を整備するのにかかる最小コストを求めることである。
入力
N E_1_,_2 E_1_,_3 .. E_1_,_N_-_1 E_1_,_N E_2_,_3 E_2_,_4 .. E_2_,_N : E_N_-_2_,_N_-_1 E_N_-_2_,_N E_N_-_1_,_N
- 1行目には整数 N が与えられます。
- N は地区の数を表します。
- 2 ≦ N ≦ 15 であることは保証されています。
- 2行目から N 行目までの N-1 行では、 整数E_i_,_j がそれぞれ半角スペース区切りで与えられます。
- E_i_,_j は i 番目の地域と j 番目の地域の間に道路を整備するコストを表します。
- 1 ≦ E_i_,_j ≦ 1,000,000 であることは保証されています。
出力
入力例
4 1 5 4 2 6 3
出力例
4 10
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
友人の残したメモによると SNS に管理者としてログインする際には、与えられた数字の素因数の最大値をパスワードとして入力する必要があるらしい。
しかし数学が苦手なSさんは素因数が何であるかがよく分からない。 そこであなたの仕事はSさんのために、与えられた数字からパスワードを求めるプログラムを作成することである。
入力
出力
入力例
10 100 12345678 20560801 0
出力例
5 5 14593 5381
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
昔々あるところに白蛇のお守りをつけた巫女さんがおりました。 彼女の名前は現代に伝えられていないため、今ではMiss.Pythonと呼ばれています。 ある時、村に邪悪な霊の大軍勢が跳梁跋扈し、村々に大きな災いが降りかかりました。 そんな中、Miss.Pythonが、蛇のお守りを掲げると、突然輝きだして、一直線に光が走ったかと思うと、光は次々に邪霊を浄化し、終いには元締めを貫いて浄化してしまいました。 お守りの光は、元締めを貫いたところで消えてしまいました。 元締めが浄化されると、周辺の邪霊も消え、村々は災いから救われたそうな。
あなたは、夏休みの自由研究で、この昔話について調べています。 古文書には、おびただしい数の邪霊がどこに浮遊していたか、克明に記載されておりました！？ その中には、Miss.Pythonが居たと思われる神社や邪霊の元締めの位置まで記されていました。
そこであなたは、お守りの光が浄化したという邪霊の数について興味を持ち、調べてみることにしました。
入力
入力は以下の形式で標準入力から与えられる。
入力制約について追記いたしました。
N NX NY QX QY
WAX_1 WAY_1 WBX_1 WBY_1
:
WAX_{N-1} WAY_{N-1} WBX_{N-1} WBY_{N-1}
- 1行目には整数 N, NX, NY, QX, QY が与えられます。
- N は邪霊の数を表します。
- NX はMiss.Pythonの X 座標を表します。
- NY はMiss.Pythonの Y 座標を表します。
- QX は邪霊の元締めの X 座標を表します。
- QY は邪霊の元締めの Y 座標を表します。
- 1 ≦ N ≦ 10,000 であることは保証されています。
- -1,000 ≦ NX, NY, QX, QY ≦ 1,000 であることは保証されています。
- Miss.Pythonと邪霊の元締めの位置は異なることが保証されています。
- 2行目から N 行目までの N-1 行では、元締め以外の邪霊の両端の X 座標および Y 座標がそれぞれ半角スペース区切りで与えられます。
- 元締め以外の邪霊は雲のように漂っている感じなので線分で表します。
- WAX_i は i 番目の元締め以外の邪霊の両端 A の X 座標を表します。
- WAY_i は i 番目の元締め以外の邪霊の両端 A の Y 座標を表します。
- WBX_i は i 番目の元締め以外の邪霊の両端 B の X 座標を表します。
- WBY_i は i 番目の元締め以外の邪霊の両端 B の Y 座標を表します。
- -1,000 ≦ WAX_i, WAY_i, WBX_i, WBY_i ≦ 1,000 であることは保証されています。
- WAX_i \neq WBX_i または WAY_i \neq WBY_i であることは保証されています。
- どの元締め以外の邪霊もMiss.Pythonと重ならないことは保証されています。
- どの元締め以外の邪霊も邪霊の元締めと重ならないことは保証されています。
- 元締め以外の邪霊の両端の X 座標および Y 座標は整数で与えられます。
出力
なお、お守りの光や邪霊の大きさは考えないものとし、お守りの光と邪霊が接する場合は貫いたものとみなす。
入力例
4 1 1 4 4 1 2 2 1 2 3 3 2 3 4 4 3
出力例
4
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
E君は高校1年生。国立医大を目指して日々勉学にいそしんでいる。 そしてこの夏、彼は予備校に通って少しでも成績を上げたいと考えている。 しかしそんな彼は、勉学を妨げる重大な問題を抱えている。 それは知人の女子達がそれぞれ別に彼をデートに連れ出そうとしていることである。
Cさんとは幼馴染の間柄。肉料理が好物で、E君の手料理を食べ、毎日「大好き」「愛してる」とE君にべったりです。 Mさんとは偽装カップルの間柄。超美人な彼女は頻繁に悪い虫がよってくるので、E君を彼氏とすることで悪い虫を寄せ付けないようにしています。 Hさんとは先輩後輩の間柄。ひきこもりがちな彼女ではあるが、好きなマンガやアニメの趣味が合うE君のことに関してはとても積極的です。 Aさんとは幼きころ契りを交わした間柄。幼稚園のころの『こんいんとどけ』を大事に持っていて、ことあるごとに婚姻を強要してきます。
もし一人とデートに行くことになれば、後日デートに行かなかった女子一人一人とデートすることになりさらに彼の勉強時間は減っていく。
彼は恋愛アンチだ。学生が恋愛などというものに現を抜かすなど言語道断だと常々思っている。 過去1日27時間女子とのデートに人生を費やすという伝説の英雄Mr. TOKOSHIなる人物がいたらしいが、そんなものはもってのほかだ。
彼女達の行動を観察したところ、誰か一人と近い位置にいる場合、デートに連行されてしまう。 逆に、もっとも近い距離に二人以上いる場合はお互いを牽制しあって、連行されないことがわかった。 また、自宅と予備校の半径50m以内は淑女協定により連行されないらしい。 このことを利用して、E君はデートに連行されないルートを通り、予備校に通うことに決めた。 場合によっては予備校までのルート上に家屋が建っている可能性もあるが、 建物を飛び越えられる素敵なブーツを持ち合わせていないので、 ラーメンのお食事中にお邪魔することになったとしても、致し方ない。
明日からの予備校に備え、いざ就寝しようと思い、ふと問題に差し掛かった。 予備校に遅刻しないように家を出たいが、特殊なルートを通るため、通常のルート検索アプリでは移動時間を調べられない。 このままでは、めざましの時間を何時にセットすればよいか決められない。 あなたの仕事は、彼のために、女子に連行されずに予備校へ通うための最短ルートの移動距離を求めてあげることである。 移動距離が判明すればE君は自分の足の速さから移動時間を計算することができる。
入力
N EX EY SX SY GX_1 GY_1 : GX_N GY_N
- 1行目には整数 N が与えられます。
- N は女子の数を表します。
- 0 ≦ N ≦ 20 であることは保証されています。
- 2行目には整数 EX, EY が与えられます。
- EX はE君の X 座標を表します。
- EY はE君の Y 座標を表します。
- -1,000 ≦ EX, EY ≦ 1,000 であることは保証されています。
- 3行目には整数SX, SYが与えられます。
- SX は予備校の X 座標を表します。
- SY は予備校の Y 座標を表します。
- -1,000 ≦ SX,SY ≦ 1,000 であることは保証されています。
- 4行目から N+3 行目までの N 行では、女子の位置に関する整数 GX_i, GY_i がそれぞれ半角スペース区切りで与えられます。
- GX_i は i 番目の女子の X 座標を表します。
- GY_i は i 番目の女子の Y 座標を表します。
- -1,000 ≦ GX_i, GY_i ≦ 1,000 であることは保証されています。
- 位置の単位は全てメートルです。
- E君の自宅と女子の位置、予備校と女子の位置、女子の位置同士はそれぞれ異なることは保証されています。
出力
ルートが存在しない場合は
impossible とだけ出力せよ。移動距離が10,000を超える場合も
impossible とだけ出力せよ。出力の数値は10,000を超えない場合は絶対誤差が 10^{-6} 以下であれば許容される。
真の最短移動距離が 10,000 - 10^{-6} を超える場合でも
impossible とだけ出力することが許容される。
入力例
4 0 0 110 10 50 -10 50 10 60 0 60 20
出力例
114.142135623731
- 下図のようなルートを通るのが最善です。
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
♪「ガラガラガラ～、レアカード来い！」 俺は今、巷で人気のソーシャルカードゲームにはまっている。 このゲームは「カードローダー」という名のガチャシステムで カードを増やし、カード合成でデッキ(手札)を強化して コンピュータや他のプレーヤーと対戦するといったゲームである。 巷によくあるゲーム形式で、課金しないとなかなか楽しめないと いうところも定番通りである。 たった今カードローダーで 引いたカード「のろのろウサギ*(N)」(名前の後ろの括弧は希少価値を表す) は戦闘力最弱の屑カードである。 いつになったら 目的のレアカードが出現してくれるのだろうか。
俺は貧乏ゲーマーなので課金はしたくない。 しかし、 ゲームヒロイン「アリシア」のレアカードが欲しくてたまらない。 そこで俺は友達に協力を依頼してカードローダーについて調査を行った。 残念なことに、カードローダーで得られるカードは10枚目ごとにかつそのときに限り必ず「のろのろウサギ*(N)」であることしか分からなかった。
そうこうしている内にゲーム主催者の方から特別なイベントの告知が行われた。 イベントは数種類あるカードローダーで入手可能なカードの種類と 入手確率が公開されるというもので、 「プレーヤーの皆様の日頃のご愛顧に感謝し、レアカードを椀飯振舞することに いたしました。奮ってご参加ください。」とのことだ。 イベント詳細を詳しく見ると、今までとカードローダーの仕組みは変わらず、 入手できるカードの入れ替えと入手確率を変更し、 いつもよりレアカードが入手しやすくなっているらしい。
いてもたってもいられず、いざカードローダーと思ったとき、ふと思った。 「いくらいつもより確率が良くても、いったい何回カードローダーを動かせば アリシアちゃんのカードが入手できるのだろう」と。 俺は金がない代わりにゲームする時間はある、けれどこの手のゲームの定番で 課金しない状況では続けて何回も動かすことはできない。 何回動かせば入手できるか知ることが出来れば、実際いつ頃入手できるか 推測がたつ。 もし、来週の今頃であるなら、今週はとてもウキウキした 一週間になるに違いない。 もし、1ヶ月先であるならば、 カードを入手する前にイベントが終了しているかもしれない。 「あ～、神よ。俺にレアカードをお恵くださいorz」
あなたの仕事はカードの入手確率とカードローダーの動作回数をもとに「俺」が入手できるアリシアのレアカードの枚数の期待値を求めることである。
ここでいうレアカードとは、N(ノーマル), R(レア), S(スーパーレア), H(ハイパーレア)の 4種類の希少価値がある中で、R,S,Hの3種類いずれかの希少価値をもつカードを指す。
入力
N T card\_name_1 rarity_1 rate_1 : card\_name_N rarity_N rate_N
- 1行目には整数 N, T が与えられます。
- N は出現率について得られた情報の数を表します。
- 1 ≦ N ≦ 10,000 であることは保証されています。
- Tは試行回数を表します。
- 0 ≦ T ≦ 100,000,000 であることは保証されています。
- 2 行目から N + 1 行目までの N 行では、カード名称、希少価値および出現頻度がそれぞれ半角スペース区切りで与えられます。
- card\_name_i は i 枚目のカード名称を表します。
- card\_name_i は半角英数字の他に
[,],&,!,?,+,-,_,/によって構成されます。 - card\_name_i は 1 文字以上 20 文字以下であることが保証されています。
- アリシアのカードである場合、card\_name_i に “Alicia” の文字列を含みます。例えば「アリシア[ひとやすみ]」は「Alicia[hitoyasumi]」となります。
- rarity_i は i 枚目のカードの希少価値を表します。
- rarity_i は
N,R,S,Hのいずれかであることが保証されています。 - rate_i は出現頻度を表します。
- 1 ≦ rate_i ≦ 100,000 であることは保証されています。
- カードローダーは指定された確率を用いるとき、 rate_i / (rate_1 + … + rate_N) の確率で i 番目のカードを生成します。
出力
入力例
3 3 Alicia[Normal] N 40 Superheroine_Alicia R 9 Secret_of_Alicia H 1
出力例
0.6
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
「主のために何としてもやり遂げねば」。 彼らは主に仕える騎士（ここにいるのは3人と1匹。1匹は犬と呼ばれている）である。 彼らは主の病を治すため、強力な魔力の保有者を打ち倒し、魔力保有者から魔力を奪い蒐めている。 魔力が蒐まれば主を治癒できると信じているからである。 つい先日も2人の魔法使いから魔力を蒐めたばかりである。 魔力蒐集も順調かと思われていたが、主の病の進行が思いの外、速い。 加えて、同じ魔力保有者から複数回魔力を奪うことはできない為、蒐集対象を探す手間も考えなければならない。 このため、今までは数人でチームを組み、事にあたってきたがこれからは単独で行動するより他にない。 今後の戦闘のために、体力は温存しておくべきで、当然、移動にも体力(移動力と呼ぶ)を消費するので出来るだけ移動を減らしたい。
あなたの仕事は、騎士達や魔力保有者達の 位置や魔力量が与えられた時、 騎士一人高々一体の魔力蒐集を行って最大量の魔力を蒐めた時、 必要となる移動力の最小値を求めることである。
移動力はマンハッタン距離に比例します。 例えば、騎士の座標が(1,1)で、魔力保有者の座標が(2,3)である場合、その間の移動には 3 移動力必要となります。 また、この世界に同一の名前を持つ人物は複数人存在しないものとします。
入力
N M KNIGHT\_NAME_1 KX_1 KY_1 : KNIGHT\_NAME_N KX_N KY_N MAGE\_NAME_1 MAGIC_1 MX_1 MY_1 : MAGE\_NAME_M MAGIC_M MX_M MY_M
- 1行目には整数 N, M が与えられます。
- N は騎士の数を表します。
- M は魔力保有者の数を表します。
- 1 ≦ N, M ≦ 50 であることは保証されています。
- 2行目から N+1 行目までの N 行では、騎士の名前、X座標およびY座標がそれぞれ半角スペース区切りで与えられます。
- KNIGHT\_NAME_i は i 番目の騎士の名前を表します。
- KX_i は i 番目の騎士のX座標を表します。
- KY_i は i 番目の騎士のY座標を表します。
- KNIGHT\_NAME_i は半角英数字1文字以上20文字以下であることが保証されています。
- 0 ≦ KX_i, KY_i ≦ 10,000 であることは保証されています。
- N+2 行目から N+M+1 行目までの M 行では、魔力保有者の名前、魔力量、X座標およびY座標がそれぞれ半角スペース区切りで与えられます。
- MAGE\_NAME_i はi番目の魔力保有者の名前を表します。
- MAGIC_i はi番目の魔力保有者の魔力量を表します。
- MX_i はi番目の魔力保有者のX座標を表します。
- MY_i はi番目の魔力保有者のY座標を表します。
- MAGE\_NAME_i は半角英数字1文字以上20文字以下であることが保証されています。
- 0 ≦ MAGIC_i ≦ 10,000,000 および 0 ≦ MX_i, MY_i ≦ 10,000 であることは保証されています。
出力
入力例
4 4 Sigunum 3 2 Viita 2 2 Shamall 3 3 Zafiira 2 3 Kame 10 1 1 Tora 10 4 1 Hebi 10 1 4 Niwatori 10 4 4
出力例
8
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
リリースされて早速遊んでいた彼方はそろそろゲームをやめようと ログアウト画面を表示、、、できません。あれ、バグかな、と思っていると 全プレーヤーに聞こえるようにアナウンスが。 アナウンスでは恐るべきことにゲーム参加者の誰かが第100層にある王の指輪に 辿り着かなければ誰一人としてゲームからログアウトできないというのです。 さらに、もしライフが0になったり、強制的にログアウトしようとした場合、 このゲームに接続するためのデバイスが高出力の電磁波を放射し、現実の 肉体を死亡させるというのです。今ここに前代未聞のデスゲームが開始されたのでした。
デスゲームが開始され、参加者は大きく２つのグループに分かれました。 １つは最初の街に立てこもり怪物の危険から逃げた者達、 もう１つは一刻も早くこのゲームをクリアしようと立ち上がった者達でした。 その中で、他者を貶め、略取を働く輩も現れ始めました。それでも、 最初の内は、他者のライフを0にするようなことはありませんでした。 ところがある時を境に他者のライフを0にする、つまり殺人を楽しむような 輩が現れ始めたのです。これは一刻も早くゲームをクリアしなければ 殺人者集団に殺されてしまうかもしれません。
頑張った彼方はかなり高層階まで辿り着きました。 殺人者には幸い出くわしませんでした。本当によかった。 すると突然、大きな揺れが!!!! （このゲームはリリースされて間もないため本当にバグがあったのか、 ここに辿り着くまでのプレイ中に怪しい動きを度々起こしておりました。 もしかしたら、ソフトのバグによって行き成り参加者全員死亡するようなことは、、、。） 揺れがおさまりました。まだ生きている。本当によかった。 おやおや、今の地震の影響で現在いる階から下の階に下りられなくなっている ことが判明しました！オー、神よ。
あなたの仕事は、現在の位置、レベルおよび敵の位置などの地図情報が 与えられた時、クリアに必要な最短時間を求めることです。
入力
T W H L [101-T層の地図] : [100層の地図]1行目には整数T, W, H, Lが与えられます。 Tは残り階層数を表します。 Wはマップの幅を表します。 Hはマップの奥行きを表します。 Lは彼方の現在レベルを表します。 1 ≦ T ≦ 10, 2 ≦ W,H ≦ 10, 1 ≦ L ≦ 999であることは保証されています。 2行目以降には各階層の地図が与えられます。
第i層の地図は次の入力形式で与えられる。
MAPi1 : MAPiH第i層の地図のj行目には文字列MAPijが与えられます。 MAPijのk文字目とk+1文字目(kは任意の奇数)の2文字によって地図の1マスを表します。意味は次の通りです。
- ”==” : 草原
- ”@@” : 街
- “01” : 01レベルの敵モンスター
- （中略）
- “99” : 99レベルの敵モンスター
- “HC” : ラスボス
- ”##” : 背の高い壁
- ” ” : 空
- “_-” : 上り階段
- ”-_” : 下り階段
- “$$” : 王の指輪の位置
- “KR” : 彼方の現在位置
出力
Impossibleを1行に出力せよ。入力例
3 5 5 99
======
==99======
_-####@@@@
##====@@@@
==-_KR
==
##_-==
-_==##====
======
==
-_
==HC==
$$
出力例
217
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
SAITAMA (Secret Association of Ill-Temperedly Armored Massive Agents) は n 人の武装工作員からなる秘密組織である。 SAITAMAの各構成員には 1, 2, ..., n の固有の構成員番号が割り当てられている。 彼らはライバル組織であるGUNMA (Great Ultimate Nation of Massive Agents) を壊滅させるため、日夜鍛錬に明け暮れている。 それゆえ彼らは自身の組織内でのパワーランクについて常に気にかけており、彼らの交わす日常会話は「俺はあいつより強い」「私はB級1位だ。番号が50番以降の誰よりも強い」「奴は我らSAITAMAの中でも最弱」といった具合である。
SAITAMAの構成員の任意の2人の間には力関係が存在する。 ある2人の構成員 a, b について、a は b より強いか、a は b より弱いかのいずれかである。 この力関係、より厳密には、「より強い」関係と「より弱い」関係の2つは、推移律と非反射律を満たしている。 すなわち、3人の構成員 a, b, c について、a が b より強く、b が c より強いとき、必ず a は c より強いことになる。 また、a が a 自身より強いということはない。これらのことは「より弱い」関係についても同様である。
GUNMAのスパイでありSAITAMAの構成員たちの会話を盗聴していたAさんは、彼らの言いふらしている力関係に矛盾が含まれていることに気付いた。 しかし、SAITAMAは極めて多くの構成員からなる組織であるため、どの発言が矛盾を生んだのかはよくわからなかった。 もしかすると矛盾があったという認識すら思い違いであるかもしれない。
幸いAさんはSAITAMAの構成員たちの発言内容と発言順序を全て記憶していた。 奇妙なことに、彼らの発言は全て「番号 p の構成員は番号が l 以上 r 以下の誰よりも強い/弱い」という形式であったそうである。
なんとしてでも矛盾の原因を突き止めたいAさんは、SAITAMAの構成員たちの発言の中でそれまでの発言内容と矛盾する最初の発言をひとまず特定したいと考えている。 すなわち、時系列順に発言を並べたとき、1番目から k-1 番目までの発言の列には矛盾が含まれないが、1番目から k 番目までの発言の列には矛盾が含まれるような整数 k を特定したい。 あなたの仕事は、Aさんのために、SAITAMAの構成員たちの発言の中で最初に矛盾が発生するものが何番目であるかを求めることである。
入力
入力は以下の形式で標準入力から与えられる。
n m p_1 c_1 l_1 r_1 p_2 c_2 l_2 r_2 : p_m c_m l_m r_m
- 1行目には2つの整数 n と m が半角スペース区切りで与えられる。
- n はSAITAMAの構成員の人数であり、1 ≦ n ≦ 1,000,000,000 を満たす。
- m はSAITAMAの構成員たちの発言の数であり、1 ≦ m ≦ 1,000 を満たす。
- 2行目から m+1 行目までの m 行にはSAITAMAの構成員たちの発言に関する情報が時系列順に与えられる。
- これらの行のうちの i 行目 (1 ≦ i ≦ m) には i 番目の発言の情報となる整数 p_i、文字 c_i、整数 l_i と整数 r_i が半角スペース区切りで与えられる。
- i 番目の発言の情報の意味は以下の通りである。
- c_i が
sの場合、「番号 p_i の構成員は、番号が l_i 以上 r_i 以下であるどの番号の構成員より強い」ということを表す。 - c_i が
wの場合、「番号 p_i の構成員は、番号が l_i 以上 r_i 以下であるどの番号の構成員より弱い」ということを表す。
- c_i が
- c_i は
sかwのいずれかである。 - p_i は 1 ≦ p_i ≦ n を満たし、l_i と r_i は 1 ≦ l_i ≦ r_i ≦ n を満たす。
出力
矛盾がない場合、
0 を1行に出力すること。 出力は標準出力に行い、最後には改行を出力すること。
入力例 1
4 5 4 w 1 3 3 w 2 2 2 s 3 4 3 s 1 1 1 s 2 2
出力例 1
5
- 4番目の発言までは矛盾はありませんが、最後の発言が矛盾しています。
- 4番目の発言までの情報で、構成員2は構成員3より強く、構成員3は構成員1より強いことがわかるので、推移律により構成員2は構成員1より強いことが言えます。
- しかし、5番目の発言では構成員1は構成員2より強いとあり、これは矛盾です。
入力例 2
2 4 1 w 2 2 1 s 2 2 2 w 1 1 2 s 1 1
出力例 2
2
- 構成員1が構成員2より弱く、かつ構成員1が構成員2より強いということはありえないので、2番目の発言は1番目の発言と矛盾しています。
- 以降の発言にも矛盾がありますが、最初に矛盾する発言の番号である
2が答えとなります。
入力例 3
1000000000 4 1 w 5 100000 1000000 s 100 888888 1000 w 10000 10000 1000000000 s 1 999999999
出力例 3
0
- 矛盾はありません。番号の大小関係がそのまま力関係になっているようです。
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
あなたはヘビゲームをプレイしている。 プレイヤーはヘビを操作し、その頭がマップの壁あるいは自身の身体にぶつからないようにしながら、ランダムで出現するエサを回収する。 エサを回収するたびにヘビの身体は 1 マスずつ長くなっていく、というゲームである。
あなたがプレイしているヘビゲームには実績という機能あり、ゲーム中に特定の行動を取るとその行動に対応した実績を獲得できる。 あなたが獲得しようとしている実績の条件は、マップ内の移動可能なすべてのマスを一筆書きのように通過する、というものである。
長さ L のヘビは L 個の連接するマスからなり、マス 1 つがヘビの体の節 1 つを表している。 ヘビの体節には 1 から L までの番号が付いており、番号順にヘビの頭からヘビの尻尾までを表す。 ヘビの i 番目の体節と i - 1 番目の体節は隣り合ったマスに存在する (i = 2..L)。 2 つのマスが隣り合っているとは、2 つのマスが共有する辺をもつということである。
ヘビは進行方向に対して前、右、左の 3 方向いずれかに 1 マスずつ移動することができる。 ヘビの進行方向は、ヘビの 2 番目の体節から見て 1 番目の体節 (ヘビの頭) がある方向である。
ヘビが移動するとき、ヘビの体はヘビの頭が通った経路を追従するように移動する。 すなわち、ヘビの頭が 1 マス移動するとき、それに合わせて i 番目の体節は i - 1 番目の体節の位置へ移動する (i = 2..L)。
この挑戦の間エサは出現しないので、ヘビの長さはスタート時から変化しない。 ヘビの長さとマップが与えられたとき、ヘビの頭がマップの壁あるいは自身の身体にぶつからないようにしながら、通行可能なすべてのマスをそれぞれちょうど 1 度ずつまわることができるか判定するプログラムを作成したい。
入力
入力は複数のデータセットからなり、入力の終わりはスペースで区切られた 3 つのゼロからなる。各データセットは以下のように構成される。
L H W m(1, 1) m(1, 2) ... m(1, w) m(2, 1) m(2, 2) ... m(2, w) : m(h, 1) m(h, 2) ... m(h, w)
L はヘビの長さ、H と W はマップの行および列の数を表す整数である。 これらは 2 ≦ L ≦ 9, 1 ≦ H, W ≦ 8 を満たす。
続く H 行にマップの状態が与えられる。各マスの状態は 1 つの半角文字で表され、それぞれ以下の意味をもつ。
#: 壁 (通行不可).: 何もない (通行可)1..9: 開始時点のヘビの位置 (通行可)
1 のマスは通過済み、それ以外の数字のマスは未通過とする。
なお、マップの最も外側のマスはすべて壁であることがわかっている。
出力
各データセットについて、すべてのマスをまわることができるならば Yes を、そうでないならば No をそれぞれ 1 行に出力せよ。
入力例
2 5 4 #### #12# #..# #..# #### 2 5 4 #### #12# #.## #..# #### 8 7 7 ####### #...#.# #1#.#.# #2..#.# #3###.# #45678# ####### 9 7 7 ####### #...#.# #1#.#.# #2..#.# #3###9# #45678# ####### 0 0 0
出力例
Yes No Yes No
- 1 セット目について、「下下右上上」と移動するとすべてのマスをまわれる。
- 2 セット目について、「下下右」と移動すると右上のマスに辿りつけない。
- 3 セット目について、「上右右下下左左下下右右右右上上上上」と移動するとすべてのマスをまわれる。
- 4 セット目について、「上右右下下左左」と移動すると、7 回目の移動のとき 1 番目の体節と 9 番目の体節が衝突してしまう。
Source Name
Maximum-Cup 2013Time Limit: 2 sec / Memory Limit: 256 MB
問題
与えられた長さ n の数列 α = (a_1, ..., a_n) が k-sorted かどうかを判定せよ。 全ての 1 ≦ i, j ≦ n に対して i < j - k ならば a_i ≦ a_j が成り立つとき、およびそのときに限り、α は k-sorted であるという。 0-sorted は普通のソートと等価である。
入力
入力は複数のデータセットからなり、入力の終わりはスペースで区切られた 2 つの -1 からなる。
各データセットは以下のように 2 行で構成される。
n k a_1 ... a_n
1 行目は 2 つの整数で構成される。 数列 α の長さを表す n に続き、k-sorted の k が与えられる。 n と k は、それぞれ 0 ≦ n ≦ 50,000, 0 ≦ k ≦ n の条件を満たす。
2 行目は n 個の整数で構成される。 i 番目の整数が数列 α の i 番目の要素 a_i を表す (1 ≦ i ≦ n)。 数列 α の要素 a_i は、0 ≦ a_i < 2^{63} の条件を満たす。
出力
各データセットについて、与えられた数列 α が k-sorted であるなら Yes を、そうでないなら No をそれぞれ 1 行に出力せよ。
入力例
3 0 1 2 3 3 0 2 1 3 3 1 2 1 3 3 1 3 1 2 3 2 3 1 2 1 1 1 1 0 1 0 0 -1 -1
出力例
Yes No Yes No Yes Yes Yes Yes