trang chủ / bài tập / trainflag

Cờ nhà ga

Đề bài

Mô tả

Trên tuyến đường sắt từ ga A đến ga B, 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 s 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ừ B về A), 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 a, lần thứ hai được xâu b. 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 ab trên một dãy màu cờ t khi và chỉ khi tồn tại hai vị trí i,j sao cho a là xâu con liên tiếp của t bắt đầu tại i, b là xâu con liên tiếp của t bắt đầu tại j, và ji+|a| (hai đoạn không giao nhau và b nằm hoàn toàn sau a).

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 s gồm các chữ cái Latin thường: dãy màu cờ theo chiều từ A đến B.
  • Dòng thứ hai chứa xâu a.
  • Dòng thứ ba chứa xâu b.

Dữ liệu ra

In ra đúng một trong bốn từ:

  • forward: chỉ có thể quan sát được khi đi từ A đến B;
  • backward: chỉ có thể quan sát được khi đi từ B về A;
  • 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

  • 1|s|105
  • 1|a|,|b|100
  • 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0