OCC '19 S3 - NAN Language

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

In Computer Science, NAN stands for not a number, that can be interpreted as a value that is undefined. bruce developed a new language, named NAN language. There are two types of words in NAN language: A-word and B-word.

Every word that satisfies the following rules is an A-word.

  • A single letter N is an A-word
  • Given an A-word, replacing any letter N with NAN or NA will generate a new A-word

Every word that satisfies the following rules is a B-word.

  • A single letter N is a B-word
  • Given a B-word, replacing any letter N with NAN or NA or AN will generate a new B-word

Based on the above rules, can you write a program to check if a given word is an A-word or a B-word in NAN language?

Constraints

For all subtasks:

1 \le |S| \le 10^6

T \le 10

Subtask 1 [17%]

|S| \le 40

Subtask 2 [65%]

|S| \le 2\,000

Input Specification

The first line contains an integer T, the number of test cases.

Each of the following T lines contains a string S, only consisting of letters N and A.

Output Specification

Output T lines. Each line contains two integers a and b. If the word is an A-word, a=1; otherwise, a=0. If the word is a B-word, b=1; otherwise, b=0.

Sample Input

4
NAN
ANN
ANAN
NANA

Sample Output

1 1
0 0
0 1
1 1

Comments

There are no comments at the moment.