2013山东省ICPC结题报告

A、Rescue The Princess

已知一个等边三角形的两个顶点A、B，求第三个顶点C，A、B、C成逆时针方向。

常规的解题思路就是用已知的两个点列出x，y方程，但这样求出方程的解的表达式比较复杂。更为简单的方法就是以A的坐标加A、C直线的角度求解，使用atan2函数求出A、B直线的角度再加上60就是A、C的角度，使用A、B求出等边三角形的边长。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 const double pi = acos(-1.0);
 8 double xx1,yy1,xx2,yy2,xx3,yy3,jiao,leng;
 9 
10 int main(int argc, char const *argv[])
11 {
12     freopen("SD_3230_Rescue_The_Princess.in","r",stdin);
13     int amount;
14     scanf("%d",&amount);
15     while(amount--){
16         scanf("%lf %lf %lf %lf",&xx1,&yy1,&xx2,&yy2);
17         jiao = atan2(yy2-yy1,xx2-xx1);
18         leng = sqrt(pow(xx1-xx2,2)+pow(yy1-yy2,2));
19         xx3 = xx1 + leng*cos(jiao+pi/3.0);
20         yy3 = yy1 + leng*sin(jiao+pi/3.0);
21         printf("(%.2lf,%.2lf)
", xx3,yy3);
22     }
23     return 0;
24 }

View Code

B、Thrall’s Dream

给出N个点N (0 <= N < 2001)，M条边M (0 <= M < 10001)构成的图，判断是否任意两点可达，可达输出“Kalimdor is just ahead“，否则输出”The Burning Shadow consume us all“。

首先拿到这题第一个出现脑海的想法就是一次对每个点进行dfs，并记录已经确定的结果。但是想一想肯定会TE，所以就此打住这个想法。采用targan算法求出所有的连通分量，再判断这些连通分量能否构成一条链（不能出现两个或两个以上出度为0的连通分量），能则true，否则false，关键在于使用targan算法求出所有的联通分量。targan算法：基于dfs，使用low记录该点所属连通分量，dfn记录遍历到此点的时间，如果遍历的点已经遍历过并在栈中说明出现了环，要更新的相应的low值到最小，并把小的low值回传给father，如果出现low==dfn则说明出现了一个联通分量，并且这个连通分量的所有元素一定都在栈中并且都相邻，然后将这些元素全部出栈并统计此连通分量的出度，最后如果有大于等于两个连通分量的出度为0则一定有连点不可达。

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <stack>
  5 
  6 #ifndef SYMBOL
  7 #define MAXN 2001
  8 #endif
  9 
 10 using namespace std;
 11 /*
 12 dfs变形的targan算法，求强连通图的强联通分量
 13 */
 14 
 15 struct node
 16 {
 17     int size;
 18     int indegree;
 19     int asked;
 20     int instack;
 21     int father;
 22 };
 23 
 24 int childs[MAXN][MAXN],low[MAXN],dfn[MAXN];
 25 int nodeAmount,edgeAmount,times,mins,outzero;
 26 stack<int> stacks;
 27 struct node nodes[MAXN];
 28 
 29 void init(){
 30     for (int i = 1;i <= MAXN;i ++){
 31         nodes[i].size = 0;
 32         nodes[i].asked = 0;
 33         nodes[i].instack = 0;
 34         nodes[i].indegree = 0;
 35     }
 36     times = 0;
 37     outzero = 0;
 38     mins = 0;
 39     memset(childs,0,sizeof(childs));
 40     memset(low,0,sizeof(low));
 41     memset(dfn,0,sizeof(dfn));
 42     memset(nodes,0,sizeof(nodes));
 43     while(!stacks.empty()){
 44         stacks.pop();
 45     }
 46 }
 47 
 48 void targan(int n){
 49     times ++;
 50     dfn[n] = times;
 51     low[n] = times;
 52     stacks.push(n);
 53     nodes[n].asked = 1;
 54     nodes[n].instack = 1;
 55     int child;
 56     mins = dfn[n];
 57     for (int i = 0;i < nodes[n].size;i ++){
 58         child = childs[n][i];
 59         nodes[child].father = n;
 60         if (nodes[child].instack){
 61             mins = std::min(mins ,dfn[child]);
 62             mins = std::min(mins ,low[child]);
 63             low[n] = mins;
 64         }
 65         if (!nodes[child].asked){
 66             targan(child);
 67         }
 68     }
 69     int father = nodes[n].father;
 70     mins = low[father];
 71     mins = std::min(mins ,dfn[n]);
 72     mins = std::min(mins ,low[n]);
 73     low[father] = mins;
 74     if (dfn[n] == low[n]){
 75         int nod;
 76         bool isout = false;
 77         while(1){
 78             nod = stacks.top();
 79             stacks.pop();
 80             nodes[nod].instack = 0;
 81             int size = nodes[nod].size;
 82             int chil;
 83             for (int k = 0;k < size;k ++){
 84                 chil = childs[nod][k];
 85                 if (low[chil] != low[nod]){
 86                     isout = true;
 87                 }
 88             }
 89             if (nod == n) break;
 90         }
 91         if (!isout){
 92             outzero ++;
 93         }
 94     }
 95 }
 96 
 97 bool judge(){
 98     if (outzero >= 2){
 99         return false;
100     }
101     return true;
102 }
103 
104 int main(){
105     freopen("SD_3231_Thralls_Dream.in","r",stdin);
106     int amount;
107     scanf("%d",&amount);
108     for (int i = 1;i <= amount;i ++){
109         scanf("%d %d",&nodeAmount,&edgeAmount);
110         init();
111         int from,to;
112         for (int j = 0;j < edgeAmount;j ++){
113             scanf("%d %d",&from,&to);
114             int size = nodes[from].size;
115             childs[from][size++] = to;
116             nodes[from].size = size;
117             nodes[to].indegree ++;
118         }
119         for (int k = 1;k <= nodeAmount;k ++){
120             if (!nodes[k].asked){
121                 targan(k);
122             }
123         }
124         if (judge()) {
125             printf("Case %d: Kalimdor is just ahead
", i);
126         } else {
127             printf("Case %d: The Burning Shadow consume us all
",i);
128         }
129     }
130     return 0;
131 }

View Code

C、A^X mod P

f(x) = K, x = 1，f(x) = (a*f(x-1) + b)%m , x > 1，求( A^(f(1)) + A^(f(2)) + A^(f(3)) + ...... + A^(f(n)) ) modular P. 1 <= n <= 10^6，0 <= A, K, a, b <= 10^9，1 <= m, P <= 10^9

10^9无论从空间还是时间上都是不可行的，所以简单的计算绝对不行，A^(10^9)我们可以预处理一下，求A^(ki+j)直接将10^9的复杂度降了一个平方。只需求出A^k即可

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <iostream>
 4 
 5 #ifndef SYMBOL
 6 #define MAXK 100005
 7 #endif
 8 
 9 typedef long long ll;
10 
11 using namespace std;
12 /*
13 合理的运用%的特性
14 预处理(A^1~n)%P次方
15 */
16 
17 ll n, A, K, a, b, m, P;
18 ll pre1[MAXK+1],pre2[MAXK+1];
19 
20 void init(){
21     pre1[0] = pre2[0] = 1LL;
22     for (int i = 1;i <= MAXK;i ++){
23         pre1[i] = A*pre1[i-1]%P;
24     }
25     for (int i = 1;i <= MAXK;i ++){
26         pre2[i] = pre2[i-1]*pre1[MAXK]%P;
27     }
28 }
29 
30 ll gao(){
31     ll res = 0,t = K;
32     for (int i = 1;i <= n;i ++){
33         res = (res + pre2[t/MAXK]*pre1[t%MAXK])%P;
34         t = (a*t + b)%m;
35     }
36     return res;
37 }
38 
39 int main(int argc, char const *argv[])
40 {
41     freopen("SD_3232_AX_mod_P.in","r",stdin);
42     int test;
43     scanf("%d",&test);
44     for (int i = 1;i <= test;i ++){
45         scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&A,&K,&a,&b,&m,&P);
46         init();
47         printf("Case #%d: %lld
", i,gao());
48     }
49     return 0;
50 }

View Code

D、Rubik’s cube

求将一个两色四方格旋转致每面都是同一颜色的最小步数。

直接模拟旋转魔方进行bfs，魔方可以前后，左右，上下共有12种旋转方案，一面的向前旋转和另一面的向后旋转是同一效果，除以2剩6种旋转可能，向后旋转一下相当于向前旋转3下，除以2剩3种可能的旋转方案，再依次对三种旋转进行bfs

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm> 
  4 #include <queue>
  5 #include <map>
  6 
  7 #ifndef SYMBOL
  8 #define CUBE 24
  9 #define ONLINE_JUDGE 1
 10 #endif
 11 
 12 using namespace std;
 13 
 14 struct node
 15 {
 16     int cu[CUBE];
 17     int step;
 18 };
 19 
 20 node start;
 21 queue<node> que;
 22 map<int,int> myhash;
 23 int rode[6][8] = {
 24     {4,6,17,16,15,13,9,8},
 25     {1,3,2,0},
 26     {1,3,17,19,22,20,10,8},
 27     {4,6,7,5},
 28     {0,1,4,5,20,21,12,13},
 29     {9,8,10,11}
 30 };
 31 
 32 void turn(node & n,int face){
 33     face<<=1;
 34     int t = n.cu[rode[face][0]];
 35     for (int i = 0;i < 7;i ++){
 36         n.cu[rode[face][i]] = n.cu[rode[face][i+1]];
 37     }
 38     n.cu[rode[face][7]] = t;
 39     t = n.cu[rode[face][0]];
 40     for (int i = 0;i < 7;i ++){
 41         n.cu[rode[face][i]] = n.cu[rode[face][i+1]];
 42     }
 43     n.cu[rode[face][7]] = t;
 44     face ++;
 45     t = n.cu[rode[face][0]];
 46     for (int i = 0;i < 3;i ++){
 47         n.cu[rode[face][i]] = n.cu[rode[face][i+1]];
 48     }
 49     n.cu[rode[face][3]] = t;
 50 }
 51 
 52 int myhashCode(const node n){
 53     int res = 0;
 54     for (int i = 0;i < 24;i ++){
 55         res = n.cu[i] + (res<<1);
 56     }
 57     return res;
 58 }
 59 
 60 bool isOK(const node n){
 61     for (int i = 0;i < 24;i += 4){
 62         for (int j = 1;j <= 3;j ++){
 63             if (n.cu[i] != n.cu[i+j]){
 64                 return false;
 65             }
 66         }
 67     }
 68     return true;
 69 }
 70 
 71 int bfs(){
 72     int red = 0;
 73     for (int i = 0;i < 24;i ++){
 74         if (start.cu[i] == 0){
 75             red ++;
 76         }
 77     }
 78     if (red%4 != 0){
 79         return -1;
 80     }
 81     if (isOK(start)){
 82         return start.step;
 83     }
 84     myhash.clear();
 85     while(!que.empty()) que.pop();
 86     myhash[myhashCode(start)] = 1;
 87     que.push(start);
 88     node s,t;
 89     while(!que.empty()){
 90         s = que.front();
 91         que.pop();
 92         for (int i = 0;i < 3;i ++){
 93             t = s;
 94             t.step ++;
 95             turn(t,i);
 96             if (myhash.find(myhashCode(t)) == myhash.end()){
 97                 if (isOK(t)){
 98                     return t.step;
 99                 }
100                 myhash[myhashCode(t)] = 1;
101                 que.push(t);
102             }
103             turn(t,i);
104             turn(t,i);
105             if (myhash.find(myhashCode(t)) == myhash.end()){
106                 if (isOK(t)){
107                     return t.step;
108                 }
109                 myhash[myhashCode(t)] = 1;
110                 que.push(t);
111             }
112         }
113     }
114     return -1;
115 }
116 
117 int main(int argc, char const *argv[])
118 {
119     #ifndef ONLINE_JUDGE
120     freopen("SD_3232_Rubiks_cube.in","r",stdin);
121     #endif
122     int test;
123     scanf("%d",&test);
124     while(test--){
125         for (int i = 0;i < 24;i ++){
126             scanf("%d",&start.cu[i]);
127         }
128         start.step = 0;
129         int res = bfs();
130         if (res == -1) printf("IMPOSSIBLE!
");
131         else printf("%d
", res);
132     }
133     return 0;
134 }

View Code

E、Mountain Subsequences

在一个数字序列中求山脉序列的个数 a1 < ...< ai < ai+1 < Amax > aj > aj+1 > ... > an

找出比当前数字前面并比当前数字小的数进行dp

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define MAX 100000
 5 #define MOD 2012
 6 using namespace std;
 7 //cnt记录单个字符的个数，dp记录以此字母结束的个数
 8 int leng,up[MAX],down[MAX],dp[26],cnt[26],t;
 9 char str[MAX];
10 int main() {
11     freopen("SD_3234_Mountain_Subsequences.in","r",stdin);
12     while(~scanf("%d",&leng)){
13         scanf("%s",str);
14         memset(up,0,sizeof(up));
15         memset(down,0,sizeof(down));
16         memset(dp,0,sizeof(dp));
17         memset(cnt,0,sizeof(cnt));
18         for (int i = 0;i < leng;i ++){
19             t = str[i] - 'a';
20             for (int j = 0;j < t;j ++){
21                 up[i] += dp[j] + cnt[j];
22                 up[i] %= MOD;
23             }
24             cnt[t] ++;
25             cnt[t] %= MOD;
26             dp[t] += up[i];
27             dp[t] %= MOD;
28         }
29         memset(dp,0,sizeof(dp));
30         memset(cnt,0,sizeof(cnt));
31         for (int i = leng-1;i >= 0;i --){
32             t = str[i] - 'a';
33             for (int j = 0;j < t;j ++){
34                 down[i] += dp[j] + cnt[j];
35                 down[i] %= MOD;
36             }
37             cnt[t] ++;
38             cnt[t] %= MOD;
39             dp[t] += down[i];
40             dp[t] %= MOD;
41         }
42         int sum = 0;
43         for (int i = 1;i < leng-1;i ++){
44             sum += up[i]*down[i];
45             sum %= MOD;
46         }
47         printf("%d
", sum);
48     }
49     return 0;
50 }

View Code

F、Alice and Bob

(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)，求x^P的系数

1 <= P <= 2^0+2^1+2^2+.....+2^(n-1)，二次项有个性质2^0+2^1+......+2^(n-1)<2^n，所以可以推断出P只能由唯一的二次项系数构成。将P的二进制求出来，将其中值为1的项的系数相乘即为结果。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cmath>
 4 #include <cstring>
 5 
 6 #ifndef SYMBOL
 7 #define MAX 55
 8 #endif
 9 
10 using namespace std;
11 /*
12 定理：一个数只能由2的多项式中唯一的序列构成2^0 2^1 2^2 2^3 2^4 ,7只能由2^0 2^1 2^2构成
13 */
14 
15 typedef long long ll;
16 
17 int n,dex;
18 int co[MAX],binary[MAX];
19 
20 void getBinary(ll number){
21     memset(binary,0,sizeof(binary));
22     dex = 0;
23     while(number){
24         binary[dex++] = number%2LL;
25         number /= 2LL;
26     }
27 }
28 
29 int calcu(ll P){
30     if (P == 0LL){
31         return 1;//一定要考虑极限问题
32     }
33     ll max = 0;
34     for (int i = 0;i < n;i ++){
35         max += pow(2LL,i);
36     }
37     if (P > max){
38         return 0;//一定要考虑极限问题
39     }
40     getBinary(P);
41     int sum = 1;
42     for (int i = 0;i < dex;i ++){
43         if (binary[i]){
44             sum *= co[i];
45             sum %= 2012;
46         }
47     }
48     return sum;
49 }
50 
51 int main(int argc, char const *argv[])
52 {
53     // freopen("SD_3235_Alice_and_Bob.in","r",stdin);
54     // freopen("SD_3235_Alice_and_Bob.out","w",stdout);
55     int test,ques;
56     ll P;
57     scanf("%d",&test);
58     while(test--){
59         scanf("%d",&n);
60         for (int i = 0;i < n;i ++){
61             scanf("%d",&co[i]);
62         }
63         scanf("%d",&ques);
64         while(ques--){
65             scanf("%lld",&P);
66             printf("%d
",calcu(P));
67         }
68     }
69     return 0;
70 }

View Code

G、A-Number and B-Number

可以被7整除或包含7的为A数字，A数字中下标为A数字的除外其余为B数字，求第n个B数字。

对位数进行dp

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 
 5 #ifndef SYMBOL
 6 #define MAX 25
 7 #endif
 8 
 9 /*
10 位数动态规划,设定最大25位,dp的方式有很多
11 */
12 using namespace std;
13 
14 typedef unsigned long long ull;
15 
16 ull number;
17 ull dp[MAX][7][2];
18 int bits[MAX];
19 
20 ull dfs(int d,int mod7,int have7,bool limit){
21     if (!d){
22         return (!mod7 || have7);
23     }
24     if (!limit && ~dp[d][mod7][have7]){
25         return dp[d][mod7][have7];
26     }
27     int mn = 9;
28     if (limit){
29         mn = bits[d];
30     }
31     ull sum = 0ULL;
32     for (int i = 0;i <= mn;i ++){
33         int tmod7 = (10*mod7+i)%7;
34         int thave7 = have7 || (i == 7);
35         sum += dfs(d-1,tmod7,thave7,(i == mn) && limit);
36     }
37     if (!limit){
38         dp[d][mod7][have7] = sum;
39     }
40     return sum;
41 }
42 
43 ull AAmount(ull n){
44     int dex = 0;
45     while(n){
46         bits[++dex] = n%10;
47         n/=10;
48     }
49     return dfs(dex,0,0,true)-1;
50 }
51 
52 ull twoSplite(){
53     ull l = 7ULL,r = (1ULL<<63) - 1,m;
54     while(l <= r){
55         m = (l+r)>>1;
56         ull amount = AAmount(m);
57         amount = amount - AAmount(amount);
58         if (amount < number){
59             l = m+1;
60         }else {
61             r = m-1;
62         }
63         //注意这里==不能返回
64     }
65     return l;
66 }
67 
68 int main(int argc, char const *argv[])
69 {
70     freopen("SD_3236_A-Number_and_B-Number.in","r",stdin);
71     memset(dp,-1,sizeof(dp));
72     while(~scanf("%llu",&number)){
73         printf("%llu
", twoSplite());
74     }
75     return 0;   
76 }

View Code

H、Boring Counting

求一定范围内一定大小范围内的数的个数。

采用线段树数据结构

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 
  5 #ifndef SYMBOL
  6 #define MAX 50005
  7 #endif
  8 
  9 /*无形的线段树*/
 10 using namespace std;
 11 
 12 struct num
 13 {
 14     int value;
 15     int dex;
 16     bool operator <(const num n) const {return value < n.value;};
 17 }nums[MAX];
 18 
 19 struct query
 20 {
 21     int l;
 22     int r;
 23     int a;
 24     int b;
 25     int dex;
 26 }querys[MAX];
 27 
 28 bool comp1(const query q1,const query q2) {
 29     return q1.a < q2.a;
 30 }
 31 
 32 bool comp2(const query q1,const query q2) {
 33     return q1.b < q2.b;
 34 }
 35 
 36 int nn,qn;
 37 int minsum[MAX<<2],ans[MAX][2];
 38 /*ans[MAX][0]记录比a小数的个数，ans[MAX][1]记录比b小数的个数，答案为ans[MAX][1]-ans[MAX][0]*/
 39 
 40 /*创建线段树,额外添加的问题值为在这个范围内的个数*/
 41 void build(int l,int r,int dex){
 42     if (l == r){
 43         minsum[dex] = 0;
 44         return ;
 45     }
 46     int m = (l+r)>>1;
 47     build(l,m,dex<<1);
 48     build(m+1,r,dex<<1|1);
 49     minsum[dex] = minsum[dex<<1] + minsum[dex<<1|1];
 50 }
 51 
 52 void update(int d,int l,int r,int dex){
 53     if (l == r){
 54         minsum[dex] ++;
 55         return ;
 56     }
 57     int m = (l+r)>>1;
 58     if (d <= m){
 59         update(d,l,m,dex<<1);
 60     }else{
 61         update(d,m+1,r,dex<<1|1);
 62     }
 63     minsum[dex] = minsum[dex<<1] + minsum[dex<<1|1];
 64 }
 65 
 66 int queryy(int ql,int qr,int l,int r,int dex){
 67     if (ql <= l && qr >= r){
 68         return minsum[dex];
 69     }
 70     int m = (l+r)>>1;
 71     int res = 0;
 72     if (ql <= m){
 73         res += queryy(ql,qr,l,m,dex<<1);
 74     }
 75     if (qr > m){
 76         res += queryy(ql,qr,m+1,r,dex<<1|1);
 77     }
 78     return res;
 79 }
 80 
 81 void calculate(){
 82     build(1,nn,1);
 83     sort(nums+1,nums+nn+1);
 84     sort(querys+1,querys+qn+1,comp1);
 85     int dd = 1;
 86     for (int j = 1;j <= qn;j ++){
 87         while(dd <= nn && nums[dd].value < querys[j].a){//注意这里等于不能包括在内
 88             update(nums[dd].dex,1,nn,1);
 89             dd++;
 90         }
 91         ans[querys[j].dex][0] = queryy(querys[j].l,querys[j].r,1,nn,1);
 92     }
 93     build(1,nn,1);
 94     sort(querys+1,querys+qn+1,comp2);
 95     dd = 1;
 96     for (int j = 1;j <= qn;j ++){
 97         while(dd <= nn && nums[dd].value <= querys[j].b){
 98             update(nums[dd].dex,1,nn,1);
 99             dd++;
100         }
101         ans[querys[j].dex][1] = queryy(querys[j].l,querys[j].r,1,nn,1);
102     }
103 }
104 
105 void print(int cases){
106     printf("Case #%d:
",cases);
107     for (int i = 1;i <= qn;i ++){
108         printf("%d
",ans[i][1]-ans[i][0]);
109     }
110 }
111 
112 int main(int argc, char const *argv[])
113 {
114     freopen("SD_3237_Boring_Counting.in","r",stdin);
115     int test;
116     scanf("%d",&test);
117     for (int i = 1;i <= test;i ++){
118         scanf("%d %d",&nn,&qn);
119         for (int j = 1;j <= nn;j ++){
120             scanf("%d",&nums[j].value);
121             nums[j].dex = j;
122         }
123         for (int j = 1;j <= qn;j ++){
124             scanf("%d %d %d %d",&querys[j].l,&querys[j].r,&querys[j].a,&querys[j].b);
125             querys[j].dex = j;
126         }
127         calculate();
128         print(i);
129     }
130     return 0;
131 }

View Code

I、The number of steps

递推

 1 #include <cstdio>
 2 #include <iostream>
 3 
 4 #define maxn 55
 5 
 6 using namespace std;
 7  
 8 double dp[maxn][maxn];
 9 
10 int main()
11 {
12     // freopen("SD_3238_The_number_of_steps.in","r",stdin);
13     int n;
14     while(scanf("%d",&n),n)
15     {
16         double a,b,c,d,e;
17         scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
18         dp[n][0]=0;
19         for(int i=1;i<=n;++i)
20             dp[n][i]=dp[n][i-1]+1.0;
21         for(int i=n-1;i>0;--i)
22         {
23             dp[i][0]=a*dp[i+1][0]+b*dp[i+1][1]+1.0;
24             for(int j=1;j<n;++j)
25                 dp[i][j]=c*dp[i+1][j]+d*dp[i+1][j+1]+e*dp[i][j-1]+1.0;
26         }
27         printf("%.2lf
",dp[1][0]);
28     }
29     return 0;
30 }

View Code

J、Contest Print Server

模拟

 1 #include <cstdio>
 2 #include <iostream>
 3 
 4 #ifndef SYMBOL
 5 #define MAX 100
 6 #endif
 7 
 8 using namespace std;
 9 
10 struct task
11 {
12     char name[30];
13     int page;
14 }tasks[MAX];
15 
16 int n,s,x,y,mod;
17 
18 
19 void print(){
20     int task = 0, sum = 0;
21     while(task < n){
22         if (sum == s){
23             printf("%d pages for %s
",0,tasks[task].name);
24             s=(s*x+y)%mod;
25             sum = 0;
26         }else if (sum + tasks[task].page <= s){
27             printf("%d pages for %s
",tasks[task].page,tasks[task].name);
28             sum += tasks[task].page;
29             task ++;
30         }else{
31             printf("%d pages for %s
",s - sum,tasks[task].name);
32             sum = 0;
33             s=(s*x+y)%mod;
34         }
35     }
36 }
37 
38 int main(int argc, char const *argv[])
39 {
40     // freopen("SD_3239_Contest Print_Server.in","r",stdin);
41     // freopen("SD_3239_Contest Print_Server.out","w",stdout);
42     int test;
43     scanf("%d",&test);
44     while(test--){
45         scanf("%d %d %d %d %d",&n,&s,&x,&y,&mod);
46         for (int i = 0;i < n;i ++){
47             scanf("%s request %d pages",tasks[i].name,&tasks[i].page);
48         }
49         print();
50         printf("
");
51     }
52     return 0;
53 }

View Code