uva1588

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

A research laboratory of a world-leading automobile company has received an order to create a special transmission mechanism, which allows for incredibly efficient kickdown -- an operation of switching to lower gear. After several months of research engineers found that the most efficient solution requires special gears with teeth and cavities placed non-uniformly. They calculated the optimal flanks of the gears. Now they want to perform some experiments to prove their findings.

The first phase of the experiment is done with planar toothed sections, not round-shaped gears. A section of length n consists of n units. The unit is either a cavity of height h or a tooth of height 2h . Two sections are required for the experiment: one to emulate master gear (with teeth at the bottom) and one for the driven gear (with teeth at the top).

There is a long stripe of width 3h in the laboratory and its length is enough for cutting two engaged sections together. The sections are irregular but they may still be put together if shifted along each other.

The stripe is made of an expensive alloy, so the engineers want to use as little of it as possible. You need to ï¬nd the minimal length of the stripe which is enough for cutting both sections simultaneously.

Input

The input file contains several test cases, each of them as described below.

There are two lines in the input, each contains a string to describe a section. The first line describes master section (teeth at the bottom) and the second line describes driven section (teeth at the top). Each character in a string represents one section unit -- 1 for a cavity and 2 for a tooth. The sections can not be flipped or rotated.

Each string is non-empty and its length does not exceed 100.

Output

For each test case, write to the output a line containing a single integer number -- the minimal length of the stripe required to cut off given sections.

Sample Input

2112112112

2212112

12121212

21212121

2211221122

21212

Sample Output

题目类型： 字符串处理题

算法分析：写一个函数Solve，通过调用不同参数的Solve函数两次，来完成向两个方向移动的判断，Solve函数只需按照题意移动一个字符串的初始比较位置，判断是否满足高度不大于3即可，下面第一个代码是更好的实现

/**************************************************
filename       :q.cpp
author         :maksyuki
created time   :2017/12/3 15:32:28
last modified  :2017/12/3 16:15:04
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char va[maxn], vb[maxn];
int lena, lenb;

void rev() {
    for(int i = 0; i < lena / 2; i++) swap(va[i], va[lena-1-i]);
    for(int i = 0; i < lenb / 2; i++) swap(vb[i], vb[lenb-1-i]);
}

int check(int p) {
    int i, j;
    for(i = p, j = 0; i < lena && j < lenb; i++, j++) {
        int tmpa = va[i] - '0', tmpb = vb[j] - '0';
        if(tmpa + tmpb > 3) return -1;
    }
    if(i == lena && j < lenb) return lena + lenb - j;
    if(i <= lena && j == lenb) return lena;
    return -1;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf(" %s", va) != EOF) {
        scanf(" %s", vb);

        lena = strlen(va), lenb = strlen(vb);
        if(lena < lenb) swap(va, vb), swap(lena, lenb);
        
        int minval = INF;
        for(int i = 0; i < lena; i++) {
            int tmp = check(i);
            if(tmp != -1) minval = min(minval, tmp);
        }

        minval = min(minval, lena + lenb);
        rev();
        for(int i = 0; i < lena; i++) {
            int tmp = check(i);
            if(tmp != -1) minval = min(minval, tmp);
        }

        printf("%d\n", minval);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

/**************************************************

filename :q.cpp

author :maksyuki

created time :2017/12/3 15:32:28

last modified :2017/12/3 16:15:04

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char va[maxn], vb[maxn];

int lena, lenb;

void rev() {

for(int i = 0; i < lena / 2; i++) swap(va[i], va[lena-1-i]);

for(int i = 0; i < lenb / 2; i++) swap(vb[i], vb[lenb-1-i]);

}

int check(int p) {

int i, j;

for(i = p, j = 0; i < lena && j < lenb; i++, j++) {

int tmpa = va[i] - '0', tmpb = vb[j] - '0';

if(tmpa + tmpb > 3) return -1;

}

if(i == lena && j < lenb) return lena + lenb - j;

if(i <= lena && j == lenb) return lena;

return -1;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(scanf(" %s", va) != EOF) {

scanf(" %s", vb);

lena = strlen(va), lenb = strlen(vb);

if(lena < lenb) swap(va, vb), swap(lena, lenb);

int minval = INF;

for(int i = 0; i < lena; i++) {

int tmp = check(i);

if(tmp != -1) minval = min(minval, tmp);

}

minval = min(minval, lena + lenb);

rev();

for(int i = 0; i < lena; i++) {

int tmp = check(i);

if(tmp != -1) minval = min(minval, tmp);

}

printf("%d\n", minval);

}

return 0;

}

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 100 + 66;

bool Test (int k, char *val_a, char *val_b)
{
int i;
for (i = 0; val_a[k+i] && val_b[i]; i++)
if ((val_a[k+i] - '0') + (val_b[i] - '0') > 3)
return false;

return true;
}


int Solve (char *val_a, char *val_b)
{
int i = 0;

while (!Test (i, val_a, val_b))
{
i++;
}

return max (strlen (val_a), strlen (val_b) + i);
}


int main()
{
//	ifstream cin ("aaa.txt");

char val_a[maxn], val_b[maxn];

while (cin >> val_a >> val_b)
{
cout << min (Solve (val_a, val_b), Solve (val_b, val_a)) << endl;
}

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn = 100 + 66;

bool Test (int k, char *val_a, char *val_b)

{

int i;

for (i = 0; val_a[k+i] && val_b[i]; i++)

if ((val_a[k+i] - '0') + (val_b[i] - '0') > 3)

return false;

return true;

}

int Solve (char *val_a, char *val_b)

{

int i = 0;

while (!Test (i, val_a, val_b))

{

i++;

}

return max (strlen (val_a), strlen (val_b) + i);

}

int main()

{

// ifstream cin ("aaa.txt");

char val_a[maxn], val_b[maxn];

while (cin >> val_a >> val_b)

{

cout << min (Solve (val_a, val_b), Solve (val_b, val_a)) << endl;

}

return 0;

}

uva1587

uva1600

一	二	三	四	五	六	日
« 6月
						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

超客的水墨烟雨

uva1588

分类目录

标签云

书签

近期评论