解題區►解題區 - UVa

UVa 10848 - Make Palindrome Checker

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

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;
}