0
Your rating: None

CodeChef submission 63171 (C++ 4.0.0-8)

CodeChef submission 63171 (C++ 4.0.0-8) plaintext list. Status: WA, problem F5, contest AUG09. By gmark (Mark Greve), 2009-08-03 05:51:37.
  1. // Magic Sequence
  2. // Source: CodeChef August 2009 Algorithm Challenge
  3. // CodeChef ID: F5
  4. // Date: 03-08-2009
  5. // Author: Mark Greve
  6.  
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cassert>
  10. #include <cctype>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <ctime>
  16. #include <deque>
  17. #include <functional>
  18. #include <iomanip>
  19. #include <iostream>
  20. #include <list>
  21. #include <map>
  22. #include <numeric>
  23. #include <queue>
  24. #include <set>
  25. #include <sstream>
  26. #include <stack>
  27. #include <string>
  28. #include <utility>
  29. #include <vector>
  30. using namespace std;
  31.  
  32. typedef long long LL;
  33. const LL MOD=1000000;
  34. vector<LL> a, b, d;
  35. LL p,q;
  36.  
  37. LL calcA(const vector<LL>& prev) {
  38. 	LL res = 0;
  39. 	for (int i=0;i<p;++i)
  40. 		res = (res + prev[prev.size()-1-i]*a[i])%MOD;
  41. 	return res;
  42. }
  43.  
  44. LL next(const vector<LL>& prev) {
  45. 	LL ret = calcA(prev);
  46. 	//printf("RET: %lld\n", ret);
  47. 	if (q==0) return ret;
  48. 	vector<LL> pprev = prev; pprev.pop_back();
  49. 	LL oo = calcA(pprev);
  50. 	ret = (ret - d[0]*(oo - prev.back()))%MOD;
  51. 	for (int i=1;i<q;++i) {
  52. 		//cout << "RET BEF " << ret << endl;
  53. 		ret = (ret - (d[i]-d[i-1])*(oo - prev.back()))%MOD;
  54. 		//cout << "RET NOW " << ret << endl;
  55. 	}
  56. 	if (ret<0) ret += MOD;
  57. 	return ret;
  58. }
  59.  
  60. int main() {
  61. 	while (2==scanf("%d %d", &p, &q)) {
  62. 		assert(!(p==0 && q==0));
  63. 		a = vector<LL>(p);
  64. 		b = vector<LL>(q);
  65. 		d = vector<LL>(q);
  66. 		for (int i=0;i<p;++i) scanf("%lld", &a[i]);
  67. 		for (int i=0;i<q;++i) scanf("%lld", &b[i]);
  68. 		for (int i=0;i<q;++i) scanf("%lld", &d[i]);
  69. 		
  70. 		vector<LL> newb, newd;
  71. 		for (int i=0;i<q;++i) {
  72. 			if (b[i]==0 || d[i]==0) continue;
  73. 			newb.push_back(b[i]);
  74. 			newd.push_back(d[i]);
  75. 		}
  76. 		b = newb, d = newd, q = newb.size();
  77.  
  78. 		vector<LL> prev(10);
  79. 		for (int i=0;i<10;++i) {
  80. 			scanf("%lld", &prev[i]);
  81. 			//printf("%lld\n", prev[i]);
  82. 		}
  83.  
  84. 		for (int i=0;i<10;++i) {
  85. 			if (i!=0) printf(" ");
  86. 			LL t = next(prev);
  87. 			prev.erase(prev.begin());
  88. 			prev.push_back(t);
  89. 			assert(t>=0);
  90. 			printf("%lld", t);
  91. 		}
  92. 	}
  93. }
  94.

Comments