a) Die Ackermann-Funktion wurde in der Fkt. int ackermanA(int,int)
implementiert. Für die Wertebereiche m = [0,3] und n = [0,9] arbeitet das
Prg. korrekt. Bei größeren Werten kommt es zu einem StackOverflowError,
da der Wert der Fkt. als auch die Rekursionstiefe vor allem mit steigendem m
sehr schnell steigt (m = 4 und n = 2 ergibt einen Wert mit über 19000 Stellen).
b) Die Fkt. int ackermanB(int,int,int,long) protokolliert die
Anzahl der Aufrufe und die Rekursionstiefe. Im Test können die Ausgaben
dieser Werte eingesehen werden (inkl. der Laufzeit). Die Anz. der max. Aufrufe
sowie die max. Rekursionstiefe kann übergeben werden, wird einer dieser
Grenzwerte überschritten, kommt es zu einer AckermanException.
c) Zur Performance-Verbesserung wurde die Zwischenspeicherung von Ergebnissen
in einem Array implementiert (in int ackermanC(int,int,int,long)).
Dieser Einbau führt zu einer Verbesserung des Wertebereiches von n = [0,11]
bei m = 3, bei n = 12 kommt es ebenfalls zu einem StackOverflowError.
Es wurde eine wesentliche Verringerung sowohl der Fkt.aufrufe als auch der Rekursionstiefe
festgestellt. Besonders bei "höheren" Werten konnte auch eine
Verbesserung der Laufzeit festgestellt werden (siehe Test).
/**
* Softwareentwicklung I - Exercise 9/1.
*
* Ackerman function realizied in three different versions.
* - First version is the simpliest one, it's only the general implemenation
* of the ackerman function.
* - The version B consists additionally of protocolling the recursion depth
* and counting of function calls as well as the possiblity to set a maximum
* number of function calls and a maximum recursion depth.
* - Version C is same as B beside the caching of ackerman results in an array.
* In-source comments are followed by the described code.
*
* @see AckermanException
* @author Daniel Brunthaler (0255054)
* @version 1.0
*/
public class Ackerman {
// the maximum recursino depth occured in ackermanB or ackermanC.
private static int recDepthMax = -1;
// counter for function calls of ackermanB or ackermanC.
private static long recCounter = -1;
// maximum number of function calls allowed in ackermanB or ackermanC.
// in case of exceeding a AckermanException is thrown.
private static long recCallMaxAllowed;
// counter for array accesses in ackermanC.
private static long arrayAccessCounter;
// maximum recursion depth allowed in ackermanB or ackermanC.
// in case of exceeding a AckermanException is thrown.
private static int recDepthMaxAllowed;
// for caching of ackerman results in ackermanC.
private static int[][] ackermanResult;
// maximum number of n values which are stored in the ackermanResult array.
private static final int ARRAY_MAX = 10000;
/**
* Simpliest (general) implementation of ackerman function.
* @param m of ackerman function A(m,n).
* @param n of ackerman function A(m,n).
* @return result of ackerman function A(m,n).
*/
public static final int ackermanA(int m, int n) {
if (m == 0) return n+1;
else if (n == 0) return ackermanA(m-1,1);
else return ackermanA(m-1,ackermanA(m,n-1));
}
/**
* By comparison to ackermanA consists additionally of protocolling
* the recursion depth and counting of function calls as well as the
* possiblity to set a maximum number of function calls and a maximum
* recursion depth.
* @param m of ackerman function A(m,n).
* @param n of ackerman function A(m,n).
* @param paramRecDepthMaxAllowed maximum recursion depth allowed,
* 0 for infinite.
* @param paramRecCallMaxAllowed maximum number of function calls
* allowed, 0 for infinite.
* @return result of ackerman function A(m,n).
* @throws AckermanException
*/
public static final int ackermanB(int m, int n,
int paramRecDepthMaxAllowed, long paramRecCallMaxAllowed)
throws AckermanException {
recCounter = 0;
recDepthMax = 0;
recDepthMaxAllowed = paramRecDepthMaxAllowed;
recCallMaxAllowed = paramRecCallMaxAllowed;
return ackermanBInt(m,n,0);
}
/**
* Internal method called by ackermanB.
* @see ackermanB(int,int,int,long).
* @throws AckermanException
*/
private static final int ackermanBInt(int m, int n, int recDepth)
throws AckermanException {
recCounter++;
if (recCallMaxAllowed != 0 &&
recCounter > recCallMaxAllowed) throw new AckermanException();
if (recDepth > recDepthMax) recDepthMax = recDepth;
if (recDepthMaxAllowed != 0 &&
recDepth > recDepthMaxAllowed) throw new AckermanException();
if (m == 0) return n+1;
else if (n == 0) return ackermanBInt(m-1,1,recDepth+1);
else return ackermanBInt(m-1,ackermanBInt(m,n-1,recDepth+1),recDepth+1);
}
/**
* By comparison to ackermanB consists additionally of caching results
* of the ackerman function (in the ackermanResult array).
* @param m of ackerman function A(m,n).
* @param n of ackerman function A(m,n).
* @param paramRecDepthMaxAllowed maximum recursion depth allowed,
* 0 for infinite.
* @param paramRecCallMaxAllowed maximum number of function calls
* allowed, 0 for infinite.
* @return result of ackerman function A(m,n).
* @throws AckermanException
*/
public static final int ackermanC(int m, int n,
int paramRecDepthMaxAllowed, long paramRecCallMaxAllowed)
throws AckermanException {
recCounter = 0;
arrayAccessCounter = 0;
recDepthMax = 0;
recDepthMaxAllowed = paramRecDepthMaxAllowed;
recCallMaxAllowed = paramRecCallMaxAllowed;
ackermanResult = new int[m+1][ARRAY_MAX+1];
// initializing of the ackermanResult array
for (int i_m = 0;i_m < ackermanResult.length;i_m++) {
for (int i_n = 0;i_n < ackermanResult[0].length;i_n++)
ackermanResult[i_m][i_n] = -1;
}
return ackermanCInt(m,n,0);
}
/**
* Internal method called by ackermanC.
* @see ackermanC(int,int,int,long).
* @throws AckermanException
*/
private static final int ackermanCInt(int m, int n, int recDepth)
throws AckermanException {
int result;
recCounter++;
if (recCallMaxAllowed != 0 &&
recCounter > recCallMaxAllowed) throw new AckermanException();
if (recDepth > recDepthMax) recDepthMax = recDepth;
if (recDepthMaxAllowed != 0 &&
recDepth > recDepthMaxAllowed) throw new AckermanException();
if (m == 0) result = n+1;
else if (n == 0)
if (ackermanResult[(int)m-1][1] >= 0) {
// cached result is used.
arrayAccessCounter++;
return ackermanResult[m-1][1];
} else {
result = ackermanCInt(m-1,1,recDepth+1);
}
else
if (n <= ARRAY_MAX && ackermanResult[m][n-1] >= 0 &&
ackermanResult[m][n-1] <= ARRAY_MAX)
if (ackermanResult[m-1][ackermanResult[m][n-1]] >= 0) {
// cached result is used.
arrayAccessCounter++;
return ackermanResult[m-1][ackermanResult[m][n-1]];
} else {
// cached result is used for second argument of ackermanC.
arrayAccessCounter++;
result = ackermanCInt(m-1,ackermanResult[m][n-1],
recDepth+1);
}
else result = ackermanCInt(m-1,ackermanCInt(m,n-1,recDepth+1),
recDepth+1);
if (n <= ARRAY_MAX)
ackermanResult[m][n] = result; // ackerman result is cached.
return result;
}
/**
* Recursion depth of last call of ackermanB or ackermanC.
* @return recursion depth of last call of ackermanB or ackermanC.
*/
public static long getRecursionDepth() {
return recDepthMax;
}
/**
* Number of function calls of ackermanB or ackermanC.
* last call of the recursion.
*/
public static long getNumberOfRecCalls() {
return recCounter;
}
/**
* Number of array accesses.
* @return number of array accesses in the last run of ackermanC.
*/
public static long getNumberOfArAccess() {
return arrayAccessCounter;
}
/**
* Test of ackerman functions version B and C. The test data is printed
* to System.out in form of a table. Output consists of m, n, result of
* the ackerman function, number of function calls, recursion depth and
* the runtime.
* Test output of version C consists additionally of the number of array
* accesses.
* @param args no arguments have to be given.
*/
public static void main(String[] args) {
int m,n;
java.util.Date begin,end;
String runtime, result;
String headerB =
"m n ackerman(m,n) calls depth runtime";
// 3 5 AE ? ? ?
//column 01234567890123456789012345678901234567890123456789012345678901234567890
// 10 20 30 40 50 60 70
String headerC =
"m n ackerman(m,n) calls depth runtime array accesses";
// 3 5 AE ? ? ?
//column 01234567890123456789012345678901234567890123456789012345678901234567890
// 10 20 30 40 50 60 70
IO.writeLn(headerB);
// Test of ackermanB.
for (int i_m = 0;i_m <= 3;i_m++) {
for (int i_n = 0;i_n <= 9;i_n++) {
IO.write(i_m + "",3);
IO.write(i_n + "",4);
begin = new java.util.Date();
try {
result = ackermanB(i_m,i_n,10000000,0) + "";
end = new java.util.Date();
} catch (AckermanException e) {
end = new java.util.Date();
result = "AE";
}
runtime = (end.getTime() - begin.getTime()) + "ms";
IO.write(result,15);
IO.write(getNumberOfRecCalls() + "",10);
IO.write(getRecursionDepth() + "",8);
IO.writeLn(runtime + "");
}
}
IO.writeLn("\n" + headerC);
// Test of ackermanC.
for (int i_m = 0;i_m <= 3;i_m++) {
for (int i_n = 0;i_n <= 11;i_n++) {
IO.write(i_m + "",3);
IO.write(i_n + "",4);
begin = new java.util.Date();
try {
result = ackermanC(i_m,i_n,10000000,0) + "";
end = new java.util.Date();
} catch (AckermanException e) {
end = new java.util.Date();
result = "AE";
}
runtime = (end.getTime() - begin.getTime()) + "ms";
IO.write(result,15);
IO.write(getNumberOfRecCalls() + "",10);
IO.write(getRecursionDepth() + "",8);
IO.write(runtime + "",9);
IO.writeLn(getNumberOfArAccess() + "");
}
}
}
}
/**
* Softwareentwicklung I - Exercise 9/1.
* Exception thrown in class Ackerman in case of exceeding maximum number
* of function calls or maximum recursion depth.
*
* @author Daniel Brunthaler (0255054)
* @version 1.0
*/
public class AckermanException extends Exception {
}
Der Test wurde in der main-Methode implementiert (siehe Source).
Es wurde für int ackermanB(int,int,int,long) der Wertebereich
m = [0,3] und n = [0,9] getestet. Hierbei werden Anz. der Fkt.aufrufe, Rekursionstiefe
sowie Laufzeit tabellarisch protokolliert. Der Test der Werte m = 4 und n =
0, welcher ebenfalls fehlerfrei möglich wäre, wurde der Einfachheit
halber gespart (ermöglicht den Test in zwei for-Schleifen).
Bei höheren Werten kommt es bei dieser Fkt. zu einem StackOverflowError.
Für int ackermanC(int,int,int,long) wurde der Wertebereich
m = [0,3] und n = [0,11] getestet. Der Test der Werte m = 4 und n = 0, welcher
ebenfalls fehlerfrei möglich wäre, wurde der Einfachheit halber gespart
(ermöglicht den Test in zwei for-Schleifen). Bei höheren
Werten kommt es bei dieser Fkt. ebenfalls zu einem StackOverflowError.
Zusätzlich zu den erwähnten Ausgaben wurden noch die Anz. der Array-Zugriffe
protokolliert. Es wird dadurch sehr gut veranschaulicht, welche Laufzeit-Verbesserungen
bei einer höhren Anz. von Array-Zugriffen gegenüber der Variante B
erzielt werden (Bsp. m = 3, n = 9).
Testausgabe
m n ackerman(m,n) calls depth runtime 0 0 1 1 0 0ms 0 1 2 1 0 0ms 0 2 3 1 0 0ms 0 3 4 1 0 0ms 0 4 5 1 0 0ms 0 5 6 1 0 0ms 0 6 7 1 0 0ms 0 7 8 1 0 0ms 0 8 9 1 0 0ms 0 9 10 1 0 0ms 1 0 2 2 1 0ms 1 1 3 4 2 0ms 1 2 4 6 3 0ms 1 3 5 8 4 0ms 1 4 6 10 5 0ms 1 5 7 12 6 0ms 1 6 8 14 7 0ms 1 7 9 16 8 0ms 1 8 10 18 9 0ms 1 9 11 20 10 0ms 2 0 3 5 3 0ms 2 1 5 14 5 0ms 2 2 7 27 7 0ms 2 3 9 44 9 0ms 2 4 11 65 11 0ms 2 5 13 90 13 0ms 2 6 15 119 15 0ms 2 7 17 152 17 0ms 2 8 19 189 19 0ms 2 9 21 230 21 0ms 3 0 5 15 6 0ms 3 1 13 106 14 0ms 3 2 29 541 30 0ms 3 3 61 2432 62 0ms 3 4 125 10307 126 0ms 3 5 253 42438 254 0ms 3 6 509 172233 510 15ms 3 7 1021 693964 1022 32ms 3 8 2045 2785999 2046 109ms 3 9 4093 11164370 4094 500ms m n ackerman(m,n) calls depth runtime array accesses 0 0 1 1 0 0ms 0 0 1 2 1 0 16ms 0 0 2 3 1 0 0ms 0 0 3 4 1 0 0ms 0 0 4 5 1 0 0ms 0 0 5 6 1 0 0ms 0 0 6 7 1 0 0ms 0 0 7 8 1 0 0ms 0 0 8 9 1 0 0ms 0 0 9 10 1 0 0ms 0 0 10 11 1 0 0ms 0 0 11 12 1 0 0ms 0 1 0 2 2 1 0ms 0 1 1 3 4 2 0ms 0 1 2 4 6 3 0ms 0 1 3 5 8 4 15ms 0 1 4 6 10 5 0ms 0 1 5 7 12 6 0ms 0 1 6 8 14 7 0ms 0 1 7 9 16 8 0ms 0 1 8 10 18 9 0ms 0 1 9 11 20 10 0ms 0 1 10 12 22 11 0ms 0 1 11 13 24 12 0ms 0 2 0 3 5 3 0ms 0 2 1 5 10 4 16ms 1 2 2 7 15 5 0ms 2 2 3 9 20 6 0ms 3 2 4 11 25 7 0ms 4 2 5 13 30 8 0ms 5 2 6 15 35 9 0ms 6 2 7 17 40 10 0ms 7 2 8 19 45 11 0ms 8 2 9 21 50 12 0ms 9 2 10 23 55 13 0ms 10 2 11 25 60 14 0ms 11 3 0 5 11 5 0ms 1 3 1 13 32 7 0ms 6 3 2 29 73 11 16ms 15 3 3 61 154 19 0ms 32 3 4 125 315 35 0ms 65 3 5 253 636 67 0ms 130 3 6 509 1277 131 16ms 259 3 7 1021 2558 259 0ms 516 3 8 2045 5119 515 15ms 1029 3 9 4093 10240 1027 16ms 2054 3 10 8189 20481 2051 0ms 4103 3 11 16381 20389972 6382 1234ms 8200
Die Rekursion muss so programmiert werden, dass alle möglichen Kombinationen
der vorhandenen Regale einmal geprüft werden (solange keine gefunden wird).
Um Raum für Erweiterung zu schaffen aber auch der korrekten Abstraktion
willen wurden die vorhandenen Regale in einer Array-Konstante (int[] AVAILABLE_RACKS)
gespeichert. Dieser Array wird in umgekehrter Reihenfolge abgearbeitet, damit
die größten Regale immer bevorzugt bei einer Lösung behandelt
werden (d.h. es wird davon ausgegangen, dass das Array in aufsteigender Reihenfolge
sortiert ist).
Bei Aufgabenstellung c führte das natürlich zu einer kleineren Erschwernis.
Dies wurde aber relativ lesbar mit Hilfe eines boolean-Arrays gelöst. Durch
Speicherung der erfolgreichen Kombinationen in diesem Array, ohne die verbleibenden
Kombinationen ungeprüft zu lassen, sowie anschließender disjunktiver
Verknüpfung der Inhalte dieses Arrays (siehe Source - vorletzten 5 Zeilen
von boolean possibleB(int)) konnte hoffentlich der Erffekt erzielt
werden, welcher in dieser Aufgabenstellung erwartet wird, es wurde eine deutliche
Erhöhung der Aufrufe beobachtet (siehe Test).
Das Programm wurde ausführlich im Source dokumentiert.
/**
* Softwareentwicklung I - Exercise 9/2.
* Recursive test of rack length combinations.
* In-source comments are followed by the described code.
*
* @author Daniel Brunthaler (0255054)
* @version 1.0
* @see RackTest.
*/
public class Rack {
// Available racks with length 50cm, 80cm and 120cm.
private static final int[] AVAILABLE_RACKS = {50,80,120};
// Counts, which number of racks manage a certain length.
private static int[] rackCounter;
// Counts calls of the recursive method.
private static int callCounter;
// Array used in possibleB(int) for testing all possible combinations of racks
// (as demanded in task c of the exercise)
private static boolean possibleB[];
/**
* Checks if given length could be managed with the available racks.
* @param l length which should be checked.
* @return true if it is possible to manage the given length with the
* available racks.
*/
public static boolean possible (int l) {
callCounter = 0;
rackCounter = new int[AVAILABLE_RACKS.length];
return possibleInt(l);
}
/**
* Internal method called by possible(int).
* @see possible(int).
*/
private static boolean possibleInt (int l) {
callCounter++;
for (int i = AVAILABLE_RACKS.length - 1;i >= 0;i--) {
if (l > AVAILABLE_RACKS[i]) {
if (possibleInt(l - AVAILABLE_RACKS[i])) {
rackCounter[i]++;
return true;
}
} else if (l == AVAILABLE_RACKS[i]) {
rackCounter[i]++;
return true;
}
}
return false;
}
/**
* Same as possible(int) beside that all possible rack combinations are
* tried out which produces considerably more recursive calls.
* @see possible(int).
*/
public static boolean possibleB (int l) {
callCounter = 0;
possibleB = new boolean[AVAILABLE_RACKS.length];
return possibleBInt(l);
}
/**
* Internal method called by possibleB(int).
* @see possibleB(int)
*/
private static boolean possibleBInt (int l) {
callCounter++;
boolean[] possibleB = new boolean[AVAILABLE_RACKS.length];
for (int i = AVAILABLE_RACKS.length - 1;i >= 0;i--) {
if (l > AVAILABLE_RACKS[i]) {
// Apart from possibleInt(int) all combinations of rack lengths
// are tested and the result is stored in an array. The so
// stored boolean values are disjunctively combined after the
// for loop (as demanded in task c of the exercise).
possibleB[i] = possibleBInt(l - AVAILABLE_RACKS[i]);
} else if (l == AVAILABLE_RACKS[i]) {
possibleB[i] = true;
}
}
for (int i = 0; i < possibleB.length;i++) {
// Disjunctive combining of the boolean values contained by the
// array.
if (possibleB[i]) return true;
}
return false;
}
/**
* Returns the combinations of racks found out in possible(int) in a String.
* @return combination of racks in a String.
*/
public static String getRacks() {
String racks = "";
for (int i = AVAILABLE_RACKS.length - 1;i >= 0;i--) {
if (racks != "") racks += "+";
racks += rackCounter[i] + "*" + AVAILABLE_RACKS[i] + "cm";
}
return racks;
}
/**
* Returns how often possible(int) or possibleB(int) has been called. Has to be
* called after calling one of these methods.
* @return how often possible(int) or possibleB(int) has been called.
*/
public static int getNumberOfCalls() {
return callCounter;
}
}
Zum Testen wurde die Klasse RackTest entwickelt, welche
das Testframework junit (http://junit.org) verwendet. Alle darin enthaltenen
Methoden testXYZ() werden im Testlauf automatisch ausgeführt. In den Testmethoden
wiederum befinden sich assert-Methoden, welche Ergebnisse von Methoden der Klasse
Rack überprüfen (meist in der Form assertEquals(exceptedValue,actualValue)).
Ergibt eine dieser Vergleiche mit assertEquals eine Ungleichheit,
schlägt der Test fehl. Das Programm wurde ausführlich kommentiert.
In diesem Fall enthält das Testprg. nur eine Testmethode, nämlich
testPossible(). In dieser findet auch nur einmal die Methode assertEquals(boolean,boolean)
Anwendung, nämlich beim Vergleich der Ergebnisse von boolean possible(int)
und boolean possibleB(int), welche ja gleich sein müssen.
Der Rest der Methode gibt die Testdaten in Tabellenform aus (unter anderem auch
Anz. der Methoden-Aufrufe sowie Zs.stellung der Regal-Kombination). Die Ausgabe
dieses Prg. folgt dem Sourcecode des Prg.
Die zu testenden Längen für die Funktionen boolean possible(int)
und boolean possibleB(int) wurden im Array int[] testLengths gespeichert.
Die zusätzlich nur für die Variante A (Kurzschlussauswertung) zu testenden
Längen wurden im Array int[] testLengthsA gespeichert (Variante B analysiert
diese Längen nicht in annehmbarer Zeit, zumindest auf meinem Rechner :-).
Die Ausgaben in Form einer Tabelle ermöglichen den anschaulichen Vergleich
der "Kurzschlussauswertung" und der vollständigen Auswertung.
Testprogramm
import junit.framework.*;
/**
* Softwareentwicklung I - Exercise 9/2.
* JUnit TestCase for class Rack.
* In-source comments are followed by the described code.
*
* @author Daniel Brunthaler (0255054)
*/
public class RackTest extends TestCase {
private static int[] testLengths =
{1,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,
200,210,220,230,240,300,400,500,600,700,800,900,1000,1100,1110};
private static int[] testLengthsA =
{2000,5000,10000,20000};
/**
* Constructor for RackTest.
* @param name of test.
*/
public RackTest(String name) {
super(name);
}
/**
* All lengths contained by the array testLengths are tested with
* possible(int) and possibleB(int). The result of these two methods
* are compared (assertEquals). The lengths, the output of the methods
* and additional information is printed to System.out in form of a table.
* The values contained by the array testLengthsA are only tested with
* possible(int) since possibleB(int) would take too long time. This
* results are also printed into the table.
*/
public void testPossible() {
int l;
boolean possibleA,possibleB;
String header =
"Length possible calls possibleB calls(B) Racks";
// 10000cm true 15 true 10000000000 7*120cm+2*80cm+0*50cm
//column 01234567890123456789012345678901234567890123456789012345678901234567890
// 10 20 30 40 50 60 70
IO.writeLn(
"test Rack.possible(int l) and Rack.possibleB(int l)");
IO.writeLn("\n" + header);
for (int i = 0;i < testLengths.length;i++) {
l = testLengths[i];
IO.write(l + "cm",9);
possibleA = Rack.possible(l);
IO.write(possibleA + "",10);
IO.write(Rack.getNumberOfCalls() + "",7);
possibleB = Rack.possibleB(l);
IO.write(possibleB + "",11);
IO.write(Rack.getNumberOfCalls() + "",13);
if (possibleA) IO.writeLn(Rack.getRacks());
else IO.writeLn("-");
assertEquals(possibleA,possibleB);
}
for (int i = 0;i < testLengthsA.length;i++) {
l = testLengthsA[i];
IO.write(l + "cm",9);
possibleA = Rack.possible(l);
IO.write(possibleA + "",10);
IO.write(Rack.getNumberOfCalls() + "",7);
IO.write("-",11);
IO.write("-",13);
if (possibleA) IO.writeLn(Rack.getRacks());
else IO.writeLn("-");
}
}
public static Test suite() {
return new TestSuite(RackTest.class);
}
public static void main(String[] args) {
junit.textui.TestRunner.run (suite());
}
}
Testausgaben
.test Rack.possible(int l) and Rack.possibleB(int l) Length possible calls possibleB calls(B) Racks 1cm false 1 false 1 - 10cm false 1 false 1 - 20cm false 1 false 1 - 30cm false 1 false 1 - 40cm false 1 false 1 - 50cm true 1 true 1 0*120cm+0*80cm+1*50cm 60cm false 2 false 2 - 70cm false 2 false 2 - 80cm true 1 true 2 0*120cm+1*80cm+0*50cm 90cm false 3 false 3 - 100cm true 3 true 3 0*120cm+0*80cm+2*50cm 110cm false 4 false 4 - 120cm true 1 true 4 1*120cm+0*80cm+0*50cm 130cm true 3 true 5 0*120cm+1*80cm+1*50cm 140cm false 7 false 7 - 150cm true 7 true 7 0*120cm+0*80cm+3*50cm 160cm true 3 true 8 0*120cm+2*80cm+0*50cm 170cm true 2 true 9 1*120cm+0*80cm+1*50cm 180cm true 6 true 11 0*120cm+1*80cm+2*50cm 190cm false 14 false 14 - 200cm true 2 true 14 1*120cm+1*80cm+0*50cm 210cm true 7 true 17 0*120cm+2*80cm+1*50cm 220cm true 4 true 20 1*120cm+0*80cm+2*50cm 230cm true 12 true 23 0*120cm+1*80cm+3*50cm 240cm true 2 true 27 2*120cm+0*80cm+0*50cm 300cm true 7 true 61 1*120cm+1*80cm+2*50cm 400cm true 5 true 258 2*120cm+2*80cm+0*50cm 500cm true 16 true 1053 2*120cm+2*80cm+2*50cm 600cm true 5 true 4362 5*120cm+0*80cm+0*50cm 700cm true 8 true 17900 5*120cm+0*80cm+2*50cm 800cm true 7 true 73502 6*120cm+1*80cm+0*50cm 900cm true 12 true 302089 6*120cm+1*80cm+2*50cm 1000cm true 10 true 1240159 7*120cm+2*80cm+0*50cm 1100cm true 21 true 5093746 7*120cm+2*80cm+2*50cm 1110cm true 15 true 5866398 8*120cm+0*80cm+3*50cm 2000cm true 17 - - 16*120cm+1*80cm+0*50cm 5000cm true 42 - - 41*120cm+1*80cm+0*50cm 10000cm true 85 - - 82*120cm+2*80cm+0*50cm 20000cm true 167 - - 166*120cm+1*80cm+0*50cm Time: 3,093 OK (1 tests)