fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 2e18;  
  10.  
  11. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false; 
  15. }
  16.  
  17. const int MX = 1e5 + 5;  
  18.  
  19. ll h; 
  20. int a, b, c;  
  21.  
  22. struct Node {
  23. 	int r; ll d; 
  24. 	bool operator<(const Node& other) const {
  25. 		return d > other.d; 
  26. 	}
  27. };
  28.  
  29. // Với những tầng u đến được, ta xét giá trị u % a
  30. // Khi đó nếu có 2 tầng u1, u2 sao cho u1 = u2 (mod a) và u1 < u2, từ u1 ta có thể đến u2 bằng cách spam nút a
  31. // => Với mỗi r từ 0 đến a - 1, ta cần biết tầng u nhỏ nhất có thể đến được sao cho u % a = r
  32.  
  33. // Từ đỉnh r ta có thể đến được đỉnh (r + b) % a, (r + c) % a với trọng số của cạnh tương ứng là b và c 
  34. // (Lưu ý (r + a) % a = r nên ta không cần xét đỉnh này)
  35. // => Bài toán tìm đường đi ngắn nhất với đỉnh xuất phát là s = 1 % a
  36.  
  37. ll dist[MX]; // dist[r] = tầng u nhỏ nhất đến được sao cho u % a = r và chỉ dùng các nút bấm b và c
  38. 			 //           hay đường đi ngắn ngắn từ s đến r
  39.  
  40. void dijkstra(int s) {
  41. 	for (int r = 0; r < a; r++) dist[r] = LINF; 
  42.  
  43. 	priority_queue<Node> pq;
  44. 	dist[s] = 1;   
  45. 	pq.push({s, dist[s]});  
  46.  
  47. 	while (!pq.empty()) {
  48. 		Node front = pq.top(); pq.pop();  
  49. 		int r = front.r; ll d = front.d; 
  50.  
  51. 		if (d > dist[r]) continue;  
  52.  
  53. 		for (int w : {b, c}) {
  54. 			int nxt_r = (r + w) % a;   
  55. 			if (minimize(dist[nxt_r], dist[r] + w)) {
  56. 				pq.push({nxt_r, dist[nxt_r]});  
  57. 			}
  58. 		}
  59. 	}
  60. }
  61.  
  62. int main() {
  63. 	ios::sync_with_stdio(false); 
  64. 	cin.tie(nullptr); 	
  65. 	cin >> h; 
  66. 	cin >> a >> b >> c;
  67.  
  68. 	dijkstra(1 % a);  
  69.  
  70. 	ll ans = 0;   
  71. 	for (int r = 0; r < a; r++) {
  72. 		ll u = dist[r]; 
  73. 		if (u > h) continue;  
  74. 		ll cnt = (h - u) / a + 1;  
  75. 		ans += cnt;  
  76. 	}
  77.  
  78. 	cout << ans << '\n'; 
  79. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
15
4 7 9
stdout
copy 
9
https://ideone.com/lcDeK4
language:
C++14 (gcc 8.3)
created:
286 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!