I贾老二的工件【noip模拟赛3】

发表于 | 分类于 ， | 阅读量 次

描述

贾老二有很多工件，最常见的工件都是长条形的，但其顶端是凹凸不平的，即不同位置的高度不同。现在贾老二有两个最常见的工件，他想将它们完全放入另一种罕见的可容纳高度不超过k的工件中，问该罕见的工件的最小长度。

输入

输入来自文件jia.in，包括三行。第一行包含一个不超过20的正整数k；接下来每行有一个长度不超过100的正整数串，其中的每个数都在1到9之间，表示该常见工件对应位置的高度。

36109a773d.png

输出

包括一个数字即罕见的工件的最小长度。如果无解则输出“Impossible”。

输入样例 1

4 2213
231223

输出样例 1

7

输入样例 2

1 2112
122111

输出样例 2

Impossible

来源：
来自 <http://www.dingbacode.com/contest/19/problem/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
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
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int mH;
    cin>>mH;
    char a[1000],b[1000];

    cin>>a;
    cin>>b;

    int changa=strlen(a);
    int changb=strlen(b);
    for(int i=0;i<changa;i++)
        if(mH<a[i]-'0') {cout<<"Impossible"<<endl;return 0;}
    for(int i=0;i<changb;i++)
        if(mH<b[i]-'0') {cout<<"Impossible"<<endl;return 0;}

    for(int i=changa;i<=changa+changb;i++) a[i]='0';
    for(int i=changb;i<=changa+changb;i++) b[i]='0';



    int ans=changa+changb;

    for(int i=0;i<changa;i++)
    {
          int flag=1;
        for(int j=0;j<changb;j++)
        {
            if(a[i+j]-'0'+b[j]-'0'>mH){flag=0;break;}
        }
        if(flag) {ans=max(max(changa,changb),min(ans,i+changb));break;}
    }


     for(int i=0;i<changb;i++)
    {
          int flag=1;
        for(int j=0;j<changa;j++)
        {
            if(b[i+j]-'0'+a[j]-'0'>mH){flag=0;break;}
        }
        if(flag) {ans=max(max(changa,changb),min(ans,i+changa));break;}
    }


    reverse(a,a+changa);

   for(int i=0;i<changa;i++)
    {
          int flag=1;
        for(int j=0;j<changb;j++)
        {
            if(a[i+j]-'0'+b[j]-'0'>mH){flag=0;break;}
        }
        if(flag) {ans=max(max(changa,changb),min(ans,i+changb));break;}
    }


     for(int i=0;i<changb;i++)
    {
          int flag=1;
        for(int j=0;j<changa;j++)
        {
            if(b[i+j]-'0'+a[j]-'0'>mH){flag=0;break;}
        }
        if(flag) {ans=max(max(changa,changb),min(ans,i+changa));break;}
    }
    cout<<ans<<endl;


    return 0;
}