交大acm队选拔赛试题

ShanghaiJiaoTongUniversityACM-ICPCTeamSelectionContest

StageI

May17th,2006

18:00∼20:30

Direction:YouareexpectedtowriteyouranswertoalltheproblemsontheANSWERSHEET.

SectionI.Mathematics

1.Usefive5’sand+(plus),-(minus),*(times),/(divide)(andbracketsifnecessary)togettheresult24.2.Givenfive2-dimension-vectors

a1=(1,0),

anddefinesetSas

S:={x1a1+x2a2+...+x5a5|x1,...,x5∈R+,x1+x2+...+x5=1}

whereR+denotesthesetofallnonnegativerealnumbers.WhichoneofthefollowingvectorsisNOTincludedinS?

(a)(1,1)(b)(3,7.92)(c)(3.5,3.1)(d)(1.5,8.8)(e)(2.5,9)

a2=(3,0),

a3=(0,5),

a4=(4,6),

a5=(2,10)

3.Findtheminimalpositivenumberwhichconsistsnothingbutdigit1and2,andisamultipleof29.4.LetSbethesetofallpermutationsof{1,2,3,4,5,6,7,8}.AndforanytwoelementsaandbinS,

wesayaa1=b1,a2=b2,...,ai=bi,ai+1Forexample,(1,2,3,4,5,6,7,8)<(1,2,3,4,5,6,8,7)withi=6.

(1)CountthenumberofelementsxinS,satisfyingx<(4,3,2,1,8,7,6,5).

(2)CountthenumberofelementsxinS,satisfyingx<(4,3,2,1,8,7,6,5)andforallt(1≤t≤8),itholdsthatxt=t.

5.Ona3×3chessboard,youhaveaKingplacedattheupper-leftcorner.Andineachstep,youmay

onlymovetheKingtooneofitsfouradjacentgrids(up,down,leftandright)ifthiswillnotcausetheKingfallouttheboard.Furthermore,excepttheupper-leftandlower-rightcorner,eachoftheother7gridshastheprobability0.5toholdanobstacleinit,sothattheKingmaynotmoveintothisgrid.

ThenwhatistheprobabilitythatyoucanmovetheKingfromtheupper-leftcornertothelower-rightcorner?

SectionII.Algorithm

6.Splitnumberset{1,2,...,n}intosubsetsundertheconditionsbelow:

1.Anytwoofthesubsetshavenocommonelements;

2.Everynumberin{1,2,...,n}belongstooneofthesubsets;3.Theminimalelementsofeachsubsetareodd.

Page1

2006-2007ShanghaiJiaoTongUniversityACM-ICPCTeamSelectionContest–StageI

4.Eachsubsetsatisfiesthataftersortingitselementsinincreasingorder,therearenoadjacentoddnumbersoradjacentevennumbers.Denotetheamountofvalidpartitiontobef(n).Youaretocalculatef(3),f(6),f(9),f(12).Hint:Hereareallthepartitionswhenn=5—12345,12/345,1234/5,125/34,12/34/5.

7.GivenasetofballsSandastandardballb,itisknownthatexactlyoneballinShasdifferent

weightwithb.Alltheballsareofthesameshapeandcolor.Nowyouhaveabalancewithnopoises.Topickupthe“bad”ballyoucanmakeatmostncomparisons.CalculatehowmanyballsatmostcanbeinS.Pleasemakesomeexplanationonyourresult.

Hint:Evensimplealgorithmforlittlensuchasn≤3canearnsomepoints,sodoesestimationonupperboundoftheamount.

Page2

2006-2007ShanghaiJiaoTongUniversityACM-ICPCTeamSelectionContest–StageI

ShanghaiJiaoTongUniversityACM-ICPCTeamSelectionContest

AnswerSheet

NameSexIDPhoneEmail

1.5

5555=24

2.Yourchoice:

3.

4.

5.

Page3

2006-2007ShanghaiJiaoTongUniversityACM-ICPCTeamSelectionContest–StageI

6.

7.

Page4