import java.util.* ;
import java.lang.* ;
import java.io.* ;
// Problem Description:
// Given a rope with length l, cut the rope into n sections
// with length l[0], l[1], ..., l[n-1]. Please get the maximal
// product of l[0] * l[1] * ... * l[n-1].
// Please note that you have to cut once at least.
class Ideone
{
public static int maxProductAfterCutting_solution1( int length) {
if ( length < 2 ) {
return 0 ;
}
if ( length == 2 ) {
return 1 ;
}
if ( length == 3 ) {
return 2 ;
}
int [ ] products = new int [ length + 1 ] ;
products[ 0 ] = 0 ;
products[ 1 ] = 1 ;
products[ 2 ] = 2 ;
products[ 3 ] = 3 ;
for ( int i = 4 ; i <= length; ++ i) {
int max = 0 ;
for ( int j = 1 ; j <= i / 2 ; ++ j) {
int product = products[ j] * products[ i - j] ;
if ( max < product) {
max = product;
}
products[ i] = max;
}
}
return products[ length] ;
}
public static int maxProductAfterCutting_solution2( int length) {
if ( length < 2 ) {
return 0 ;
}
if ( length == 2 ) {
return 1 ;
}
if ( length == 3 ) {
return 2 ;
}
int timesOf3 = length / 3 ;
if ( ( length - timesOf3 * 3 ) % 2 == 1 ) {
timesOf3 -= 1 ;
}
int timesOf2 = ( length - timesOf3 * 3 ) / 2 ;
return ( int ) ( Math .
pow ( 3 , timesOf3
) ) * ( int ) ( Math .
pow ( 2 , timesOf2
) ) ; }
//////////////////////////////////////////////////////////////
// Test Code Begins
//////////////////////////////////////////////////////////////
private static void test
( String testName,
int length,
int expected
) { int result1 = maxProductAfterCutting_solution1( length) ;
if ( result1 == expected) {
System .
out .
println ( "Solution1 for " + testName
+ " passed." ) ; }
else {
System .
out .
println ( "Solution1 for " + testName
+ " FAILED." ) ; }
int result2 = maxProductAfterCutting_solution2( length) ;
if ( result2 == expected) {
System .
out .
println ( "Solution2 for " + testName
+ " passed." ) ; }
else {
System .
out .
println ( "Solution2 for " + testName
+ " FAILED." ) ; }
}
private static void test1( ) {
int length = 1 ;
int expected = 0 ;
test( "test1" , length, expected) ;
}
private static void test2( ) {
int length = 2 ;
int expected = 1 ;
test( "test2" , length, expected) ;
}
private static void test3( ) {
int length = 3 ;
int expected = 2 ;
test( "test3" , length, expected) ;
}
private static void test4( ) {
int length = 4 ;
int expected = 4 ;
test( "test4" , length, expected) ;
}
private static void test5( ) {
int length = 5 ;
int expected = 6 ;
test( "test5" , length, expected) ;
}
private static void test6( ) {
int length = 6 ;
int expected = 9 ;
test( "test6" , length, expected) ;
}
private static void test7( ) {
int length = 7 ;
int expected = 12 ;
test( "test7" , length, expected) ;
}
private static void test8( ) {
int length = 8 ;
int expected = 18 ;
test( "test8" , length, expected) ;
}
private static void test9( ) {
int length = 9 ;
int expected = 27 ;
test( "test9" , length, expected) ;
}
private static void test10( ) {
int length = 10 ;
int expected = 36 ;
test( "test10" , length, expected) ;
}
public static void main
( String [ ] args
) { test1( ) ;
test2( ) ;
test3( ) ;
test4( ) ;
test5( ) ;
test6( ) ;
test7( ) ;
test8( ) ;
test9( ) ;
test10( ) ;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovLyBQcm9ibGVtIERlc2NyaXB0aW9uOiAKLy8gR2l2ZW4gYSByb3BlIHdpdGggbGVuZ3RoIGwsIGN1dCB0aGUgcm9wZSBpbnRvIG4gc2VjdGlvbnMKLy8gd2l0aCBsZW5ndGggbFswXSwgbFsxXSwgLi4uLCBsW24tMV0uIFBsZWFzZSBnZXQgdGhlIG1heGltYWwKLy8gcHJvZHVjdCBvZiBsWzBdICogbFsxXSAqIC4uLiAqIGxbbi0xXS4KLy8gUGxlYXNlIG5vdGUgdGhhdCB5b3UgaGF2ZSB0byBjdXQgb25jZSBhdCBsZWFzdC4KCmNsYXNzIElkZW9uZQp7CglwdWJsaWMgc3RhdGljIGludCBtYXhQcm9kdWN0QWZ0ZXJDdXR0aW5nX3NvbHV0aW9uMShpbnQgbGVuZ3RoKSB7CgkJaWYobGVuZ3RoIDwgMikgewoJCQlyZXR1cm4gMDsKCQl9CgkJaWYobGVuZ3RoID09IDIpIHsKCQkJcmV0dXJuIDE7CgkJfQoJCWlmKGxlbmd0aCA9PSAzKSB7CgkJCXJldHVybiAyOwoJCX0KCQkKCQlpbnRbXSBwcm9kdWN0cyA9IG5ldyBpbnRbbGVuZ3RoICsgMV07CgkJcHJvZHVjdHNbMF0gPSAwOwoJCXByb2R1Y3RzWzFdID0gMTsKCQlwcm9kdWN0c1syXSA9IDI7CgkJcHJvZHVjdHNbM10gPSAzOwoKCQlmb3IoaW50IGkgPSA0OyBpIDw9IGxlbmd0aDsgKytpKSB7CgkJCWludCBtYXggPSAwOwoJCQlmb3IoaW50IGogPSAxOyBqIDw9IGkgLyAyOyArK2opIHsKCQkJCWludCBwcm9kdWN0ID0gcHJvZHVjdHNbal0gKiBwcm9kdWN0c1tpIC0gal07CgkJCQlpZihtYXggPCBwcm9kdWN0KSB7CgkJCQkJbWF4ID0gcHJvZHVjdDsKCQkJCX0KCgkJCQlwcm9kdWN0c1tpXSA9IG1heDsKCQkJfQoJCX0KCQkKCQlyZXR1cm4gcHJvZHVjdHNbbGVuZ3RoXTsKCX0KCglwdWJsaWMgc3RhdGljIGludCBtYXhQcm9kdWN0QWZ0ZXJDdXR0aW5nX3NvbHV0aW9uMihpbnQgbGVuZ3RoKSB7CgkJaWYobGVuZ3RoIDwgMikgewoJCQlyZXR1cm4gMDsKCQl9CgkJaWYobGVuZ3RoID09IDIpIHsKCQkJcmV0dXJuIDE7CgkJfQoJCWlmKGxlbmd0aCA9PSAzKSB7CgkJCXJldHVybiAyOwoJCX0KCQkKCQlpbnQgdGltZXNPZjMgPSBsZW5ndGggLyAzOwoJCWlmKChsZW5ndGggLSB0aW1lc09mMyAqIDMpICUgMiA9PSAxKSB7CgkJCXRpbWVzT2YzIC09IDE7CgkJfQoJCQoJCWludCB0aW1lc09mMiA9IChsZW5ndGggLSB0aW1lc09mMyAqIDMpIC8gMjsKCQkKCQlyZXR1cm4gKGludCkoTWF0aC5wb3coMywgdGltZXNPZjMpKSAqIChpbnQpKE1hdGgucG93KDIsIHRpbWVzT2YyKSk7Cgl9CgoJLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCS8vIFRlc3QgQ29kZSBCZWdpbnMKCS8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCglwcml2YXRlIHN0YXRpYyB2b2lkIHRlc3QoU3RyaW5nIHRlc3ROYW1lLCBpbnQgbGVuZ3RoLCBpbnQgZXhwZWN0ZWQpIHsKCQlpbnQgcmVzdWx0MSA9IG1heFByb2R1Y3RBZnRlckN1dHRpbmdfc29sdXRpb24xKGxlbmd0aCk7CgkJaWYocmVzdWx0MSA9PSBleHBlY3RlZCkgewoJCQlTeXN0ZW0ub3V0LnByaW50bG4oIlNvbHV0aW9uMSBmb3IgIiArIHRlc3ROYW1lICsgIiBwYXNzZWQuIik7CgkJfQoJCWVsc2UgewoJCQlTeXN0ZW0ub3V0LnByaW50bG4oIlNvbHV0aW9uMSBmb3IgIiArIHRlc3ROYW1lICsgIiBGQUlMRUQuIik7CgkJfQoJCQoJCWludCByZXN1bHQyID0gbWF4UHJvZHVjdEFmdGVyQ3V0dGluZ19zb2x1dGlvbjIobGVuZ3RoKTsKCQlpZihyZXN1bHQyID09IGV4cGVjdGVkKSB7CgkJCVN5c3RlbS5vdXQucHJpbnRsbigiU29sdXRpb24yIGZvciAiICsgdGVzdE5hbWUgKyAiIHBhc3NlZC4iKTsKCQl9CgkJZWxzZSB7CgkJCVN5c3RlbS5vdXQucHJpbnRsbigiU29sdXRpb24yIGZvciAiICsgdGVzdE5hbWUgKyAiIEZBSUxFRC4iKTsKCQl9Cgl9CgkKCXByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDEoKSB7CgkJaW50IGxlbmd0aCA9IDE7CgkJaW50IGV4cGVjdGVkID0gMDsKCQl0ZXN0KCJ0ZXN0MSIsIGxlbmd0aCwgZXhwZWN0ZWQpOwoJfQoJCglwcml2YXRlIHN0YXRpYyB2b2lkIHRlc3QyKCkgewoJCWludCBsZW5ndGggPSAyOwoJCWludCBleHBlY3RlZCA9IDE7CgkJdGVzdCgidGVzdDIiLCBsZW5ndGgsIGV4cGVjdGVkKTsKCX0KCQoJcHJpdmF0ZSBzdGF0aWMgdm9pZCB0ZXN0MygpIHsKCQlpbnQgbGVuZ3RoID0gMzsKCQlpbnQgZXhwZWN0ZWQgPSAyOwoJCXRlc3QoInRlc3QzIiwgbGVuZ3RoLCBleHBlY3RlZCk7Cgl9CgkKCXByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDQoKSB7CgkJaW50IGxlbmd0aCA9IDQ7CgkJaW50IGV4cGVjdGVkID0gNDsKCQl0ZXN0KCJ0ZXN0NCIsIGxlbmd0aCwgZXhwZWN0ZWQpOwoJfQoJCglwcml2YXRlIHN0YXRpYyB2b2lkIHRlc3Q1KCkgewoJCWludCBsZW5ndGggPSA1OwoJCWludCBleHBlY3RlZCA9IDY7CgkJdGVzdCgidGVzdDUiLCBsZW5ndGgsIGV4cGVjdGVkKTsKCX0KCQoJcHJpdmF0ZSBzdGF0aWMgdm9pZCB0ZXN0NigpIHsKCQlpbnQgbGVuZ3RoID0gNjsKCQlpbnQgZXhwZWN0ZWQgPSA5OwoJCXRlc3QoInRlc3Q2IiwgbGVuZ3RoLCBleHBlY3RlZCk7Cgl9CgkKCXByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDcoKSB7CgkJaW50IGxlbmd0aCA9IDc7CgkJaW50IGV4cGVjdGVkID0gMTI7CgkJdGVzdCgidGVzdDciLCBsZW5ndGgsIGV4cGVjdGVkKTsKCX0KCQoJcHJpdmF0ZSBzdGF0aWMgdm9pZCB0ZXN0OCgpIHsKCQlpbnQgbGVuZ3RoID0gODsKCQlpbnQgZXhwZWN0ZWQgPSAxODsKCQl0ZXN0KCJ0ZXN0OCIsIGxlbmd0aCwgZXhwZWN0ZWQpOwoJfQoJCglwcml2YXRlIHN0YXRpYyB2b2lkIHRlc3Q5KCkgewoJCWludCBsZW5ndGggPSA5OwoJCWludCBleHBlY3RlZCA9IDI3OwoJCXRlc3QoInRlc3Q5IiwgbGVuZ3RoLCBleHBlY3RlZCk7Cgl9CgkKCXByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDEwKCkgewoJCWludCBsZW5ndGggPSAxMDsKCQlpbnQgZXhwZWN0ZWQgPSAzNjsKCQl0ZXN0KCJ0ZXN0MTAiLCBsZW5ndGgsIGV4cGVjdGVkKTsKCX0KCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgewoJCXRlc3QxKCk7CgkJdGVzdDIoKTsKCQl0ZXN0MygpOwoJCXRlc3Q0KCk7CgkJdGVzdDUoKTsKCQl0ZXN0NigpOwoJCXRlc3Q3KCk7CgkJdGVzdDgoKTsKCQl0ZXN0OSgpOwoJCXRlc3QxMCgpOwoJfQp9