A robot is placed at the origin of a 2D coordinate plane (.e. position (0,0)). The...

Transcribed Image Text:

A robot is placed at the origin of a 2D coordinate plane (.e. position (0,0)). The robot is given a string S containing characters in (N. E. S. W) as its instructions. For each character from the beginning of the string. the robot has to move 1 unit to the following direction: . If the character is 1, the robot has to move 1 unit to the positive -axis direction. . If the character is E, the robot has to move 1 unit to the positive z-axis direction. . If the character is 5, the robot has to move 1 unit to the negative -axis direction. . If the character is w, the robot has to move 1 unit to the negative -axis direction. You do not know the string S. However, you know another string P that is an anagram of S (ie. P has the same number of N, E., S, w characters as S). You also have M data points: T.X₁ and ₁. For all , you know that the robot is at position (X,Y) after moving exactly 7, units. You want to know the number of possible string S that satisfies all the information you know. GUIDES: USE C PROGRAMMING LANGUAGE Input Input begins with a line containing two integers: NM (1≤M≤N≤ 400000) representing the number of characters in P and the number of data points, respectively. The next line contains a string P containing N characters in the set (N.E.S.W). The next lines each contains three integers: T, X, Y, (1 ≤ T ≤N; -T.≤X..Y. ST.) representing the data points. It is guaranteed that 7. A robot is placed at the origin of a 2D coordinate plane (.e. position (0,0)). The robot is given a string S containing characters in (N. E. S. W) as its instructions. For each character from the beginning of the string. the robot has to move 1 unit to the following direction: . If the character is 1, the robot has to move 1 unit to the positive -axis direction. . If the character is E, the robot has to move 1 unit to the positive z-axis direction. . If the character is 5, the robot has to move 1 unit to the negative -axis direction. . If the character is w, the robot has to move 1 unit to the negative -axis direction. You do not know the string S. However, you know another string P that is an anagram of S (ie. P has the same number of N, E., S, w characters as S). You also have M data points: T.X₁ and ₁. For all , you know that the robot is at position (X,Y) after moving exactly 7, units. You want to know the number of possible string S that satisfies all the information you know. GUIDES: USE C PROGRAMMING LANGUAGE Input Input begins with a line containing two integers: NM (1≤M≤N≤ 400000) representing the number of characters in P and the number of data points, respectively. The next line contains a string P containing N characters in the set (N.E.S.W). The next lines each contains three integers: T, X, Y, (1 ≤ T ≤N; -T.≤X..Y. ST.) representing the data points. It is guaranteed that 7.

Answer rating: 100% (QA)

To solve this problem we can iterate through each character in string P and check if it satisfies th... View the full answer