The More The Better

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 800 Accepted Submission(s): 208

Problem Description

Given an sequence of numbers {X₁, X₂, ... , X_n}, where X_k = (A * k + B) % mod. Your task is to find the maximum sub sequence {Y₁, Y₂, ... , Y_m} where every pair of (Y_i, Y_j) satisfies Y_i + Y_j <= L (1 ≤ i < j ≤ m), and every Y_i <= L (1 ≤ i ≤ m ).
Now given n, L, A, B and mod, your task is to figure out the maximum m described above.

Input

Multiple test cases, process to the end of input. Every test case has a single line. A line of 5 integers: n, L, A, B and mod. (1 ≤ n ≤ 2*10⁷, 1 ≤ L ≤ 2*10⁹, 1 ≤ A, B, mod ≤ 10⁹)

Output

For each case, output m in one line.

Sample Input

1 8 2 3 6 

5 8 2 3 6

Sample Output

1 4

Source

2012 Multi-University Training Contest 8

简单题，首先想到所有小于 L/2 的，统统可以放进来，最后，按照题意，还可能可以放一个大于 L/2 的数进来，当小于 L/2 的数里面的最大值加上这个大于 L/2 的数的和小于 L 时，答案加一。最后要注意所有数都小于 L/2 的处理。O(n) 算法可过此题。

好想说这是好蛋疼的一道题，错了不知道多少次，发现错在了 min = 1<<62 和 min = 1 min<<= 62 的值竟然不一样（min 为 long long）tmd。。。。。

View Code

1 #include<stdio.h>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<map>
9 #define Min(a,b)  a>b?b:a
10 #define Max(a,b)  a>b?a:b
11 #define CL(a,num)  memset(a,num,sizeof(a));
12 #define inf  1<<62
13 #define maxn    1000010
14 #define eps  1e-6
15 #define ll  __int64
16
17
18 using namespace std;
19
20
21 int main()
22 {
23
24     ll a,b;
25
26     ll mod,n;
27     ll l;
28      int  k;
29      //freopen("data.txt","r",stdin);
30     while(scanf("%I64d%I64d%I64d%I64d%I64d",&n,&l,&a,&b,&mod)!=EOF)
31     {
32          ll mx = 0;
33         int cnt = 0;
34         ll  mi = inf ;
35          int mid = l/2;
36         for( k = 1 ; k <= n;++k)
37         {
38              ll tmp = ( a*k + b)%mod ;
39             if(tmp <= mid)
40             {
41                 cnt ++;
42                 if(tmp > mx) mx = tmp;
43
44             }
45             else
46             {
47
48                 if(mi > tmp) mi = tmp ;
49
50
51             }
52
53         }
54
55
56         if(mi + mx <= l)cnt++;
57         printf("%d\n",cnt);
58     }
59     return 0;
60
61 }