Description
Problem H Enemy at the Gateway Input: Standard Input
Output: Standard Output
This is the year 9002, the war between the Earth and Triton has broken out. Being a spy for the Earth, you are trying to find all means to destroy Triton protections. Being a very smart spy, you have somehow managed to enter into the Triton network and take over the control of a gateway. Now, you are trying to decode the messages passed between them.
o
The messages are arbitrarily long sequence of integers with a preamble of P integers. Each integer will fit inside a 32 bit signed integer. You have managed to capture the actual preamble. But, the communication lines are too noisy, and for this reason, you can not get the sequence accurately. For each number in the sequence si, you have determined that, it can actually be any value between pi and qi inclusive.
Now, given the sequence of numbers, find in how many places, the message may start.
Input
First line contains T, the number of test cases. Each test case starts with an integer P, the length of the pattern. The next line contains Pintegers. Next line contains 10 integers, N, p0, q0, A, B, C, D, E, F, M. N is the length of the sequence. The range for each element in the sequence is generated using a generator function
pi = (A * pi-1 + B * qi-1 + C) % M
qi = (D * pi-1 + E * qi-1 + F) % M
if(qi < pi) swap(pi,qi)
[p1,q1], [p2, q2],...,[pN,qN] describes the sequence. Please note that [p0,q0] is not included in the sequence
Output
For each test case, output the number of places, the preamble may start.
Constraints
l T <= 100
l P <= 60
l N <= 1000000
l 0 <= p0,q0,A,B,C,D,E,F,M <= 1000000000
Sample Input Output for Sample Input
| 2 1 10 4 6 12 1 0 2 0 1 2 100000 2 1 2 3 1 3 1 0 0 0 1 0 10
| Case 1: 2 Case 2: 2
|
In the first case. the intervals are:
[8,14],[10,16],[12,18],[14,20]. The value 10 can only be contained in the first two.
In the second case, all the intervals are [1,3], so, you can find two positions to start the preamble.
Problem setter: Manzurur Rahman Khan
Special Thanks: Samee Zahur
数据水了，暴力。。。
#include#include #include using namespace std;int T, t = 1;int N, A, B, C, D, E, F, M, p;int a[61];int ans;//区间struct Range{ int p, q;}r[1000001];int main(){ int i, j; scanf("%d", &T); while(T--) { ans = 0; scanf("%d", &p); for(i = 0; i < p; i++) scanf("%d", &a[i]); scanf("%d %d %d %d %d %d %d %d %d %d", &N, &r[0].p, &r[0].q, &A, &B, &C, &D, &E, &F, &M); for(i = 0; i < N; i++) { r[i+1].p = ( ( (A * r[i].p) % M + (B * r[i].q) % M) % M + C) % M; r[i+1].q = ( ( (D * r[i].p) % M + (E * r[i].q) % M) % M + F) % M; if(r[i+1].p > r[i+1].q) swap(r[i+1].p, r[i+1].q); } //注意loop的条件是i <= N - p + 1 for(i = 1; i <= N - p + 1; i++) { int k = i; for(j = 0; j < p; j++, k++) { if(a[j] > r[k].q || a[j] < r[k].p) break; } if(j == p) ans++; } printf("Case %d: %d\n", t++, ans); } return 0;}