Josif_tepe

Untitled

Jan 21st, 2026
22
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. const int maxn = 105;
  5. string s[maxn];
  6. int n;
  7.  
  8. int to_int(string & S) {
  9.     int res = 0;
  10.     for(int i = 0; i < (int) S.size(); i++) {
  11.         res = (res * 10) + (S[i] - '0');
  12.     }
  13.    
  14.     return res;
  15. }
  16.  
  17. int dp[maxn];
  18. int rec(int at) {
  19.     if(at >= n) {
  20.         return 1;
  21.     }
  22.     if(at == n - 1 and s[at] == "N") {
  23.         return 1;
  24.     }
  25.     if(dp[at] != -1) {
  26.         return dp[at];
  27.     }
  28.    
  29.     int res = 0;
  30.    
  31.     if(s[at] == "N") {
  32.         int num = -1;
  33.         int cnt = 0;
  34.         for(int i = at; i < n; i++) {
  35.             if(s[i] != "N") {
  36.                 if(num == -1) {
  37.                     num = to_int(s[i]);
  38.                 }
  39.             }
  40.            
  41.             if(s[i] == "N" and num == -1) {
  42.                 res += rec(i + 1);
  43.             }
  44.            
  45.             if(s[i] != "N" and num != to_int(s[i])) {
  46.                 break;
  47.             }
  48.             cnt++;
  49.            
  50.             if(cnt == num) {
  51.                 res += rec(i + 1);
  52.             }
  53.         }
  54.     }
  55.     else {
  56.         int cnt = 0;
  57.         int num = -1;
  58.         for(int i = at; i < n; i++) {
  59.             if(s[i] != "N" and num == -1) {
  60.                 num = to_int(s[i]);
  61.             }
  62.            
  63.             if(s[i] != "N" and num != to_int(s[i])) {
  64.                 break;
  65.             }
  66.            
  67.             cnt++;
  68.             if(cnt == num) {
  69.                 res += rec(i + 1);
  70.             }
  71.         }
  72.     }
  73.    
  74.     dp[at] = res;
  75.     return dp[at];
  76. }
  77. int main() {
  78.     memset(dp, -1, sizeof dp);
  79.     cin >> n;
  80.    
  81.     int cnt = 0;
  82.     for(int i = 0; i < n; i++) {
  83.         cin >> s[i];
  84.         if(s[i] == "N") {
  85.             cnt++;
  86.         }
  87.     }
  88.    
  89.     if(cnt == n) {
  90.         cout << "NE" << endl;
  91.     }
  92.     else if(rec(0) <= 1) {
  93.         cout << "DA" << endl;
  94.     }
  95.     else {
  96.         cout << "NE" << endl;
  97.     }
  98.     return 0;
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment