{
  Copyright (C) 2008 Dmitry Negoda, http://ndv.mywebcommunity.org
  
  This file is part of Book of Programming Problems (http://ndv.mywebcommunity.org/problems).
  It is free software; you can redistribute it and/or modify
  it with no limits.	This software is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of	MERCHANTABILITY or 
  FITNESS FOR A PARTICULAR PURPOSE.
}
{ Given mountain-climbers' profiles, find a schedule for climbing a mountain with minimum number of climbers. }
uses dos;
const
  MaxAlp = 60;          { max. number of climbers }
  MaxN   = 30;          { max. number of days }
type
  AlpNum = 1..MaxAlp;   { climber index }
  AlpSet = set of AlpNum;{ climber set }
  Alp =                 { climber parameters }
    record
      num:AlpNum;       { a real (original) climber number }
      S,C:integer       { how much provision can he carry and how much provision does he consume }
    end;
  AlpGroup =            { climber group parameters }
    record
      AS:AlpSet;        { a set of climbers }
      S,C:integer;      { how mush do they carry and consume altogether }
      Si:integer        { how much do the carry at the moment }
    end;
  TIMETAB =             { schedule }
    record
      S:integer;        { initial amount of provision }
      AS:array[0..MaxN] of AlpSet { which days which climbers turn back }
      { we can assume they consume 2*C per day (there and back) }
    end;
const
  EmptyGroup:AlpGroup = (AS:[]; S:0; C:0; Si:0); { empty group }
var
  m:array[AlpNum] of Alp; { all climbers parameters }
  NA:AlpNum;              { number of climbers }
  N:integer;              { number of days }
  T:TimeTab;              { schedule }
  fin,fout:TEXT;
  k:AlpNum;
  G:AlpGroup;

{ input climbers parameters from file f }
Procedure InputAlps(var f:TEXT);
var i:AlpNum;
begin
  for i:=1 to NA do
  begin
    ReadLn(f,m[i].s);
    ReadLn(f,m[i].c);
    m[i].num:=i
  end
end;

{ sorting criterion }
Function Val(i:AlpNum):real;
begin  Val:=m[i].C / m[i].S  end;

{ sorting climbers by Val(i) }
Procedure sort;
var i,k,imin:AlpNum;
    v1,v2:real;
 Procedure Swap(i,k:AlpNum);
 var S:Alp;
 begin S:=m[i]; m[i]:=m[k]; m[k]:=S end;
begin
  for i:=1 to NA-1 do
  begin
    imin:=i; v1:=Val(i);
    for k:=i+1 to NA do
    begin
      v2:=Val(k);
      if v2<v1 then begin  imin:=k; v1:=v2 end
    end;
    Swap(i,imin)
  end
end;

{ Adding a climber A in group G }
Procedure AppAlp(var G:AlpGroup; A:AlpNum);
begin  G.AS:=G.AS+[A];
       Inc(G.S,m[A].S);
       Inc(G.C,m[A].C)
end;

{ Go back with group G nd days }
Procedure days_down(var G:AlpGroup;nd:integer);
begin  Inc(G.Si,nd*G.C*2)  end;

{ output climbers AS to the file f }
Procedure OutputASet(AS:AlpSet; var f:TEXT);
var i:AlpNum;
    ComFl:Boolean;
begin
  ComFl:=FALSE;
  for i:=1 to NA do
    if i in AS then
    begin
      if ComFl then Write(f,', ');
      Write(f,m[i].num);
      ComFl:=TRUE
    end;
  WriteLn
end;

{ output the timetable T in the file f }
Procedure OutputTab(var f:TEXT);
var i:integer;
begin
  Write(f,'Climbers participating: '); OutputASet(T.AS[0],f);
  WriteLn(f,'Initial amount of provision: ',T.s);
  for i:=2 to N do
    if T.AS[i]<>T.AS[i-1] then
    begin
      Write(f,'After ',i-1,' days this climber turns back: ');
      OutputASet(T.AS[i-1]-T.AS[i],f)
    end;
  Write(f,'Reaching the top: '); OutputASet(T.AS[N],f)
end;

{ Try to build a schedule with nalps climbers, starting from day nd.
{ Return TRUE on success }
Function Make_Table(nalps:AlpNum; nd:Integer;G:AlpGroup):Boolean;
var
    i:AlpNum;
    nds,k:integer;
begin
  if (nd=0) then
    if (nalps=0)  then { complete }
    begin
      T.S:=G.Si;
      T.AS[0]:=G.AS;
      Make_Table:=TRUE
    end else  { some extra climbers }
      Make_Table:=FALSE
  else if (nalps=0) then  { not enough climbers }
       Make_Table:=FALSE  { try another group of climbers }
  else
  begin
    for i:=1 to NA do
      if NOT (i in G.AS) then
      begin
        AppAlp(G,i);
        nds:=(G.S-G.Si) div (G.C*2); { how many days max. can travel the group }
        if nd<=nds then nds:=nd;
        days_down(G,nds);
        if Make_table(nalps-1,nd-nds,G) then
        begin  { a schedule is found }
          for k:=nd-nds+1 to nd do  T.AS[k]:=G.AS; { fill the schedule }
          Make_Table:=TRUE;
        end else Make_Table:=FALSE;
        Exit
      end;
  end { else (nd<>0), (nalps<>0) }
end;
procedure OutpTime;
var h,m,s,s100:WORD;
begin
  GetTime(h,m,s,s100);
  WriteLn('Time is ',h,':',m,':',s,':',s100,':');
end;
begin
  Assign(fout,'');
  Rewrite(fout);
  Assign(fin,'');
  Reset(fin);
  Write('Number of days to reach the top: '); ReadLn(fin,N);
  Write('Number of climbers: '); ReadLn(fin,NA);
  InputAlps(fin);
  Sort;
  G:=EmptyGroup;
  OutpTime;
  For k:=1 to NA do
    if Make_Table(k,N,G) then
    begin
      OutputTab(fout);
      Exit
    end;
  OutpTime;
  WriteLn(fout,'Cannot reach the top')
end.