数学建模社区-数学中国

标题: 编程竞赛题目（一） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:35
标题: 编程竞赛题目（一）
本帖最后由 厚积薄发 于 2010-5-6 18:40 编辑
% w; V+ Y- @7 g* c3 N, @' w
! p+ z. ?: I* Q& V/ i2 oSorting It All OutDescription6 i: u5 |, v8 H! \
: j' @0 u. g; F% \" U3 d
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.
" I. Y2 e& p# c% mInput
7 p! _5 C4 F' `" p! g
6 j4 k7 x1 \9 d! B9 QInput 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.
# t& ]# ~. K6 {/ WOutput
" F1 K  d: N5 `7 q. o
9 u; S6 K$ ^  S  f) SFor each problem instance, output consists of one line. This line should be one of the following three:
1 ?4 E7 u" ?& E( b  A" J) W9 v5 e! V
Sorted sequence determined after ** relations: yyy...y. 4 Q* K$ i8 T( I. h6 i+ }# ?" i
Sorted sequence cannot be determined. ' `/ B( }. f3 Z9 g+ E9 Z, ~; ?9 N! C
Inconsistency found after ** relations.   l8 q  |+ N2 b# J

/ {! \; T# w! a+ qwhere ** 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. 6 J6 L8 R3 y3 K

  n) L8 \$ a, n+ Q0 v: v输入样例


) H! `8 }7 x" p; @4 6( D7 q9 m9 l& y7 H; x( t
A<B
6 ^1 X& `/ q/ o: r8 x( MA<C  s0 G8 A2 b- w$ F
B<C. k) I  \7 S6 |1 L
C<D
% N% K! r0 |* R5 e5 dB<D
" m" \* P, k. J* U- o1 Q5 zA<B: Z5 P! Z5 x% u4 L, ]0 M" e
3 2
1 S) C, w& ~1 @: }# e7 ^) hA<B
( Z" h3 W8 D7 M& pB<A: d. l& }: |7 v$ _0 q; G
26 1, d5 I% L  i5 w/ y7 x
A<Z& a3 c9 x: s( f4 I
0 0* e1 d; I& P% [2 \8 I


. C, i+ k+ `0 T输出样例


# l( A# f2 a9 _! Z1 A+ H# C  W' U% DSorted sequence determined after 4 relations: ABCD.2 W+ y, H* O; J. }
Inconsistency found after 2 relations.- q6 k4 U- g0 E  j5 @4 O
Sorted sequence cannot be determined.

0 I  `4 W" m0 f  q  V; m. K

Source
3 F5 o/ b5 _+ |) @' N/ T$ O9 P* W; J" I
East Central North America 2001

4 D$ C' x( H  X5 D- U7 @

程序解题1：

; p; P& l  j, |, f  h0 B& ?
//By Jackie Cheung% \. s/ Y6 a8 V0 q& l% }6 T
#include <iostream>
, Q1 Q1 v* d/ Y7 v#include <string>9 r( u* r# \" A- t7 V
#include <cassert>  K; |4 v3 x/ X% }+ V3 @
typedef  struct tagNODE
3 _4 S6 b8 |: M" O( N4 g{* _9 c) x! e; ^9 C) T
    char val;0 H* P# ~% K) ~* x) Z. x) Z, k/ p
    struct tagNODE* link;' }' h! I* t3 E2 C( g6 Z0 ?5 a
}NODE;8 T3 {; r4 y5 @. i
using namespace std;) a; T; {- k) S( p6 j7 P- e8 M
void Marshall(bool** arrary,int n): O: W; {; S9 t4 O. Y# L. X, J
{" A2 w! w+ w7 n
    for(int i=0;i<n;i++)
3 o0 n/ B9 P7 |9 U: W- {    {* {* G, p) }  B" d: y2 m) `
        for (int j=0;j<n;j++)  N( g, d3 `& c9 T5 ~! f
        {
) N% E0 O! s% h# F7 x            if(true==arrary[j])4 Y8 b2 [+ g# {7 P& o3 Y
                for (int k=0;k<n;k++)
$ t9 ]1 j3 g5 E4 j                {) y) `( P* _  T3 E$ k6 Q
                    arrary[j][k]=arrary[j][k] || arrary[k];
; y# z) s1 ^2 d5 q2 M                }, M1 l4 S1 T1 [8 S) M. S, J0 I. O
        }
4 j  k$ s! j8 I6 T    }
. j% ]/ C7 S, W- }7 X};
! H6 V2 @2 t2 u- Ebool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
: I  A5 W6 \0 Z& x% y{3 b& a; `! S% h( p7 w1 R
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
  b* \0 l) R  ~( ^1 B  T    bool bFlag=false;
; c1 F: @5 `7 I    if(1==nLeft)
! \  d& g0 M" R) R" y5 d. ]4 S    {7 }1 [8 D3 ?: y+ K
        Seq[n]='\0';
' ]/ R( t  @1 ]        return true;  Z" v/ Z% u' c  e# O: D, h0 [* }
    }
  n4 o$ K, H0 L- y7 a5 g# X    for (int i=0;i<n;i++)7 V* m# z" k; X& {1 G7 ^. \
    {
* G( h* w5 k/ Z  M$ r/ N        if(true==array[nIndex])3 w; }9 d8 k3 I5 y5 h' g) ?
        {
) H" ?3 b3 u& Y7 f3 A            
) X" V1 R  G3 {* h) b7 u/ p            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
, L% c5 i% y) l3 s% @9 R        }; a+ `0 }; ?, b, t+ w  ~) N
        if(true==bFlag)& U- Z1 o2 M, Z) y
            return true;
2 X3 p, Y1 t. V1 E4 b    }6 c. K7 @7 h# S; G: w7 u
    return false;0 c: p+ y' e( d# A) M1 r5 k
};
" S, r8 e+ j6 Q( ^% sint main(): D* X. |  L- ~/ I
{6 Q: E3 D4 _% A$ Q  n
    int nSeqLen;
* t. F2 @' I" F" r5 u2 F; [    int nRelNum;
0 `, u. |. r" z6 L7 ^- V) Y' Y# d    cout<<"Input the length of the sequence:"<<endl;- z5 n+ A& Q# C8 o, A/ |
    cin>>nSeqLen;
) j$ K1 e) ^- t9 p& |    cout<<"Input the number of relations between the elements:"<<endl;) m: M. x0 {7 |0 U% W) |
    cin>>nRelNum;+ X1 g7 a% d, x. J6 d( e, Q, L
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
& g8 g; }: Y0 L4 G+ H    if(nRelNum<nSeqLen-1)
- k& f, t( n5 \! e2 P3 m9 K9 Z$ h    {
0 o9 L5 H5 @$ h$ C  d5 Z        cout<<"The relation can not be determined!"<<endl;5 O' R0 b8 S( x. x) x9 f; W
        return 0;- ?1 h3 m9 g( Q
    }
9 T- e; p( ?  z1 U8 ^# d) }1 b: o8 n    string* strRelations=new string[nRelNum];$ J$ H' h. d- b! O: {7 k7 `' Z% v
    char* Seq=new char[nSeqLen+1];" H, @# f0 t# n9 x" A$ W3 L
    bool** array=new bool*[nSeqLen];3 L+ h: a* O: I6 ~6 M1 V
9 N( t3 W- f/ o
    for(int i=0;i<nRelNum;i++)
% b$ ~8 M- X* x! _    {" @6 I; w" x  `+ n, n! T
        cout<<"Input the "<<i+1<<"th relation:"<<endl;0 Y6 M1 L0 g6 J" i7 w! s
        cin>>strRelations;9 ^2 \* V0 a, l% G& I0 L4 I
    }
1 j( z7 C, m' B% }   
) V) l7 x2 y! L+ C    for (int i=0;i<nSeqLen;i++)
0 D) Q* Z; d# R8 W1 B9 |    {4 c( a0 g0 ~% d) U; g: S8 w" z
        array=new bool[nSeqLen];
3 K/ c( s  e8 M" T; [        for (int j=0;j<nSeqLen;j++)
  i! S+ @* ^2 j2 w( P; e6 G7 k            array[j]=false;
8 N% y6 u5 J: O+ [    }
3 a; i* {* x- X8 ^$ P    //The main loop) B! P8 i3 b) \/ y% @$ S
    for (int i=0;i<nRelNum;i++)# {( p9 B, k0 i( @" q) T. t: @& ^
    {8 F1 b3 O7 Y1 o, i2 C: D0 K* }
        char a=strRelations[0];! U! C) Z) b3 U! x- ~7 ~% g
        char b=strRelations[2];1 w1 Q' P' E. f6 F
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);: s- x9 I6 r7 A) N( D+ x) B# b2 u/ w
        array[a-'a'][b-'a']=true;
/ e. F/ [. t1 G* O; z7 C& g2 n4 s% \* S% S; I" q
        Marshall(array,nSeqLen);
; i) t, g/ u* f0 t# P! }5 r/ {- I
        //Check for Inconsistency after  every relation  F+ X8 j# p1 V
        for (int m=0;m<nSeqLen;m++)
& S: Z% u" c* u- [        {
) D9 \8 ^) o# ^' m% G( D# K            if(true==array[m][m])5 N2 r0 D% t5 {( A' t
            {: }# b1 E4 B% f7 e+ M
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
! n! |% f7 L+ L3 G5 h' A8 D                    delete []strRelations;
/ I' \( p( k: D& h" Z! f                    for(int k=0;k<nSeqLen;k++)+ p) [9 Z% s. Y- }# e' G
                        delete []array[k];3 r- u% G+ P* ^* x8 O
                    delete []array;6 k4 o1 p4 L8 i0 v6 s% i+ s0 b
                    delete []Seq;) I! ^& E+ i" M
                    return 0;: m% l3 x2 s- t6 J$ P( |
- {  w# p& }1 N, _% a( l* `: g. u$ [
            }3 A; R! L# K$ W, P" |2 g1 ~
        }
4 E/ e' q- ]8 z7 Q" k( ]
8 s$ C; O0 p# U- P1 ~        //Check for the determined sequence after  every relation    4 U, G5 O. B; P  t" m& j
        for (int j=0;j<nSeqLen;j++)
) {0 J/ u# o" J) [4 y5 B- G, i! o$ E5 c        {+ E5 N! V3 y0 z, n& a0 z4 m
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))0 m, c; n$ [9 Q# _# W; J
            {; |: x2 a/ ~3 L7 M! u
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
" G& A" n- p5 J2 q5 s% X                delete []strRelations;. Y* b1 p8 ?1 g# ]4 }4 v7 ^: H6 C
                for(int m=0;m<nSeqLen;m++)
! ^9 x$ {1 U" U9 Q. X" R                    delete []array[m];
6 w! T: {  T# e% \                delete []array;/ D( N0 X2 p) \0 ?2 u0 M) ^2 G
                delete []Seq;
( E' F. f- x+ V4 z                return 0;
8 ^/ z4 I8 a: m/ J& H3 ~. M$ t            }
7 L% B2 T) j" I' i5 M) e8 L) R        }2 W5 k) H4 T8 C& P) d, k" O
8 h- ~% n) w/ s8 J( j! q/ y
& y( \' a9 d/ y5 J
    }" a( B; V- z5 s7 E
    //If the program has come to here ,then the relationship hasn't been determined!!!0 p9 b- d1 N" v( P; C$ z
    cout<<"The relation can not be determined!"<<endl;
, q" S# G; ]$ U* g, m3 |( s& l    delete []strRelations;
7 m0 R3 [+ n2 z: f6 x    for(int m=0;m<nSeqLen;m++)
! x( |- w% z8 R) Z& N        delete []array[m];, q* j* v6 d7 Z; B: F  r' X
    delete []array;+ c" T4 H. ?! J$ z" n5 u
    delete []Seq;
  w% q$ O( J5 k  [; C' ?    0 Y% g) d+ L) ]6 q9 T& X
    return 0;- s, X  L% M+ f9 W9 I
}
  Z7 c/ Y8 L9 N! Z( I. A& p$ T& i
3 Y. ?" o9 G& @程序解题二：#include"stdio.h"2 X0 q. g! ^8 b2 H; ^. H& `, Y
void main()
1 F. X9 z, ^. \8 U) {: W) Z0 J{1 R, M" W8 b" ~1 p! F0 U
    int n_m[100][2];! M) }, ]+ B+ f; W9 y
    char re[1000][3],/ S" t5 q- r2 {5 }) o" o6 h; [
    temp[26];
1 U7 }& I. b! P6 @) @8 v0 B! i8 Q    int i=0,j=0;
: v3 ^2 x$ _+ b) N& l    scanf("%d%d",&n_m[0],&n_m[1]);/ ~9 G& E3 P3 H2 f
    for( ;j<n_m[1];j++)
3 q7 M7 O" z1 u/ D    scanf("%s",&re[j]);
: d$ X3 d. D! [! S8 _1 W9 t( x    while(n_m[0]!=0&&n_m[1]!=0)9 I! R% C) F5 y! i
    {
# p* z1 Z# _1 x    i++;
* v- |, x* w3 y# A! u) [    scanf("%d%d",&n_m[0],&n_m[1]);
0 @0 W2 M3 N4 c/ J  m" z$ I    for( int f=0;f<n_m[1];f++,j++)
/ q0 b# R& s; ]5 ?1 F! {    scanf("%s",&re[j]);
  o, N  p7 ]( V6 V1 j# ]0 g. w+ ~& n2 @    }3 G$ S% S, l  q
    i=0;
. B- V8 K$ Q+ z# X4 @. Q# O# ~: z    j=0;
. d( p; _. q1 v8 ?1 q   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
2 D- u5 |3 k1 k' Y6 H) w    {) w: _7 Q( {  e! r+ p5 a  ]
       int a=0,b=0,l=1;
2 A& d3 ~4 X3 Q/ q7 R+ h; u       for(a=j;a<j+n_m[1]-1;a++)
  M) Q- g, L- H- E. f6 Y         for(b=a+1;b<j+n_m[1];b++)5 a0 V/ V* w' \& s9 H
         {
" F! p: [& S* I) T! O- U              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])7 h6 R) U9 J. G( Z
            {
0 N0 P  H9 O' S4 {4 i% C            l=0;
4 f9 B# D5 Q2 J; w6 v3 A            printf("Inconsistency found after %d relations.\n",n_m[1]);2 S* {1 o2 X6 }
            break;* c) \' q0 @/ k# S3 L
            }" K- P- N" f7 c
         }
; R% U6 o% ~2 h      if(l==0) ' ]% h/ q. z& [, Q6 h
          continue;//Inconsistency found after x relations.
: n* }# ^/ q+ F/ c    else{
! w) t+ X" y8 o1 `$ @           if(n_m[1]<n_m[0]-1)) ^3 {5 d6 w1 V7 q
        {. {; p/ h# C" o& K
            printf("Sorted sequence cannot be determined.\n");
* i6 \& V0 `; P. K( D            l=0;. u7 b- Z' M" d/ ?
        }, X3 G/ e& J$ G& m
        else' H6 M5 C8 R* D4 P3 e
        {
* I- E" q! ~+ `* t# }2 q" N          if(n_m[1]==n_m[0]-1)
7 f- p9 S2 b$ ~9 J7 w5 \) m+ a! r, e& `          {   
4 v+ m' u% V: g1 g2 x- _! e/ H              int k=0,p=0;
' @, ?5 A3 H" y) x$ A3 ]6 m              for( ;k<n_m[1]-1;k++)" _' |/ N9 k3 w' r! ~5 ^8 B
                  for(p=k+1;p<n_m[1];p++)4 E" H# J+ H2 V' B, a" p" W$ Z' c
                      if(re[0]==re[0]||re[2]==re[2])
; E  ~# w+ Y0 Y* u                      {
5 Q& a2 G8 B) x: l- \; Z                      printf("Sorted sequence cannot be determined.\n");. j2 M/ |$ j9 W3 P: _
                      break;# z" `3 P, Q4 ^6 S' u! N
                      l=0;
9 U7 q  ~3 a9 Z/ [2 s                      }
6 c$ v# `; j7 d  i; Y3 N* E          }
+ F( u5 X& B% _! n5 w" x2 |4 \# v        }; R( j* F! ~9 E/ P0 T" B
        if(l==0)
9 k' C$ J9 Z9 L        continue;//Sorted sequence cannot be determined.$ |2 B7 e2 D3 }$ I, l  [  k
+ _- s7 M" Q6 x; ?
        else* U  i) _. g' J" j
         {
# L8 J  B( Z8 j+ v! c; q$ U- i" ]+ K           / C2 K7 O7 ~* R' r
            for(int k=0;k<n_m[0];k++)
$ X+ k+ K( E" |8 x) G8 o0 [5 l             temp[k]=k+65;& n- n7 p( q6 B$ `% R% Y
            for(k=0;k<n_m[1];k++,j++): q) k/ {+ }  s: z+ _! F4 l
            {1 ?  ?/ j3 L+ d  j9 C
                int t1=0,t2=0;
" m" D& r8 Y  [; c$ c# u6 v              for(int s=0;s<n_m[0];s++)
4 z6 }2 B; N* `. k              {
' M3 ?6 G- Y( w, g  ?, V  G               if(temp==re[0])( p; q6 i" L' J7 u
                   t1=s;5 Q' y0 K4 {" O5 Z$ [
                      if(temp==re[2])
3 e7 D" C% m3 ]1 k2 ?7 |                   t2=s;
! h: a9 S/ O) S' l/ ~- K' B              }
9 L1 {3 l0 Q9 O- R% A              if((t1>t2)&&re[1]=='<')6 S- u" \, Y9 e* s2 h# T
              {
: O! W$ Y6 `1 k9 S' o, V4 }! s0 ~                char t3=temp[t1];+ t' _6 {4 P4 _' k* o
                temp[t1]=temp[t2];
- y: Z+ j* i! u" U- N                temp[t2]=t3;- C" b- L! h* Q1 Q
              }
% ^. Y, S" w2 S* h            }
* e+ |8 s- n' l- s( r. V        int count=0;% m! n8 h+ ~! [
        for(int s=0;s<n_m[0]-1;s++)4 K2 }0 K/ `5 c" l
        for(int d=j-n_m[1];d<j;d++)+ d# @. ?/ H" T* [
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
; D  x4 u6 S/ m0 M3 ?            {$ k  q( P( l6 o
                count++;  T8 d1 x6 S6 ^( H" P/ P
                break;
7 u' M" V! e/ d1 @( K7 _4 ?" S            }
  ~7 g. e+ e6 n5 d: f            if(count==n_m[0]-1), b7 O7 M3 D4 L9 i* z
            {1 C& l5 C% _# e8 i3 E2 k6 E* N
                printf("Sorted sequence determined after %d relations:",n_m[1]);5 ^- v# A- `& K) z) v
                for(int f=0;f<n_m[0];f++). c% d5 O. t/ E+ B$ L9 k
                  printf("%c",temp[f]);7 \: M( g! F3 r7 P
                 printf("\n");! v: V& `: J3 D8 `& }* j
            }3 _4 \1 i6 S. s
            else
/ p2 [( P. M- E7 x, p1 ^               printf("Sorted sequence cannot be determined.\n");
( e4 d4 I) b( j: _- D$ h0 y; M        }
. R8 O5 a2 j  P( ?* @: G2 A+ g    }
9 ^2 Y- G' h& }$ i. B" _    }+ E: V8 m( Y" u, D) l( y
}
) S0 C* _2 C4 w, T7 \* K
6 m; r# Y+ C) h3 X: e
0 M2 f5 K3 H$ T' X/ z2 o& }) _  @$ T, f; T, c) y5 [, `
3 g% i  t0 n) ]7 ]& F# x
: R& s6 c$ q# b' h
; i$ J+ D* G8 \' m0 Y4 i. A

9 s/ h4 u& B* Z& E
# M" x( `' |% w8 Z" M# s

来源：编程爱好者acm题库



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