?? usaco 2_2_1 preface numbering 題解_leokan的blog.mht
字號:
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.2.1 Preface Numbering =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C228=C8=D5 =D0=C7=C6=DA=D2=BB =
16:14</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<P></P>
<H2>USACO 2.2.1 Preface Numbering</H2>
<DIV class=3Dt_msgfont>Preface Numbering<BR><BR>A certain book's =
prefaces=20
are numbered in upper case Roman numerals. Traditional Roman =
numeral=20
values use a single letter to represent a certain subset of =
decimal=20
numbers. Here is the standard set: <BR><BR> =
=20
I 1 L 50 M 1000<BR> =20
V 5 C =20
100<BR> X 10 =
=20
D 500<BR><BR>As many as three of the same marks that =
represent=20
10n may be placed consecutively to form other numbers: <BR><BR>III =
is 3=20
<BR>CCC is 300 <BR>Marks that have the value 5x10n are never used=20
consecutively. <BR><BR>Generally (with the exception of the next =
rule),=20
marks are connected together and written in descending order to =
form even=20
more numbers: <BR><BR>CCLXVIII =3D 100+100+50+10+5+1+1+1 =3D 268=20
<BR>Sometimes, a mark that represents 10^n is placed before a mark =
of one=20
of the two next higher values (I before V or X; X before L or C; =
etc.). In=20
this case, the value of the smaller mark is SUBTRACTED from the =
mark it=20
precedes: <BR><BR>IV =3D 4 <BR>IX =3D 9 <BR>XL =3D 40 <BR>This =
compound mark=20
forms a unit and may not be combined to make another compound mark =
(e.g.,=20
IXL is wrong for 39; XXXIX is correct). <BR>Compound marks like =
XD, IC,=20
and XM are not legal, since the smaller mark is too much smaller =
than the=20
larger one. For XD (wrong for 490), one would use CDXC; for IC =
(wrong for=20
99), one would use XCIX; for XM (wrong for 990), one would use =
CMXC. 90 is=20
expressed XC and not LXL, since L followed by X connotes that =
successive=20
marks are X or smaller (probably, anyway). <BR><BR>Given N (1 =
<=3D N <=20
3,500), the number of pages in the preface of a book, calculate =
and print=20
the number of I's, V's, etc. (in order from lowest to highest) =
required to=20
typeset all the page numbers (in Roman numerals) from 1 through N. =
Do not=20
print letters that do not appear in the page numbers specified. =
<BR><BR>If=20
N =3D 5, then the page numbers are: I, II, III, IV, V. The total =
number of=20
I's is 7 and the total number of V's is 2. <BR><BR>PROGRAM NAME:=20
preface<BR>INPUT FORMAT<BR>A single line containing the integer N. =
<BR>SAMPLE INPUT (file preface.in) <BR>5<BR><BR>OUTPUT =
FORMAT<BR>The=20
output lines specify, in ascending order of Roman numeral letters, =
the=20
letter, a single space, and the number of times that letter =
appears on=20
preface page numbers. Stop printing letter totals after printing =
the=20
highest value letter used to form preface numbers in the specified =
set.=20
<BR>SAMPLE OUTPUT (file preface.out)<BR>I 7<BR>V =
2<BR><BR><BR><BR>Preface=20
Numbering<BR><BR>=D0=F2=D1=D4=D2=B3=C2=EB<BR><BR>=D2=EB by Jeru=20
=
<BR><BR>=A1=A1<BR><BR>=D2=BB=C0=E0=CA=E9=B5=C4=D0=F2=D1=D4=CA=C7=D2=D4=C2=
=DE=C2=ED=CA=FD=D7=D6=B1=EA=D2=B3=C2=EB=B5=C4=A1=A3=B4=AB=CD=B3=C2=DE=C2=ED=
=CA=FD=D7=D6=D3=C3=B5=A5=B8=F6=D7=D6=C4=B8=B1=ED=CA=BE=CC=D8=B6=A8=B5=C4=CA=
=FD=D6=B5=A3=AC=D2=BB=CF=C2=CA=C7=B1=EA=D7=BC=CA=FD=D7=D6=B1=ED: =
<BR><BR>I 1=20
L 50 M 1000<BR>V 5 C 100<BR>X 10 D=20
=
500<BR><BR>=D7=EE=B6=E03=B8=F6=BF=C9=D2=D4=B1=ED=CA=BE=CE=AA10n=B5=C4=CA=FD=
=D7=D6(I,X,C,M)=BF=C9=D2=D4=C1=AC=D0=F8=B7=C5=D4=DA=D2=BB=C6=F0=A3=AC=B1=ED=
=CA=BE=CB=FC=C3=C7=B5=C4=BA=CD: <BR><BR>III=3D3=20
<BR>CCC=3D300=20
=
<BR>=BF=C9=B1=ED=CA=BE=CE=AA5x10n=B5=C4=D7=D6=B7=FB(V,L,D)=B4=D3=B2=BB=C1=
=AC=D0=F8=B3=F6=CF=D6=A1=A3<BR><BR>=B3=FD=C1=CB=CF=C2=D2=BB=B8=F6=B9=E6=D4=
=F2=A3=AC=D2=BB=B0=E3=C0=B4=CB=B5=A3=AC=D7=D6=B7=FB=D2=D4=B5=DD=BC=F5=B5=C4=
=CB=B3=D0=F2=BD=D3=C1=AC=B3=F6=CF=D6:=20
<BR><BR>CCLXVIII =3D 100+100+50+10+5+1+1+1 =3D 268=20
=
<BR>=D3=D0=CA=B1=A3=AC=D2=BB=B8=F6=BF=C9=B1=ED=CA=BE=CE=AA10^n=B5=C4=CA=FD=
=B3=F6=CF=D6=D4=DA=D2=BB=B8=F6=B1=C8=CB=FC=B4=F3=B5=C4=CA=FD=C7=B0(I=D4=DA=
V=BB=F2X=C7=B0=C3=E6=A3=ACX=D4=DAL=BB=F2C=C7=B0=C3=E6=A3=AC=B5=C8=B5=C8)=A1=
=A3=D4=DA=D5=E2=D6=D6=C7=E9=BF=F6=CF=C2=A3=AC=CA=FD=D6=B5=B5=C8=D3=DA=BA=F3=
=C3=E6=B5=C4=C4=C7=B8=F6=CA=FD=BC=F5=C8=A5=C7=B0=C3=E6=B5=C4=C4=C7=B8=F6=CA=
=FD:=20
<BR><BR>IV =3D 4 <BR>IX =3D 9 <BR>XL =3D 40 <BR>=CF=F1XD, IC,=20
=
=BA=CDXM=D5=E2=D1=F9=B5=C4=B1=ED=B4=EF=CA=C7=B7=C7=B7=A8=B5=C4=A3=AC=D2=F2=
=CE=AA=C7=B0=C3=E6=B5=C4=CA=FD=B1=C8=BA=F3=C3=E6=B5=C4=CA=FD=D0=A1=CC=AB=B6=
=E0=A1=A3=B6=D4=D3=DAXD(490=B5=C4=B4=ED=CE=F3=B1=ED=B4=EF)=A3=AC=BF=C9=D2=
=D4=D0=B4=B3=C9 CDXC;=20
=
=B6=D4=D3=DAIC(99=B5=C4=B4=ED=CE=F3=B1=ED=B4=EF)=A3=AC=BF=C9=D2=D4=D0=B4=B3=
=C9XCIX; =
=B6=D4=D3=DAXM(990=B5=C4=B4=ED=CE=F3=B1=ED=B4=EF)=A3=AC=BF=C9=D2=D4=D0=B4=
=B3=C9CMXC=A1=A3 <BR><BR>=B8=F8=B6=A8N(1 <=3D N=20
< 3,500)=A3=AC =
=D0=F2=D1=D4=B5=C4=D2=B3=C2=EB=CA=FD=A3=AC=C7=EB=CD=B3=BC=C6=D4=DA=B5=DA1=
=D2=B3=B5=BD=B5=DAN=D2=B2=D6=D0=A3=AC=D3=D0=BC=B8=B8=F6I=B3=F6=CF=D6=A3=AC=
=BC=B8=B8=F6V=B3=F6=CF=D6=A3=AC=B5=C8=B5=C8 =
(=B4=D3=D0=A1=B5=BD=B4=F3=B5=C4=CB=B3=D0=F2)=A1=A3=B2=BB=D2=AA=CA=E4=B3=F6=
=B2=A2=C3=BB=D3=D0=B3=F6=CF=D6=B9=FD=B5=C4=D7=D6=B7=FB=A1=A3=20
<BR><BR>=B1=C8=C8=E7N =3D 5, =C4=C7=C3=B4=D2=B3=C2=EB=CA=FD=CE=AA: =
I, II, III, IV, V. =
=D7=DC=B9=B2=D3=D07=B8=F6I=B3=F6=CF=D6=A3=AC2=B8=F6V=B3=F6=CF=D6=A1=A3=20
<BR><BR>PROGRAM NAME: preface<BR><BR>INPUT =
FORMAT<BR>=D2=BB=B8=F6=D5=FB=CA=FDN=A1=A3 <BR><BR>SAMPLE=20
INPUT(preface.in) <BR>5<BR><BR>OUTPUT=20
=
FORMAT<BR>=C3=BF=D0=D0=D2=BB=B8=F6=D7=D6=B7=FB=BA=CD=D2=BB=B8=F6=CA=FD=D7=
=D6k=A3=AC=B1=ED=CA=BE=D5=E2=B8=F6=D7=D6=B7=FB=B3=F6=CF=D6=C1=CBk=B4=CE=A1=
=A3=D7=D6=B7=FB=B1=D8=D0=EB=B0=B4=CA=FD=D7=D6=B1=ED=D6=D0=B5=C4=B5=DD=D4=F6=
=CB=B3=D0=F2=CA=E4=B3=F6=A1=A3 <BR><BR>SAMPLE=20
OUTPUT(preface.out)<BR>I 7<BR>V 2</DIV>
<P></P>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.2.1 Preface Numbering =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1</STRONG></P>
=
<P><STRONG>=BF=B4=CB=C6=C2=E9=B7=B3=B5=C4=C4=A3=C4=E2=CC=E2=A3=AC=D2=BB=BF=
=AA=CA=BC=B2=BB=C3=F7=B0=D7=C2=DE=C2=ED=CA=FD=D7=D6=D4=F5=C3=B4=D7=AA=BB=BB=
=A3=AC=C6=E4=CA=B5=C2=DE=C2=ED=CA=FD=D7=D6=D4=DA=C3=BF=D2=BB=CE=BB=C9=CF=B5=
=C4=C3=BF=D2=BB=B8=F6=CA=FD=D3=C0=D4=B6=B6=BC=CA=C7=CF=E0=CD=AC=B5=C4=A3=AC=
=D5=E2=D1=F9=BE=CD=BA=C3=D7=AA=BB=BB=C1=CB=A1=A3</STRONG></P>
=
<P><STRONG>=D7=AA=BB=BB=B7=BD=B7=A8[i,j]i=CE=BB=B5=C4j=D3=A6=B8=C3=D3=C3=CA=
=B2=C3=B4=B1=ED=B4=EF=A1=A3</STRONG></P>
=
<P><STRONG>10=BD=F8=D6=C6=D7=AA=C2=DE=C2=ED=CA=FD=D7=D6=B1=ED=A1=A3<FONT =
style=3D"BACKGROUND-COLOR: #ffffff"=20
color=3D#ffffff =
size=3D1>tab=A3=BA10=BD=F8=D6=C6=D7=AA=C2=DE=C2=ED=CA=FD=D7=D6 =
=B0=A2=C0=AD=B2=AE=CA=FD=D7=D6=D7=AA=C2=DE=C2=ED=CA=FD=D7=D6 =
=C2=DE=C2=ED=CA=FD=D7=D6=D7=AA=BB=BB=C6=F7=20
=CA=FD=D7=D6=D7=AA=BB=BB</FONT></STRONG></P>
<P><STRONG>change:array[1..4,0..9]of=20
=
string=3D(('','I','II','III','IV','V','VI','VII','VIII','IX'),<BR> &=
nbsp; &n=
bsp; &nb=
sp; =20
=
('','X','XX','XXX','XL','L','LX','LXX','LXXX','XC'),<BR>  =
; =
&=
nbsp; =20
=
('','C','CC','CCC','CD','D','DC','DCC','DCCC','CM'),<BR>  =
; =
&=
nbsp; =20
('','M','MM','MMM','','','','','',''));</STRONG></P>
<P><STRONG>code=A3=BA</STRONG></P>
<P><STRONG>{<BR>TASK:preface<BR>LANG:PASCAL<BR>}<BR>program=20
preface;<BR>const<BR> change:array[1..4,0..9]of=20
=
string=3D(('','I','II','III','IV','V','VI','VII','VIII','IX'),<BR> &=
nbsp; &n=
bsp; &nb=
sp; =20
=
('','X','XX','XXX','XL','L','LX','LXX','LXXX','XC'),<BR>  =
; =
&=
nbsp; =20
=
('','C','CC','CCC','CD','D','DC','DCC','DCCC','CM'),<BR>  =
; =
&=
nbsp; =20
=
('','M','MM','MMM','','','','','',''));<BR>var<BR> =20
ans:array['A'..'Z'] of integer;<BR> =20
n:integer;<BR>procedure init;<BR>begin<BR> =20
assign(input,'preface.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR>end;<BR>procedure=20
reverse(x:integer);<BR>var<BR> =20
w,i:integer;<BR> =20
s:string;<BR>begin<BR> =20
w:=3Dtrunc(ln(x)/ln(10))+1;<BR> =20
s:=3D'';<BR> for i:=3D1 to w=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
s:=3Ds+change[i,x mod=20
=
10];<BR>  =
;=20
x:=3Dx div 10;<BR> =20
end;<BR> for i:=3D1 to length(s)=20
do<BR> =20
inc(ans[s[i]]);<BR>end;<BR>procedure =
work;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
=
assign(output,'preface.out');rewrite(output);<BR> for=20
i:=3D1 to n do<BR> =20
reverse(i);<BR> if ans['I']>0 then writeln('I =
',ans['I']);<BR> if ans['V']>0 then =
writeln('V=20
',ans['V']);<BR> if ans['X']>0 then =
writeln('X=20
',ans['X']);<BR> if ans['L']>0 then =
writeln('L=20
',ans['L']);<BR> if ans['C']>0 then =
writeln('C=20
',ans['C']);<BR> if ans['D']>0 then =
writeln('D=20
',ans['D']);<BR> if ans['M']>0 then =
writeln('M=20
',ans['M']);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6=A3=AC=D2=B2=CA=C7=C3=B6=BE=D9</STRONG>=
</P>
<P><STRONG>Since the maximum problem size is fairly small, it =
makes sense=20
to just calculate the corresponding roman number for each page =
number, and=20
count letters. </STRONG></P>
<P><STRONG>The tricky part is generating the roman numbers. The =
key=20
insight is that roman numbers are not much different than our own =
decimal=20
digits. The two differences are that the set of digits changes =
depending=20
on which decimal place we're worrying about, and that sometimes a =
"digit"=20
is multiple letters or no letters (in the case of zero). So for =
example,=20
in the ones place 7 is written "VII" and in the tens place "LXX", =
and so=20
on, but it's always the same format: the letter for 5 and then two =
occurrences of the letter for 1. </STRONG></P>
<P><STRONG>We use a lookup table called "encode" to encode each =
digit,=20
translating from the letters for the ones place to the letters for =
the=20
place that we care about. The "romandigit" function takes care of =
each=20
digit, and the "roman" function strings them all together. =
</STRONG></P><PRE><STRONG>/*
PROG: preface
ID: rsc001
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
static char *encode[] =3D {
"", "I", "II", "III", "IV",
"V", "VI", "VII", "VIII", "IX",
};
char*
romandigit(int d, char *ivx)
{
char *s, *p;
static char str[10];
for(s=3Dencode[d%10], p=3Dstr; *s; s++, p++) {
switch(*s){
case 'I':
*p =3D ivx[0];
break;
case 'V':
*p =3D ivx[1];
break;
case 'X':
*p =3D ivx[2];
break;
}
}
*p =3D '\0';
return str;
}
char*
roman(int n)
{
static char buf[20];
strcpy(buf, "");
strcat(buf, romandigit(n/1000, "M"));
strcat(buf, romandigit(n/100, "CDM"));
strcat(buf, romandigit(n/10, "XLC"));
strcat(buf, romandigit(n, "IVX"));
return buf;
}
void
main(void)
{
FILE *fin, *fout;
int i, n;
char *s;
int count[256];
fin =3D fopen("preface.in", "r");
fout =3D fopen("preface.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &n);
for(s=3D"IVXLCDM"; *s; s++)
count[*s] =3D 0;
for(i=3D1; i<=3Dn; i++)
for(s=3Droman(i); *s; s++)
count[*s]++;
for(s=3D"IVXLCDM"; *s; s++)
if(count[*s])
fprintf(fout, "%c %d\n", *s, count[*s]);
exit(0);
}
</STRONG></PRE>
<H3>Alex Schendner's Algorithm</H3>
<P><STRONG>Alex writes: <BR>While you certainly can find out what =
the=20
Roman numerals are, the problem does not ask for that information =
and the=20
program can be made simpler if you only keep track of how many for =
each=20
digit there are. [Kolstad simplified the program slightly.] =
</STRONG></P><PRE><STRONG>#include <fstream.h>
int Ig =3D 0;
int Vg =3D 0;
int Xg =3D 0;
int Lg =3D 0;
int Cg =3D 0;
int Dg =3D 0;
int Mg =3D 0;
inline void=20
roman (int x)
{
int I =3D 0;
int V =3D 0;
int X =3D 0;
int L =3D 0;
int C =3D 0;
int D =3D 0;
int M =3D 0;
for ( ; x >=3D 1000; ++M, x -=3D 1000);
for ( ; x >=3D 500; ++D, x -=3D 500);
for ( ; x >=3D 100; ++C, x -=3D 100);
for ( ; x >=3D 50; ++L, x -=3D 50);
for ( ; x >=3D 10; ++X, x -=3D 10);
for ( ; x >=3D 5; ++V, x -=3D 5);
for ( ; x >=3D 1; ++I, x -=3D 1);
while (D > 0 && (C / 4) > 0) {
--D; C -=3D 4; ++M; ++C;
}
while (C >=3D 4) {
C -=3D 4; ++D; ++C;
}
while (L > 0 && (X / 4) > 0) {
--L; X -=3D 4; ++C; ++X;
}
while (X >=3D 4) {
X -=3D 4; ++L; ++X;
}
while (V > 0 && (I / 4) > 0) {
--V; I -=3D 4; ++X; ++I;
}
while (I >=3D 4) {
I -=3D 4; ++V; ++I;
}
Ig +=3D I;
Vg +=3D V;
Xg +=3D X;
Lg +=3D L;
Cg +=3D C;
Dg +=3D D;
Mg +=3D M;
return;
}
int=20
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -