uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1146

 

과제로 나와서 간단하게 설명해둬야겠다

 

해석만 할줄 알면 쉽게 풀 수 있는 문제다

 

부족한 영어실력이지만 간단히 해석해보면

표준 카드덱은 52장, 13개의 값을 각각 4종류로 가지고 있다

값은 2,3,4,5,6,7,8,9,10,잭,퀸,킹,에이스 로 이루어져있다

종류(suit)는 클로버, 다이아, 하트, 스페이드 로 이루어져있다

카드덱은 값과 종류로 서로 식별가능하며 <값, 종류> 의 형태로 이루어진다

예를 들어 king of spades, 9of hearts 가 있다

관례적으로 기본 덱은 종류(suit) -> 알파벳 순서, 값 -> 위의 주어진 형태 순으로 정렬되어있다

중간부분은 딱히 필요없다 

문제에서 요구하는 부분은 다음과 같다

 

1. 테스트케이스가 주어진다

2. 카드덱을 섞을 수 있는 n가지 방법이 주어진다.

3. 1~52의 카드가 중복없이 n번 주어진다 ( 52개당 한 세트?에 속한다고 보면된다)

4. 덱을 섞을 수가 1~n 사이의 수로 \n이 나오기전까지 계속 주어진다

5. 각 주어진 세트 번호로 현재 덱을 섞는다

6. \n으로 더이상 섞지 않는다면 현재 덱을 출력한다

7. 반복

 

'algorithm > uva' 카테고리의 다른 글

uva 11994번 Happy Painting!  (0) 2020.04.06
uva 384번 Slurpys, BOJ 14906번 스러피  (0) 2020.03.31
uva 10150번 Doublets  (0) 2020.03.27
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 10010번 Where's Waldorf?  (0) 2020.03.23

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3145

 

espa에서는 괜찮은데 uva에서 제출해봤는데 TLE가 뜬다..

아무래도 소스가 lct나 splay를 쓰지않은 탐색코드이고 espa의 tc가 uva보다 약하기 때문인 것 같은데

lct ? splay를 공부해서 제출해봐야겠다.

 

지금 소스는 espa에서는 빠르게 통과되는 코드로

type2, 3번의 시간을 최대한 단축시키기 위해서

height 높이 개념을 이용했다.

 

LCA를 알면 좀더 빠르게 해결할 수 있다는데 뭐 통과는 되니까 일단 올려놓고

고급 자료구조를 공부한 후에 다시 적용해봐야겠다.

 

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
struct NODE {
    int root = -1;
    int pn = -1;
    int pn_color = -1;
    int height = -1;
    struct pii {
        int num;
        int color;
    };
    vector<pii> other;
}node[50001];
 
bool visit[50001];
bool color_arr[31];
int inn, inm;
int join = 0;
int answer_edge, answer_color;
 
int check_tree(int x) {
    answer_edge++;
    if (color_arr[node[x].pn_color] == false) {
        answer_color++;
        color_arr[node[x].pn_color] = true;
    }
 
    return node[x].pn;
}
 
void make_height2(int x, int y) {
    memset(color_arr, 0, sizeof(color_arr));
    while (node[x].height != node[y].height) {
        if (node[x].height > node[y].height) x = check_tree(x);
        else y = check_tree(y);
    }
    if (x != y) {
        while (x != y) {
            x = check_tree(x);
            y = check_tree(y);
        }
    }
}
 
int color_change(int x, int c) {
    for (int i = 0; i < node[node[x].pn].other.size(); i++) {
        if (node[node[x].pn].other[i].num == x) {
            node[node[x].pn].other[i].color = c;
            break;
        }
    }
    node[x].pn_color = c;
    return node[x].pn;
}
 
void make_height(int x, int y, int c) {
    while (node[x].height != node[y].height) {
        if (node[x].height > node[y].height) x = color_change(x, c);
        else y = color_change(y, c);
    }
 
    if (x != y) {
        while (x != y) {
            x = color_change(x, c);
            y = color_change(y, c);
        }
    }
}
 
void delete_node(int x, int y) {
    for (int i = 0; i < node[x].other.size(); i++) {
        if (node[x].other[i].num == y) {
            node[x].other.erase(node[x].other.begin() + i, node[x].other.begin() + i + 1);
            break;
        }
    }
}
 
void change_father(int x, int y, int c) {
    if (node[x].root != x)    delete_node(node[x].pn, x);
 
    node[y].other.push_back({ x, c });
    node[x].pn_color = c;
 
    queue<pair<pair<int,int>,int> > q;
    q.push({ {x,y},node[y].height });
 
    while (!q.empty()) {
        int temp = q.front().first.first;
        int p = q.front().first.second;
        int h = q.front().second;
        q.pop();
 
        node[temp].root = node[y].root;
        node[temp].pn = p;
        node[temp].height = h + 1;
        for (int i = 0; i < node[temp].other.size(); i++) {
            q.push({{ node[temp].other[i].num, temp}, h+1});
        }
    }
}
 
bool check_father(int x, int y) {
    if (x == y) return true;
    if (node[x].root == x) return false;
    return check_father(node[x].pn, y);
}
 
void insert_node(int num, int parent, int color) {
    if (parent == 0) { // root
        visit[num] = true;
        node[num].height = 0;
        node[num].pn = num;
        node[num].root = num;
        join++;
        return;
    }
 
    if (node[parent].root == -1) return;
    if (visit[num]) {
        join++;
        return;
    }
 
    visit[num] = true;
    node[num].root = node[parent].root;
    node[num].pn = parent;
    node[num].pn_color = color;
    node[num].height = node[parent].height + 1;
    node[parent].other.push_back({ num, color });
    join++;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    vector<pair<pair<int, int>, int> > in;
    cin >> inn >> inm;
 
    for (int i = 1; i <= inn; i++) {
        int num;
        cin >> num;
        in.push_back({ {num,0},i });
    }
    for (int i = 0; i < inn; i++) {
        int col;
        cin >> col;
        in[i].first.second = col;
    }
    sort(in.begin(), in.end());
 
    while (join != inn) {
        join = 0;
        for (int i = 0; i < inn; i++)
            insert_node(in[i].second, in[i].first.first, in[i].first.second);
    }
    for (int i = 1; i <= inn; i++) visit[i] = 0;
 
    while (inm--) {
        int type, x, y, c;
        cin >> type >> x >> y;
        if (type == 1) {
            cin >> c;
            if (x == y) continue;
            if (node[x].root != node[y].root) change_father(x, y, c);
            else {
                if (!check_father(y, x)) change_father(x, y, c);
            }
        }
        if (type == 2) {
            cin >> c;
            if (x == y || node[x].root != node[y].root) continue;
            make_height(x, y, c);
        }
        if (type == 3) {
            if (x == y || node[x].root != node[y].root)
                cout << "0 0\n";
            else {
                answer_edge = answer_color = 0;
                make_height2(x, y);
                cout << answer_edge << " " << answer_color << "\n";
            }
        }
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > uva' 카테고리의 다른 글

uva 10205번 stack 'em up  (0) 2020.04.27
uva 384번 Slurpys, BOJ 14906번 스러피  (0) 2020.03.31
uva 10150번 Doublets  (0) 2020.03.27
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 10010번 Where's Waldorf?  (0) 2020.03.23

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=320

 

BOJ : https://www.acmicpc.net/problem/14906

 

문제를 보면서 그대로 구현했는데

소스가 좀 더러울 수 있지만 최대한 정리해봤습니다.

 

재귀를 이용하여 문제를 해결했습니다.

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
#include <iostream>
#include <string>
using namespace std;
 
int slumps(string str, int idx, bool si) {
    if (idx >= str.size()) return -1;
    if (si) {
        if (!(str[idx] == 'D' || str[idx] == 'E')) return -1;
        if (idx + 1 < str.size() && str[idx + 1] == 'F') return slumps(str, idx + 2, false);
    }
    else {
        if (str[idx] == 'F') return slumps(str, idx + 1, false);
        if (str[idx] == 'G' && str[idx - 1] == 'F') return idx;
        if (str[idx] == 'D' || str[idx] == 'E') return slumps(str, idx, true);
    }
    return -1;
}
 
int slimps(string str, int idx, bool si) {
    if (idx >= str.size()) return -1;
    if (si) {
        if (str[idx] != 'A') return -1;
        if (idx + 1 < str.size()) {
            if (str[idx + 1] == 'H') return idx + 1;
            else return slimps(str, idx + 1, false);
        }
    }
    else {
        if (str[idx] == 'B') {
            int res = slimps(str, idx + 1, true);
            if (res != -1 && str[res + 1] == 'C') return res + 1;
        }
        if (str[idx] == 'D' || str[idx] == 'E') {
            int res = slumps(str, idx, true);
            if (res != -1 && str[res + 1] == 'C') return res + 1;
        }
    }
    return -1;
}
 
bool solve(string str) {
    int idx = slimps(str, 0, true);
    if (idx == -1) return false;
    idx = slumps(str, idx + 1, true);
    return idx == str.size() - 1 ? true : false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cout << "SLURPYS OUTPUT\n";
    int tc;
    cin >> tc;
    while (tc--) {
        string str;
        cin >> str;
        if (solve(str)) cout << "YES\n";
        else cout << "NO\n";
    }
    cout << "END OF OUTPUT";
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > uva' 카테고리의 다른 글

uva 10205번 stack 'em up  (0) 2020.04.27
uva 11994번 Happy Painting!  (0) 2020.04.06
uva 10150번 Doublets  (0) 2020.03.27
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 10010번 Where's Waldorf?  (0) 2020.03.23

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1091

 

doublets 의 의미는 한 쌍의 단어를 비교했을 떄 알파벳이 1개만 다른 단어의 쌍을 말한다

[aaa, aab] 같은 경우가 됨

 

문제풀이는 다음과 같다

1. 단어의 사전이 개행이 나오기 전까지 주어진다

2. 단어의 한 쌍이 주어진다

3. 주어진 한 쌍 중에서 첫번째 단어에서 두번째 단어로 가는 가장 짧은 경로를 찾는다

4. EOF가 아니면 2번부터 다시 반복한다

 

일단 최단경로에 관한 문제이기 때문에 bfs로 접근했다

탐색과정은 다음과 같다

1. bfs탐색은 현재 단어를 기준으로 방문하지 않은 doublets string을 찾았다.

2. end string을 발견하면 bfs 종료 후 탐색해왔던 string을 찾는다. 

 

아 참고로 문제 인풋이 좀 더러운 문제였다

사전이 주어질 때 단어 뒤에 ' ' 형태의 공백이 같이 딸려오는 인풋이 있어서 pop_back() 을 통해 정확한 단어를 삽입했다

 

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
using namespace std;
 
struct pii {
    string my_str;
    int my_cnt;
    int my_num;
};
 
vector<string> dict;
int arr[30000];
 
bool check(string a, string b) {
    if (a.size() != b.size()) return false;
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) cnt++;
        if (cnt > 1) return false;
    }
    if (cnt == 1) return true;
    return false;
}
 
vector<string> solve(string start, string end, int pin) {
    set<string> visit;
    queue<pii> q;
    vector<pair<string,int> > btr;
    vector<string> answer;
    int last_pin;
    bool sol = false;
 
    q.push({ start,0,pin});
    while (!q.empty()) {
        string str = q.front().my_str;
        int cnt = q.front().my_cnt;
        int my_num = q.front().my_num;
        q.pop();
 
        if (str.compare(end) == 0) {
            sol = true;
            last_pin = my_num;
            break;
        }
 
        int visit_size = visit.size();
        visit.insert(str);
        if (visit_size == visit.size()) continue;
 
        for (int i = 0; i < dict.size(); i++) {
            if (check(str, dict[i])) {
                visit_size = visit.size();
                visit.insert(dict[i]);
                if (visit_size != visit.size()) {
                    visit.erase(dict[i]);
                    q.push({ dict[i], cnt + 1, i});
                    if (arr[i] == -1) arr[i] = my_num;
                }
            }
        }
    }
 
    if (!sol) return answer;
    else {
        answer.push_back(end);
        while (1) {
            string str = dict[arr[last_pin]];
            answer.push_back(str);
            if (str.compare(start) == 0) break;
            last_pin = arr[last_pin];
        }
        return answer;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    string str, start, end;
    while (getline(cin, str), str != "") {
        while (1) {
            if (str[str.size() - 1] == ' ') str.pop_back();
            else break;
        }
        dict.push_back(str);
    }
 
    while (cin >> start >> end) {
        memset(arr, -1, sizeof(arr));
 
        if (start.size() != end.size()) {
            cout << "No solution.\n\n";
            continue;
        }
        if (start.compare(end) == 0) {
            cout << end << "\n" << end << "\n\n";
            continue;
        }
 
        int pin;
        for (int i = 0; i < dict.size(); i++) {
            if (start.compare(dict[i]) == 0) {
                pin = i;
                break;
            }
        }
        vector<string> answer = solve(start, end, pin);
 
        if (answer.size() == 0) cout << "No solution.\n";
        else for (int i = answer.size() - 1; i >= 0; i--) cout << answer[i] << "\n";
        cout << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > uva' 카테고리의 다른 글

uva 11994번 Happy Painting!  (0) 2020.04.06
uva 384번 Slurpys, BOJ 14906번 스러피  (0) 2020.03.31
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 10010번 Where's Waldorf?  (0) 2020.03.23
uva 679 - Dropping Balls  (0) 2020.03.19

+ Recent posts

티스토리툴바