0
Your rating: None

CodeChef submission 601289 (C++ 4.3.2)

CodeChef submission 601289 (C++ 4.3.2) plaintext list. Status: AC, problem CANDY, contest . By azizkhan (azizkhan), 2011-07-18 20:29:09.
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <set>
  5. #include <map>
  6. #include <vector>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstring>
  10. #include <queue>
  11. #include <stack>
  12. #include <algorithm>
  13. using namespace std;
  14.  
  15. const int maxn = 250000;
  16.  
  17. int a[100], b[100], c[100], P, Q, n;
  18. int q[500005], head, tail;
  19. bool used[500005];
  20.  
  21. int main() {
  22. 	scanf("%d", &n);
  23. 	int i, j, k;
  24. 	for (i = 0; i < n; ++i)
  25. 		scanf("%d%d", &a[i], &b[i]);
  26. 	scanf("%d%d", &P, &Q);		
  27. 	for (i = 0; i < n; ++i) {
  28. 		c[i] = a[i] * Q - b[i] * P;
  29. 	}
  30. 	
  31. 	q[tail++] = maxn;
  32. 	used[maxn] = 1;
  33. 	int res = 0;	
  34. 	bool found = false;
  35. 	while (head < tail) {
  36. 		++res;
  37. 		int size = tail - head;
  38. 		while (size--) {
  39. 			int u = q[head++];
  40. 			for (i = 0; i < n; ++i) {
  41. 				if (c[i] > 0 && u > maxn) continue;
  42. 				if (c[i] < 0 && u < maxn) continue;
  43. 				int v = u + c[i];
  44. 				if (v == maxn) {
  45. 					found = true;
  46. 					break;
  47. 				}
  48. 				if (!used[v]) {
  49. 					used[v] = 1;
  50. 					q[tail++] = v;					
  51. 				}
  52. 			}
  53. 			if (found) break;
  54. 		}
  55. 		if (found) break;
  56. 	}	
  57. 	if (found)
  58. 		printf("%d\n", res);
  59. 	else
  60. 		puts("-1");		
  61. 	return 0;		
  62. }
  63.  
  64.

Comments