Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の秘書のなぎさちゃんは、高橋君からハンドルネームを貰いました。
しかし、残念なことに、このハンドルネームは、既に登録しようとしたサービスで使われてしまっていました。
仕方がないので、なぎさちゃんが好きなC++に肖って、ハンドルネームの末尾にpp
を付けることにしました。
元のハンドルネームが入力されるので、新しいハンドルネームを出力してください。
入力
入力は以下の形式で標準入力から与えられる。
S
- 1 行目には、元のハンドルネーム S (1 ≦ |S| ≦ 10) が与えられる。
- S に含まれる文字は、全て小文字アルファベットであることが保障されている。
出力
新しいハンドルネームを 1 行で出力せよ。出力の末尾にも改行をいれること。
入力例1
chokudai
出力例1
chokudaipp
ハンドルネームがchokudai
なので、それにpp
を足したものが、新しいハンドルネームになります。
入力例2
sanagi
出力例2
sanagipp
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の秘書のなぎさちゃんは、高橋君が大好きです。つまり、高橋君もなぎさちゃんの事が大好きであるに違いありません。 そのことを確認するために、庭に咲いている花で、花占いをすることにしました。
「好き」、「嫌い」、「好き」、「嫌い」、「好き」、「嫌い」……。
おかしいです。高橋君はなぎさちゃんの事が好きであるはずなのに、花占いの結果は「嫌い」でした。 これは、花が悪いに違いありません。
なぎさちゃんは、使用人達に、花占いの結果が「嫌い」にならないように、花びらを毟るよう命じました。
なぎさちゃんの花占いは、2つのパターンがあります。 一つは、「好き」「嫌い」を交互に言いながら、花びらを 1 枚ずつ毟っていくパターンです。 もう一つは、「好き」「嫌い」「大好き」の 3 つを繰り返しながら、花びらを1枚ずつ毟っていくパターンです。
どちらのパターンにおいても、最後に言った言葉が、花占いの結果となります。
なぎさちゃんの使用人であるあなたは、なぎさちゃんがどちらのパターンで花占いをしたときも、「嫌い」にならないように、 花びらを事前に毟ってあげる必要があります。
庭に咲いている花の数と、その花びらの枚数が与えられるので、花びらを毟る必要のある枚数を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
n a_1 a_2 ... a_n
- 1 行目には、庭に咲いている花の数を表す整数 n (1 ≦ n ≦ 10) が与えられる。
- 2 行目では、それぞれの花の花びらの枚数に関する情報が、スペース区切りで与えられる。 i 番目の花の花びらの枚数は、 i 番目に与えられる整数 a_i (1 ≦ a_i ≦ 9)によって与えられる。
出力
毟る必要のある花びらの枚数を 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
3 5 8 2
出力例1
4
最初の花に注目します。
- 花びらの数が 5 枚の時、2 つ目のパターンの花占いで、「好き」「嫌い」「大好き」「好き」「嫌い」となり、「嫌い」になってしまうので、花びらを毟らなければなりません。
- 花びらの数が 4 枚の時、1 つ目のパターンの花占いで、「好き」「嫌い」「好き」「嫌い」となり、「嫌い」になってしまうので、花びらを毟らなければなりません。
- 花びらの数が 3 枚の時、1 つ目のパターンで「好き」、2 つ目のパターンで「大好き」となるため、花びらを毟る必要がありません。
同様に、花びら 8 枚の花は 7 枚に、花びら 2 枚の花は 1 枚にすることにより、「嫌い」になることを防ぐことが出来ます。
花びらを毟る必要のある枚数の合計は、2 + 1 + 1 = 4 枚となります。
入力例2
9 1 2 3 4 5 6 7 8 9
出力例2
8
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の秘書のなぎさちゃんは、高橋君が大好きです。今日も高橋君に電話をかけてみることにしました。 すると、どうでしょう? 電話口から、高橋君の声以外の、女の声が聞こえてきます。
なぎさちゃんは、高橋君と付き合ってはいませんが、高橋君に悪い虫が付いたら大変なので、浮気調査を行うことにしました。
高橋君の携帯に仕込んだアプリケーションから、高橋君の居場所をGPSで取得すると、高橋君は、電話をかける前は座標 (tx_a, ty_a) に、 電話をかけた後は、座標 (tx_b, ty_b) にいることがわかりました。また、この間にかかった時間は T 分です。 高橋君は、最大毎分 V の距離を移動することが可能であり、家などの障害物を無視して同じ速度で移動することが可能です。
なぎさちゃんは、このデータを元に、高橋君が、近所の女の子の家に寄っていないかを調査することにしました。 近所の女の子は n 人おり、それぞれ座標 (x_i, y_i) に住んでいます。
高橋君が、他の女の子の家に寄った可能性が少しでもある場合はYES
、そうでない場合はNO
と出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。
tx_a ty_a tx_b ty_b T V n x_1 y_1 x_2 y_2 : x_n y_n
- 1 行目には、高橋君の電話前の座標を表す整数 tx_a, ty_a (0 ≦ tx_a, ty_a ≦ 1000)、電話後の座標を表す整数 tx_b, ty_b (0 ≦ tx_b, ty_b ≦ 1000)、移動に掛かった時間を表す整数 T (1 ≦ T ≦ 50)、高橋君の毎分の速度を表す整数 V (1 ≦ V ≦ 100)がスペース区切りで与えられる。
- 2 行目には、浮気調査の対象となる女の子の数 n (1 ≦ n ≦ 1000) が与えられる。
- 3 行目から n 行では、女の子の家の情報が与えられる。このうち i 行目では、i 番目の女の子の家の座標を表す整数 x_i, y_i (0 ≦ x_i, y_i ≦ 1000) が与えられる。
- 高橋君が、座標 (tx_a, ty_a) から、座標 (tx_b, ty_b)まで真っ直ぐ毎分 V 移動した時に、T 分より長くかかってしまうような入力は与えられない。
出力
高橋君が、他の女の子の家に寄ることが可能であればYES
、そうでなければNO
を 1 行で出力せよ。出力の末尾にも改行をいれること。
入力例1
1 1 8 2 2 4 1 4 5
出力例1
NO
高橋君が (1,1) から (8,2) に移動した際に、(4,5) の家に寄ることが可能かどうか考えます。
- (1,1)から(4,5)に移動する際、\sqrt{(4-1)^2 + (5-1)^2} = 5となるため、移動距離は 5
- (4,5)から(8,2)に移動する際、\sqrt{(8-4)^2 + (2-5)^2} = 5となるため、移動距離は 5
となり、総移動距離は10となります。
高橋君が移動可能な距離は、2 分間で 分速 4 なので、 8 までしか移動することが出来ません。
よって、高橋君がこの家に寄る事は不可能なため、NO
と出力します。
入力例2
1 1 8 2 2 6 1 4 5
出力例2
YES
入力例1と同じ配置ですが、高橋君の移動速度が 6 に変わっています。
高橋君の移動可能距離が 12 になったので、今度は家に寄ることが可能となっています。
よって、YES
と出力します。
入力例3
1 1 8 2 2 5 1 4 5
出力例3
YES
ぴったり移動可能な場合も、寄ること自体は可能なので、YES
と出力します。
入力例4
7 7 1 1 3 4 3 8 1 1 7 9 9
出力例4
YES
2 番目の女の子の家にだけ、寄ることが可能です。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の秘書のなぎさちゃんは、高橋君が大好きです。今日も、高橋君に悪い虫が取り憑かないように、高橋君を監視しなければなりません。
高橋君は、女の子と仲良くなるために、自前のSNSを使います。SNSで友人関係にある人を辿って行き、見つけた女の子にメッセージを送ります。 なぎさちゃんは、高橋君のメッセージを女の子が見ることがないように、このSNSに対して、工作を行うことにしました。
行える工作活動は、以下の 2つです。
- 特定の二人の友人関係を解消する
- 特定の一人のパスワードを変え、ログイン出来なくする 高橋君のパスワードは変更できません。(21:11追記)
友人関係が解消されると、高橋君は、その二人の間を辿ることが出来なくなります。しかし、他の友人を経由して、辿ることが可能な場合は、その限りではありません。
パスワードを変更すると、その人は、メッセージを見ることが不可能になります。友人関係に変化はないので、パスワードを変更された人を辿って、別の友人を探すのは可能です。
なぎさちゃんは、出来るだけ工作の回数を少なくして、予めマークした女の子達が、高橋君のメッセージを閲覧できないようにしたいです。なぎさちゃんが工作を行う必要のある回数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N G E p_1 p_2 ... p_G a_1 b_1 a_2 b_2 : a_E b_E
- 1 行目には、SNSの登録人数を表す整数 N (1 ≦ N ≦ 100) と、なぎさちゃんがマークしている女の子の数 G (0 ≦ G ≦ N - 1)、 SNSの友人関係の数を表す整数 E (0 ≦ E ≦ N × (N-1) / 2)がスペース区切りで与えられる。
- 2 行目では、なぎさちゃんがマークしている i 番目の女の子のIDを表す整数 p_i (1 ≦ p_i ≦ N - 1) の値が、スペース区切りで G 個与えられる。
- 3 行目から E 行では、友人関係に関する情報が与えられる。このうち i 行目では i 番目の友人関係における、二人のID番号を表す 2 つの整数 a_i (0 ≦ a_i ≦ N - 1) b_i (0 ≦ b_i ≦ N - 1) の値が、スペース区切りで与えられる。
- i ≠ j のとき、a_i = a_j かつ b_i = b_j、または a_i = b_j かつ b_i = a_j になることはないことが保障されている。
- 全ての入力において、高橋君のIDは 0 であることが保障されている。
部分点
0 ≦ E ≦ 12 を満たすテストケースに正解した場合、部分点として 99 点が与えられる。
出力
なぎさちゃんが工作を行う必要のある回数の最小値を、 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
4 2 3 2 3 0 1 1 2 1 3
出力例1
1
図のように、 1 つの友人関係を解消するだけで、2 人の女の子を高橋君から切り離すことが出来ます。
入力例2
4 1 4 3 0 1 0 2 1 3 2 3
出力例2
1
マークしている女の子は一人だけなので、この人をログイン出来なくするだけで、目的を達成することができます。
入力例3
10 3 11 7 8 9 0 1 0 2 0 3 0 4 1 5 2 5 5 6 6 7 6 8 3 9 4 9
出力例3
2
図のように工作を行うことで、全ての女の子に対して工作を行えます。
入力例4
6 2 6 4 5 0 1 0 2 1 3 2 3 3 4 3 5
出力例4
2
IDが 3 の人をログイン出来ないようにしても、高橋君が友達を探すのに影響がないことに注意してください。
入力例5
4 3 3 1 2 3 1 2 1 3 2 3
出力例5
0
高橋君には友達がいないため、工作を行う必要はありません。