SRM 327, Div 1, Easy
Contest/TopCoder 2010/08/13 22:19[Easy - NiceOrUgly]
SRM 당시 많은 사람들이 낚였다고 해서 풀어봤다. - 그 사실을 알고 풀어서 그런지 몰라도 NFA 돌리면 낚일만한게 없는데 조심해서 풀게 되더라. 다 해놓고 소스코드 정리까지 해서 262.59로 submit. 문제 알고 풀었으니 빠른건 아니다. systest 통과.
#include <queue>
using std::string;
using std::queue;
struct in_que
{
int p, v, c;
};
int visited[100][10][10];
class NiceOrUgly
{
public:
string describe(string s)
{
queue<in_que> q;
in_que c, d;
bool nice = false, ugly = false;
c.p = c.v = c.c = 0;
q.push(c);
int n = s.length();
while (!q.empty())
{
c = q.front(); q.pop();
if (c.p == n) continue;
d.p = c.p + 1;
bool nextVowel = false, nextConsonant = false;
if (s[c.p] == '?')
nextVowel = nextConsonant = true;
else if (s[c.p] == 'A' || s[c.p] == 'E' || s[c.p] == 'I' || s[c.p] == 'O' || s[c.p] == 'U')
nextVowel = true;
else
nextConsonant = true;
if (nextVowel)
{
d.v = c.v + 1; d.c = 0;
if (d.v == 3)
{
ugly = true;
}
else if (visited[d.p][d.v][d.c] == 0)
{
visited[d.p][d.v][d.c] = 1;
q.push(d);
}
}
if (nextConsonant)
{
d.v = 0; d.c = c.c + 1;
if (d.c == 5)
{
ugly = true;
}
else if (visited[d.p][d.v][d.c] == 0)
{
visited[d.p][d.v][d.c] = 1;
q.push(d);
}
}
}
nice = (visited[n][0][0] || visited[n][1][0] || visited[n][2][0] || visited[n][0][1] || visited[n][0][2] || visited[n][0][3] || visited[n][0][4]);
if (nice && ugly)
return "42";
else if (ugly)
return "UGLY";
else
return "NICE";
}
};
덧 - 그건 그렇고, 블루스크린과 함께 한 주말 때문에 윈도우까지 싹 민 상태라서 java가 없어서 oracle 홈페이지에서 java 다운받으려고 했는데, 다운 링크가 깨져서 다운이 안된다. oracle은 sun 인수하고 나서 욕먹을 짓만 골라서 하는듯. -ㅅ-
