program ioi94day2prb3ver2(input, output, inp, out) ; { (c) 1994, Tom Verhoeff, Eindhoven University of Technology } { Uses a more sophisticated upper bound on numbers to try } { General Section } const Test = true; Trace = false; var inp, out: text; procedure Init; begin if Test then writeln('IOI''94 - Day 2 - Problem 3: The Circle') ; assign(inp, 'input.txt') ; reset(inp) ; assign(out, 'output.txt') ; rewrite(out) ; if Test then writeln('Initialized') end { Init } ; procedure Fini; begin close(inp) ; close(out) end { Fini } ; { Problem Specific Section } const Max_n = 6; { maximum number of sectors } Max_k = 20; { maximum lower bound on numbers in sectors } Max_m = 20; { maximum number that starts sequence } type Circle = array [1..Max_n] of integer; procedure WriteCircle(var f: text; c: Circle; len: integer); var i: integer; begin for i := 1 to len do write(f, ' ',c[i]:2) ; writeln(f) end { WriteCircle } ; var n: 1..Max_n; { input value } m: 1..Max_m; { input value } k: 1..Max_k; { input value } var BestCount: integer ; { # best arrangements so far } BestTail: integer; { maximum tail found so far } procedure ReadInput; begin readln(inp, n) ; readln(inp, m) ; readln(inp, k) ; if Test then writeln('n, m, k = ', n:1, ', ', m:1, ', ', k:1) end { ReadInput } ; procedure WriteOutput; var i, j: integer; begin if Test then writeln('Max tail = ', BestTail:1, '; # arr. = ', BestCount:1) end { WriteOutput } ; var Arr: Circle; { Arr[i] is number in sector i of circular arrangement } Tail: integer; procedure ComputeTail; { post: Tail = tail of m for circular arrangement Arr[1..n] } var a, b, s, u: integer ; Creatable: array[1..51] of boolean ; { Creatable[i] = i is creatable } begin u := 1 + m + (n-1)*n ; { 1 + upper bound on maximum tail } for a := 1 to u do Creatable[a] := false ; for a := 1 to n do begin s := 0 ; { s = sum of Arr[a..b] } for b := a to n do begin s := s + Arr[b] ; if s <= u then Creatable[s] := true end { for b } ; for b := 1 to a-2 do begin s := s + Arr[b] ; if s <= u then Creatable[s] := true end { for b } end { for a } ; Tail := m ; { linear search for smallest uncreatable number } while Creatable[Tail] do inc(Tail) ; dec(Tail) end { ComputeTail } ; procedure CheckArrangement; begin ComputeTail ; if Tail > BestTail then begin { improved arrangement } BestCount := 1 ; BestTail := Tail ; close(out) ; rewrite(out) ; writeln(out, BestTail:1) ; WriteCircle(out, Arr, n) end { then } else if Tail = BestTail then begin { equally good arrangement } inc(BestCount) ; WriteCircle(out, Arr, n) end { then } end { CheckArrangement } ; procedure ComputeUpperBound(i: integer; var ub: integer); { post: ub = upper bound for Arr[i] based on Arr[1..i-1] } var a, b, s, u: integer ; Creatable: array[1..51] of boolean ; { Creatable[p] = p is creatable } begin u := 1 + m + (n-1)*n ; { 1 + upper bound on maximum tail } for a := 1 to u do Creatable[a] := false ; for a := 1 to pred(i) do begin s := 0 ; { s = sum of Arr[a..b] } for b := a to pred(i) do begin s := s + Arr[b] ; if s <= u then Creatable[s] := true end { for b } end { for a } ; a := n - i ; { a = # unfilled sectors besides Arr[i] } a := n*a - (a*succ(a)) div 2 + 1 ; { a = 1 + # segment sums involving Arr[i+1..n] and not Arr[i] } ub := m ; while a <> 0 do begin while Creatable[ub] do inc(ub) ; inc(ub) ; dec(a) end { while } end { ComputeUpperBound } ; procedure FillRemainder(i: integer); { Fill remaining sectors Arr[i..n] in all possible ways } { pre: i > 1 } var j, u: integer ; begin if i > n then { all sectors filled, check whether filling is useful } CheckArrangement else begin { fill sector i in all possible ways } if Trace then WriteCircle(output, Arr, pred(i)) ; ComputeUpperBound(i, u) ; for j := Arr[1] to u do begin Arr[i] := j ; FillRemainder(succ(i)) end { for j } end { else } end { FillRemainder } ; procedure ComputeAnswer; { pre: k <= m } var j: integer; begin BestCount := 0 ; BestTail := m+n-1 ; for j := k to m do begin Arr[1] := j ; { N.B. this is the smallest number in the circle } FillRemainder(2) ; end { for j } end { ComputeAnswer } ; begin Init ; ReadInput ; ComputeAnswer ; WriteOutput ; Fini end.