fork(3) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // Number of ways to reduce score to 0 using n darts.
  5. int dartsGame(int ndarts, int total){
  6.  
  7. 	// Maximum score is 60 per dart, so any higher total is impossible.
  8. 	if(total > ndarts * 60) return 0;
  9.  
  10. 	// Final dart must land on double ring or bullseye
  11. 	if(ndarts == 1){
  12. 		if(total == 50) return 1;
  13. 		if(total <= 40 && total%2 == 0) return 1;
  14. 		return 0;
  15. 	}
  16.  
  17. 	// Try all possible scores for the current dart
  18. 	// Then recursively continue with 1 fewer darts.
  19. 	int count = 0;
  20. 	for(int score = 1; score <= 20; score++){
  21. 		count += dartsGame(ndarts-1, total - score);
  22. 		count += dartsGame(ndarts-1, total - 2*score);
  23. 		count += dartsGame(ndarts-1, total - 3*score);
  24. 	}
  25. 	// Bullseye
  26. 	count += dartsGame(ndarts-1, total - 50);
  27.  
  28. 	return count;
  29. }
  30.  
  31. int main() {
  32. 	cout << dartsGame(9, 501);
  33. 	return 0;
  34. }
Success #stdin #stdout 0.07s 4340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3944
https://ideone.com/ses6Jt
language:
C++ (gcc 8.3)
created:
6 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!