Gym 100917J---Judgement(01背包+bitset)，gym100917c

Gym 100917J---Judgement(01背包+bitset)，gym100917c

題目鏈接

http://codeforces.com/gym/100917/problem/J

 

Description

standard input/output
Statements

The jury of Berland regional olympiad in informatics does not trust to contest management systems, so the Berland regional programming contest is judged by the next way. There are n judges in the jury, each judge have authority a_i. When jury receives a diskette with the new solution, each jury member reads its source and votes "OK" or "WA". If after the voting ends the sum of authorities of jury members, who think that solution is correct, is equal or greater to p, then soluton is accepted, otherwise it is rejected.

Several jury members think, that current system is too complicated for them and proposed some changes: each jury member will have new authority b_i, and limit is changed to q; then, in their opinion, calculations will be easier, and nothing more changes.

You are hired by the Department of Education of Berland region to check if the new system is equivalent to old one, i.e. that at any possible distribution of votes final verdict with the new and with the old parameters will be the same. If the systems differ, output an example of voting, when verdicts in both systems are different.

Input

First line of the input contains one integer n (1 ≤ n ≤ 100) — number of judges in the jury.

Second line contains n + 1 integers p, a₁, a₂, ..., a_n (1 ≤ p, a_i ≤ 10⁶) — the current acception limit and the current values of authorities of jury members, respectively.

Third line contains n + 1 integers q, b₁, b₂, ..., b_n (1 ≤ q, b_i ≤ 10⁶) — the new acception limit and the new values of authorities of jury members, respectively.

Output

If old and new systems are equivalent, print "YES". Otherwise in the first line of output print "NO", and in second print example of voting, with different verdicts in old and new systems. Voting is encoded with the string of length n, where i-th character is '1', if i-th judge considered solution correct and '0' otherwise.

If several answers are possible, print any of them.

Sample Input

Input

3
8 4 5 6
2 1 1 1

Output

YES

Input

3
6 4 5 6
2 1 1 1

Output

NO
001

題意：輸入n表示有n個評委，現在有兩種裁決方案：1、  p a[1]、a[2]......a[n] 表示每個評委的權值，如果第i個評委同意則總的評分加上a[i]，如果總分達到p則表示通過；
2、   q  b[1]、b[2]......b[n]  與上面相同，如果總分達到q表示通過；   現在要求判斷兩種評選方案在任何情況下結果是否都是一樣；

思路：定義mx[i]表示在第一種方案總分達到i（i<p）時，第二種方案能達到的最大得分，當在i<p&&mx[i]>=q時，則輸出“NO” ，為了輸出路徑，可以使用bitset； 同樣對調p和q  a和b 再計算一次；

代碼如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
bitset<120>s[maxn];
int a[105],b[105];
int mx[maxn];
int n;

bool calc(int *a,int *b)
{
    for(int i=0; i<maxn; i++)  s[i].reset();
    memset(mx,-1,sizeof(mx));
    mx[0]=0;
    int top=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=top; j>=0; j--)
        {
            if(mx[j]>-1)
            {
                if(j+a[i]<a[0]&&mx[j]+b[i]>mx[j+a[i]])
                {
                    mx[j+a[i]]=mx[j]+b[i];
                    s[j+a[i]]=s[j];
                    s[j+a[i]].set(i);
                    top=max(top,j+a[i]);

                }
                if(j+a[i]<a[0]&&mx[j+a[i]]>=b[0])///一定要加上j+a[i]<a[0] 否則可能越界；
                {
                    puts("NO");
                    for(int k=1; k<=n; k++)
                        printf("%d",(int)s[j+a[i]][k]);
                    puts("");
                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d",&n);
    for(int i=0; i<=n; i++)    scanf("%d",&a[i]);
    for(int i=0; i<=n; i++)    scanf("%d",&b[i]);
    if(calc(a,b)) return 0;
    if(calc(b,a)) return 0;
    puts("YES");
    return 0;
}