Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- using namespace std;
- const int maxn = 105;
- string s[maxn];
- int n;
- int to_int(string & S) {
- int res = 0;
- for(int i = 0; i < (int) S.size(); i++) {
- res = (res * 10) + (S[i] - '0');
- }
- return res;
- }
- int dp[maxn];
- int rec(int at) {
- if(at >= n) {
- return 1;
- }
- if(at == n - 1 and s[at] == "N") {
- return 1;
- }
- if(dp[at] != -1) {
- return dp[at];
- }
- int res = 0;
- if(s[at] == "N") {
- int num = -1;
- int cnt = 0;
- for(int i = at; i < n; i++) {
- if(s[i] != "N") {
- if(num == -1) {
- num = to_int(s[i]);
- }
- }
- if(s[i] == "N" and num == -1) {
- res += rec(i + 1);
- }
- if(s[i] != "N" and num != to_int(s[i])) {
- break;
- }
- cnt++;
- if(cnt == num) {
- res += rec(i + 1);
- }
- }
- }
- else {
- int cnt = 0;
- int num = -1;
- for(int i = at; i < n; i++) {
- if(s[i] != "N" and num == -1) {
- num = to_int(s[i]);
- }
- if(s[i] != "N" and num != to_int(s[i])) {
- break;
- }
- cnt++;
- if(cnt == num) {
- res += rec(i + 1);
- }
- }
- }
- dp[at] = res;
- return dp[at];
- }
- int main() {
- memset(dp, -1, sizeof dp);
- cin >> n;
- int cnt = 0;
- for(int i = 0; i < n; i++) {
- cin >> s[i];
- if(s[i] == "N") {
- cnt++;
- }
- }
- if(cnt == n) {
- cout << "NE" << endl;
- }
- else if(rec(0) <= 1) {
- cout << "DA" << endl;
- }
- else {
- cout << "NE" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment