problems.ps

1995年ACM contest FINAL试题和源码

FC01C00000FE03800000FE038000007F070000007F070000007F8F0000003F8E0000003FDE0000

001FDC0000001FDC0000000FF80000000FF80000000FF800000007F000000007F000000003E000

000003E000000001C000000001C000000003800000000380000038078000007C07000000FE0F00

0000FE0E000000FE1E000000FE3C0000007C780000003FE00000000FC000000021277F9A24>

121 D E end

%%EndProlog

%%BeginSetup

%%Feature: *Resolution 300dpi

TeXDict begin



%%EndSetup

%%Page: 1 1

0 bop 82 45 a Fl(A)n(CM)23 b(In)n(ternational)f(Collegiate)e(Programming)j

(Con)n(test)f(95/96)761 104 y Fk(Sp)q(onsored)15 b(b)o(y)e(Microsoft)526

163 y Fj(Cen)n(tral)21 b(Europ)r(ean)c(Regional)j(Con)n(test)559

254 y Fl(Problem)i(A:)h(Ma)n(y)n(a)h(Calendar)793 341 y Fk(Input)14

b(\014le:)k Fi(maya.in)766 391 y Fk(Output)c(\014le:)k Fi(maya.out)634

440 y Fk(Program)13 b(\014le:)18 b Fi(maya.pas)12 b Fk(or)i

Fi(maya.cpp)83 527 y Fk(During)d(his)h(last)f(sabbatical,)g(professor)i(M.)e

(A.)g(Y)m(a)g(made)f(a)i(surprising)g(disco)o(v)o(ery)g(ab)q(out)f(the)h(old)

f(Ma)o(y)o(a)g(calendar.)0 576 y(F)m(rom)e(an)i(old)f(knotted)h(message,)g

(professor)h(disco)o(v)o(ered)g(that)f(the)g(Ma)o(y)o(a)f(civilization)f

(used)j(a)f(365)f(da)o(y)g(long)g(y)o(ear,)h(called)0 626 y

Fh(Haab)p Fk(,)k(whic)o(h)h(had)f(19)g(mon)o(ths.)22 b(Eac)o(h)16

b(of)f(the)i(\014rst)f(18)f(mon)o(ths)g(w)o(as)g(20)g(da)o(ys)h(long,)e(and)i

(the)g(names)f(of)g(the)h(mon)o(ths)0 676 y(w)o(ere)f Fh(p)q(op,)f(no,)g

(zip,)g(zotz,)h(tzec,)g(xul,)f(y)o(o)o(xkin,)e(mol,)g(c)o(hen,)j(y)o(ax,)e

(zac,)i(ceh,)g(mac,)e(k)n(ankin,)g(m)o(uan,)f(pax,)i(k)o(o)o(y)o(ab,)e(cumh)o

(u)p Fk(.)0 726 y(Instead)j(of)f(ha)o(ving)g(names,)f(the)i(da)o(ys)g(of)f

(the)h(mon)o(ths)e(w)o(ere)j(denoted)f(b)o(y)g(n)o(um)o(b)q(ers)f(starting)g

(from)f(0)h(to)h(19.)k(The)c(last)0 776 y(mon)o(th)e(of)g(Haab)h(w)o(as)h

(called)f Fh(ua)o(y)o(et)g Fk(and)g(had)g(5)g(da)o(ys)h(denoted)g(b)o(y)f(n)o

(um)o(b)q(ers)g(0,)g(1,)f(2,)h(3,)g(4.)19 b(The)c(Ma)o(y)o(a)e(b)q(eliev)o

(ed)i(that)0 825 y(this)d(mon)o(th)e(w)o(as)i(unluc)o(ky)m(,)f(the)i(court)g

(of)e(justice)h(w)o(as)g(not)g(in)g(session,)g(the)h(trade)g(stopp)q(ed,)f(p)

q(eople)h(did)e(not)h(ev)o(en)h(sw)o(eep)0 875 y(the)h(\015o)q(or.)83

925 y(F)m(or)k(religious)f(purp)q(oses,)j(the)f(Ma)o(y)o(a)e(used)i(another)g

(calendar)f(in)g(whic)o(h)g(the)h(y)o(ear)f(w)o(as)g(called)g

Fh(Tzolkin)f Fk(\(holly)0 975 y(y)o(ear\).)31 b(The)19 b(y)o(ear)f(w)o(as)g

(divided)g(in)o(to)g(thirteen)h(p)q(erio)q(ds,)g(eac)o(h)g(20)f(da)o(ys)g

(long.)30 b(Eac)o(h)19 b(da)o(y)e(w)o(as)h(denoted)i(b)o(y)d(a)h(pair)0

1025 y(consisting)c(of)g(a)g(n)o(um)o(b)q(er)f(and)h(the)h(name)e(of)h(the)h

(da)o(y)m(.)j(They)d(used)g(20)e(names:)18 b Fh(imix,)12 b(ik,)h(akbal,)g(k)n

(an,)g(c)o(hicc)o(han,)h(cimi,)0 1075 y(manik,)d(lamat,)h(m)o(uluk,)f(ok,)j

(c)o(h)o(uen,)g(eb,)g(b)q(en,)g(ix,)f(mem,)e(cib,)j(caban,)g(eznab,)g(canac,)

g(ahau)g Fk(and)f(13)h(n)o(um)o(b)q(ers;)f(b)q(oth)h(in)0 1124

y(cycles.)83 1174 y(Notice)i(that)g(eac)o(h)g(da)o(y)g(has)f(an)h(unam)o

(biguous)e(description.)24 b(F)m(or)15 b(example,)g(at)g(the)i(b)q(eginning)e

(of)g(the)h(y)o(ear)g(the)0 1224 y(da)o(ys)e(w)o(ere)h(describ)q(ed)g(as)f

(follo)o(ws:)83 1310 y Fh(1)g(imix,)e(2)j(ik,)f(3)g(akbal,)f(4)i(k)n(an,)f(5)

g(c)o(hicc)o(han,)h(6)f(cimi,)f(7)h(manik,)f(8)h(lamat,)e(9)i(m)o(uluk,)f(10)

h(ok,)g(11)g(c)o(h)o(uen,)h(12)g(eb,)f(13)0 1360 y(b)q(en,)j(1)e(ix,)h(2)g

(mem,)d(3)j(cib,)g(4)g(caban,)g(5)f(eznab,)i(6)f(canac,)g(7)g(ahau,)g

Fk(and)f(again)g(in)h(the)g(next)h(p)q(erio)q(d)f Fh(8)g(imix,)d(9)j(ik,)f

(10)0 1410 y(akbal)e Fg(:)7 b(:)g(:)83 1496 y Fk(Y)m(ears)20

b(\(b)q(oth)g(Haab)g(and)f(Tzolkin\))g(w)o(ere)i(denoted)g(b)o(y)e(n)o(um)o

(b)q(ers)g(0,)i(1,)f Fg(:)7 b(:)g(:)18 b Fk(,)j(where)g(the)f(n)o(um)o(b)q

(er)f(0)h(w)o(as)f(the)0 1546 y(b)q(eginning)13 b(of)h(the)g(w)o(orld.)j(Th)o

(us,)d(the)h(\014rst)f(da)o(y)g(w)o(as:)83 1605 y(Haab:)k(0.)f(p)q(op)d(0)83

1655 y(Tzolkin:)j(1)d(imix)d(0)83 1714 y(Help)k(professor)h(M.)e(A.)h(Y)m(a)f

(and)g(write)i(a)e(program)f(for)i(him)e(to)h(con)o(v)o(ert)i(the)f(dates)h

(from)d(the)j(Haab)e(calendar)h(to)0 1763 y(the)f(Tzolkin)g(calendar.)83

1850 y Ff(Input)83 1909 y Fk(The)g(date)h(in)e(Haab)h(is)f(giv)o(en)h(in)f

(the)i(follo)o(wing)c(format:)83 1958 y Fe(Numb)n(erOfTheDay)p

Fi(.)19 b Fe(Month)c(Y)m(e)n(ar)83 2008 y Fk(The)d(\014rst)g(line)f(of)g(the)

h(input)f(\014le)h(con)o(tains)f(the)h(n)o(um)o(b)q(er)f(of)f(the)i(input)g

(dates)g(in)f(the)h(\014le.)17 b(The)12 b(next)g Fg(n)f Fk(lines)g(con)o

(tain)0 2058 y Fg(n)j Fk(dates)g(in)g(the)g(Haab)g(calendar)g(format,)e(eac)o

(h)i(in)f(separate)i(line.)j(The)c(y)o(ear)g(is)g(smaller)e(then)j(5000.)83

2144 y Ff(Output)83 2203 y Fk(The)f(date)h(in)e(Tzolkin)g(should)h(b)q(e)g

(in)g(the)g(follo)o(wing)d(format:)83 2253 y Fe(Numb)n(er)k(NameOfTheDay)g(Y)

m(e)n(ar)83 2303 y Fk(The)g(\014rst)g(line)f(of)f(the)i(output)g(\014le)f

(con)o(tains)g(the)h(n)o(um)o(b)q(er)f(of)f(the)i(output)g(dates.)20

b(In)14 b(the)h(next)g(n)f(lines,)g(there)i(are)0 2353 y(dates)f(in)e(the)i

(Tzolkin)e(calendar)h(format,)d(in)j(the)g(order)h(corresp)q(onding)g(to)e

(the)i(input)f(dates.)83 2439 y Ff(Example)83 2489 y Fk(Input)g(\014le:)83

2539 y Fi(3)83 2588 y(10.)21 b(zac)g(0)83 2638 y(0.)g(pop)h(0)83

2688 y(10.)f(zac)g(1995)83 2738 y Fk(Output)15 b(\014le:)83

2788 y Fi(3)83 2837 y(3)22 b(chuen)e(0)83 2887 y(1)i(imix)f(0)83

2937 y(9)h(cimi)f(2801)p eop

%%Page: 2 2

1 bop 82 45 a Fl(A)n(CM)23 b(In)n(ternational)f(Collegiate)e(Programming)j

(Con)n(test)f(95/96)761 107 y Fk(Sp)q(onsored)15 b(b)o(y)e(Microsoft)526

169 y Fj(Cen)n(tral)21 b(Europ)r(ean)c(Regional)j(Con)n(test)565

275 y Fl(Problem)i(B:)h(T)-6 b(ransp)r(ortation)782 374 y Fk(Input)14

b(\014le:)k Fi(train.in)755 424 y Fk(Output)c(\014le:)k Fi(train.out)612

474 y Fk(Program)13 b(\014le:)18 b Fi(train.pas)12 b Fk(or)i

Fi(train.cpp)83 573 y Fk(Ruratania)h(is)h(just)h(en)o(tering)f(capitalism)e

(and)i(is)g(establishing)g(new)h(en)o(terprising)g(activities)f(in)g(man)o(y)

e(\014elds)j(in-)0 623 y(cluding)c(transp)q(ort.)19 b(The)14

b(transp)q(ortation)g(compan)o(y)d(T)m(ransRuratania)i(is)g(starting)h(a)f

(new)h(express)h(train)f(from)d(cit)o(y)j(A)0 673 y(to)d(cit)o(y)g(B)g(with)g

(sev)o(eral)g(stops)h(in)e(the)i(stations)f(on)g(the)g(w)o(a)o(y)m(.)16

b(The)11 b(stations)h(are)f(successiv)o(ely)i(n)o(um)o(b)q(ered,)d(cit)o(y)h

(A)g(station)0 723 y(has)16 b(n)o(um)o(b)q(er)f(0,)g(cit)o(y)g(B)h(station)f

(n)o(um)o(b)q(er)g Fg(m)p Fk(.)24 b(The)16 b(compan)o(y)e(runs)i(an)f(exp)q

(erimen)o(t)h(in)f(order)h(to)g(impro)o(v)o(e)d(passenger)0

773 y(transp)q(ortation)h(capacit)o(y)g(and)f(th)o(us)i(to)e(increase)i(its)f

(earnings.)k(The)d(train)e(has)h(a)g(maxim)n(um)9 b(capacit)o(y)14

b Fg(n)g Fk(passengers.)0 822 y(The)g(price)h(of)e(the)i(train)e(tic)o(k)o

(et)h(is)g(equal)f(to)h(the)h(n)o(um)o(b)q(er)e(of)g(stops)h(\(stations\))h

(b)q(et)o(w)o(een)g(the)f(starting)g(station)g(and)f(the)0

872 y(destination)e(station)f(\(including)g(the)h(destination)g(station\).)16

b(Before)c(the)f(train)g(starts)h(its)e(route)i(from)d(the)i(cit)o(y)f(A,)h

(tic)o(k)o(et)0 922 y(orders)k(are)g(collected)g(from)d(all)h(onroute)i

(stations.)k(The)c(tic)o(k)o(et)f(order)h(from)e(the)i(station)f(S)g(means)f

(all)g(reserv)n(ations)j(of)0 972 y(tic)o(k)o(ets)g(from)e(S)i(to)g(a)f

(\014xed)h(destination)g(station.)23 b(In)16 b(case)g(the)h(compan)o(y)d

(cannot)i(accept)h(all)d(orders)j(b)q(ecause)g(of)e(the)0 1022

y(passenger)j(capacit)o(y)f(limitatio)o(ns,)e(its)i(rejection)g(p)q(olicy)f

(is)h(that)g(it)f(either)i(completely)d(accept)j(or)f(completely)f(reject)0

1072 y(single)e(orders)h(from)d(single)h(stations.)83 1171

y(W)m(rite)d(a)g(program)f(whic)o(h)h(for)g(the)i(giv)o(en)d(list)h(of)g

(orders)i(from)d(single)h(stations)g(on)g(the)i(w)o(a)o(y)d(from)g(A)i(to)f

(B)h(determines)0 1221 y(the)k(biggest)g(p)q(ossible)g(total)f(earning)g(of)h

(the)g(T)m(ransRuratania)e(compan)o(y)m(.)19 b(The)c(earning)f(from)f(one)i

(accepted)i(order)e(is)0 1271 y(the)f(pro)q(duct)g(of)f(the)g(n)o(um)o(b)q

(er)g(of)g(passengers)i(included)e(in)g(the)h(order)g(and)f(the)g(price)h(of)

f(their)h(train)f(tic)o(k)o(ets.)18 b(The)c(total)0 1321 y(earning)g(is)f

(the)i(sum)e(of)g(the)i(earnings)f(from)e(all)g(accepted)k(orders.)83

1420 y Ff(Input)83 1470 y Fk(The)i(input)g(\014le)g(is)g(divided)f(in)o(to)g

(blo)q(c)o(ks.)31 b(The)18 b(\014rst)h(line)e(in)h(eac)o(h)g(blo)q(c)o(k)f

(con)o(tains)h(three)i(in)o(tegers:)26 b(passenger)0 1520 y(capacit)o(y)14

b Fg(n)h Fk(of)f(the)h(train,)f(the)h(n)o(um)o(b)q(er)f(of)g(the)h(cit)o(y)f

(B)h(station)f(and)h(the)g(n)o(um)o(b)q(er)f(of)g(tic)o(k)o(et)h(orders)g

(from)e(all)g(stations.)0 1570 y(The)20 b(next)h(lines)f(con)o(tain)f(the)i

(tic)o(k)o(et)f(orders.)38 b(Eac)o(h)20 b(tic)o(k)o(et)g(order)h(consists)g

(of)e(three)j(in)o(tegers:)31 b(starting)20 b(station,)0 1619

y(destination)15 b(station,)g(n)o(um)o(b)q(er)g(of)g(passengers.)24

b(In)15 b(one)h(blo)q(c)o(k)f(there)i(can)e(b)q(e)h(maxim)o(um)11

b(22)j(orders.)24 b(The)16 b(n)o(um)o(b)q(er)f(of)0 1669 y(the)h(cit)o(y)g(B)

g(station)f(will)g(b)q(e)h(at)g(most)e(7.)23 b(The)16 b(blo)q(c)o(k)g(where)h

(all)d(three)j(n)o(um)o(b)q(ers)f(in)f(the)h(\014rst)h(line)e(are)h(equal)g

(to)f(zero)0 1719 y(denotes)g(the)g(end)f(of)f(the)i(input)e(\014le.)83

1819 y Ff(Output)83 1881 y Fk(The)18 b(output)g(\014le)f(consists)i(of)e

(lines)g(corresp)q(onding)i(to)e(the)h(blo)q(c)o(ks)g(of)f(the)h(input)f

(\014le)h(except)h(the)f(terminating)0 1931 y(blo)q(c)o(k.)g(Eac)o(h)c(suc)o

(h)h(line)e(con)o(tains)h(the)g(biggest)g(p)q(ossible)g(total)f(earning.)83

2030 y Ff(Example)83 2093 y Fk(input)h(\014le:)83 2143 y Fi(10)21

b(3)h(4)83 2192 y(0)g(2)f(1)83 2242 y(1)h(3)f(5)83 2292 y(1)h(2)f(7)83

2342 y(2)h(3)f(10)83 2392 y(10)g(5)h(4)83 2441 y(3)g(5)f(10)83

2491 y(2)h(4)f(9)83 2541 y(0)h(2)f(5)83 2591 y(2)h(5)f(8)83

2641 y(0)h(0)f(0)83 2690 y Fk(output)14 b(\014le:)83 2740 y

Fi(19)83 2790 y(34)p eop

%%Page: 3 3

2 bop 82 45 a Fl(A)n(CM)23 b(In)n(ternational)f(Collegiate)e(Programming)j

(Con)n(test)f(95/96)761 105 y Fk(Sp)q(onsored)15 b(b)o(y)e(Microsoft)526

164 y Fj(Cen)n(tral)21 b(Europ)r(ean)c(Regional)j(Con)n(test)626

259 y Fl(Problem)i(C:)g(John's)i(trip)793 349 y Fk(Input)14

b(\014le:)k Fi(trip.in)766 398 y Fk(Output)c(\014le:)k Fi(trip.out)634

448 y Fk(Program)13 b(\014le:)18 b Fi(trip.pas)12 b Fk(or)i

Fi(trip.cpp)83 538 y Fk(Little)j(Johnn)o(y)h(has)g(got)f(a)h(new)g(car.)30

b(He)18 b(decided)g(to)g(driv)o(e)g(around)f(the)i(to)o(wn)e(to)g(visit)h

(his)f(friends.)30 b(Johnn)o(y)0 587 y(w)o(an)o(ted)16 b(to)g(visit)g(all)e

(his)i(friends,)h(but)f(there)h(w)o(as)f(man)o(y)f(of)g(them.)24

b(In)16 b(eac)o(h)g(street)i(he)f(had)e(one)i(friend.)24 b(He)17

b(started)0 637 y(thinking)c(ho)o(w)h(to)g(mak)o(e)f(his)h(trip)h(as)f(short)

h(as)f(p)q(ossible.)20 b(V)m(ery)14 b(so)q(on)h(he)g(realized)f(that)h(the)g

(b)q(est)g(w)o(a)o(y)f(to)g(do)g(it)g(w)o(as)g(to)0 687 y(tra)o(v)o(el)i

(through)f(eac)o(h)i(street)g(of)f(to)o(wn)f(only)g(once.)25

b(Naturally)m(,)14 b(he)i(w)o(an)o(ted)g(to)g(\014nish)g(his)g(trip)f(at)h

(the)h(same)d(place)i(he)0 737 y(started,)f(at)e(his)h(paren)o(ts')g(house.)

83 787 y(The)j(streets)h(in)e(Johnn)o(y's)h(to)o(wn)f(w)o(ere)h(named)f(b)o

(y)g(in)o(teger)h(n)o(um)o(b)q(ers)f(from)f(1)h(to)g Fg(n)p

Fk(,)h Fg(n)e(<)h Fk(1995.)25 b(The)17 b(junctions)0 837 y(w)o(ere)g(indep)q

(enden)o(tly)f(named)f(b)o(y)h(in)o(teger)g(n)o(um)o(b)q(ers)f(from)f(1)i(to)

g Fg(m)p Fk(,)g Fg(m)f Fd(\024)g Fk(44.)23 b(No)16 b(junction)f(connects)j

(more)d(than)g(44)0 886 y(streets.)20 b(All)13 b(junctions)h(in)g(the)g(to)o

(wn)g(had)f(di\013eren)o(t)i(n)o(um)o(b)q(ers.)j(Eac)o(h)c(street)i(w)o(as)d

(connecting)i(exactly)f(t)o(w)o(o)f(junctions.)0 936 y(No)i(t)o(w)o(o)g

(streets)i(in)e(the)g(to)o(wn)g(had)g(the)h(same)e(n)o(um)o(b)q(er.)21

b(He)