B. Дагавар бүтцүүд

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

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

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

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

Аварга Бизон зөвхөн бизон үхэр биш. Тэр мөн "Бизонууд" багийн хайртай Бизон.

Тэмцээн дээр "Бизонуудад" дараах бодлого байсан: "Танд хоёр ялгаатай үг $s$ ба $t$ (Англи цагаан толгойн үсгүүдээс бүрдсэн тэмдэгт мөрүүд) өгөгдсөн". Та $s$ үгийг $t$ үгрүү хөрвүүлэх хэрэгтэй. Залуусд энэ ажил хялбархан харагдсан учир нь тэд дагавар өгөгдлийн бүтцүүдийг сайн мэднэ. Ахлах Бизон автомат дагаварт дуртай. Үүнийг тэмдэгт мөрд нэг удаа хэрэгжүүлэхэд Ахлах Бизон уг тэмдэгт мөрөөс дурын нэг тэмдэгтийг устгаж чадна. Дунд Бизон дагавар массивыг сайн мэднэ. Үүнийг тэмдэгт мөрд нэг удаа хэрэгжүүлснээр тэр тэмдэгт мөрийн дурын хоёр тэмдэгтийг хооронд нь сольж чадна. Залуус дагавар модны тухай юу ч мэдэхгүй боловч энэ нь тэдэнд илүү ихийг хийхэд туслах болно.

Аварга Бизон "Бизонууд" энэ бодлогыг шийдэж чадах болов уу гэж бодож байна. Шийдэл хоёр өгөгдлийн бүтцүүдийг шаардахгүй байж болох юм. Залуус бодлогыг шийдэж чадах эсэхийг олох ба хэрвээ тэд чадвал хэрхэн хийж чадсан бэ? Тэд үүнийг зөвхөн автомат дагавар эсвэл зөвхөн дагавар массив ашиглан хийж чадах уу эсвэл тэдэнд хоёр бүтэц хоёулаа хэрэгтэй юу? Ямар ч бүтэц хязгааргүй олон удаа ашиглагдаж болох ба бүтцүүд дурын дарааллаар ашиглагдаж болно.

Оролт

Эхний мөрөнд хоосон биш үг $s$ байна. Хоёр дахь мөрөнд хоосон биш үг $t$ байна. $s$ болон $t$ үгүүд ялгаатай байна. Үг бүр зөвхөн Англи цагаан толгойн жижиг үсгүүдээс тогтоно. Үг бүр хамгийн ихдээ 100 үсэгтэй байна.

Гаралт

Бодлогын хариултыг нэг мөрөнд хэвлэ. Хэрвээ $s$ үг $t$ үгрүү дагавар массив болон автомат дагавар хоёуланг нь хэрэглээд ч хөрвөж чадахгүй бол "$need tree$" (хашилтгүйгээр) гэж хэвлэ. Хэрвээ бодлогыг шийдэхэд танд зөвхөн автомат дагавар хэрэгтэй бол "$automaton$" (хашилтгүйгээр) гэж хэвлэ. Хэрвээ бодлогыг шийдэхэд танд зөвхөн дагавар массив хэрэгтэй бол "$array$" (хашилтгүйгээр) гэж хэвлэ. Хэрвээ бодлогыг шийдэхэд танд хоёр бүтэц хоёулаа хэрэгтэй бол "$both$" (хашилтгүйгээр) гэж хэвлэ.

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

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

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

Оролт
automaton
tomat
Гаралт
automaton
Оролт
array
arary
Гаралт
array
Оролт
both
hot
Гаралт
both
Оролт
need
tree
Гаралт
need tree

Тэмдэглэл

Гурав дахь жишээн дээр дараах байдлаар шийдэж чадна: эхлээд "$both$"-г эхний тэмдэгтийг нь автомат дагавар ашиглан устгаж "$oth$" болгох ба тэгээд дагавар массивыг ашиглан хоёр удаа солих үйлдэл хийгээд "$hot$"-г гаргаж авч чадна.

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