[URI ONLINE JUDGE] – 2070 – Counting MadSequences

Given an integer K and 3 sequences S1S2 and S3, we call MadSequence, a sequence consisting of positive integers smaller or equal to K and that is not subsequence of S1, S2 or S3. Remember that a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

For example, for K = 3, S1 = <1, 2, 3, 1, 2>, S2 = <2, 3, 1, 2> and S3 = <3, 1, 2, 3, 1, 2> , all possible sequences of size 1 ( and ) are not MadSequences, because are subsequences of S1, S2 and S3.

Analyzing all possible sequences of length 2 for K = 3:

  • <1, 1> is not subsequence of S2, then <1, 1> is a MadSequence;
  • <1, 2> is subsequence of S1, S2 and S3;
  • <1, 3> is not subsequence of S2, then <1, 3> is a MadSequence;
  • <2, 1> is subsequence of S1, S2 and S3;
  • <2, 2> is subsequence of S1, S2 and S3;
  • <2, 3> is subsequence of S1, S2 and S3;
  • <3, 1> is subsequence of S1, S2 and S3;
  • <3, 2> is subsequence of S1, S2 and S3;
  • <3, 3> is not subsequence of S1 and S2, then <3, 3> is a MadSequence;

Thus, the size of the smallest MadSequence, for this example, is equal to 2. We also conclude that there are 3 MadSequences of length 2.

Input

The first line of input consists of four integers KL1L2 and L3 represent, respectively, the integer K and sizes of S1S2 and S3 (1 ≤ ≤ 20 and 1 ≤ L1L2 and L3 ≤ 200). The second line consists of L1 integers, representing the elements of S1. The third line consists of L2 integers, representing the elements of S2. The fourth line consists of L3 integers, representing the elements of S3. Assume that all elements of the sequences S1S2 and S3 are positive integers smaller than or equal to K.

Output

The integer M is the smallest size of a MadSequence for the input data. Print a single line containing M and the amount of MadSequences with M size.

Input Sample Output Sample
3 5 4 6
1 2 3 1 2
2 3 1 2
3 1 2 3 1 2
2 3
 Solution:
“`cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;struct tri {
int a, b, c;
tri() {}
tri(int _a, int _b, int _c){a = _a; b = _b; c = _c; }
};
int k, l[3];
int s[3][205];
int G[3][205][25];
int marca[205][205][205];
int cc[205][205][205];

pair<int,int> BFS() {
int menor = 1000000, quantidade = 0;
queue fila;
fila.push(tri(0, 0, 0));
memset(marca, 0, sizeof marca);
memset(cc, 0, sizeof cc);
cc[0][0][0] = 1;

while(fila.size()) {
int p1 = fila.front().a;
int p2 = fila.front().b;
int p3 = fila.front().c;
fila.pop();
if(menor <= marca[p1][p2][p3]) { break; }
for(int i = 1; i <= k; i++) { if(G[0][p1][i] == l[0] + 1 or G[1][p2][i] == l[1] + 1 or G[2][p3][i] == l[2] + 1) { menor = marca[p1][p2][p3] + 1; quantidade += cc[p1][p2][p3]; } if(quantidade) { continue; } int pp1 = G[0][p1][i]; int pp2 = G[1][p2][i]; int pp3 = G[2][p3][i]; if(! marca[pp1][pp2][pp3]) { marca[pp1][pp2][pp3] = marca[p1][p2][p3]+1; cc[pp1][pp2][pp3] = cc[p1][p2][p3]; fila.push(tri(pp1, pp2, pp3)); } else { if(marca[pp1][pp2][pp3] == marca[p1][p2][p3]+1){ cc[pp1][pp2][pp3] += cc[p1][p2][p3]; } } } } return make_pair(menor, quantidade); } int main() { cin >> k >> l[0] >> l[1] >> l[2];
for(int i = 0; i < 3; i++) {
for(int j = 1; j <= l[i]; j++) { cin >> s[i][j];
}
}
for(int i = 0; i < 3; i++) {
for(int j = 1; j <= l[i]; j++) {
for(int w = 0; w <= k; w++) {
G[i][j][w] = l[i] + 1;
}
}
}
for(int i = 0; i < 3; i++) {
for(int j = 1; j <= l[i]; j++) { for(int w = j-1; w >= 0; w–) {
G[i][w][s[i][j]] = j;
if(s[i][w] == s[i][j]) break;
}
}
}

pair<int,int> ans = BFS();
printf(“%d %d\n”, ans.first, ans.second);

return 0;
}

“`
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s