A - 1→1
言語を記述するものとして形式文法があります。
ここでいう言語とは終端記号の列の集合です。
形式文法を構成するものとして生成規則の集合が定義されます。
そして、開始記号から生成規則を適用して作ることのできる終端記号の列の集合、として言語を定義することができます。
生成規則の適用の例としては、生成規則 A → ab を1回適用することで AAB を AabB にすることができます。
よく知られているものとしては正規文法や文脈自由文法があります。
この問題は、制限のない文法を扱う問題です。
入力は以下の形式に従う。与えられる数は全て整数である。
a_i, b_i は生成規則 a_i 個の 1 → b_i 個の 1 を表す。 例えば、a_i = 2, b_i = 3 は 11→111 を表す。 これによって形式言語 G = (V, Σ, P, S) が表現される。 非終端記号 V = \{S\}、 終端記号 Σ = \{1\}、開始記号は S である。 生成規則 P は S→1 と、入力で与えられる生成規則である。
開始記号 S から n 個の 1 を作るには最低何回生成規則を適用すればよいかを求めよ。
不可能であれば
Time Limit: 2 sec / Memory Limit: 64 MB
ここでいう言語とは終端記号の列の集合です。
形式文法を構成するものとして生成規則の集合が定義されます。
そして、開始記号から生成規則を適用して作ることのできる終端記号の列の集合、として言語を定義することができます。
生成規則の適用の例としては、生成規則 A → ab を1回適用することで AAB を AabB にすることができます。
よく知られているものとしては正規文法や文脈自由文法があります。
この問題は、制限のない文法を扱う問題です。
入力
m n a_1 b_1 a_2 b_2 : a_m b_mm は入力で与えられる生成規則の数を表す。 n は作りたい 1 の数を表す。
a_i, b_i は生成規則 a_i 個の 1 → b_i 個の 1 を表す。 例えば、a_i = 2, b_i = 3 は 11→111 を表す。 これによって形式言語 G = (V, Σ, P, S) が表現される。 非終端記号 V = \{S\}、 終端記号 Σ = \{1\}、開始記号は S である。 生成規則 P は S→1 と、入力で与えられる生成規則である。
制約
- 1 ≦ m ≦ 300^2
- 1 ≦ n ≦ 10000
- 1 ≦ a_i ≦ 300
- 1 ≦ b_i ≦ 300
- i ≠ j ならば、 a_i ≠ a_j または b_i ≠ b_j
出力
-1
を出力せよ。
Input 1
2 5 1 2 3 5
Output 1
4
- 生成規則は、\{S → 1,\ 1 → 11,\ 111 → 11111\} である。
- S → 1 → 11 → 111 → 11111 で 4 回となる。
Input 2
2 6 1 3 5 3
Output 2
-1
- 生成規則は、\{S → 1,\ 1 → 111,\ 11111 → 111\} である。
B - 01:01
6月10日はhasiの誕生日なので日付問題を出します。
嘘です。時刻問題を出します。
プログラミングコンテストは世界中で開催されていますが、そこで問題になってくるのはタイムゾーンです。
webページには開始時間が現地時間で載っていていちいち計算しないといけません。
そこでhasiは、世界共通で使える、時間に付ける名前があったら便利じゃないかなと思いました。
10日(Sun)、11日(Mon)のような曜日のように、例えば、3時(Sun)、4時(Mon)というように名前を付けられないか、と。
そして、この「時間に付ける名前」を曜時と名付けました。
この問題は、曜時を計算する問題です。
入力は以下の形式に従う。
hour_i は、時間の名前を表す。 都市 A において、 00:00 ~ 00:59 には hour_0、 01:00 ~ 01:59 には hour_1、 …、 23:00 ~ 23:59 には hour_{23}、 という名前が与えられる。 時間の名前は世界共通であり、ある時刻において、ある都市の時間の名前が hour_i のとき、すべての都市で時間の名前が hour_i となる。
city_{i,j} は都市の名前、time_{i,j} は時刻を表す。 都市 city_{i,1} が時刻 time_{i,1} のとき、都市 city_{i,2} は時刻 time_{i,2} であるという情報が N 個与えられる。
都市 B が時刻 time_B のときの時間の名前を求めよ。夏時間はないものとする。
Time Limit: 2 sec / Memory Limit: 64 MB
嘘です。時刻問題を出します。
プログラミングコンテストは世界中で開催されていますが、そこで問題になってくるのはタイムゾーンです。
webページには開始時間が現地時間で載っていていちいち計算しないといけません。
そこでhasiは、世界共通で使える、時間に付ける名前があったら便利じゃないかなと思いました。
10日(Sun)、11日(Mon)のような曜日のように、例えば、3時(Sun)、4時(Mon)というように名前を付けられないか、と。
そして、この「時間に付ける名前」を曜時と名付けました。
この問題は、曜時を計算する問題です。
入力
city_A hour_0 hour_1 … hour_{23} N city_{1,1} time_{1,1} city_{1,2} time_{1,2} city_{2,1} time_{2,1} city_{2,2} time_{2,2} : city_{N,1} time_{N,1} city_{N,2} time_{N,2} city_B time_Bcity_A, city_B は、それぞれ都市 A、都市 B の名前を表す。
hour_i は、時間の名前を表す。 都市 A において、 00:00 ~ 00:59 には hour_0、 01:00 ~ 01:59 には hour_1、 …、 23:00 ~ 23:59 には hour_{23}、 という名前が与えられる。 時間の名前は世界共通であり、ある時刻において、ある都市の時間の名前が hour_i のとき、すべての都市で時間の名前が hour_i となる。
city_{i,j} は都市の名前、time_{i,j} は時刻を表す。 都市 city_{i,1} が時刻 time_{i,1} のとき、都市 city_{i,2} は時刻 time_{i,2} であるという情報が N 個与えられる。
制約
- 1≦N≦20
- 都市の名前・時間の名前は大文字・小文字の英字からなる
- 都市の名前・時間の名前の文字列長は 20 以下
- 異なる都市が同じ名前を持つことはない
- 時間の名前は互いに異なる
- 時刻は
hh:mm
の形式で与えられる hh
は00
~23
mm
は00
~59
- 情報の矛盾や不足は存在しないことが保証される
出力
Input 1
UTC A B C D E F G H I J K L M N O P Q R S T U V W X 1 UTC 00:00 Akashi 09:00 Akashi 00:00
Output 1
P
Input 2
Tokyo P Q R S T U V W X A B C D E F G H I J K L M N O 3 Tokyo 00:00 Connecticut 11:00 Moskow 19:30 Connecticut 11:30 India 21:30 Moskow 20:00 India 00:39
Output 2
T
C - 1=0.999...
1 と 0.999... がまったく同じ実数を表すということは、
ネット上でもしばしば議論される話題です。
この問題は、そんな小数に関する問題です。
入力は以下の形式に従う。
a_i は有限小数または循環小数であり、実数の集合 A = {a_i} のすべての要素を表す。 1 つの実数が異なる表記で与えられる場合がある。
有限小数および循環小数は以下のBNFに従う。 循環小数において括弧で囲まれた部分は循環節を表し、 例えば
実数の集合 A の要素数を求めよ。
Time Limit: 2 sec / Memory Limit: 64 MB
この問題は、そんな小数に関する問題です。
入力
N a_1 a_2 : a_N1行目には、与えられる小数の数 N が与えられる。 2行目から続く N 行では、実数 a_i が与えられる。
a_i は有限小数または循環小数であり、実数の集合 A = {a_i} のすべての要素を表す。 1 つの実数が異なる表記で与えられる場合がある。
有限小数および循環小数は以下のBNFに従う。 循環小数において括弧で囲まれた部分は循環節を表し、 例えば
0.(01)
は 0.010101... を表現する。<有限小数> ::= <整数部> "." <\d+> <循環小数> ::= <整数部> "." <\d*> "(" <\d+> ")" <整数部> ::= "0" | <[1-9]> <\d*> <\d*> ::= "" | <\d+> <\d+> ::= <[0-9]> <\d*> <[0-9]> ::= "0" | <[1-9]> <[1-9]> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
制約
- 1 ≦ N ≦ 300
- a_i の文字列長は 300 以下
出力
Input 1
2 1.0 0.(9)
Output 1
1
Input 2
3 3.(142857) 3.1(428571) 3.14(285714)
Output 2
1
D - 1+1
手を用いた遊びのひとつに 数字を増やす遊び というものがあります。
二人でやる遊びで、まず、両手の人差し指を出してお互いに見せ合います。
そして、交互に右手か左手のどちらかで相手の手のどちらかを選んで指の数を増やしていきます。
この問題は、このゲームを最善手でプレイしたときの勝敗を求める問題です。
入力は以下の形式に従う。与えられる数は全て整数である。
無限に行動を続ける手順が存在するならば
存在しないならば、先手と後手は以下の基準で行動を選んだとき、 ゲームの結果とゲームが何ターンで終了するかを求めよ。 そして、先手が勝つ場合は
Time Limit: 2 sec / Memory Limit: 64 MB
二人でやる遊びで、まず、両手の人差し指を出してお互いに見せ合います。
そして、交互に右手か左手のどちらかで相手の手のどちらかを選んで指の数を増やしていきます。
この問題は、このゲームを最善手でプレイしたときの勝敗を求める問題です。
入力
n m rそれぞれ以下のルールにおける 要素の状態数 n, 最大分割回数 m, 加算ルール r を表す。
- 状態を (x,y) で表す。x, y を「要素」と呼ぶ。
- 初期状態は、先攻後攻ともに (1,1) である。
- 各ターンでとれる「行動」は「選択」または「分割」のいずれかである。
- 先攻後攻交互に行動を繰り返し、(0,0) となったほうが負けとなる。
- 選択: 自分の 0 でない要素 x と相手の 0 でない要素 y を選び、選んだ相手の要素に x を「加算」し、x+y にする。このとき、以下のどちらかの加算ルール r を適用する。
- 加算ルール 0 : x+y が n 以上になった場合は 0 になる。
- 加算ルール 1 : x+y が n 以上になった場合は x+y-n になる。
- 分割: 一方の要素が 0、かつ、もう一方の要素 k が 2 以上ならば、「分割」を行うことができる。 a + b = k, a ≧ 1, b ≧ 1 となるような自然数 a, b を選び (a,b) とする。
- 分割は最大 m 回行うことができる。
制約
- 2 ≦ n ≦ 16
- 0 ≦ m ≦ 2
- 0 ≦ r ≦ 1
出力
Infinite
を出力せよ。
このとき、先手と後手は無限に行動を続けるために協力して良い。存在しないならば、先手と後手は以下の基準で行動を選んだとき、 ゲームの結果とゲームが何ターンで終了するかを求めよ。 そして、先手が勝つ場合は
First
、後手が勝つ場合は Second
と 1 行目に出力せよ。
2 行目にゲームが終了するのが何ターン目になるのかを出力せよ。
- 自分が勝ちになる手が存在するときはその手を選ぶ。自分が勝ちになる手が複数存在するときはその中からゲームが最短で終了するような手を選ぶ。
- 自分が負けになる手しか存在しないとき、ゲームが最長で終了するような手を選ぶ。
Input 1
2 0 0
Output 1
First 3
Input 2
4 0 1
Output 2
Infinite