This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
母音が$3$つ連続，または子音が$5$つ連続する場合はその文字列は$ugly$である．$nice$とは$ugly$ではない文字列の事を言う．'?‘はどの文字列にも変更することができる．$nice$にも$ugly$である場合は$42$を，そうではに場合はその文字列がどちらかを返す．
$$
dp[i][j][k][0] := i番目までに母音がj文字連続，子音がk文字連続して，未だuglyでない\\
dp[i][j][k][1] := i番目までに母音がj文字連続，子音がk文字連続して，既にugly
$$
として動的計画法．はてなの場合は，母音にするか子音にするか選べるので，どちらにも遷移する．後は今見ている文字通りに遷移する．母音が$3$つ連続，または子音が$5$つ連続がどこかでしていた場合，$ugly$になる可能性がある．その中で最後まで$ugly$にならなかったものがあれば，双方になり得るので$42$とする．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
bool vowels ( char c ) {
if ( c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' ) return true ;
return false ;
}
bool dp [ 55 ][ 55 ][ 55 ][ 2 ];
class NiceOrUgly {
public :
string describe ( string s ) {
memset ( dp , 0 , sizeof ( dp ));
dp [ 0 ][ 0 ][ 0 ][ 0 ] = true ;
rep ( i , s . size ()) {
rep ( j , 3 ) {
rep ( k , 5 ) {
rep ( l , 2 ) {
if ( dp [ i ][ j ][ k ][ l ]) {
if ( s [ i ] == '?' ) {
if ( j + 1 == 3 ) {
dp [ i + 1 ][ j + 1 ][ 0 ][ 1 ] = true ;
} else {
dp [ i + 1 ][ j + 1 ][ 0 ][ 0 ] = true ;
}
if ( k + 1 == 5 ) {
dp [ i + 1 ][ 0 ][ k + 1 ][ 1 ] = true ;
} else {
dp [ i + 1 ][ 0 ][ k + 1 ][ 0 ] = true ;
}
} else {
if ( vowels ( s [ i ])) {
if ( j + 1 == 3 ) {
dp [ i + 1 ][ j + 1 ][ 0 ][ 1 ] = true ;
} else {
dp [ i + 1 ][ j + 1 ][ 0 ][ 0 ] = true ;
}
} else {
if ( k + 1 == 5 ) {
dp [ i + 1 ][ 0 ][ k + 1 ][ 1 ] = true ;
} else {
dp [ i + 1 ][ 0 ][ k + 1 ][ 0 ] = true ;
}
}
}
}
}
}
}
}
bool flag = false ;
rep ( i , s . size () + 1 ) {
rep ( j , 4 ) {
rep ( k , 6 ) {
flag |= dp [ i ][ j ][ k ][ 1 ];
}
}
}
if ( flag ) {
bool check = false ;
rep ( j , 4 ) {
rep ( k , 6 ) {
check |= dp [ s . size ()][ j ][ k ][ 0 ];
}
}
if ( check ) return "42" ;
return "UGLY" ;
}
else return "NICE" ;
}
};