数学建模社区-数学中国

标题: 编程竞赛题目(一) [打印本页]

作者: 厚积薄发    时间: 2010-5-6 18:35
标题: 编程竞赛题目(一)
本帖最后由 厚积薄发 于 2010-5-6 18:40 编辑
/ H6 v" R# q+ s# ^; l( c, M0 z5 x& T% v
Sorting It All OutDescription
7 ?; @$ p8 h$ R4 M" n, t; K& ?8 L$ A: W8 T9 Q8 ]6 w
An 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. 1 T! X+ r6 k! d$ n
Input8 M& t1 [* E: {5 u# E
# h1 P  c% y5 w) ~  W4 h% l
Input 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.5 ?( O! f0 m1 X
Output
& Y4 F' A' ?2 J+ `# Y3 O: `2 h4 v( p' q; [
For each problem instance, output consists of one line. This line should be one of the following three:
9 v6 r) H! x$ k' r' a, U
" E, f7 B1 V1 _/ N7 N1 JSorted sequence determined after ** relations: yyy...y. ! p' o, e! k. f/ ^
Sorted sequence cannot be determined. + a4 s! V9 [" i' x
Inconsistency found after ** relations. $ C' n0 J% N9 w, i" {! l$ W2 y, J

0 F9 M, p  ^7 lwhere ** 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.
- J! f) }! O; @, F0 C/ x& E8 h
* l6 V! Q# Z, M% c输入样例


, G2 p* [$ }/ l# ]4 6
3 w6 R# s0 ~/ D# |6 z: xA<B
: @' m' j! v* X; ?3 QA<C! g, m. k! M0 T) ~% l3 }# w
B<C
! Y' s0 S' J1 V" W5 G3 wC<D
' ?8 s; I$ u) R! `3 U! g' e5 \B<D
) m4 F4 y# m! i$ F. D# K  [  T) eA<B/ ^+ I4 T# g, C7 {. |
3 2
7 k* ^$ J' F! @0 uA<B
* W+ ]1 F! \% X0 e& lB<A- N0 Q$ E' c  ]
26 1
( C, v& C) j0 H; yA<Z3 W5 V; W3 d6 `# j' [& {$ L
0 0
& r6 I' q! q+ g) i0 {* q3 |

4 K2 Y4 {! P$ Q: L- d
输出样例


3 ]( ^- I2 j2 z2 ^: PSorted sequence determined after 4 relations: ABCD.
. o4 D4 h0 n4 H  O+ KInconsistency found after 2 relations.
% e$ _1 e0 I# i3 c& `: KSorted sequence cannot be determined.

# |8 z: A1 ^- x

Source. b: ~* w- R. K" o. h) M. m
1 w4 [. A$ P- M' ^5 |
East Central North America 2001

- q$ x0 C3 q( _3 E/ G

程序解题1:


0 d& T7 r1 |: }. ~- y: l//By Jackie Cheung* j$ e& T" r! x% P
#include <iostream>" T7 J: R# |/ k- x7 M3 M- _
#include <string>
1 j' n. {0 H4 F: l) E. ?#include <cassert>: s( |3 ?- p# N9 W- o6 F
typedef  struct tagNODE 5 b8 {& r: Z8 s$ f% H. C
{, P/ G% j. E' s$ p+ o, h
    char val;
0 |* g4 W- e5 @$ {5 `: m9 j    struct tagNODE* link;  V) [1 h3 z: O" }1 D
}NODE;! \$ W* F! n; R) s! H9 l" m
using namespace std;
& E! Z8 m. a' R7 Uvoid Marshall(bool** arrary,int n)6 m- a# U( ~; a* Y& Q
{7 Z: [4 t2 T0 k4 Y8 e5 d
    for(int i=0;i<n;i++)
. o# W& A& c3 R    {
7 I, y$ ]) z3 e        for (int j=0;j<n;j++)
" M9 y+ N- o3 |        {3 Y5 D! u8 v3 u1 Q3 @
            if(true==arrary[j])8 ~/ E3 E7 `4 E) Q
                for (int k=0;k<n;k++)3 Y" T' j2 i# V6 m' b
                {
( T0 o( w: d# D                    arrary[j][k]=arrary[j][k] || arrary[k];
: _% ], z2 h& b8 R                }
$ S- O% O3 e. @6 n+ w, a3 }        }
, s+ |  Q* F: y5 G) u8 y    }" o0 q5 G7 Y. c6 D/ y
};2 Z+ D% I* S+ p3 X7 u) X0 I/ _
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)$ c6 X! R7 C) |) A
{6 q0 l( r* j* L' z
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
* I7 ]  j2 {& S    bool bFlag=false;
' Q$ z7 v/ G/ H& \  f    if(1==nLeft)% x4 o# D. p( O* _4 M
    {
% x4 f, ^0 m8 p0 W        Seq[n]='\0';, h$ o# g# ]; y  |
        return true;
; n; l# X( U* h" Q    }. A* D/ v3 W; g
    for (int i=0;i<n;i++)$ `1 H+ ~1 R5 W& S( W+ s
    {
5 k4 H- G, V3 c8 R- @3 a1 t        if(true==array[nIndex])1 o. |$ E. O' I! l5 R; ^: w
        {
0 C: v6 P- [! Z$ D4 W$ f# U            
2 A% j! @7 ?4 b; R' L            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);. D6 f* n* J/ T" G4 V8 X
        }
' d8 `) @4 A, B        if(true==bFlag)
2 B- t! ~+ {0 H+ q& D( ]  |! j# r            return true;3 i4 Q; d/ Z- |' q; q* B8 C
    }4 _$ S( p3 i$ ]6 N" `/ h, q+ q
    return false;
8 `' v0 ]3 C9 I$ f  M2 ^2 F% V' U};/ I0 P) ^7 j) ?
int main()& B% g- [  r) G# g9 n2 i
{
/ z3 Z6 P! y* }" ^! E6 p7 L; Q  m4 `    int nSeqLen;
4 g: P1 J; y, ?/ [& V3 y, s" Z    int nRelNum;
* Y3 s. [8 F9 N& r5 z+ d. z& Z# H    cout<<"Input the length of the sequence:"<<endl;
, K0 L) `/ H8 M/ g. Y# Y    cin>>nSeqLen;
1 T, X! P" f/ D1 V' K3 B; T7 A    cout<<"Input the number of relations between the elements:"<<endl;
( i  H$ v  Y, ?% h    cin>>nRelNum;
& P! k  F  l( j# S! p    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
7 w# k8 l+ f  l8 ~' {7 h& _    if(nRelNum<nSeqLen-1)
7 f% T# R! U1 V% `    {- G$ |$ [6 {+ B. g! O. S
        cout<<"The relation can not be determined!"<<endl;, ^& q0 i* I  ?3 R
        return 0;+ H3 v2 I' Q- f2 @0 n" f7 r
    }
- Z5 Q3 K" Y& L- o1 s    string* strRelations=new string[nRelNum];
2 s4 Y0 r1 ]! S# s2 t6 ]0 D    char* Seq=new char[nSeqLen+1];
9 ]" I+ _$ z0 y/ |& U$ |0 Y! C5 s# |% y" ?    bool** array=new bool*[nSeqLen];# b6 F9 V) f1 [( P, y% u! [& p3 @
' v- D8 W; R( T$ q5 S0 j. v
    for(int i=0;i<nRelNum;i++)
. i; s4 D7 c9 Y8 Z3 S    {
6 {! ]( K9 t) Y4 k        cout<<"Input the "<<i+1<<"th relation:"<<endl;
7 g* J; k8 {9 \/ g) q: S6 t        cin>>strRelations;
$ M# [) L1 o/ y: j5 c4 o    }
) I; l: @; A- i6 l" q( Y, K- k    5 F7 i! z/ |6 m% Z7 b
    for (int i=0;i<nSeqLen;i++)
9 l, Z) [0 _- h, x( n% r6 r7 V    {
! n8 I" c# D) k$ \* s3 H        array=new bool[nSeqLen];4 O/ K" |! G$ Y7 s# r4 a1 f$ ]
        for (int j=0;j<nSeqLen;j++)9 o; f& j/ x) c
            array[j]=false;
) g/ t$ v3 Q3 {, r1 p! U9 _0 v0 d    }
3 X! Z4 |- H# k" r. w    //The main loop
  j" Z; h* I6 g# h5 [% C    for (int i=0;i<nRelNum;i++)4 c- {/ C9 m5 I. J
    {
# F! z% ?4 k7 M4 ~0 W+ M5 c        char a=strRelations[0];
( b. B7 h' ?7 n3 k4 L        char b=strRelations[2];
4 J  X8 H  t$ l* c        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
7 i! @) j$ g! ?4 C        array[a-'a'][b-'a']=true;
( H+ u2 ^$ [+ X3 M( N6 s( d- h
7 {7 K3 m8 Z; U% n; I        Marshall(array,nSeqLen);
$ p) b+ q2 t4 ^2 t) H6 y+ ]0 R/ h  L$ \) c- q; N' p5 S2 Q/ e9 c. x
        //Check for Inconsistency after  every relation. d5 V. W4 A- f) t* v
        for (int m=0;m<nSeqLen;m++)
, d6 M6 ?  c9 S        {' [# X. H/ o! C- N! C
            if(true==array[m][m])* b1 b5 Y5 e* S1 ]* q
            {
; I1 Q, j" R9 K                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
. B8 l0 ~9 T  i( t9 u4 ], A                    delete []strRelations;  T1 ~3 x2 m  S2 o( e- I
                    for(int k=0;k<nSeqLen;k++)
! m. i- M+ H; Z                        delete []array[k];
# D& |/ Z% M, i- \/ {9 v                    delete []array;
. f$ Q% p+ T! K/ t4 n; {                    delete []Seq;
) `% G: b" J3 N0 y2 t                    return 0;7 S* g8 q# ]/ A# a* l  ?, x

) d+ z5 J9 |3 F( `, i+ _            }
* U( [8 ~- l. B9 e/ R        }; k( Z9 k6 F0 `7 i

. U1 ~% z: |& y  e        //Check for the determined sequence after  every relation   
$ u  e- C: A( `! J# m. n1 g        for (int j=0;j<nSeqLen;j++)
$ Q3 F9 ?+ o3 O: w        {2 F* m) ^) j, H1 {! k9 |
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))  E( m. F+ j! {
            {! p5 \  N! `$ o3 L
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
+ v# z2 Z9 A7 `3 o                delete []strRelations;
6 C3 B6 L# \! ]& e8 M' k1 k9 R0 O                for(int m=0;m<nSeqLen;m++)
7 D0 |" d  S  c2 n                    delete []array[m];0 F5 \" \6 \( J
                delete []array;  J# j+ o. V& _" |& A. x9 V, ]
                delete []Seq;$ U5 Z8 s. y/ n3 J4 {
                return 0;
- N( P  \6 G1 r# T6 ?2 i! f            }
) j0 N2 A3 l. v, y; ^2 T; s        }" q  B+ B  Y8 f4 h
* `8 B" ^8 ~4 v! C) T" }

1 u; o6 x% q& S4 v. U4 y4 V4 q    }" x# @$ \6 I% @5 D- Q6 k7 G
    //If the program has come to here ,then the relationship hasn't been determined!!!8 }- {- I. t: e3 a, U) J
    cout<<"The relation can not be determined!"<<endl;' H6 W- P% @. l; v5 r1 |/ A
    delete []strRelations;) R- t% j* i6 e: h* O! l
    for(int m=0;m<nSeqLen;m++)% |  q* G# z8 ?
        delete []array[m];4 T1 }$ S- V& R2 B6 x+ r- z
    delete []array;" q  e- U9 ]- N5 G( Z  S
    delete []Seq;) p5 g9 U) {! m1 d: i
    . b6 q+ ]+ k" N" A
    return 0;
* \9 A' v. Q0 g8 v8 u: ^) m}
2 X  S/ O4 I; D3 G& ]% z: H( U, G% u8 z6 A5 o9 A
程序解题二:#include"stdio.h"
  F7 @0 _. V& w# i& Rvoid main()
) i! K. t! ?  S. x+ C8 g3 B9 M{
. w1 j& s/ q" i    int n_m[100][2];& I4 m- v+ A( I
    char re[1000][3],
5 n9 H. i+ |6 O$ R- }4 O) y; N    temp[26];
7 G) R4 o: f' {; F- D  `% d    int i=0,j=0;) V$ H) I, [( S) ]% L" J# n/ e) r) a
    scanf("%d%d",&n_m[0],&n_m[1]);
# R. X: @2 h6 g    for( ;j<n_m[1];j++)
+ v) X8 r. k" @    scanf("%s",&re[j]);; r0 S5 y$ w  x6 l; H
    while(n_m[0]!=0&&n_m[1]!=0)
: I; q( ~' Z7 \    {
- D8 O& r. x( Z( e    i++;. G& x7 \$ W2 e$ ?4 c2 W2 J2 o
    scanf("%d%d",&n_m[0],&n_m[1]);
; Q, `+ V1 W2 I+ B! C6 t/ v! F    for( int f=0;f<n_m[1];f++,j++)
( v' I3 k: ?7 w' W/ u' ?    scanf("%s",&re[j]);
3 Q. Z6 V# R7 H, A* H/ c    }
8 S* F6 \2 y1 F; z7 h    i=0;
2 H$ w" g3 I! t3 k7 i9 n    j=0;  C8 k& r( e5 F
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
5 |9 q, K( z0 F  I& [    {$ ]3 F3 i8 c7 H7 b6 j4 Z. m
       int a=0,b=0,l=1;
$ a, p9 j' Y: D# ~2 ]       for(a=j;a<j+n_m[1]-1;a++)
" M( n2 m  L# h! j0 V         for(b=a+1;b<j+n_m[1];b++)
" g; H, ~1 ?( f& R+ `         {$ x* x' `& a$ d) p/ z( F  V
              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])
. p7 C$ t7 t" h3 L( w. S            {& _; H2 k$ C3 g% M
            l=0;; w8 v# q7 ]2 t9 j3 Q5 U
            printf("Inconsistency found after %d relations.\n",n_m[1]);
. b3 e; ~  K5 k, n  D0 y+ b, R            break;4 e5 U% e7 {8 ~7 z6 A& a+ `* O9 l
            }
- i7 I4 i2 g% _+ C6 f# n6 b         }% `+ {; I+ u" [2 g5 {( J% }
      if(l==0)   V/ {% N9 b$ h  }4 J- R! S% e
          continue;//Inconsistency found after x relations.+ ]  M. C; R* U# v1 R
    else{7 n! v$ l0 c/ w' j& z0 P- B" ]
           if(n_m[1]<n_m[0]-1)
+ G! R6 X* D7 z' C: G( W+ b        {! M( H4 P1 ~# g1 c! M' A9 o, _2 H3 ]
            printf("Sorted sequence cannot be determined.\n");
( D6 k" S# }8 x) ?# m7 H            l=0;
7 r' e8 d5 o. o: q" \. t        }* Q# N# Y/ H4 e% ^, J) [0 l
        else
5 W  r* f, g* O! Q, D6 {        {
7 B  j! |8 G5 O5 q7 p. t$ i+ S/ N          if(n_m[1]==n_m[0]-1)
7 S7 {6 t) E/ d          {   
3 C" r9 V- Y' ]8 \              int k=0,p=0;
9 D& j+ ]( j/ A2 Q8 R              for( ;k<n_m[1]-1;k++)# r; g/ o; A+ c! C: s. S
                  for(p=k+1;p<n_m[1];p++)
1 U& H! W+ E4 p* a# O7 X" l                      if(re[0]==re[0]||re[2]==re[2])
; Y0 p, f- @6 m( s0 r$ X! Y3 k                      {, Z! S# j1 q. ?% O. ^
                      printf("Sorted sequence cannot be determined.\n");3 s2 ?+ i+ G+ ?& U* ~
                      break;" j1 D8 N+ U3 s9 L
                      l=0;
) E. d2 B/ A$ f% q                      }- X0 [. i3 W8 B3 X
          }/ ~: B- T& N3 O
        }; {1 c9 D) \! {
        if(l==0) 9 z, W9 y5 D9 Q, B! F4 }
        continue;//Sorted sequence cannot be determined.
* ~9 U; f7 ]$ K
) ^& A1 V/ F  f        else% y3 `! W7 ]" M; X! {4 s
         {8 b2 C' E" `, c
           
: d0 _& s5 G* E/ z/ {2 x' S3 k; L3 i8 [4 U            for(int k=0;k<n_m[0];k++)
' X* j8 ^0 ^2 \! v- R# [# F+ B             temp[k]=k+65;. i9 I1 t8 p0 Z9 `  T
            for(k=0;k<n_m[1];k++,j++)
  I% S9 w" N$ x6 S# E1 M            {; C, K8 D# v2 ?  A7 w# M9 k
                int t1=0,t2=0;/ h( j5 Y) E/ j: m1 A/ l7 T* z
              for(int s=0;s<n_m[0];s++)
- y) b( M+ R6 z9 |              {5 w# W+ X9 J! e0 B2 f9 L
               if(temp==re[0]), a. @5 c6 B' B3 O" F
                   t1=s;
+ e) W# d3 q6 s0 q  O7 ?                      if(temp==re[2])9 X: B* L! }) t4 Q
                   t2=s;; R0 h2 h0 M6 g" I
              }7 Z5 E9 S% q) V# {# c+ Y6 @1 B
              if((t1>t2)&&re[1]=='<')3 q, l# q! L  y. ~  v( ]
              {
* b* k" q% g4 L, X8 k                char t3=temp[t1];
$ j( I# i$ G7 h5 N% \                temp[t1]=temp[t2];, U& r( X" ]8 \6 n% N8 ^" H4 [
                temp[t2]=t3;
% o; S( P; U! q* B! l8 ?              }. c% ?+ p8 G3 S9 V
            }
6 h# j/ a$ P7 p. y$ {6 m        int count=0;1 l1 @, p& g4 [$ h* k  _# O; R
        for(int s=0;s<n_m[0]-1;s++). _4 Z/ H% W4 r/ x
        for(int d=j-n_m[1];d<j;d++)
3 m. A; a: V# _            if(re[d][0]==temp&&re[d][2]==temp[s+1])
/ p' ]! s4 [, _6 z$ Y- D4 N            {
7 \+ T  u3 @0 G; x  y( ~! J5 Y- l                count++;( Q2 y1 G2 |! j% S; ?5 u
                break;
5 I3 t7 v* ^+ F) ]            }
+ t6 \: H/ I1 i+ ~            if(count==n_m[0]-1)5 u8 n* s/ d/ u4 ?- o  S
            {+ \" ]. @. q: ]2 X, k6 L
                printf("Sorted sequence determined after %d relations:",n_m[1]);3 Q' N$ u& I7 O' }5 J9 y- `# A
                for(int f=0;f<n_m[0];f++)
8 F: B" }' t2 J; P9 g                  printf("%c",temp[f]);4 X+ U9 G( X& F( z
                 printf("\n");  S" K2 S8 v6 M& `
            }& Z. f  k; I+ k& W
            else
( Q: T8 O4 k, m8 B               printf("Sorted sequence cannot be determined.\n");
3 J+ q+ ?$ l2 ?6 e/ [) M  v        }
+ E1 P/ f2 k) |6 g9 Y! D. Z    }
# L. U& H  B9 R  ^1 _( c! g1 ^5 N    }
% |. g+ M1 K& `7 {2 R- A$ J}5 F2 ~/ s3 ~7 l( X$ U8 Y8 u
8 L/ X" |' A4 @; I5 b) @; T' ^

2 R: m, o& Z$ x9 r( Q% e
7 \/ Z& F* C: G4 }+ w- e/ ]1 v0 s' x) F' _% N9 ?! M5 {

" i7 o* `6 v- N4 W$ I% d- m. u( {" J; a
- o- z* x8 P; I

2 x# n. [1 D# L4 J8 \

来源:编程爱好者acm题库






欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5