2009機試2

計算和的數位2

大寫改小寫3

素數對3

求最大公約數和最小公倍數5

排序后求位置處的數6

*路由器連接8

*編譯原理10

*分開連接12

2010機試16

ECNU的含義16

空瓶換啤酒17

統計字符18

2010機試熱身20

粽子買三送一，買五送二20

工程流水線問題21

2011機試22

helloworld22

Specialjudge25

查詢成績26

2011機試熱身29

貪吃蛇29

仰望星空32

*編輯距離35

2012機試37

字母排序37

幸運數37

十六進制的加法40

號碼簿合并排序40

*五子棋41

*止則表達式匹配43

2013機試44

斐波那契數列的素數個數44

*將a字符變成b字符最少修改次數45

2013機試熱身47

去重排序47

蛇形圖案49

數學手稿51

2009機試

計算和的數位

Sumofdigit

Description

Writeaprogramwhichcorrputesthedigitnumberofsumoftwointegersaandb.

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

Eachtestcaseconsistsoftwointegersaandbwhichareseparetedbyaspaceinaline.

(0<=a,b<=100000000).

Output

Foreachtestcase,printthenumberofdigitsofa+b.

SampleInput

3

57

199

1000999

SampleOutput

2

3

4

#include<stdio.h>

intmain()

(

intn;

inta,b;

intsum;

while(scanf("%d",&n)!=EOF)

(

while(n-)

(

intan=0;

scanf("%d%d"/&a/&b);

sum=a+b;

while(sum)

(

an++;

sum/=10;

)

printf("%d\n",an++);

)

)

return0;

)

大寫改小寫

Capitalize

Description

Writeaprogramwhichreplaceallthelower-caseletterso:agiventextwiththecorresponding

captitalletters.

Input

Atextincludinglower-caseletters,periods,andspace.

Output

OutputTheconvertedtext.

SampleInput

welcometoeastchinanormaluniversity.

SampleOutput

WELCOMETOEASTCHINANORMALUNIVERSITY.

#include<stdio.h>

#include<string.h>

charstr[1000];

intmain()

(

intI;

while(gets(str))

(

l=strlen(str);

inti;

for(i=0;i<l;i++)

(

if(str[i]>='a'&&str[i]<='z,)

prindT%c”,str[i]-32);

else

printf(”%c”,str[i]);

)

printf("\n")；

)

return0;

)

素數對

PrimpsPair

Description

Wearrangethenumbersbetween1andN(1<=N<=10000)inincreasingorderanddecreasing

orderlikethis:

123456789…N

N...987654321

Twonumbersfacedeachotherformapair.YourtaskistocomputethenumberofpairsPsuch

thatbothnumbersinthepairsareprime.

Input

Thefirstlineofinputgivesthenumberofcases,C(1VC/100).Ctestcasesfollow.

EachtestcaseconsistsofanintegerNinoneline.

Output

Foreachtestcase,outputP.

SampleInput

4

1

4

7

51

SampleOutput

0

2

2

6

#include<stdio.h>

#include<string.h>

boolprime[10005];

voidinit()

(

inti;

intj;

prime[0]=prime[l]=false;〃不是素數

prime[2]=true;〃是素數

for(i=3;i<=10005;i+=2)

|

prime[i]=true;〃是素數

prime[i+l]=false;〃不是素數除0和2之外的偶數都不是素數

)

for(i=3;i<=10005;i+=2)

(

if(prime[i]==true)〃是素數

(

j=i+i;

while(j<=10005)

prime[j]=false;〃不是素數

j+=i；

)

)

}

)

intmain()

(

intc;

intn;

init();〃初始化

while(scanf("%d",&c)!=EOF)

{

while(c--)

(

scanf("%d"z&n);

intsum=O;

inti;

for(i=2;i<=n^;i++)

(

if(prime[i]==true&&prime[n+l-i]==true)

sum++;

)

sum*=2;

if(n%2==l)//n為奇數

(

if(prime[n/2+l]==true)

sum+=l;

}

printf("%d\n“,sum);

)

)

return0;

)

求最大公約數和最小公倍數

GCDandLCM

Description

Writeaprogramwhichcomputesthegreatestcommondivisor(GCD)andtheleastcommon

multiple(LCM)ofgivenaandb(0<a,bW44000).

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

Eachtestcasecontainstwoimergeraandbseparatedbyasinglespaceinaline.

Output

Foreachtestcase,printGCDandLCMseparatedbyasinglespaceinaline.

SampleInput

2

86

50003000

SampleOutput

224

100015000

#include<stdio.h>

intgetgcd(intajntb)

(

intgcd;

inttl,t2;

tl=a;

t2=b;

gcd=tl%t2;

while(gcd!=0)

(

tl=t2;

t2=gcd;

gcd=tl%t2;

)

returnt2;

)

intmain()

{

intn;

inta,b;

while(scanf("%d",&n)!=EOF)

(

while(n-)

(

scanf("%d%d"/&a,&b);

printf("%d%d\n",getgcd(azb),a*b/(getgcd(a,b)));

}

)

return0;

)

排序后求位置處的數

Sortit...

Description

Thereisadatabase,partychenwantyoutosortthedatabase'sdataintheorderfromtheleastup

tothegreatestelement,thendothequery:"Whichelementisi-thbyitsvalue?"-withibeinga

naturalnumberinarangefrom1toN.

Itshouldbeabletoprocessquicklyquerieslikethis.

Input

Thestandardinputoftheproblemconsistsoftwoparts.Atfirst,adatabaseiswritten,andthen

there'sasequenceofqueries.Theformatofdatabaseisverysimple:inthefirstlinethere'sa

numberN(l<=N<=100000j,inthenextNlinestherearenumbersofthedatabaseoneineach

lineinanarbitraryorder.Asequenceofqueriesiswrittensimplyaswell:inthefirstlineofthe

sequenceanumberofqueriesK(1<=K<=100)iswritten,andinthenextKlinesthereare

queriesoneineachline.Thequery"Whichelementisi-thbyitsvalue?"iscodedbythenumber

i.

Output

TheoutputshouldconsistofKlines.Ineachlinethereshouldbeananswertothecorresponding

query.Theanswertothequery"i"isanelementfromthedatabase,whichisi-thbyitsvalue(in

theorderfromtheleastuptothegreatestelement).

SampleInput

5

7

121

123

7

121

3

3

2

5

SampleOutput

121

7

123

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

intnum[100010];

intpos[105];

intmain()

(

intn;

inti;

intk;

while(scanf("%d",&n)!=EOF)

{

for(i=l;i<=n;i++)

scanf("%d",&num[i]);

scanf("%d",&k);

for(i=l;i<=k;i++)

scanf("%d，&pos[i]);

sort(num+l,num+l+n);

for(i=l;i<=k;i++)

printf("%d\rT,num[pos[i]]);

)

return0;

)

*路由器連接

HubConnectionplan

Description

Partychenisworkingassystemadministratorandisplanningtoestablishanewnetworkinhis

company.TherewillbeNhubsinthecompany,theycanbeconnectedtoeachotherusingcables.

Sinceeachworkerofthecompanymusthaveaccesstothewholenetwork,eachhubmustbe

accessiblebycablesfromanyotherhub(withpossiblysomeintermediatehubs).

Sincecablesofdifferenttypesareavailableandshorteronesarecheaper,itisnecessarytomake

suchaplanofhubconnection,thatthecostisminimal,partychenwillprovideyouallnecessary

informationaboutpossiblehubconnections.Youaretohelppartychentofindthewayto

connecthubssothatallaboveconditionsaresatisfied.

Input

Thefirstlineoftheinputcontainstwointegernumbers:N-thenumberofhubsinthenetwork(2

<=N<=1000)andM-thenumberofpossiblehubconnections(1<=M<=15000).Allhubsare

numberedfrom1toN.ThefollowingMlinescontaininformationaboutpossibleconnections-

thenumbersoftwohubs,whichcanbeconnectedandthecablecostrequiredtoconnectthem,

costisapositiveintegernumberthatdoesnotexceed106.Therewillalwaysbeatleastoneway

toconnectallhubs.

Output

Outputtheminimizecostofyourhubconnectionplan.

SampleInput

46

121

131

142

231

341

241

SampleOutput

3

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

structEdge{

inta,b;

intcost;

}E[15010];

intTree[1010];

intfindRoot(intx)

(

if(Tree[x]==-l)

returnx;

else

(

inttmp=findRoot(Tree[x]);

Tree[x]=tmp;

returntmp;

)

)

boolCmp(Cdgea,匚dgeb)

(

returna.cost<b.cost;

)

intmain()

{

intn;

intm;

inti;

while(scanf("%d",&n)!=EOF)

(

scanf("%d",&m);

for(i=l;i<=m;i++)

scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].cost);

sort(E+l,E+l+m,Cmp);〃排序

for(i=l;i<=n;i++)

Tree[i]=-1;

intans=0;

for(i=l;i<=m;i++)

(

inta=findRoot(E[i].a);

intb=findRoot(E[i].b);

if(a!=b)

Tree[a]=b;

ans+=E[i].cost;

)

printf("%d\rT,ans);

)

return0;

)

*編譯原理

PrinciplesofCompiler

Description

AfterlearntthePrinciplesofCompilecpartychenthoughtthathecansolveasimpleexpression

problem.Sohegiveyoustringsoflessthan100characterswhichstrictlyadheretothefollowing

grammar(giveninEBNF):

A:='('B')Tx'.

B:=AC.

C:={'+'A}.

Canyousolvethemtoo?

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

ThenextNlineswilleachcontainastringasdescribedabove.

Output

Foreachtestcase,iftheexpressionisadapttotheEBNFaboveoutput"Good"zelseoutput

"Bad".

SampleInput

3

(x)

(x+(x+x))

()(x)

SampleOutput

Good

Good

Bad

//include<cstdio>

#include<cstring>

ttinclude<cstdlib>

ttinclude<vector>

#include<cmath>

ttinclude<iostream>

#include<algorithm>

//include<functional>

#include<string>

ttinclude<map>

//include<cctype>

usingnamespacestd;

charex[110];

intindex;

boolA();

boolB();

boolC();

boolA()

(

if(ex[index]=='x')

(

index++;

while(ex[index]=='')index++;

returntrue;

)

if(ex[index]=="(')

(

index++;

while(ex[index]=='')index++;

if(D()&&ex[index]==')')

(

index++;

while(ex[index]=='')index++;

returntrue;

)

)

returnfalse;

)

boolB()

(

returnA()&&C();

)

boolC()

(

while(ex[index]=='+')

(

index++;

while(ex[index]=='')index++;

//returnA();

if(!A())

returnfalse;

)

returntrue;

)

intmain()

intN;

scanf("%d"z&N);

getchar();

while(N-)

{

gets(ex);

index=O;

printf("%s\n",A()&&ex[index]=='\0,?"Good":"Bad");

)

return0;

)

*分開連接

SeparateConnections

Description

Partychenareanalyzingacommunicationsnetworkwithatmost18nodes.Characterinamatrix

i,j(i,jboth0-based,asmatrix[i][j])denoteswhethernodesiandjcancommunicate('Y'foryes,'N'

forno).Assuminganodecannotcommunicatewithtwonodesatonce,returnthemaximum

numberofnodesthatcancommunicatesimultaneously.Ifnodeiiscommunicatingwithnodej

thennodejiscommunicatingwithnodei.

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

Ineachtestcase,thefirstlineisthenumberofnodesM(1WMW18),thenthereareagridby

M*Mdescribledthematrix.

Output

Foreachtestcase,outputthemaximumnumberofnodesthatcancommunicatesimultaneously

SampleInput

2

5

NYYYY

YNNNN

YNNNN

YNNNN

YNNNN

5

NYYYY

YNNNN

YNNNY

YNNNY

YNYYN

SampleOutput

2

4

Hint

Thefirsttestcase:

Allcommunicationsmustoccurwithnode0.Sincenode0canonlycommunicatewith1nodeat

atime,theoutputvalueis2.

Thesecondtestcase:

Inthissetup,wecanletnode0communicatewithnode1,andnode3communicatewithnode4.

^include<cstdio>

ttinclude<cstring>

#include<rcstdlib>

ttinclude<vector>

//include<cmath>

#include<iostream>

#include<algorithm>

^include<functional>

//include<string>

#include<map>

//include<queue>

usingnamespacestd;

ttdefineMAXN250

ttdefineMAXEMAXN*MAXM*2

#defineSET(a,b)memsetfa^sizeoffa))

deque<int>Q;

boolg[MAXN][MAXN],inque[MAXN],inblossom[MAXN];

intmatch[MAXN],pre[MAXN],base[MAXN];

intfindancestor(intujntv)

(

boolinpath[MAXN]={false};

while(l)

(

u=base[u];

inpath[u]=true;

if(match[u]==-l)break;

u=pre[match[u]];

)

while(l)

(

v=base[v];

if(inpath[v])returnv;

v=pre[match[v]];

)

)

voidreset(intujntanc)

{

while(u!=anc)

intv=match[u];

inblossom[base[u]]=l;

inblossom[base[v]]=l;

v=pre[v];

if(base[v]!=anc)pre[v]=match[u];

u=v;

)

)

voidcontract(intujntv,intn)

(

intanc=findancestor(u,v);

SET(inblossom,0);

reset(u,anc);

reset(v,anc);

if(base[u]!=anc)pre[u]=v;

if(base(v]!=anc)pre[v]=u;

for(inti=l;i<=n;i++)

if(inblossom[base[i]])

{

base[i]=anc;

if(!inque[i])

(

Q.push_back(i);

inque[i]=l;

)

)

)

booldfsfintS,intn)

(

for(inti=O;i<=n;i++)pre[i]=-l,inque[i]=O,base[i]=i;

Q.clear();

Q.push_back(S);

inque[S]=l;

while(!Q.empty())

(

intu=Q.front();

Q.pop_front();

for(intv=l;v<=n;v++)

(

i^(g[u][v]&&base[v]!=base[u]&&match[u]!=v)

(

if(v==S||(match[v]!=-l&&pre[match[v]]!=-l))contract(u,v,n);

elseif(pre[v]==-l)

pre[v]=u;

if(match(v]!=-l)Q.push_back(match[v])zinque[match[v]]=l;

else

u=v;

while(u!=-l)

(

v=pre[u];

intw=match[v];

match[u]=v;

match[v]=u;

u=w;

)

returntrue;

)

}

)

)

)

returnfalse;

)

intsolve(intn)

(

SET(match,-l);

intans=O;

for(inti=l;i<=n;i++)

if(match[i]==-l&&dfs(izn))

ans++;

returnans;

)

intmain()

(

intans;

intn,m;

chartmp[30];

scanf("%d",&n);

while(n-)

(

ans=O;

memset(g,0,sizeof(g));

scanf("%d",&m);

for(inti=l;i<=m;i++)

scanf("%s",tmp+l);

for(intj=l;j<=m;j++)

if(tmp[jl=='Y')

(

g[i][j]=gU][i]=l；

)

)

)

ans=solve(m);

printf("%d\n",ans*2);

)

return0;

2010機試

ECNU的含義

Welcometo2009ACMselectivetrial

Description

Welcometo2009ACMselectivetrial.ACMisalongwaytogo,andit'snotjustamatch.Sowhat

youneedtodofornowisdoyourbest!AndasmembersofACMlab,wearegoingtoteachyou

somethingimportant.FirstyyoushouldbeproudthatyouareamemberofECNU,because'E'

represents"Excellent",'Crepresents"Cheer",'N'represents"Nice",*U'represents"Ultimate".

SecondyoushouldrememberImpossibleisnothing,because"Impossible"represents"I'm

possible".ThirdfortodayyoushouldkeepACM,becauseforyouACMrepresents"AcceptMore".

Doyourememberthemclearly?

Nowwewillgiveyouastringeither"E"/'C","N'7'U","Impossible"or"ACM",youneedtotellme

whatdoesitmeans?

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW10).Ntestcasesfollow.

Eachtestconsistsofastringwhichw川beoneof"E","C","N","U","lmpossible"or"ACM".

Output

Tellmewhatdoesitmeans

SampleInput

3

E

Impossible

ACM

SampleOutput

Excellent

I'mpossible

AcceptMore

#include<stdio.h>

#include<string.h>

charstr[2O];

intmain()

(

intN;

scanf("%d",&N);

while(N--)

(

scanf("%s"zstr);

if(strcmp(str；'E")==O)

printf("Excellent\n");

elseif(strcmp(str；'C")==O)

printf("Cheer\n");

elseif(strcmp(str/'N")==O)

printf("Nice\n");

elseif(strcmp(str/,U")==O)

printf("Ultimate\n");

elseif(strcmp(stc"lmpossible")==0)

printf('Tmpossible\n");

elseif(strcmp(str；'ACM")==3)

printf("AcceptMore\n")；

)

return0;

)

空瓶換啤酒

SodaSurpler

Description

Timisanabsolutelyobsessivesodadrinkeohesimplycanno:getenough.Mostannoyingly

though,healmostneverhasanymoney,sohisonlyobviouslegalwaytoobtainmoresodaisto

takethemoneyhegetswhenherecyclesemptysodabottlestobuynewones.Inadditiontothe

emptybottlesresultingfromhisownconsumptionhesometimesfindemptybottlesinthes:reet.

Onedayhewasextrathirsty,soheactuallydranksodasuntilhecouldn'tafordanewone.

Input

Threenon-negativeintegerse,f,c,wheree<1000equalsthenumberofemptysoda

bottlesinTim'spossessionatthestartoftheday,f<1000thenumberofemptysoda

bottlesfoundduringtheday,and1<c<2000thenumberofemptybottlesrequiredto

buyanewsoda.

Output

HowmanysodasdidTimdrinkonhisextrathirstyday?

SampleInput

903

552

SampleOutput

4

9

#include<stdio.h>

#include<string.h>

intmain()

(

inte,fzc;

intt;

intsum;

intfull,empty;

while(scanf("%d%d%d',,&e,&f,&c)!=EOF)

(

sum=0;

empty-ee〃空瓶數量

while(empty>=c)〃空瓶數量可換

(

sum+=empty/c;〃換的滿瓶

empty=empty/c+empty%c;〃新的空瓶數量

)

printf("%d\n",sum);

)

return0;

統計字符

統計字符

Description

輸入一行字符，分別統計其中英文字母、空格、數字和其他字符的個數。

Input

輸入一個整數t,表示有幾組數據

接下來有t行，每行字符不超過10000個

Hint可能有空格之類的字符

Output

對于每行字符輸出其中

1英文字母（大小寫都算）的個數

2數字的個數

3其他字符的個數

SampleInput

2

q2e2

qweqrwwerr232424fwetetg===2342gdsg3.//-=@321

SampleOutput

character:2

number:2

others:l

character:21

number:14

others:9

#include<stdio.h>

#include<string.h>

charstr[10010];

intmain()

(

intt;

inti;

intcn,nn,on;

scanf(”%d”,&t);

getchar();〃去除上一個換行符

while(t-)

(

gets(str);

intl=strlen(str);

cn=nn=on=0;

for(i=0;i<l;i++)

(

if(str[i]>='0'&&str[i]<='9')

nn++;

elseif(str[i]>='A'&&str[i]<=,Z'11str[i]>='a'&&str[i]<='z,)

cn++;

else

on++;

)

printf("character:%d\n",cn);

printf("number:%d\n"/nn);

printf("others:%cl\n",on);

return0;

2010機試熱身

粽子買三送一，買五送二

端午節快樂

Description

今天是端午節，ECNU決定請大家吃粽子。恰好，今天超市為了迎合“端午節”，推出了“端午

大酬賓”，即促銷活動。嚴格的買三送一，買五送二。

ECNU想用現有的人民幣，買最多的粽子，但是他自己又不會算，所以希望你能幫幫他。

Input

輸入第一行為一個數N(l<=N<=100),表示測試數據的組數。

每組測試數據有兩個整數，A,B(0<=A<=1000,0<B<10)表示ECNU有A元人民幣,每個粽子價格

為B元人民幣,超市推出了買5個送2個，和買3個送1個的活動。

Output

輸出ECNU最多能買到的粽子數量。

SampleInput

2

103

223

SampleOutput

4

9

Hint:

有兩組測試數據：

對于第一組測試數據:有1。元人民幣，粽子3元一個，可以買3個,但是買3送1,所以最后有4

個。

對于第二組測試數據:有22元人民幣，粽子3元一個，可以買7個,但是買5送2,所以最后有9

個。

#include<stdio.h>

#include<string.h>

intmain()

(

intn;

intazb;

intzn;

intnum;

scanf("%d",&n);

while(n-)

(

scanf("%d%d",&a,&b);〃輸入人民幣數和粽子單價

zn=a/b;〃買了zn個

num=zn;

if(zn/5!=0)

(

num+=zn萬*2;

zn=zn%5;

)

if(zn/3!=0)

(

num+=zn/3;

)

printf("%d\n",num);

)

return0;

工程流水線問題

工程

Description

Castor在ECNU工廠工作。總廠有一條生產線，現在生產流水線上排隊的零件總數為當

前Castor開場加工第一個零件。

流水線上的零件總是按順序加工的。例如零件i必須是在零件i+1之前加工.

現在Castor只需要再加工K(K<=M)個零件就能休息了，Castor想知道他還要工作多長時間才

能休息.

Input

第一行為一個整數T,表示測數數據的組數.

對每組測試數據

第一行有兩個整數M,K(l<=K<=M<=1000)

然后一行有M個數字第i個數字表示零件隊列的第i個零件需要加工的時間為

ti(l<=ti<=10000)

Output

每組數據輸出一行，每行只有一個整數表示Castor還需要工作多長時間

SampleInput

2

32

523

31

123

SampleOutput

7

1

#include<stdio.h>

#include<string.h>

#include<math.h>

ffinclude<stdlib.h>

intmain()

intT;

intM,K;

inti;

intt[1005];

intsum;

scanf("%d",&T);

while(T-)

(

sum=O;

scanf("%d%d",&M/&K];

for(i=0;i<M;i++)

scanf("%d"z&t[i]);

for(i=0;i<K;i++)

(

sum+=t[i];

)

printf("%d\n",sum);

)

return0;

2011機試

helk）world

HelloWorld!

Description

當開場學習程序語言，第一個程序肯定是在屏幕上輸出一些字符:，比方輸出〃Hell。

Worldo

遇到輸出的句子過長時，輸出的句子由于換行將被屏幕裁斷。現在給你一些文本，文本的文

法如下：

TEXT（文本）:=SENTENCE|SENTENCESPACETEXT

SENTENCE（句子）:=WORDSPACESENTENCE|WORDEND

END（完畢符）:={：?,T}

WORD（單詞）:=LETTER|LETTERWORD

LETTER（字母）:={'a'./z','A'./Z'}

SPACE（空格

你的任務是把滿足上述文法的文木分割成多行（每行文木的長度都不超過n）。并且滿足如

下條件：

一、輸出的句子不能被截斷。如："Hi!WelcometoECNU."假設被分割成"Hi!Welcome"

則認為被截斷，即不合法。

二、文本分割后保證行數最小。如："Hi!WelcometoECNU.Haveaniceday!"在每行文本長

度要求在n=20的情況下,可以分割為："Hi!""WelcometoECNU.""Haveaniceday!"也可

以被分割為："Hi!WelcometoECNU./zHaveaniceday!z/此時認為第二種分法才合法。

注意：如果兩個相鄰的句子被分割到兩行，句子中間的空格可以被忽略。

Input

第1行為測試數據組數T(T<=100),接下來為T組數據。

每組數據包含2行，第1行為屏幕每行最多可以顯示的字符數n(2<=n<=255)。第二行為文本,

字符總數不超過10001,并且保證符合上述文法。

Output

輸出包含T行，每行輸出分解后的文本最少需要的屏幕行數。如果無法到達要求，則輸出"

Impossible"(不要輸出引號)。

SampleInput

3

12

HelloWorld!

11

HelloWorld!

40

Hello.WelcometoEastChinaNormalUniversity!Whatisyojrname?

SampleOutput

i

Impossible

3

#include<stdio.h>

#include<string.h>

charstr[10010];

intnum[5010];〃每個句子的個數

intmain()

{

intT;

intn;

inti;

scanf("%d"z&T);

while(T-)

scanf(”％d”,&n);〃每行的限制字符個數

getchar();〃丟棄上一個換行

gets(str);〃輸入文本

intl=strlen(str);〃文本的長度

intcn=O;〃統計句子的長度

intk=0;〃句子長度數組的下標

i=0;

while(i<l)

|

if(str[i]==?||str[i]==?||str[i]==T)〃遇到句子完畢為止

(

cn++;

i+=2;〃跳過空格

num[k]=cn;

k++;

cn=0;〃長度清空

)

else

(

cn++;

i++;

)

)

intflag=l;

for(i=0;i<k;i++)

(

if(num[i]>n)〃單個句子字符數大于限制的個數

(

flag=O;

break;

)

)

if(flag==0)

printf("lmpossible\n");

else

(

inth=l;〃行數為1

intsum=0;

for(i=0;i<k;i++)

(

if(sum+num[i]<=n)

(

sum+=num[i];

)

else〃累加句子字符數大于限制個數

h++;

sum=num[];〃清空

)

)

printf("%d\n",h);

}

)

return0;

)

Specialjudge

SpecailJudge

Description

大家都知道OnlineJud浜(在線判題系統，比方你現在使用的EOJ),它的工作原理是通過對■比

用戶提交的程序運行獲得的數據是否和系統的測試數據一致，對比的方式往往是逐個字節的

比對。但是有一些題需要特殊的比對，比方標準數據是0.01,而用戶提交的數據是0.02,那

么在0.1的誤差允許范圍內，認為用戶是正確的。現在請你來寫一個程序判斷用戶的程序是

否正確。

Input

第1行為測試數據組數T(T<=1000),接下來為T組數據。

每組數據包含三行，每行一個浮點數s,t,e,分別表示通過運行用戶程序獲得的數據，標準數

據，誤差允許的范圍

Output

輸出包含T行,如果用戶數據和標準數據相差在誤差范圍內(|s-t|<=e),則輸出"Accept",

否則輸出"WrongAnswer"?(不要輸出引號)

SampleInput

3

0.02

0.01

0.1

0.02

0.01

0.01

0.02

0.01

0.001

SampleOutput

Accept

Accept

WrongAnswer

#include<stdio.h>

#include<math.h>〃使用fabs()函數求絕對值

intmain()

(

intT;

doubles,t?

scanf("%d",&T);

while(T-)

(

scanf("％lf%lf%吃&s,&t,&e);

if(fabs(s-t)<=e)//假設|s-t|<=e

printf("Accept\n");

else

printf("WrongAnswer\n")；

}

return0;

)

查詢成績

Description

給你n(n<=50,000)個學生的名字和成績，查詢大于某個分數s的第一個學生，并輸出其名字,

如果兩個學生成績一樣，則以名字字典序小的在前輸出。

Input

第1行為測試數據總數T(T<=10),接下來為T組數據。

每組數據包含假設干行，第1行為人的數量n(n<=50,000),接下來n行為以空格隔開學生的名

字和成績，名字由大小寫字母組成，長度<=5,并且保證不存在重復的名字，成績為非負整

?s(s<=2A31-l)o

接下來一行為一個整數Q(Q<=50,000),表示查詢的次數，再接下來Q行，每行一個非負整

數，表示要查詢的分數s(s<=271-1)。

注意：當輸入輸出數據很大時，請使用scanf和printf而不要用cin和cout。

Output

輸出包含假設干行，每組測試數據包含Q行，為查詢到的學生的名字，如果不存在，則輸出"

Impossible"(不要輸出引號)。

SampleInput

2

3

one955

three1000

two994

3

900

955

1000

2

three995

one1000

2

500

1000

SampleOutput

one

two

Impossible

three

Impossible

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

structstu{

charname[10];

longintre;

⑶50010];

longintquery[50010];〃孩子的分數

intfind(intlowjnthighjongintx)〃查詢大于x的第一個元素位置

(

intmid=(low+high)/2;

while(low<=high)

(

if(s[mid].re>x)

(

high=mid-l;

mid=(low+high)/2;

)

else

(

low=mid+l;

mid=(low+high)/2;

)

returnlow;〃找到該位置

)

boolCmp(stua,stub)〃成績低的排在前面，假設成績一樣，以名字字典序小的在前輸出

(

if(a.re!=b.re)

returna.re<b.re;

else

return<;

)

intmain()

|

intT;

intn,q;

inti;

intj;

scanf(”%d”,&T);

while(T--)

{

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%s%ld",s[i].name,&s[i].re);〃輸入孩子的姓名和成績

sort(s,s+n,Cmp);〃排序

scanf(”%d",&q);

for(i=0;i<q;i++)

scanf(”％ld”,&query「])；〃輸入查詢的成績

for(i=0;i<q;i++)

{

if(queMi]>=s[n-l].re)〃如果查詢成績大于等于最大值

printf("lmpossible\n")；

else

(

,,

printf(%s\n"/s[find(O/n-l/query[i])].name);

}

)

return0;

2011機試熱身

貪吃蛇

Description

相信很多人都玩過這個游戲，當然這個題目不是叫你寫一個貪吃蛇游戲，而是很簡單的模擬

而已，為了簡化規則，我們把游戲抽象為：

在HxW的格點上有一條小小的長度為1的蛇，這條蛇每次只能向上下左右四個方向移動一

個單位距離。在某些格點上有營養價值不同的蘑菇，當蛇移動到含有蘑菇的點的時候，其生

命力會增加相應的值。在每個時間點，其選擇的方向是由函數。％4決定的，其中尸0=0,

Fl=l,Fn=Fn-l+Fn-2.如果蛇選擇的方向會立即撞到墻，它會沿著該方向的順時針選

擇第一個不會撞到墻的方向作為該時刻的方向。初始時刻是0時刻，蛇在左上角，初始生命

力為0,某個點上的蘑菇在吃掉后會立刻長出來。最外一圈是墻，沒有給出來。

請你輸出T時刻蛇的生命力。方向對應關系為：上(0)、右(1)、下(2)、左(3).

Input

每個文件一個測試數據：

數據的第一行三個整數H,W,T。(2<=H、W<=100,0<=T<=1000)

接下來H行，每行W個字符，其中？表示可行走的空地，0-9表示價值不同的蘑菇，相應

的價值分別為0-9

Output

對于每組數據，輸出一個值，表示T時刻后(含T時刻：蛇的生命力

SampleInput

234

145

1..

SampleOutput

10

Hint:

。時刻蛇在(0,0),方向0,但是會出界，順時針選擇第一個不出界的方向1,生命力1

1時刻蛇在(0,1),方向1,生命力5

2時刻蛇在(0,2),方向1,會出界.選擇方向2.牛命力10

3時刻蛇在(1,2),方向2,會出界,選擇方向3,生命力10

4時刻蛇在(1,1),方向3,生命力10

#include<stdio.h>

#include<string.h>

intf[1010];〃蛇的t時刻移動方向

voidinit()

inti;

f[0]=0；

f[l]=l;

for(i=2;i<=1000;i++)

(

intg。⑷⑵={〃定義方向

-1,0,〃上

0,1,〃右

1,0,〃下

0,-1}；〃左

structE{

intx;〃橫坐標

inty;〃縱坐標

intt;〃小蛇的生命力

回〃定義小蛇

char〃是否有蘑菇

intmain()

(

init();〃初始化

inti;

intj;

inth,w,t;

while(scanf("%d%d%d"/&h,&w/&t)!=EOF)

(

〃小蛇的初始狀態

e.x=0;

e.y=0;

e.t=0;

for(i=0;i<h;i++)

(

scanf('%s”,ch[i]);〃輸入生命值

)

for(i=0;i<=t;i++)

{

if(ch[e.x][eM>='(T&&(:h[e.x][e.y]<=9)〃此處有蘑菇

(

e.t+=(ch[e.x][e.y]-,0,);

)

if(e.x==0&&e.y==0)〃小蛇處于左上角

if(f[i]==0||f[i]==3)〃向上走或向左走

f[i]=l；〃改變方向向右，更新坐標

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==O&&e.y==w-l)〃小蛇在右上角

(

if(f[i]==O||f[i]==l)〃向上走或向右走

(

f「]=2;〃改變方向向下，更新坐標

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

}

elseif(e.x==h-l&&e.y==O)〃小蛇在左下角

|

if(f[i]==2||f[i]==3)〃向下走或向左走

{

f[i]=O；〃改變方向向上，更新坐標

)

e.x+=go[f(i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==h-l&&e.y==w-l)〃小蛇在右下角

(

if(f[i]==l||皿==2)〃向下走或向右走

{

f[i]=3;〃改變方向向左，更新坐標

}

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==O)〃在最上面

|

if(f[i]==O)

{

f[i]=l；

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==h-l)〃在最卜面

if(f[i]==2)

f[i]=3；

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

|

elseif(e.y==O)

(

(

f[i]=O;

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

}

elseif(e.y==w-l)

(

if(f[i]==l)

f[i]=2；

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

}

else{〃否則直接轉”

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

)

printf("%d\rr,e.t);

|

return0;

)

仰望星空

仰望星空

假設天空為w*h的平面，星座由相鄰的星星組成。兩顆星相鄰的條件為橫向或縱向或對角

相連。如以以下列圖為10*5的天空：

?**

*******

**

*******

????***

星星為',空白的局部為'上圖星空共有2個星座。

Input

第1行：兩個由空格分開的整數,l<=w<=80和l<=h<=1000.

第2到h+1行：每一行包含w個‘*，或者’代表星空的組成。

Output

一行：表示當前星空星座的個數。

SampleInput

105

***

*******

**

*******

*******

158

******

???????????????

***********

???****??

???**??*??*????

***********

????**???*??*??

********

SampleOutput

2

7

#include<stdio.h>

charmaze[1010][85];〃保存地圖信息

boolmark[1010][85];〃為圖上每一個點設立一個狀態

intn,m;

intgo[][2]={

1,0,

-1,0,

0,1,

0”,

1,1,

1,」，

-1,-1,

-1,1};/出個相鄰點與當前位置的坐標差

voidDFSfintxjnty)

(

inti;

for(i=0;i<8;i++)

(

intnx=x+go[i][0];

intny=y+go皿1];〃計算其坐標

if(nx<l11nx>n11ny<l11ny>m)

continue;〃假設該坐標在地圖之外

if(maze[nx][ny]=='.')

continue;〃假設該位置不是*

if(mark[nx][ny]==true)

continue;〃該位置己經被計算過

mark[nx][ny]=true;

DFS(nx,ny);〃遞歸查詢與該相鄰位置直接相鄰的點

)

return;

)

intmain()

(

intij;

whilelscanfd？id？idl&rrb&nWuEOF)〃輸入列和行:

(

if(n==0&&m==0)

break;

for(i=l;i<=n;i++)

scanf("%s",maze[]+D；〃第i行地圖信息保存在maze[i][l]到maze[i][m]中

〃按行為單位輸入地圖信息

for(i=l;i<=n;i++)

(

for(j=l;j<=m;j++)

mark[i][j]=false;〃初始化所有位置為未被計算

)

intans=0;〃初始化塊計算器

for(i=l;i<=n;i++)

(

for(j=l;j<=m;j++)

(

if(mark[i][j]==true)

continue;

if(maze[i][j]=='.')

continue;

DFS(iJ);

ans++;

)

)

printf("%d\n",ans);

)

return0;

*編輯距離

編輯距離

Description

有兩個字符串(僅有英文小寫字母組成〕A,Bo我們可以通過一些操作將A修改成亂操作

有三種：1修改一個字母，2