fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <bitset>
  6. #include <stdio.h>
  7. #include <math.h>
  8. using namespace std;
  9. typedef std::vector<int> vi;
  10. typedef std::vector<pair<int, int> > vii;
  11. //----------Main source code -----------------//
  12. float d, cap, mpg, icost, sd[54], p[54], fuel, ans;
  13. int n;
  14. void rcr(int i){
  15. 	float tfuel =fuel, tcost = icost;
  16. 	fuel -= (sd[i]-sd[i-1])/mpg;
  17. 	if(fuel>0){
  18. 		//----end------//
  19. 		if(i==n+1){
  20. 			if(icost<ans) ans=icost;
  21. 			fuel=tfuel;
  22. 			icost=tcost;
  23. 			return;
  24. 		}
  25.  
  26. 		//Skips this station
  27. 		rcr(i+1);
  28. 		//or fuel up here
  29. 		icost+= floor(p[i]*(cap-fuel)+0.5)+200;
  30. 		fuel=cap;
  31. 		if(icost<ans)
  32. 			rcr(i+1);
  33. 	}
  34. 	fuel=tfuel;
  35. 	icost=tcost;
  36. }
  37. int main() {
  38. 	int t=1;
  39. 	while(cin>>d&&d>=0){
  40. 		cin>>cap>>mpg>>icost>>n;
  41. 		for(int i=1;i<=n;i++) cin>>sd[i]>>p[i];
  42. 		sd[n+1]=d;
  43. 		p[n+1]=sd[0]=0;
  44. 		fuel=cap;
  45. 		ans = 999999999;
  46. 		icost*=100;
  47. 		rcr(1);
  48. 		printf("Data Set #%d\nminimum cost = $%.2f\n",t++, ans/100);
  49. 	}
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
475.6
11.9 27.4 14.98 6
102.0 99.9
220.0 132.9
256.3 147.9
275.0 102.9
277.6 112.9
381.8 100.9
516.3
15.7 22.1 20.87 3
125.4 125.9
297.9 112.9
345.2 99.9
-1
stdout
copy 
Data Set #1
minimum cost = $27.31
Data Set #2
minimum cost = $38.09
https://ideone.com/EuOVJ0
recursive
language:
C++ (gcc 8.3)
created:
10 years 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!