Cờ nhà ga
Đề bài
Mô tả
Trên tuyến đường sắt từ ga đến ga , tàu lần lượt đi qua một dãy nhà ga, mỗi nhà ga treo một lá cờ có màu nhất định. Dãy màu cờ này được cho bởi xâu gồm các chữ cái Latin thường: mỗi chữ cái ứng với một màu, hai chữ cái khác nhau ứng với hai màu khác nhau. Khi đi theo chiều ngược lại (từ về ), tàu đi qua đúng các nhà ga đó nhưng theo thứ tự đảo ngược.
Trong một chuyến đi, Peter tỉnh dậy hai lần và ghi lại màu cờ của các nhà ga liên tiếp mà cậu nhìn thấy: lần thứ nhất được xâu , lần thứ hai được xâu . Vì tàu chạy liên tục nên mỗi nhà ga chỉ được nhìn thấy đúng một lần, và toàn bộ lần quan sát thứ hai diễn ra sau lần quan sát thứ nhất.
Nói cách khác, Peter có thể nhìn thấy hai xâu và trên một dãy màu cờ khi và chỉ khi tồn tại hai vị trí sao cho là xâu con liên tiếp của bắt đầu tại , là xâu con liên tiếp của bắt đầu tại , và (hai đoạn không giao nhau và nằm hoàn toàn sau ).
Hãy xác định Peter có thể quan sát được hai xâu đó khi đi theo chiều nào.
Dữ liệu vào
- Dòng thứ nhất chứa xâu gồm các chữ cái Latin thường: dãy màu cờ theo chiều từ đến .
- Dòng thứ hai chứa xâu .
- Dòng thứ ba chứa xâu .
Dữ liệu ra
In ra đúng một trong bốn từ:
- forward: chỉ có thể quan sát được khi đi từ đến ;
- backward: chỉ có thể quan sát được khi đi từ về ;
- both: quan sát được theo cả hai chiều;
- fantasy: không thể quan sát được theo chiều nào.
Ràng buộc
- Cả ba xâu chỉ gồm các chữ cái Latin thường.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| atob a b |
forward | Theo chiều thuận, a ở vị trí 1 và b ở vị trí 4, hai đoạn rời nhau. Theo chiều ngược, dãy là bota, xâu a nằm ở cuối nên không còn chỗ cho b phía sau. |
| aaacaaa aca aa |
both | Theo chiều thuận, aca nằm ở vị trí 3..5, sau đó aa nằm ở vị trí 6..7. Xâu đảo ngược cũng là aaacaaa nên kết quả tương tự. |
| ba a b |
backward | Hai màu đều xuất hiện nhưng theo chiều thuận thì b đứng trước a, không đúng thứ tự quan sát. Đảo ngược thành ab thì hợp lệ. |
Bình luận