B. Шинэ Төрлийн Хялбар Бодлого

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Олны дунд танигдсан Беларус-ын спортын программист Леша нэгэн томхон байр худалдан авахын тулд мөнгө олох хэрэгтэй болов. Ингэхийн тулд тэрээр Torcoder.com хэмээх вэб хуудас дээрх Super Rated Match буюу SRM-ыг хийж үүнийгээ цааш хөгжүүлэх хэрэгтэй болжээ. Гэвч тэрээр нэгэн асуудалтай тулгарчээ. Тодруулбал torcoder-ын хашир хатуу зохицуулагч Иван Леша-ын зохиосон ямар ч бодлогыг хүлээн зөвшөөрөхгүй байгаа бөгөөд түүний зохиосон бодлого бүрийг нь давхацсан хэмээн зохисгүй байдлаар хэлж байв. Нэгэн өдөр Иваны бас нэгэн хүлээн зөвшөөрөхгүй байгаа бодлогын талаар тэд бараг л муудалцах шахжээ.

Та энэ үйл явдлыг шүүх шударга шүүгчийн ажлыг хийх бөгөөд уг бодлого нь шинэ төрлийн бодлого уу эсвэл Иваны зөв буюу уг бодлого нь өмнөх SRM-ууд дээр ашигласан бодлогуудтай төстэй эсэхийг тодорхойлж өгөх юм.

Танд Леша-ын зохиосон бодлого болон Torcoder.com-ын архив доторх бодлого бүрийн тайлбарууд өгөгдөнө. Бодлого бүрийн тайлбар нь үгсийн дараалал хэлбэртэй өгөгдөх юм. Түүнчлэн Леша-ын бодлого нь давтагдсан үгс агуулаагүй байх боловч архив доторх бодлогуудын тайлбар дотор давтагдсан үгс агуулагдсан байж болно.

Леша-ын бодлого болон архив доторх бодлогын хоорондох "төстэй байдал"-ыг дараах байдлаар тодорхойлж болно. Леша-ын бодлого доторх үгсийн бүх боломжит сэлгэмлүүд дундаас бид архив доторх бодлогын дэд дараалал хэлбэрээр орж буй нэгэн сэлгэмлийг сонгоно. Хэрэв ийм байх олон тооны сэлгэмэл оршин байвал тэдгээрийн дундаас хамгийн бага тооны сэлгэлт хийсэн сэлгэмлийг сонгоно. Үүний дараа бидний хайж буй "төстэй байдал" нь хэлбэртэйгээр бичигдэх бөгөөд энд $n$ нь Леша-ын бодлого доторх үгсийн тоог, $x$ нь сонгогдсон сэлгэмлийн сэлгэлтийн тоог тус тус илэрхийлнэ. "төстэй байдал" $p$ нь үргэлж эерэг бүхэл тоо байхыг анхаарна уу.

Хэрэв Иваны бодлогын архив дотор Леша-ын бодлогын үгсийн сэлгэмлийг өөрийн дэд дараалал болгон агуулж байх нэг ч бодлого оршин байхгүй байвал Леша-ын уг бодлогыг шинэ төрлийн бодлого гэж үзэх юм.

Хөвгүүдэд туслан уг өгөгдсөн бодлого нь шинэ төрлийн бодлого эсэхийг тодорхойлж өгнө үү. Хэрэв шинэ төрлийн бодлого биш байвал архив дотроос Леша-ын бодлоготой хамгийн төстэй бодлогыг олно уу.

Оролт

Эхний мөрөнд ганц бүхэл тоо $n$ ($1 ≤ n ≤ 4$) өгөгдөх ба энэ нь Леша-ын бодлого доторх үгсийн тоог илэрхийлнэ. 2-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан үгс өгөгдөх бөгөөд эдгээр нь уг бодлогын богино тайлбарыг илэрхийлнэ.

3-дахь мөрөнд ганц бүхэл тоо $m$ ($1 ≤ m ≤ 10$) өгөгдөх ба энэ нь Torcoder.com-ын архив доторх бодлогуудын тоог илэрхийлнэ. Дараагийн $m$ ширхэг мөрийн мөр болгонд бодлогуудын тайлбарууд нь "$k$ $s_{1}$ $s_{2}$ $...$ $s_{k}$" гэсэн хэлбэртэйгээр өгөгдөх бөгөөд энд $k$ ($1 ≤ k ≤ 20$) нь тухайн бодлого доторх үгсийн тоог илэрхийлэх бөгөөд $s_{i}$-ууд нь тухайн бодлогын тайлбар доторх үгүүдийг илэрхийлнэ.

Бүх бодлогуудын тайлбарууд доторх бүх үгс нь 10-аас ихгүй тооны Англи жижиг үсэг агуулсан байна.

Гаралт

Хэрэв Леша-ын бодлого нь шинэ төрлийн бодлого байвал "Brand new problem!" (хашилтгүйгээр) гэсэн тэмдэгт мөрийг хэвлэнэ үү.

Бусад тохиолдолд гаралтын эхний мөрөнд Леша-ын бодлоготой хамгийн төстэй, архив доторх бодлогын дугаарыг хэвлэнэ үү. Хэрэв ийм байх олон тооны бодлогууд байвал тэдгээрийн дундаас хамгийн бага дугаартай нэгэн бодлогын дугаарыг хэвлэнэ үү. Гаралтын 2-дахь мөрөнд [: тэмдэгтүүд, $p$ ширхэг | тэмдэгтүүд болон :] тэмдэгтүүдээс тогтох нэгэн тэмдэгт мөрийг хэвлэнэ үү (Жишээнүүдийг сайтар харна уу). Энд $p$ нь уг архив доторх бодлого болон Леша-ын бодлогын хоорондох "төстэй байдал"-ыг илэрхийлнэ. Архив доторх бодлогуудыг оролтод өгөгдсөн дарааллынхаа дагуу 1-ээс эхлэн дугаарлагдсан байна гэж үзнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4
find the next palindrome
1
10 find the previous palindrome or print better luck next time
Гаралт
1
[:||||||:]
Оролт
3
add two numbers
3
1 add
2 two two
3 numbers numbers numbers
Гаралт
Brand new problem!
Оролт
4
these papers are formulas
3
6 what are these formulas and papers
5 papers are driving me crazy
4 crazy into the night
Гаралт
1
[:||||:]
Оролт
3
add two decimals
5
4 please two decimals add
5 decimals want to be added
4 two add decimals add
4 add one two three
7 one plus two plus three equals six
Гаралт
3
[:|||:]

Тэмдэглэл

Сэлгэлтийн тоо гэдэг нь тухайн сэлгэмэл дотор анх байсан дарааллаасаа өөр дарааллаар орж буй хос үгсийн тоог хэлнэ. Жишээлбэл анхны бодлого нь "add two numbers" байвал "numbers add two" гэсэн сэлгэмэл нь 2 ширхэг сэлгэлт агуулж байх бөгөөд тодруулбал "numbers" болон "add", "numbers" болон "two" гэсэн хос үгс нь өөр дарааллаар орсон байгаа юм.

Хэрэв $a_{i_{j}}  =  b_{j}$ байх $1 ≤ i_{1} <  i_{2} < ...   < i_{k} ≤ n$ гэсэн индексүүдийн олонлог оршин байвал (өөрөөр хэлбэл хэрэв $a$ дарааллаас зарим нэг элементийн хасах замаар $b$ дарааллыг гарган авч болдог байвал) $b_{1},  b_{2},  ...,  b_{k}$ гэсэн дарааллыг $a_{1}, a_{2},  ...,  a_{n}$ гэсэн дарааллын дэд дараалал гэж үзнэ.

Эхний жишээний эхний архивын бодлого нь "find the palindrome next" гэсэн сэлгэмлийг дэд дараалал болгон агуулах бөгөөд уг сэлгэмлийн сэлгэлтийн тоо нь 1-тэй тэнцүү байна ("palindrome" болон "next" гэсэн үгс).

2-дахь жишээнд архив доторх ямар ч бодлого нь Леша-ын бодлогын үгсийн сэлгэмлийг өөрийн дэд дараалал болгон агуулаагүй байна.

Сэтгэгдлүүдийг ачааллаж байна...