[UVA][SlidingWindow] 11536 - Smallest Sub-Array
H |
Smallest Sub-Array Input: Standard Input Output: Standard Output |
Consider an integer sequence consisting of N elements where –
X1 = 1
X2 = 2
X3 = 3
Xi = (Xi-1 + Xi-2 + Xi-3) % M + 1 for i = 4 to N
Find 2 values a and b so that the sequence (Xa Xa+1 Xa+2 ... Xb-1 Xb) contains all the integers from [1,K]. If there are multiple solutions then make sure (b-a) is as low as possible.
In other words, find the smallest subsequence from the given sequence that contains all the integers from 1 to K.
Consider an example where N = 20, M = 12 and K = 4.
The sequence is {1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.
The smallest subsequence that contains all the integers {1 2 3 4} has length 13 and is highlighted in the following sequence:
{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.
Input
First line of input is an integer T(T<100) that represents the number of test cases. Each case consists of a line containing 3 integers N(2 < N < 1000001), M(0 < M < 1001) and K(1< K < 101). The meaning of these variables is mentioned above.
Output
For each case, output the case number followed by the minimum length of the subsequence. If there is no valid subsequence, output “sequence nai” instead. Look at the sample for exact format.
Sample Input Output for Sample Input
|
2 20 12 4 20 12 8 |
Case 1: 13 Case 2: sequence nai |
Problemsetter: Sohel Hafiz
Special Thanks: Md. Arifuzzaman Arif
#include <stdio.h>
int X[1000005] = {0,1,2,3};
int main() {
int T, cases = 0;
int N, M, K, i;
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &N, &M, &K);
int modM[3005] = {};
for(i = 0; i < 3005; i++)
modM[i] = i%M;
for(i = 4; i <= N; i++) {
X[i] = X[i-1] + X[i-2] + X[i-3];
if(X[i] >= M) X[i] = modM[X[i]];
X[i] ++;
}
int used[105] = {}, d = 0;
int tail = 1, mndist = 0xfffffff;
for(i = 1; i <= N; i++) {
while(tail <= N && d < K) {
if(X[tail] <= K && used[X[tail]] == 0)
d++;
if(X[tail] <= K)
used[X[tail]]++;
tail++;
}
if(tail > N && d < K)
break;
if(mndist > tail-i && d == K)
mndist = tail-i;
if(X[i] <= K && used[X[i]] == 1)
d--;
if(X[i] <= K)
used[X[i]]--;
}
printf("Case %d: ", ++cases);
if(mndist != 0xfffffff)
printf("%d\n", mndist);
else
puts("sequence nai");
}
return 0;
}
為了加速其運算，全部指針化。
#include <stdio.h>
int X[1000005] = {0,1};
int Y[1000005] = {0,1};
int main() {
int T, cases = 0;
int N, M, K, i;
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &N, &M, &K);
int modM[3005] = {};
for(i = 0; i < 3005; i++)
modM[i] = i%M;
int xi1 = 3, xi2 = 2, xi3 = 1, xi;
int idx = 2;
int *p = &X[1], *q = &Y[1], *pp = &X[1], *qq = &Y[1];
if(2 <= K) *(++p) = 2, *(++q) = 2;
if(3 <= K) *(++p) = 3, *(++q) = 3;
for(i = 4; i <= N; i++) {
xi = xi1 + xi2 + xi3;
if(xi >= M) xi = modM[xi];
xi++;
if(xi <= K)
*(++p) = xi, *(++q) = i;
xi3 = xi2, xi2 = xi1, xi1 = xi;
}
*(++q) = N+1;
int *end = p+1;
int used[105] = {}, d = 0;
int mndist = 0xfffffff;
p = &X[1], q = &Y[1], pp = &X[1], qq = &Y[1];
for(; pp != end;) {
while(p != end && d < K) {
if(used[*p] == 0)
d++;
used[*p]++;
p++, q++;
}
if(p == end && d < K)
break;
if(mndist > (*(q-1))-(*qq) && d == K)
mndist = (*(q-1))-(*qq);
if(used[*pp] == 1)
d--;
used[*pp]--, pp++, qq++;
}
printf("Case %d: ", ++cases);
if(mndist != 0xfffffff)
printf("%d\n", mndist+1);
else
puts("sequence nai");
}
return 0;
}