[ACM Asian 1996 Problem A]

fishcrazy

1996-1997 Asia Regional
ACM International Collegiate Programming Contest
Shanghai University, Shanghai, P. R. China, Nov. 3, 1996
Problem A
Schedule Problem
Input file: schedule.in
A project can be divided into several parts. Each part should be completed continuously. This means if a part should take 3 days, we should use a continuous 3 days do complete it. There are four types of constrains among these parts which are FAS, FAF, SAF and SAS. A constrain between parts is FAS if the second one should finish after the first one started. FAF is finish after finish. SAF is start after finish, and SAS is start after start. Assume there are enough people involved in the projects, which means we can do any number of parts concurrently. You are to write a program to give a schedule of a given project, which has the shortest time.

Input
The input file consists a sequences of projects, with an empty line indicates the end of input.

Each project consists the following lines:

the count number of parts (one line)
times should be taken to complete these parts, each time occupies one line
a list of FAS, FAF, SAF or SAS and two part number indicates a constrain of the two parts
a line only contains a ¡&REG#¡&hibar indicates the end of a project
Output
Output should be a list of lines, each line includes a part number and the time it should start. Time should be a non-negative integer, and the start time of first part should be 0. If there is no answer for the problem, you should give a non-line output containing "impossible".

A blank line should appear following the output for each project.

Sample Input
3
2
3
4
SAF 1 2
FAF 2 3
#
3
1
1
1
SAF 1 2
SAF 2 3
SAF 3 1
#
Output for the Sample Input
Case 1:
1 0
2 2
3 1

Case 2:
impossible

fishcrazy

很奇怪，为什么一直都是无人问津呢？

难道…… :-( 是看不懂题目？？

sjinny

[quote:f090a474fb="fishcrazy"]很奇怪，为什么一直都是无人问津呢？

难道…… :-( 是看不懂题目？？[/quote]
我可不是看不懂题目，因为......我一看是e文就给吓跑了，还没看呢~~   

fishcrazy

没有办法啊，ACM的题目就是E文，什么时候咱中国强大了，也让洋人跟着咱走

fishcrazy

一个工程可以分成几个部分，每个部分必须连续地工作才能完成。这就意味着如果其中一部分需要3天时间，那么就必须用连续3天去完成它。现在，在这些部分有四种约束条件，分别是FAF，FAS，SAS和SAF。 SAF表示第二部分必须在第一部分结束之后才能开始，同理，FAF是结束之后才能结束，SAS是开始之后才开始，FAS是开始之后才能结束。假设有足够多的工人可以同时进行工作。

写一个程序为所给的工程输出日程，要求最高效率。

fishcrazy

sjinny啊，来写写输入的部分吧，我不拿手

这个程序要求在输入规则的时候，规则的第一部分必须按照由小到大的顺序读入

例如：SAMPLE
SAF  1 2
SAS  1 4
FAS  2 1
FAS  2 3
SAS  2 4

[code:1]

/*宏定义四个规则*/
#define SAS 1
#define SAF 2
#define FAS 3
#define FAF 4

typedef struct{
     int rule;
     int first, second;
}RULE;

int n; /*工程被分为N个部分*/
int m; /*记录规则的数量*/
int times[n]; /*每个部分所需要的时间*/
int spoint[n] = {0}; /*每个部分开始的时间*/
int epoint[n]; /*每个部分结束的时间*/

RULE rule[m]; /*用结构数组存储每一条规则*/

int Caculate(int *sp, int *ep, RULE *ru, int *times)
{
     int i;
     int temp;

     ep[0] = sp[0] + times[0];

     for(i = 0; i < m; i++){
          switch(ru[i].rule)
          {
                case SAS: temp = sp[ru[i].first];
                                 break;
                case SAF: temp = ep[ru[i].first];
                                 break;
                case FAS: temp = ((sp[ru[i].first]-times[ru[i].second]) > 0 ? (sp[ru[i].first]-times[ru[i].second]) : 0);
                                 break;
                case FAF: temp = ((ep[ru[i].first]-times[ru[i].second]) > 0 ? (ep[ru[i].first]-times[ru[i].second]) : 0);
                                 break;
                default: break;
          }
          if(temp > sp[ru[i].second])
                sp[ru[i].second] = temp;
     }
     
      return 1;
}
[/code:1]