编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription
% z" g! J2 E+ g9 l5 b6 q# c
' W2 [( u' x+ K. i% m! kAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
: T* z) o  K& CInput
- K" [8 z! ]" n0 W
7 \/ r  s. S# _5 F0 |3 @( v/ CInput consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
0 V: B7 p! {: Q
$ f/ d- d: {% ]: x; N# w3 nFor each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.

4 P4 o& _# P1 |5 u: cwhere ** is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
7 Z% L  q$ _4 R- U
输入样例

4 6
% U! k/ i3 g) u- m( V: _9 WA<B
4 r9 b; X: A( TA<C
B<C
4 y  x, M) \- ]9 e; g: l7 u% uC<D
B<D
A<B
3 2
A<B
B<A
# x6 t+ ~: x; R+ A. M9 }26 1
6 h, Y; `) n8 c& sA<Z
0 0
  M$ I6 _% V( C. E

输出样例

Sorted sequence determined after 4 relations: ABCD.
9 m2 p/ s: b% b, A$ {1 T* KInconsistency found after 2 relations.
% ~% U8 I* H! ISorted sequence cannot be determined.

Source

East Central North America 2001

程序解题1：

3 w4 Y; i4 b) A//By Jackie Cheung
#include <iostream>
#include <string>
; t) V1 t: y7 `7 v#include <cassert>
typedef  struct tagNODE
{
( T, M, Z* r% m) Z' P    char val;
    struct tagNODE* link;
" M! j( ?6 e* W+ w6 B}NODE;
9 M$ s* K! R; F% _7 Rusing namespace std;
: _+ Q% Y" ]* v+ ^3 z3 _void Marshall(bool** arrary,int n)
0 O7 o- }( y7 T' G2 L6 D  C{
    for(int i=0;i<n;i++)
    {
3 b! \: q7 ~2 T! t1 f- n        for (int j=0;j<n;j++)
        {
            if(true==arrary[j])
% _1 f( e, p7 A2 O) d) T* t                for (int k=0;k<n;k++)
+ s) w9 m- Y6 _" ?- H- k, e                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
8 M. {' T8 S* G% e, C8 M4 U, N7 i                }
6 V& w. G% e/ T7 L# O3 p4 l        }
    }
};
3 c2 w8 a+ O+ p8 e8 Bbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
. ]: S1 v/ j* B6 M* V8 A" P{
$ W  r  @6 ]+ A/ {; g3 u6 h' l+ w# h    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
4 s* _& y3 t0 S7 E" T( `    if(1==nLeft)
    {
        Seq[n]='\0';
        return true;
    }
    for (int i=0;i<n;i++)
$ k# U- y- l; n' J% Q    {
        if(true==array[nIndex])
        {
. ]# X4 u/ u; H4 A7 h            
5 L8 J! K! q2 V7 N( w' X. d* w0 q9 `            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
1 ~) m- M5 _. Q) F9 G6 p        }
) F7 C* A6 B! N+ t7 G) r+ |        if(true==bFlag)
            return true;
    }
    return false;
};
* b6 Y: x8 k+ f4 `int main()
. o( w( p/ G  i& H2 @{
. d- L1 d4 ?5 m3 i, h* A9 r6 h5 f    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
2 a2 K, W% |7 A2 d    cin>>nRelNum;
( V. r( }; D6 W5 w5 F  _6 R$ R    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
    {
6 A8 D# p  u& n        cout<<"The relation can not be determined!"<<endl;
        return 0;
' q' b. Y. O8 O; m  E    }
! _) W( R. N  }& V; i: @1 X, _( u    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
, {" [; U8 `; U4 N8 }- D1 h$ {+ A
    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
2 {4 d4 K' a, }* |$ ~        cin>>strRelations;
0 ^, p- A$ F  b% m- T    }
( H+ \5 I2 t; x3 `1 g0 J   
    for (int i=0;i<nSeqLen;i++)
/ {6 ~4 S1 O/ E    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
    }
    //The main loop
* F" D6 ^' n4 d* `: h6 t8 L) K  A, l3 F) Q    for (int i=0;i<nRelNum;i++)
    {
        char a=strRelations[0];
/ S4 v" s; w7 C  Q* x        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
# I* W, c* W: I2 |9 Y- @5 }
0 g& E0 m6 O* j" U$ D        Marshall(array,nSeqLen);
- G* w: d. G8 q/ m* m" t) b( i% Z, v
% i: v) Z* |/ W8 q3 t# a, @3 V        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
: f2 O( l/ {! ~# j( A                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
$ t+ x2 F. V7 [0 s  z: P                    delete []array;
; e2 x2 r7 O/ r: h9 c* w                    delete []Seq;
                    return 0;

1 Y- g  {4 y; @! U# \: `1 z            }
& h: x/ o2 U9 U5 w5 R% f* E        }

& s5 S0 ?( I5 d8 _8 x' L5 Q        //Check for the determined sequence after  every relation   
: y1 S/ O. x- N+ F        for (int j=0;j<nSeqLen;j++)
* o- l, s- d" ^* F/ V/ y        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
; C$ [: t4 n, u. t; @8 w" F                delete []strRelations;
7 Y' f' s4 m+ O, G7 n( m2 b                for(int m=0;m<nSeqLen;m++)
( \) `/ x% [3 E- Y; T5 a                    delete []array[m];
8 Z# {( ~$ p& L                delete []array;
                delete []Seq;
                return 0;
1 k" b9 G( A/ |' G3 I2 q            }
        }


  V; ^) c$ l8 k    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
7 ~# L0 E% R  i1 L. J    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
    delete []Seq;
   
) H7 X( @3 `# o8 T/ a1 p; E    return 0;
4 X0 z9 e* ]4 m" ~- k& S}

( _7 h5 u; k, F" ^程序解题二：#include"stdio.h"
void main()
9 }. |! C. K) g8 m$ ^& z( {{
    int n_m[100][2];
    char re[1000][3],
1 t6 ?- ?3 w0 L' U    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
/ {8 K3 ^5 [# b    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
' H$ z  W- p3 y' g" B6 K    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
) D0 A: W$ \9 |8 }8 f$ e   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
  B- @- ~) z& Z* J& K" m1 m# J" S    {
       int a=0,b=0,l=1;
3 J& N' M: K7 i6 [       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
$ a* A/ t( r/ G: f         {
              if(re[a][0]==re[0]&&re[a][2]==re[2]&&re[a][1]!=re[1]||re[a][0]==re[2]&&re[a][2]==re[0]&&re[a][1]==re[1])
            {
- I$ h6 L; S) `* I            l=0;
% R$ R7 I: p: k2 K8 E            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
7 h/ ^& x8 q$ U. ?9 Q4 R            }
         }
& n! c* t( `) R5 m: C4 P" \      if(l==0)
) L4 H9 N; F5 F' |9 X& u; U          continue;//Inconsistency found after x relations.
# @7 z+ C( p/ E, F% {2 }  m, J$ d! y    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
' P! z$ W4 N: T+ v+ {( j3 }            l=0;
3 x8 X+ f9 S( \+ c/ G        }
        else
( e/ `7 z# b: K( X        {
          if(n_m[1]==n_m[0]-1)
          {   
' V& E* ?% U  k. n' s2 D' D9 ?              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
* ~0 h1 P, @- v; `/ z* W                      if(re[0]==re[0]||re[2]==re[2])
1 a2 a& F; Z, {# H3 Y, W; L* o/ Q                      {
; M3 `3 z0 Y6 s  G                      printf("Sorted sequence cannot be determined.\n");
. m/ R& T+ _! @5 E                      break;
                      l=0;
; y, I2 `6 g+ U4 T6 N- c+ G                      }
          }
        }
8 o' N4 }- y9 n1 Z. ~4 r* K9 j        if(l==0)
3 o4 F% @+ e4 T' n3 o+ X( y/ Y        continue;//Sorted sequence cannot be determined.
) L* e3 V$ [$ f: v1 O9 _1 @
4 y. d+ [! _  P  h$ s2 D        else
6 R8 {+ K5 @; u5 x. U$ ]# d. }         {
           
            for(int k=0;k<n_m[0];k++)
, k; O( }/ y+ z7 i3 `3 L) z* A+ ?             temp[k]=k+65;
3 o5 A" ]! d/ k3 B: @# p2 o: q$ O            for(k=0;k<n_m[1];k++,j++)
            {
0 k5 U. h& ]1 ?5 I$ {                int t1=0,t2=0;
* I6 S: t5 \/ C+ @              for(int s=0;s<n_m[0];s++)
  C" h4 y! y" @% ~* R. F" a2 k( ^6 W              {
               if(temp==re[0])
                   t1=s;
5 f1 w! c" ^: L4 T- Q& K                      if(temp==re[2])
                   t2=s;
              }
* ?% P. p& Q$ b1 W1 g1 [8 X              if((t1>t2)&&re[1]=='<')
$ [; k( f& q5 J# |# z" N              {
" ~" q2 x  U4 q' {% n7 Y                char t3=temp[t1];
                temp[t1]=temp[t2];
6 z9 a- r7 V( B8 l- U/ S                temp[t2]=t3;
( ?+ B) S2 u# R# L8 ^. I/ ]              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
1 D7 Z, c) X) D8 O2 C$ W            if(re[d][0]==temp&&re[d][2]==temp[s+1])
: Z- O+ g+ @* A+ t$ X1 {" c0 T            {
                count++;
                break;
# M8 H7 ~; F3 ?+ m& h- h* G3 w            }
            if(count==n_m[0]-1)
" f7 d) i$ V; T1 p0 w  V- L            {
- H8 _/ }& ?7 s4 H2 C4 ]                printf("Sorted sequence determined after %d relations:",n_m[1]);
( W7 A% L8 u% A* d% V0 v7 F                for(int f=0;f<n_m[0];f++)
. \: v5 ?7 N; @5 ?& S4 W                  printf("%c",temp[f]);
                 printf("\n");
6 ^/ h: m. D# F0 q# h8 `            }
8 B- t( r  t; r) c& r6 V            else
7 E% [7 D' J5 M  b0 p4 }! s, [& b               printf("Sorted sequence cannot be determined.\n");
& S& Q" S/ h. L        }
    }
' j; _( ^$ |9 z  I    }
}


* ~7 U: b/ g) ]& ^- _' B! t
: B( n2 `; q2 `5 P8 [0 ?


1 G( I* ~2 [5 j' V( |
5 S4 \4 v0 ^  h5 Q9 R1 \0 \

来源：编程爱好者acm题库