fork(5) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. // Problem Description: 
  6. // Given a rope with length l, cut the rope into n sections
  7. // with length l[0], l[1], ..., l[n-1]. Please get the maximal
  8. // product of l[0] * l[1] * ... * l[n-1].
  9. // Please note that you have to cut once at least.
  10.  
  11. class Ideone
  12. {
  13. 	public static int maxProductAfterCutting_solution1(int length) {
  14. 		if(length < 2) {
  15. 			return 0;
  16. 		}
  17. 		if(length == 2) {
  18. 			return 1;
  19. 		}
  20. 		if(length == 3) {
  21. 			return 2;
  22. 		}
  23.  
  24. 		int[] products = new int[length + 1];
  25. 		products[0] = 0;
  26. 		products[1] = 1;
  27. 		products[2] = 2;
  28. 		products[3] = 3;
  29.  
  30. 		for(int i = 4; i <= length; ++i) {
  31. 			int max = 0;
  32. 			for(int j = 1; j <= i / 2; ++j) {
  33. 				int product = products[j] * products[i - j];
  34. 				if(max < product) {
  35. 					max = product;
  36. 				}
  37.  
  38. 				products[i] = max;
  39. 			}
  40. 		}
  41.  
  42. 		return products[length];
  43. 	}
  44.  
  45. 	public static int maxProductAfterCutting_solution2(int length) {
  46. 		if(length < 2) {
  47. 			return 0;
  48. 		}
  49. 		if(length == 2) {
  50. 			return 1;
  51. 		}
  52. 		if(length == 3) {
  53. 			return 2;
  54. 		}
  55.  
  56. 		int timesOf3 = length / 3;
  57. 		if((length - timesOf3 * 3) % 2 == 1) {
  58. 			timesOf3 -= 1;
  59. 		}
  60.  
  61. 		int timesOf2 = (length - timesOf3 * 3) / 2;
  62.  
  63. 		return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));
  64. 	}
  65.  
  66. 	//////////////////////////////////////////////////////////////
  67. 	// Test Code Begins
  68. 	//////////////////////////////////////////////////////////////
  69. 	private static void test(String testName, int length, int expected) {
  70. 		int result1 = maxProductAfterCutting_solution1(length);
  71. 		if(result1 == expected) {
  72. 			System.out.println("Solution1 for " + testName + " passed.");
  73. 		}
  74. 		else {
  75. 			System.out.println("Solution1 for " + testName + " FAILED.");
  76. 		}
  77.  
  78. 		int result2 = maxProductAfterCutting_solution2(length);
  79. 		if(result2 == expected) {
  80. 			System.out.println("Solution2 for " + testName + " passed.");
  81. 		}
  82. 		else {
  83. 			System.out.println("Solution2 for " + testName + " FAILED.");
  84. 		}
  85. 	}
  86.  
  87. 	private static void test1() {
  88. 		int length = 1;
  89. 		int expected = 0;
  90. 		test("test1", length, expected);
  91. 	}
  92.  
  93. 	private static void test2() {
  94. 		int length = 2;
  95. 		int expected = 1;
  96. 		test("test2", length, expected);
  97. 	}
  98.  
  99. 	private static void test3() {
  100. 		int length = 3;
  101. 		int expected = 2;
  102. 		test("test3", length, expected);
  103. 	}
  104.  
  105. 	private static void test4() {
  106. 		int length = 4;
  107. 		int expected = 4;
  108. 		test("test4", length, expected);
  109. 	}
  110.  
  111. 	private static void test5() {
  112. 		int length = 5;
  113. 		int expected = 6;
  114. 		test("test5", length, expected);
  115. 	}
  116.  
  117. 	private static void test6() {
  118. 		int length = 6;
  119. 		int expected = 9;
  120. 		test("test6", length, expected);
  121. 	}
  122.  
  123. 	private static void test7() {
  124. 		int length = 7;
  125. 		int expected = 12;
  126. 		test("test7", length, expected);
  127. 	}
  128.  
  129. 	private static void test8() {
  130. 		int length = 8;
  131. 		int expected = 18;
  132. 		test("test8", length, expected);
  133. 	}
  134.  
  135. 	private static void test9() {
  136. 		int length = 9;
  137. 		int expected = 27;
  138. 		test("test9", length, expected);
  139. 	}
  140.  
  141. 	private static void test10() {
  142. 		int length = 10;
  143. 		int expected = 36;
  144. 		test("test10", length, expected);
  145. 	}
  146.  
  147. 	public static void main (String[] args) {
  148. 		test1();
  149. 		test2();
  150. 		test3();
  151. 		test4();
  152. 		test5();
  153. 		test6();
  154. 		test7();
  155. 		test8();
  156. 		test9();
  157. 		test10();
  158. 	}
  159. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solution1 for test1 passed.
Solution2 for test1 passed.
Solution1 for test2 passed.
Solution2 for test2 passed.
Solution1 for test3 passed.
Solution2 for test3 passed.
Solution1 for test4 passed.
Solution2 for test4 passed.
Solution1 for test5 passed.
Solution2 for test5 passed.
Solution1 for test6 passed.
Solution2 for test6 passed.
Solution1 for test7 passed.
Solution2 for test7 passed.
Solution1 for test8 passed.
Solution2 for test8 passed.
Solution1 for test9 passed.
Solution2 for test9 passed.
Solution1 for test10 passed.
Solution2 for test10 passed.
https://ideone.com/wGvr86
Get the maximal product after cutting
language:
Java (HotSpot 12)
created:
11 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!