Thảo luậnSnackDown Online Qualifier 2017 - Snake Procession

**MrKen** · 21.05.2017 / 14:50

Lễ hội rắn hàng năm là dịp mà tất cả những con rắn của vương quốc đã tập hợp và tham gia diễu hành. Chef được giao nhiệm vụ là đón các con rắn, chính vì vậy anh quyết định theo dõi tất cả những con rắn này. Khi anh ấy thấy một con rắn lần đầu tiên, đó sẽ là đầu con rắn và sẽ được đánh dấu “H”. Những con rắn khá dài và khi anh ấy nhìn thấy một con rắn lần cuối anh ấy kí hiệu là ‘T’ – là đuôi của con rắn đó. Khi con rắn đang chuyển động qua Chef, hoặc giữa một con rắn và con rắn sau, anh ta đánh những dấu ‘.’.

Do các con rắn chỉ đi theo một thứ tự nên báo cáo của Chef có thể là: "..H..T...HTH....T.", hoặc "...", hoặc "HT", còn đây là những báo cáo sai "T...H..H.T", "H..T..H", "H..H..T..T" (xem thêm phần giải thích phía dưới).

Một con rắn sẽ được biểu thị bằng một chữ ‘H’ theo sau đó là một vài (có thể không có) kí tự ‘.’ và sau đó là một chữ ‘T’. Một báo cáp hợp lệ khi bắt đầu với một chuỗi các ký tự ‘.’ (chiều dài có thể bằng 0) và sau đó là các con rắn (có thể là không có con rắn nào) mà giữa chúng có một vài dấu ‘.’, báo cáo kết thúc bằng một vài dấu ‘.’ (có thể là không có)

Lúc này, Chef đang sau xỉn sau bữa liên hoan và rất buồn ngủ. Do đó báo cáo có thể sai sót. Hãy giúp anh ấy chỉ ra xem báo cáo của mình có hợp lệ không.

Dữ liệu vào

- Dòng đầu tiên của dữ liệu vào chứa một số nguyên R – số báo cáo cần kiểm tra. Mỗi báo cáo được miêu tả như sau:

- Dòng đầu tiên của mỗi báo cáo chứa một số nguyên L – chiều dài của báo cáo.

- Dòng thứ hai của mỗi báo cáo chứa một chuỗi có độ dài L. Chuỗi này chỉ chứa các kí tự '.', 'H' và 'T'.

Dữ liệu ra

- Ở mỗi báo cáo, in ra "Valid" hoặc "Invalid" tương ứng khi báo cáo hợp lệ hoặc báo cáo không hợp lệ.

Ràng buộc

- 1 ≤ R ≤ 500

- 1 ≤ độ dài mỗi báo cáo ≤ 500

Vı́du:

Input

TEXT

6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..H

Output

TEXT

Valid
Valid
Invalid
Valid
Invalid
Invalid

Giải thích

"H..H..T..T" là không hợp lệ vì con rắn thứ hai bắt đầu trước khi con rắn thứ nhất di chuyển xong, điều này trái quy luật

".T...H..H.T" là không phù hợp vì ta có 'T' trước 'H'.

"H..T..H" là không phù hợp vì kí hiệu ‘H’ cuối cùng lại không có một ‘T’ tương ứng kèm theo sau. (nghĩa là ‘H’ không được đứng cuối).

______________________

Time Limit: 1 secs

Source Limit: 50000 Bytes

Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

**Cvhungs20** · 21.05.2017 / 16:50

CPP

#include <bits/stdc++.h>
using namespace std;
 
int n, k;
string s;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> k;
    cin >> s;
    int h = 0;
    bool ok = true;
    for (int j = 0; j < k; j++) {
      if (s[j] == 'H') {
        if (h == 1) {
          ok = false;
          break;
        } else h = 1;
      }
      if (s[j] == 'T') {
        if (h != 1) {
          ok = false;
          break;
        } else h = 2;
      }
      if (h == 1 && j == k - 1) {
        ok = false;
        break;
      }
    }
    if (!ok) cout << "Invalid\n";
    else cout << "Valid\n";
 
  }
}