UVa 12639 - Hexagonal Puzzle

Problem

每個六角形會有 1 ~ 6 的數字在每一條邊,可以旋轉六角形,但是相鄰的數字要相同。

請問是否可以拼出目標的形狀。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 2 3 4 5 6
1 3 6 5 2 4
1 4 2 5 6 3
1 5 2 3 6 4
1 6 2 4 3 5
1 6 2 4 5 3
1 6 5 3 2 4
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6

Sample Output

1
2
YES
NO

Solution

決定好中心,中心不需要旋轉,接著考慮外面繞一圈的接法。窮舉一下即可。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
struct Hex {
int v[6], m[7], rotate;
int read() {
for (int i = 0; i < 6; i++) {
if (scanf("%d", &v[i]) == 1);
else
return 0;
}
return 1;
}
void normal() {
int t[6], mnexp = 0;
for (int i = 0; i < 6; i++)
t[i] = v[i];
for (int i = 1; i < 6; i++)
if (t[i] == 1) mnexp = i;
for (int i = 0; i < 6; i++)
v[i] = t[(mnexp + i)%6];
for (int i = 0; i < 6; i++)
m[v[i]] = i;
}
int getPos(int x) {
return m[x];
}
int next() {
return v[(rotate+1)%6];
}
int prev() {
return v[(rotate+5)%6];
}
void println() {
for (int i = 0; i < 6; i++)
printf("%d ", v[(rotate+i)%6]);
puts("");
}
};
int used[7], path[7];
Hex h[7];
int dfs(int idx) {
if (idx == 7)
return 1;
// printf("%d\n", idx);
// for (int i = 0; i < idx; i++) {
// printf("%d : ", h[path[i]].rotate);
// h[path[i]].println();
// }
// puts("--");
// getchar();
if (idx == 0) {
for (int i = 0; i < 7; i++) {
if (used[i] == 0) {
used[i] = 1;
path[idx] = i, h[i].rotate = 0;
if (dfs(idx + 1)) return 1;
used[i] = 0;
}
}
} else {
if (idx == 1) {
for (int i = 0; i < 7; i++) {
if (used[i] == 0) {
used[i] = 1;
path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
if (dfs(idx + 1)) return 1;
used[i] = 0;
}
}
} else if (idx < 6) {
for (int i = 0; i < 7; i++) {
if (used[i] == 0) {
used[i] = 1;
path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
if (h[path[idx-1]].prev() == h[i].next())
if (dfs(idx + 1)) return 1;
used[i] = 0;
}
}
} else {
for (int i = 0; i < 7; i++) {
if (used[i] == 0) {
used[i] = 1;
path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
if (h[path[idx-1]].prev() == h[i].next() && h[path[1]].next() == h[i].prev())
if (dfs(idx + 1)) return 1;
used[i] = 0;
}
}
}
}
return 0;
}
int main() {
while (true) {
for (int i = 0; i < 7; i++) {
if (!h[i].read())
return 0;
h[i].normal();
}
memset(used, 0, sizeof(used));
int ret = dfs(0);
puts(ret ? "YES" : "NO");
}
return 0;
}
/*
*/
Read More +

UVa 11104 - Cousins

Problem

first cousin :如果兩個字串可以藉由移除不多於一半的字符,可以變成相同的字串。

ex. abcdefaxcyd 分別移除 (b, e, f)(x, y),就可以變成 acd

然而如果它們 string (A, B)要稱為 (n+1)th cousin,則存在一個媒介 C,A 和 C 是 first cousin 以及 B 和 C 是 nth cousin

Sample Input

1
2
3
4
5
6
7
8
a
b
abb
baa
abcdef
axcyd
0
0

Sample Output

1
2
3
2
2
1

Solution

這題看題看得很痛苦,也就是說找兩個字串最短的關係 (請無視長的)。

然而要如何找到最短的,思考一下絕對跟 LCS 有點關係,想了一整個早上仍然沒有結果,後來看了大神代碼回溯想法:

1
2
3
4
5
6
7
8
9
10
11
12
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.

仔細想想,這解法類似於貪心?而 LCS 存在的關係是起手用。增倍貪心,把不需要的地方直接填跟目標的內容。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
char a[128], b[128];
while (scanf("%s %s", a, b) == 2 && a[0] != '0') {
int dp[128][128] = {};
int la = strlen(a), lb = strlen(b);
for (int i = 0; i < la; i++)
for (int j = 0; j < lb; j++)
if (a[i] == b[j])
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
else
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
int lcs = dp[la][lb];
int ret = 1, len = lcs;
if (la > lb) swap(la, lb);
while (len + len < lb) {
len += la, la <<= 1;
ret++;
}
printf("%d\n", ret);
}
return 0;
}
/*
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.
*/
Read More +

UVa 10961 - Chasing After Don Giovanni

Problem

A 要追 B,結果 B 偽裝成 C,B 告訴 A,B 將會怎麼走並且沿路指導 A 該怎麼走,然而真正的 C 也會在地圖中某一個地方開始移動。

如果 A、C 相遇,則會發現 B 是偽裝的,給予兩個人的路線,請問 B 是否能安全抵達目的地,如果再目的地被抓到也相當於安全抵達,因為他已經抵達目的地。

假設 A、C 的移動速度相同。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
2 3
5 2
3
5 4
3 4
3 6
4
4 3
4 5
5 5
5 6
2 2
4 2
3
6 2
6 3
3 3
3
2 4
5 4
5 6

Sample Output

1
2
3
No
Yes

Solution

這一題與 11796 - Dog Distance 很類似。找兩個路線的最接近距離。

  • 题目大意:
    两条狗匀速分别沿着折线跑,已知同时出发,同时到达,问你求相差最大的距离 与相差的最小的距离之间的差值。
  • 解题思路:
    如果两只狗都走1条线段的话,根据相对运动的理论,可以把其中一只狗看成静止不动,另一只狗相对运动,且线路为线段,那么立刻转化为点到线段的距离的问题。
http://blog.csdn.net/a1061747415/article/details/38682243

而這一題檢查最近距離是否為 0 即可。特別 case 終點碰到的情況,此外測資中兩個路線的距離長貌似相同,因為討論區的有幾組不同長的測資,雖然以下代碼沒有通過,但是還是 AC。

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
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
// similar 11796 - Dog Distance
#define eps 1e-8
struct Pt {
double x, y;
Pt(double a = 0, double b = 0):
x(a), y(b) {}
bool operator<(const Pt &a) const {
if(fabs(x-a.x) > eps) return x < a.x;
return y < a.y;
}
bool operator==(const Pt &a) const {
return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
}
Pt operator+(const Pt &a) const {
return Pt(x + a.x, y + a.y);
}
Pt operator-(const Pt &a) const {
return Pt(x - a.x, y - a.y);
}
Pt operator/(const double val) const {
return Pt(x / val, y / val);
}
Pt operator*(const double val) const {
return Pt(x * val, y * val);
}
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
double distProjection(Pt as, Pt at, Pt s) {
double a, b, c;
a = at.y - as.y;
b = as.x - at.x;
c = - (a * as.x + b * as.y);
return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double distToSeg(Pt sa, Pt sb, Pt a) {
if(!(sa == sb) && between(sa, sb, a))
return distProjection(sa, sb, a);
return min(dist(sa, a), dist(sb, a));
}
int main() {
int testcase, cases = 0, A, B;
Pt DA[105], DB[105];
scanf("%d", &testcase);
while(testcase--) {
scanf("%lf %lf", &DB[0].x, &DB[0].y);
scanf("%lf %lf", &DA[0].x, &DA[0].y);
scanf("%d", &A);
for(int i = 1; i <= A; i++)
scanf("%lf %lf", &DA[i].x, &DA[i].y);
scanf("%d", &B);
for(int i = 1; i <= B; i++)
scanf("%lf %lf", &DB[i].x, &DB[i].y);
A++, B++;
double speed_a = 1, speed_b = 1;
int aIdx, bIdx;
double sa, sb, run;
Vector va, vb;
Pt apos = DA[0], bpos = DB[0];
aIdx = bIdx = 0;
double mxDist = 0, mnDist = 1e+30;
while(aIdx < A - 1 && bIdx < B - 1) {
sa = dist(DA[aIdx+1], apos);
sb = dist(DB[bIdx+1], bpos);
run = min(sa/speed_a, sb/speed_b); // run time
va = (DA[aIdx+1] - apos)/sa * run * speed_a;
vb = (DB[bIdx+1] - bpos)/sb * run * speed_b;
if (bpos + vb == DB[B - 1] && apos + va == DA[A - 1]) { // a route is safe even if the villagers meet Leporello at the destination.
mnDist = min(mnDist, dist(bpos, apos));
if (!(bpos == bpos+vb-va) && between(bpos, bpos+vb-va, apos) && !(apos == bpos+vb-va))
mnDist = min(mnDist, distProjection(bpos, bpos+vb-va, apos));
} else
mnDist = min(mnDist, distToSeg(bpos, bpos+vb-va, apos));
// mxDist = max(mxDist, dist(apos, bpos));
// mxDist = max(mxDist, dist(apos, bpos+vb-va));
apos = apos + va;
bpos = bpos + vb;
if(apos == DA[aIdx+1])
aIdx++;
if(bpos == DB[bIdx+1])
bIdx++;
}
if (cases++) puts("");
if (fabs(mnDist) < eps)
puts("No");
else
puts("Yes");
}
return 0;
}
/*
*/
Read More +

UVa 10867 - Cutting a Polygon

Problem

給一個簡單多邊形,接著詢問許多通過兩點的直線,與多邊形的交集長度為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
0 0

Sample Output

1
2
3
4
5
2.798
6.000
3.000
2.954
2.000

Solution

一開始以為是線段與簡單多邊形,後來才發現不太對勁,原來是直線與簡單多邊形。

事實上也很簡單,直接拿所有多邊形的線段進行嘗試,算出所有交點後,將其放置於直線上,會看得出很多線段,檢查線段中點是否在多邊形內部,如果是則將該線段的長度納於交集。

如果該線段位於簡單多邊形內,則保證其線段中點也一定在。

這一題鬼畜的地方在於測資的精準度,因為在多邊形邊界上也要算交集,死活地卡不過去,最後下了測資,看下才發現是多邊形端點是否在直線上,那裏必須特別判斷,靠很近就可以將其算為交點。

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-9
#define MAXN 131072
struct Pt {
double x, y;
Pt(double a = 0, double b = 0):
x(a), y(b) {}
Pt operator-(const Pt &a) const {
return Pt(x - a.x, y - a.y);
}
Pt operator+(const Pt &a) const {
return Pt(x + a.x, y + a.y);
}
Pt operator*(const double a) const {
return Pt(x * a, y * a);
}
bool operator==(const Pt &a) const {
return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
}
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps)
return x < a.x;
if (fabs(y - a.y) > eps)
return y < a.y;
return false;
}
double length() {
return hypot(x, y);
}
};
double dist(Pt a, Pt b) {
return (a-b).length();
}
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) > -eps && dot(c - b, a - b) > -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
if (cross(as, at, bs) * cross(as, at, bt) < -eps &&
cross(at, as, bs) * cross(at, as, bt) < -eps &&
cross(bs, bt, as) * cross(bs, bt, at) < -eps &&
cross(bt, bs, as) * cross(bt, bs, at) < -eps)
return 1;
return 0;
}
struct Seg {
Pt s, e;
double angle;
int label;
Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
angle = atan2(e.y - s.y, e.x - s.x);
}
bool operator<(const Seg &other) const {
if (fabs(angle - other.angle) > eps)
return angle > other.angle;
if (cross(other.s, other.e, s) > -eps)
return true;
return false;
}
};
Pt getIntersect(Seg a, Seg b) {
Pt u = a.s - b.s;
double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
return a.s + (a.e - a.s) * t;
}
int inPolygon(Pt p[], int n, Pt q) {
int i, j, cnt = 0;
for(i = 0, j = n-1; i < n; j = i++) {
if(onSeg(p[i], p[j], q))
return 1;
if(p[i].y > q.y != p[j].y > q.y &&
q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
cnt++;
}
return cnt&1;
}
double solve(Pt D[], int n, Pt s, Pt e) {
vector<Pt> p;
for (int i = 0, j = n - 1; i < n; j = i++) {
if (cross(s, e, D[i]) * cross(s, e, D[j]) < -eps) {
Pt t = getIntersect(Seg(D[i], D[j]), Seg(s, e));
p.push_back(t);
} else if (onSeg(s, e, D[i]) || fabs(cross(s, e, D[i])) < eps)
p.push_back(D[i]);
}
p.push_back(s);
p.push_back(e);
sort(p.begin(), p.end());
double ret = 0;
for (int i = 0; i + 1 < p.size(); i++) {
Pt mid = (p[i] + p[i+1]) * 0.5;
if (inPolygon(D, n, mid))
ret += dist(p[i], p[i+1]);
// printf("%lf %lf ++++\n", p[i].x, p[i].y);
}
return ret;
}
int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2 && n) {
Pt D[2048];
for (int i = 0; i < n; i++)
scanf("%lf %lf", &D[i].x, &D[i].y);
Pt s, e;
for (int i = 0; i < m; i++) {
scanf("%lf %lf", &s.x, &s.y);
scanf("%lf %lf", &e.x, &e.y);
double ret = solve(D, n, s, e);
printf("%.3f\n", ret);
}
}
return 0;
}
/*
9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
4 9
0 0
0 1
1 1
1 0
0 0 1 1
1 1 0 0
0 0 1 0
0 0 0.5 0
0 0.5 1 0.5
0 1 1 1
1 1 1 0
0.75 0.75 0.75 0.25
0 0.25 1 0.75
*/
Read More +

UVa 10848 - Make Palindrome Checker

Problem

檢查生的測資是否符合規格,規則共有七條,分別告知每一條是否符合規格。

  1. 第一個字串必須為小寫字母構成,其長度最多為 1000,第二個字串表示一個不大於 1000 的非負整數。第三個字串必須為小寫字母構成,其長度最多為 2000。
  2. 規則 1 && 第三個字串必須為回文。
  3. 規則 1 && 第一個字串出現的英文字母類型都必須在第三字串中出現。
  4. 規則 1 && 第一個字串出現的英文字母頻率都必須小於等於第三個字串中出現的。
  5. 規則 1 && 第一個字串可以由第三個字串移除某些位置的字元構成。
  6. 規則 1 && 第一字串長度加上輸入的整數等於第二字串長度。
  7. 規則 1 && 整數必須小於第一字串長度。

Sample Input

1
2
3
4
5
6
abcd 3 abcdcba
aaaa 3 abcdcba
abc 2 abdcba
aab b baab
abababaabababa 0 abababaabababa
pqrsabcdpqrs 9 pqrsabcdpqrqpdcbasrqp

Sample Output

1
2
3
4
5
6
TTTTTTT The solution is accepted
TTTFFTT The solution is not accepted
TFTTTFT The solution is not accepted
FFFFFFF The solution is not accepted
TTTTTTT The solution is accepted
TTTTTTT The solution is accepted

Solution

附上討論區的噁心測資

1
2
3
4
5
6
7
8
9
10
abcd 3 abcdcba
aaaa 3 abcdcba
abc 2 abdcba
aab b baab
abababaabababa 0 abababaabababa
pqrsabcdpqrs 9 pqrsabcdpqrqpdcbasrqp
a 0 aa
aa 0 aa
0
2 aa

很明顯地方發現,居然有空字串 …,用空白切割檢查一下參數個數是否正確。

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
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <sstream>
#include <ctype.h>
using namespace std;
int isValidString(string s, int limit) {
int ok = 1;
for (int i = 0; i < s.length(); i++)
ok &= 'a' <= s[i] && s[i] <= 'z';
return ok && s.length() <= limit;
}
int isValidInteger(string s) {
int ok = 1, num = 0;
for (int i = 0; i < s.length(); i++) {
ok &= isdigit(s[i]);
if (isdigit(s[i])) {
num = num * 10 + s[i] - '0';
if (num > 1000)
return 0;
}
}
return ok;
}
int ispalindrome(string s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--)
if (s[i] != s[j])
return 0;
return 1;
}
int allLetterIn(string s1, string s2) {
int c[128] = {};
for (int i = 0; i < s1.length(); i++)
c[s1[i]] = 1;
for (int i = 0; i < s2.length(); i++)
c[s2[i]] = 0;
for (int i = 0; i < 128; i++)
if (c[i] > 0)
return 0;
return 1;
}
int checkfrequency(string s1, string s2) {
int c[128] = {};
for (int i = 0; i < s1.length(); i++)
c[s1[i]]++;
for (int i = 0; i < s2.length(); i++)
c[s2[i]]--;
for (int i = 0; i < 128; i++)
if (c[i] > 0)
return 0;
return 1;
}
int checkBuild(string s1, string s2) {
int idx = 0;
for (int i = 0; i < s2.length() && idx < s1.length(); i++) {
if (s1[idx] == s2[i])
idx++;
}
return idx == s1.length();
}
int checkCond6(string s1, string s2, string s3) {
stringstream sin(s2);
int n;
sin >> n;
return s1.length() + n == s3.length();
}
int checkCond7(string s1, string s2) {
stringstream sin(s2);
int n;
sin >> n;
return s1.length() > n;
}
int main() {
string s1, s2, s3;
char line[32767];
while (gets(line)) {
s1 = s2 = s3 = "";
int n = 0;
for (int i = 0; line[i]; i++) {
if (line[i] == ' ')
n++;
else {
if (n == 0) s1 += line[i];
if (n == 1) s2 += line[i];
if (n == 2) s3 += line[i];
}
}
if (n != 2) {
puts("FFFFFFF The solution is not accepted");
continue;
}
int P[10];
P[0] = isValidString(s1, 1000) && isValidString(s3, 2000) && isValidInteger(s2);
P[1] = P[0] && ispalindrome(s3);
P[2] = P[0] && allLetterIn(s1, s3);
P[3] = P[0] && checkfrequency(s1, s3);
P[4] = P[0] && checkBuild(s1, s3);
P[5] = P[0] && checkCond6(s1, s2, s3);
P[6] = P[0] && checkCond7(s1, s2);
int ok = 1;
for (int i = 0; i < 7; i++) {
printf("%c", P[i] ? 'T' : 'F');
ok &= P[i];
}
printf(" The solution is %saccepted\n", ok ? "" : "not ");
}
return 0;
}
Read More +

UVa 1641 - ASCII Area

Problem

給一個用 ASCII Area 拉出來的簡單多邊形,求其面積為何?

Sample Input

1
2
3
4
5
4 4
/\/\
\../
.\.\
..\/

Sample Output

1
8

Solution

看別人的代碼相當簡單,只是有點不知道它們怎麼構思的。

首先,保證每一個端點都是格子點,靈機一動想到 Pick’s theorem,$A = i + b/2 - 1$,那麼接著就是找到 i 的個數 (內部存在的整數節點個數),b 個數 (邊上的整數節點個數)。

b 很好求得,相當於 \/ 的個數而已,然而 i 求法會比較特別一點,思路類似於掃描線的方式,性質則是利用射線法 (一個點拉一個射線無限延伸,如果該點在簡單多邊形內,則會穿過奇數個點。)。

如果是凸多邊形,也許就能用行列式求值。

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
#include <stdio.h>
// Pick's theorem, A = i + b/2 - 1
int main() {
char g[128][128];
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
int B = 0, I = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '/' || g[i][j] == '\\')
B++;
}
}
for (int i = 0; i <= n; i++) {
int in = 0;
for (int j = 0; j <= m; j++) {
int f = 0;
if (i-1 >= 0 && g[i-1][j] == '/' && g[i][j] == '\\')
in++;
if (i-1 >= 0 && j-1 >= 0 && g[i-1][j-1] == '\\' && g[i][j-1] == '/')
in++;
if (i-1 >= 0 && j-1 >= 0 && g[i-1][j-1] == '\\' && g[i][j] == '\\')
in++;
if (i-1 >= 0 && j-1 >= 0 && g[i-1][j] == '/' && g[i][j-1] == '/')
in++;
if (i-1 >=0 && j-1 >= 0 && g[i-1][j-1] == '\\') f = 1;
if (i-1 >=0 && g[i-1][j] == '/') f = 1;
if (g[i][j] == '\\') f = 1;
if (j-1 >= 0 && g[i][j-1] == '/') f = 1;
if (!f && in%2 == 1)
I ++;
}
}
printf("%d\n", I + B/2 - 1);
}
return 0;
}
Read More +

UVa 1610 - Party Games

Problem

給定 N 個字串 (N 為偶數),現在來了一個人,將其命名名字,其名字長度越小越好,同時必須按照字典順序時,必須大於等於前 N/2 個人,大於 N/2 個人。

在相同的最短長度下,輸出一個字典順序最小的。

Sample Input

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
4
FRED
SAM
JOE
MARGARET
2
FRED
FREDDIE
2
JOSEPHINE
JERRY
2
LARHONDA
LARSEN
2
ABA
AC
2
ABCA
AC
2
ABZA
AC
2
ABZCA
AC
0

Sample Output

1
2
3
4
5
6
7
8
K
FRED
JF
LARI
ABA
ABD
ABZA
ABZD

Solution

先對輸入的字串排序,找到相鄰的兩個中位數字串 p, q (p < q)。

接著分開討論。

  1. p.length() < q.length():要不前綴相同,或者是比 p 大一點,當前綴都相同時跟 p 相同。
  2. p.length() >= q.length():一樣貪心處理前綴,特別小心 ‘Z’ 的存在,這種情況將會逼不得已將長度增加,而其他狀況只要想辦法增加字典順序的大小即可。
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
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
char s[1024];
while (scanf("%d", &n) == 1 && n) {
vector<string> A;
for (int i = 0; i < n; i++)
scanf("%s", s), A.push_back(s);
sort(A.begin(), A.end());
string p = A[n/2-1], q = A[n/2];
if (p.length() < q.length()) {
for (int i = 0; i < p.length(); i++) {
if (p[i] == q[i] || i == p.length() - 1) // equal.
putchar(p[i]);
else { // less
putchar(p[i] + 1);
break;
}
}
} else {
for (int i = 0; i < q.length(); i++) {
if (p[i] == q[i])
putchar(p[i]);
else {
if (i == q.length() - 1) {
if (i == p.length() - 1) { // equal
putchar(p[i]);
break;
}
if (p[i] + 1 != q[i]) {
putchar(p[i] + 1);
break;
} else {
putchar(p[i]);
for (int j = i+1; j < p.length(); j++) {
if (j == p.length() - 1) // equal
putchar(p[j]);
else if (p[j] != 'Z') {
putchar(p[j] + 1);
break;
} else
putchar(p[j]);
}
break;
}
} else {
putchar(p[i] + 1);
break;
}
}
}
}
puts("");
}
return 0;
}
/*
4
FRED
SAM
JOE
MARGARET
2
FRED
FREDDIE
2
JOSEPHINE
JERRY
2
LARHONDA
LARSEN
2
ABA
AC
2
ABCA
AC
2
ABZA
AC
2
ABZCA
AC
0
*/
Read More +

UVa 1605 - Building for UN

Problem

現在有 N 個國家在一棟建築物裡面各自擁有辦公室,辦公室相鄰的定義為同一樓層的前後左右,或者是上一樓層的同一位置、下一樓層的同一位置。

由於各方想要藉由一面牆或者是天花板進行秘密會議。因此希望每一個國家的辦公室可以跟其他所有辦公室相鄰。

輸出其中一組解即可。

Sample Input

1
2
4
8

Sample Output

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
2 2 2
AB
CC
zz
zz
2 8 8
aaaaaaaa
bbbbbbbb
cccccccc
dddddddd
eeeeeeee
ffffffff
gggggggg
hhhhhhhh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh

Solution

直接建造兩層,參照如上圖的建造方式,交錯的形式能保證可以在 O(2 n^2) 個數內完成建築物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
// ignore Print a blank line between test cases.
int main() {
int n, cases = 0;
while (scanf("%d", &n) == 1) {
printf("%d %d %d\n", 2, n, n);
for (int i = 0; i < n; i++, puts(""))
for (int j = 0; j < n; j++)
putchar(i < 26 ? i + 'a' : i-26 + 'A');
puts("");
for (int i = 0; i < n; i++, puts(""))
for (int j = 0; j < n; j++)
putchar(j < 26 ? j + 'a' : j-26 + 'A');
puts("");
}
return 0;
}
Read More +

UVa 1600 - Patrol Robot

Problem

機器人能轉移只有上下左右四個方向,機器人切換快速移動模式,將自己跨過小於等於 K 個連續的障礙物。也就是說,當障礙物連續出現形成一座厚牆時,機器人就爬不過去。

求最少移動次數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 5
0
0 1 0 0 0
0 0 0 1 0
4 6
1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0
2 2
0
0 1
1 0

Sample Output

1
2
3
7
10
-1

Solution

將每一點多一個狀態 s,表示當前經過連續 s 個障礙物。如果下一個轉移地點不是障礙物,則 s 會歸零。

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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int g[32][32];
int dist[32][32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
int testcase;
int N, M, K;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
scanf("%d", &g[i][j]);
memset(dist, 63, sizeof(dist));
dist[0][0][0] = 0;
queue<int> X, Y, S;
int x, y, s, tx, ty, ts;
X.push(0), Y.push(0), S.push(0);
while (!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
s = S.front(), S.pop();
for (int i = 0; i < 4; i++) {
tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= N || ty >= M)
continue;
if (g[tx][ty])
ts = s + 1;
else
ts = 0;
if (ts > K) continue;
if (dist[tx][ty][ts] > dist[x][y][s] + 1) {
dist[tx][ty][ts] = dist[x][y][s] + 1;
X.push(tx), Y.push(ty), S.push(ts);
}
}
}
int ret = 0x3f3f3f3f;
for (int i = 0; i <= K; i++)
ret = min(ret, dist[N-1][M-1][i]);
printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
}
return 0;
}
/*
3
2 5
0
0 1 0 0 0
0 0 0 1 0
4 6
1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0
2 2
0
0 1
1 0
*/
Read More +

UVa 1579 - Matryoshka

Problem

俄羅斯套娃遊戲,每一次只能將相鄰的兩個套娃合併。合併時,打開套娃的次數相當於操作成本,請問至少要打開的次數為何,使得最後的數個套娃可以收成連續大小 1 ~ n

一開始給定每個套娃內部都沒有別的套娃。

從第二組測資中,可以看出必須整理成 [1 2 3][1 2 3 4] 兩組完整的套娃。要把 [2][4] 合併成 [2 4] 要打開大小為 4 的套娃,並且把大小為 2 的套娃裝進去。同理,[1][3] 合併成 [1 3] 也需要打開一次。最後合併 [2 4][1 3][1 2 3 4] 其中必須將 4 打開 (看到 2),再把 2 打開,把 3 打開,接著把 1 裝進 2,把 2 裝進 3,最後裝進 4 中。

此時已經花費成本 5 次 (打開次數),而要把 [1][2][3] 合併成 [1 2 3] 需要打開 2、打開 3 才能完成。共計成本 7 次。

Sample Input

1
2
3
4
7
1 2 1 2 4 3 3
7
1 2 3 2 4 1 3

Sample Output

1
2
impossible
7

Solution

類似矩陣鏈乘積 DP,但是這一題必須使用兩次 DP。

  1. 第一次計算 dp[l, r] 找到序列 [l, r] 之間合併成一個套娃的花費。-O(n^3)
  2. 之後檢查 A[l, r] 之間是否是一個 complete set,也就是一個完整的套娃 (連續大小)。-O(n^3) 這裡應該還可以更快,不過步驟 1 應該很慢,所以沒有必要。
  3. 最後,組合數個連續區段套娃,進行區間合併的操作。-O(n^2)
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 512
int A[MAXN];
int dp[MAXN][MAXN] = {}, complete[MAXN][MAXN];
int main() {
int n;
while (scanf("%d", &n) == 1) {
for (int i = 0; i < n; i++)
scanf("%d", &A[i]);
for (int i = 1; i < n; i++) { // build cost table.
for (int j = 0; i + j < n; j++) {
int l = j, r = i + j;
int &val = dp[l][r];
val = 0x3f3f3f3f;
for (int k = l; k < r; k++) {
int open = 0; // [l, r] = L[l, k] + R[k+1, r]
int minL = 0x3f3f3f3f, minR = 0x3f3f3f3f;
for (int p = l; p <= k; p++)
minL = min(minL, A[p]);
for (int p = k+1; p <= r; p++)
minR = min(minR, A[p]);
for (int p = l; p <= k; p++)
open += A[p] > minR;
for (int p = k+1; p <= r; p++)
open += A[p] > minL;
// printf("[%d %d %d %d] %d %d\n", l, k, k+1, r, dp[l][k] + dp[k+1][r]+ open, open);
val = min(val, dp[l][k] + dp[k + 1][r] + open);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; i + j < n; j++) {
int l = j, r = i + j, m = i + 1; // [l, r] need 1, 2, 3, ..., m
int used[MAXN] = {}, ok = 1;
for (int k = l; k <= r && ok; k++) {
if (A[k] > m) {
ok = 0;
break;
}
used[A[k]]++;
if (used[A[k]] > 1) ok = 0;
}
complete[l][r] = ok;
}
}
int dp2[MAXN];
for (int i = 0; i <= n; i++)
dp2[i] = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (complete[i][j]) {
int comb = dp[i][j];
if (i) comb += dp2[i-1];
dp2[j] = min(dp2[j], comb);
}
}
}
if (dp2[n - 1] == 0x3f3f3f3f)
puts("impossible");
else
printf("%d\n", dp2[n - 1]);
}
return 0;
}
/*
7
1 2 1 2 4 3 3
7
1 2 3 2 4 1 3
2
1 1
2
2 1
5
1 3 2 3 1
5
1 2 2 3 1
*/
Read More +