fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	static HashMap<String, Integer> map = new HashMap<String, Integer>();
  11.  
  12. 	public static void main(String[] args){
  13. 		new Ideone().run();
  14. 	}
  15.  
  16. 	static int[] arr = new int[3];
  17.  
  18. 	public void run(){
  19. 		arr[0] = 100;
  20. 		arr[1] = 100;
  21. 		arr[2] = 200;
  22. 		System.out.println(minCost(0, 4));
  23. 		printBestAllocation(0, 4, minCost(0, 4));
  24. 	}
  25.  
  26. 	static void printBestAllocation(int i, int n, int ans){
  27. 		if(i>=arr.length){
  28. 			return;
  29. 		}
  30. 		if(n<=0){
  31. 			throw new RuntimeException();
  32. 		}
  33.  
  34. 		int remainingCities = arr.length - i - 1;
  35. 		for(int place=1; place<=n-remainingCities; place++){
  36. 			if(arr[i] % place == 0){
  37. 				int ppl = Math.max(arr[i] / place, minCost(i+1, n-place));
  38. 				if(ppl == ans){
  39.  
  40. 					System.out.print(place + " ");
  41. 					printBestAllocation(i+1, n-place, minCost(i+1, n-place));
  42. 					return;
  43. 				}
  44. 			}else{
  45. 				int ppl = Math.max(arr[i] / place + 1, minCost(i+1, n-place));
  46. 				if(ppl==ans){
  47. 					System.out.print(place + " ");
  48. 					printBestAllocation(i+1, n-place, minCost(i+1, n-place));
  49. 					return;
  50. 				}
  51. 			}
  52. 		}
  53. 		throw new RuntimeException("Buggy code. If this exception is raised");
  54. 	}
  55.  
  56. 	static int minCost(int i, int n){
  57. 		if(i>=arr.length){
  58. 			return 0;
  59. 		}
  60. 		if(n<=0){
  61. 			throw new RuntimeException();
  62. 		}
  63. 		String s = i + " " + n;
  64. 		if(map.containsKey(s)){
  65. 			return map.get(s);
  66. 		}
  67. 		int remainingCities = arr.length - i - 1;
  68. 		int best = Integer.MAX_VALUE;
  69. 		for(int place=1; place<=n-remainingCities; place++){
  70. 			int ppl;
  71. 			if(arr[i] % place==0){
  72. 				ppl = Math.max(arr[i] / place, minCost(i+1, n-place));
  73. 			}else{
  74. 				ppl = Math.max(arr[i] / place + 1, minCost(i+1, n-place));
  75. 			}
  76. 			best = Math.min(best, ppl);
  77. 		}
  78. 		map.put(s, best);
  79. 		return best;
  80. 	}
  81. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
100
1 1 2
https://ideone.com/t83C0P
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

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!