ripoff.tcl

set MAX_N 200
set MIN_VALUE -2147483648
set MAX_VALUE 2147483647

proc read_data {} {
    # Open file in read mode
    set input [open "ripoff.in" r]

    # read the file content
    set file_data [read $input]

    regsub -all "\n" $file_data " " file_data

    # split the data in array of lines
    set data [split $file_data " "]

    # Prints data spltted
    return $data
}

proc judgeCheckData {n s t amt} {
    set MAX_N 200
    set MIN_N 2
    set MIN_S 2
    set MAX_S 10
    set CHANGE_BOUND 9999

    if {($n > $MAX_N) || ($n < $MIN_N) || ($s > $MAX_S) || ($s < $MIN_S) || ($n > [expr "$s" * "$t"]) || ($t > [expr "$n" + "1"])} {
        puts "Bad param!"
    }
}

proc ripoff {startPoint turnsUsed numSquares numTurns maxJump} {
    global MAX_N 

    global MAX_VALUE

    global MIN_VALUE

    global CHANGE_BOUND 

    global rebates

    global values

    if {$startPoint >= $numSquares} {
        return 0;

    } elseif {$rebates($startPoint,$turnsUsed) != $MAX_VALUE} {

        return $rebates($startPoint,$turnsUsed)
    } else {

        set max $MIN_VALUE

        if {$turnsUsed == [expr "$numTurns" - "1"]} {
            return [lindex $values $startPoint]
        } else {

            for {set step 1} {$step <= $maxJump} {incr step} {

                set part2 [expr "$numTurns" - "$turnsUsed" - "1"]

                set part3 [expr ("$part2") * "$maxJump"]

                set expression [expr "$startPoint" + "$step" + "$part3"]
                if {$expression >= $numSquares} {
                    set thisStep [expr [lindex $values $startPoint] + [ripoff [expr "$startPoint" + "$step"] [expr "$turnsUsed" + "1"] $numSquares $numTurns $maxJump]]
                    set max [expr max($max, $thisStep)]
                }
            }
        }
        set rebates($startPoint,$turnsUsed) $max
        return $max
    }
}


proc calculate {numSquares maxJump numTurns} {

    global values
    global MIN_VALUE

    set max $MIN_VALUE

    for {set step 1} {$step <= $maxJump} {incr step} {

    set part1 [expr "$step" - "1"]
    set part2 [expr "$numTurns" - "1"]
    set part3 [expr "$part2" * "$maxJump"]

       set expression [expr  "$part1" + "$part3"]

       if { $expression >= $numSquares } {

            #int thisStep = calculate(step - 1,  1);
            set thisStep [ripoff [expr "$step" - "1"] 1 $numSquares $numTurns $maxJump] 

            #max = Math.max(max, thisStep);
            set max [expr max($max, $thisStep)]
       }
    }
    return $max
}


# set input of ints
set in [read_data]

# Set list index
set index 0

# Set n
set n [lindex $in $index]

# set ammount
set values ""



while {$n > 0} {

    #s = in.nextInt();
    set s [lindex $in [incr index]]

    # t = in.nextInt();
    set t [lindex $in [incr index]]


    #for (int sq = 0; sq < numSquares; sq++)
        #values[sq] = s.nextInt();    
    for {set sq 1} {$sq <= $n} {incr sq} {
        set values [linsert $values $sq [lindex $in [incr index]]]
    }   

    #puts $values

    #for (int i = 0; i < numSquares; i++)
        #for (int j = 0; j < numTurns; j++)
            #rebates[i][j] = Integer.MAX_VALUE;
    for {set i 0} {$i < $n} {incr i} {
        for {set j 0} {$j < $t} {incr j} {
            set rebates($i,$j) $MAX_VALUE
        }
    }


    #int maxRebate = calculate();
    set max_rebate [calculate $n $s $t]

    #System.out.println(maxRebate);
    puts "$max_rebate"

    #n = in.nextInt();
    set n [lindex $in [incr index]]

    set values ""


}