C. Формуроса

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

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

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

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

Байтлэндийн Биологийн судалгааны хүрээлэн бактерийн хоёр төрлийг судлаж байгаа ба тэдгээрийг хялбараар 0 ба 1 гэж нэрлэсэн. Микроскопоор ч гэсэн уг хоёр төрлийн бактерийг ялгахад маш хэцүү. Үнэндээ энэ хоёрыг ялгахаар эрдэмтдийн олсон ганц зүйл нь Формуроса нэртэй ургамал юм.

Хэрвээ эрдэмтэд бактериудыг Формуросагийн навч бүр дээр нэгийг байрлуулбал эдгээр нь төвөгтэй тэжээлийн үйл явцыг идэвхжүүлнэ. Энэ үйл явцын үеэр Формуросагийн өнгө маш ярвигтай байж болох бактеруудын төрөл дээр хийгдэх логик томьёоны хариунаас үүдэн өөрчлөгдөнө. Энэ томьёо нь тогтмолууд болон $|$ (OR), $\&$ (AND) ба $^$ (XOR) үйлдлүүдээс тогтоно. Хэрвээ хариу нь 0 байвал ургамал улаан харин бусад тохиолдолд хөх өнгөтэй болно.

Жишээлбэл хэрвээ Формуросагийн тэжээлийн үйл явцыг $(((?^?)|?)&(1^?))$ томьёогоор тодорхойлбол Формуроса нийт дөрвөн навчтай ("$?$" нь навчийг заана). Хэрвээ бид харгалзах навчнууд дээр $0, 1, 0, 0$ гэж байрлуулвал тэжээлийн үйл явцын үр дүн $(((0^1)|0)&(1^0)) = 1$ болж ургамал хөх өнгөтэй болно.

Эрдэмтдэд $n$ бактери байна. Тэд эдгээрийн төрлийг мэдэхгүй боловч нэг баттай мэдэж байгаа зүйл нь бүх бактери ижил төрлийнх биш байна. Тэд Формуросаг ашиглан давтан тооцоолол хийж бактеруудын төрлүүдийг тодорхойлохыг хүсч байна. Тооцоолол бүрийн үед тэд ургамалын навч бүр дээр яг нэг бактери тавих ёстой. Гэсэн ч тэд нэг төрлийн хэд хэдэн бактерийг нэг тооцооллын үед ашиглаж болно мөн ургамалыг зөвхөн нэг төрлийн бактериар хучиж бас болно.

Тэдний хувьд бактери бүрийн төрлийг тодорхойлох боломжтой юу (мэдээж бүгд ижил төрлийн биш гэдгийг тооцоод)?

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($2 ≤ n ≤ 10^{6}$) байх буюу бактериудын тоо юм.

Хоёр дахь мөрөнд Формуросагийн тэжээлийн үйл явцын томьёог тодорхойлно. Энэ мөрөнд зөвхөн «$0$», «$1$», «$?$», «$|$», «$&$», «$^$», «$($», «$)$» тэмдэгтүүд л байх ба дараах дүрмийг мөрдөнө:

$s -> 0|1|?|(s|s)|(s&s)|(s^s)$

Томьёо $10^{6}$ ихгүй тэмдэгтээс бүрдэнэ.

Гаралт

Хэрвээ бактер бүрийн төрлийг үргэлж тодорхойлох боломжтой бол "$YES$" (хашилтгүйгээр) гэж хэвлэ. Бусад тохиолдолд "$NO$" (хашилтгүйгээр) гэж хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
2
(?^?)
Гаралт
NO
Оролт
10
?
Гаралт
YES
Оролт
2
((?^?)&?)
Гаралт
YES
Сэтгэгдлүүдийг ачааллаж байна...