?? usaco 2_2_3 runaround numbers 題解_leokan的blog.mht
字號:
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<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.3 Runaround Numbers =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C228=C8=D5 =D0=C7=C6=DA=D2=BB =
19:59</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.2.3 Runaround Numbers</H2>
<DIV class=3Dt_msgfont>Runaround Numbers<BR><BR>Runaround numbers =
are=20
integers with unique digits, none of which is zero (e.g., 81362) =
that also=20
have an interesting property, exemplified by this demonstration:=20
<BR><BR>If you start at the left digit (8 in our number) and count =
that=20
number of digits to the right (wrapping back to the first digit =
when no=20
digits on the right are available), you'll end up at a new digit =
(a number=20
which does not end up at a new digit is not a Runaround Number). =
Consider:=20
8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so =
the next=20
digit is 6. <BR>Repeat this cycle (this time for the six counts =
designed=20
by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely =
2.=20
<BR>Repeat again (two digits this time): 8 1 <BR>Continue again =
(one digit=20
this time): 3 <BR>One more time: 6 2 8 and you have ended up back =
where=20
you started, after touching each digit once. If you don't end up =
back=20
where you started after touching each digit once, your number is =
not a=20
Runaround number. <BR>Given a number M (that has anywhere from 1 =
through 9=20
digits), find and print the next runaround number higher than M, =
which=20
will always fit into an unsigned long integer for the given test =
data.=20
<BR><BR>PROGRAM NAME: runround<BR>INPUT FORMAT<BR>A single line =
with a=20
single integer, M <BR>SAMPLE INPUT (file runround.in)=20
<BR>81361<BR><BR>OUTPUT FORMAT<BR>A single line containing the =
next=20
runaround number higher than the input value, M. <BR>SAMPLE OUTPUT =
(file=20
runround.out)<BR>81362<BR><BR><BR><BR>Runaround =
Numbers<BR><BR>=D1=AD=BB=B7=CA=FD=20
<BR><BR>=D2=EB by Henry =
HuGang<BR><BR>=D1=AD=BB=B7=CA=FD=CA=C7=C4=C7=D0=A9=B2=BB=B0=FC=C0=A80=D5=E2=
=B8=F6=CA=FD=D7=D6=B5=C4=C3=BB=D3=D0=D6=D8=B8=B4=CA=FD=D7=D6=B5=C4=D5=FB=CA=
=FD (=B1=C8=C8=E7=CB=B5, 81362)=20
=
=B2=A2=C7=D2=CD=AC=CA=B1=BE=DF=D3=D0=D2=BB=B8=F6=D3=D0=C8=A4=B5=C4=D0=D4=D6=
=CA, =BE=CD=CF=F1=D5=E2=B8=F6=C0=FD=D7=D3: =
<BR><BR>=C8=E7=B9=FB=C4=E3=B4=D3=D7=EE=D7=F3=B1=DF=B5=C4=CA=FD=D7=D6=BF=AA=
=CA=BC ( =D4=DA=D5=E2=B8=F6=C0=FD=D7=D3=D6=D0=CA=C78)=20
=
=CA=FD=D7=EE=D7=F3=B1=DF=D5=E2=B8=F6=CA=FD=D7=D6=B8=F6=CA=FD=D7=D6=B5=BD=D3=
=D2=B1=DF(=BB=D8=B5=BD=D7=EE=D7=F3=B1=DF=C8=E7=B9=FB=CA=FD=B5=BD=C1=CB=D7=
=EE=D3=D2=B1=DF),=C4=E3=BB=E1=CD=A3=D6=B9=D4=DA=C1=ED=D2=BB=B8=F6=D0=C2=B5=
=C4=CA=FD=D7=D6(=C8=E7=B9=FB=C3=BB=D3=D0=CD=A3=D4=DA=D2=BB=B8=F6=B2=BB=CD=
=AC=B5=C4=CA=FD=D7=D6=C9=CF=A3=AC=D5=E2=B8=F6=CA=FD=BE=CD=B2=BB=CA=C7=D1=AD=
=BB=B7=CA=FD). =BE=CD=CF=F1:=20
8 1 3 6 2 =
=B4=D3=D7=EE=D7=F3=B1=DF=BD=D3=CF=C2=C8=A5=CA=FD8=B8=F6=CA=FD=D7=D6: 1 3 =
6 2 8 1 3 6 =CB=F9=D2=D4=CF=C2=D2=BB=B8=F6=CA=FD=D7=D6=CA=C76. =
<BR>=D6=D8=B8=B4=D5=E2=D1=F9=D7=F6=20
=
(=D5=E2=B4=CE=B4=D3=A1=B06=A1=B1=BF=AA=CA=BC=CA=FD6=B8=F6=CA=FD=D7=D6) =
=B2=A2=C7=D2=C4=E3=BB=E1=CD=A3=D6=B9=D4=DA=D2=BB=B8=F6=D0=C2=B5=C4=CA=FD=D7=
=D6=C9=CF: 2 8 1 3 6 2, =D2=B2=BE=CD=CA=C72. =
<BR>=D4=D9=D5=E2=D1=F9=D7=F6 (=D5=E2=B4=CE=CA=FD=C1=BD=B8=F6): 8 1=20
<BR>=D4=D9=D2=BB=B4=CE (=D5=E2=B4=CE=D2=BB=B8=F6): 3 =
<BR>=D3=D6=D2=BB=B4=CE: 6 2 8 =
=D5=E2=CA=C7=C4=E3=BB=D8=B5=BD=C1=CB=C6=F0=B5=E3, =
=D4=DA=B4=D3=C3=BF=D2=BB=B8=F6=CA=FD=D7=D6=BF=AA=CA=BC=CA=FD1=B4=CE=D6=AE=
=BA=F3.=20
=
=C8=E7=B9=FB=C4=E3=D4=DA=B4=D3=C3=BF=D2=BB=B8=F6=CA=FD=D7=D6=BF=AA=CA=BC=CA=
=FD=D2=BB=B4=CE=D2=D4=BA=F3=C3=BB=D3=D0=BB=D8=B5=BD=C6=F0=B5=E3, =
=C4=E3=B5=C4=CA=FD=D7=D6=B2=BB=CA=C7=D2=BB=B8=F6=D1=AD=BB=B7=CA=FD=A1=A3 =
<BR>=B8=F8=C4=E3=D2=BB=B8=F6=CA=FD=D7=D6 M =
(=D4=DA1=B5=BD9=CE=BB=D6=AE=BC=E4), =D5=D2=B3=F6=B5=DA=D2=BB=B8=F6=B1=C8 =
M=B4=F3=B5=C4=D1=AD=BB=B7=CA=FD, =
=B2=A2=C7=D2=D2=BB=B6=A8=C4=DC=D3=C3=D2=BB=B8=F6=CE=DE=B7=FB=BA=C5=B3=A4=D5=
=FB=D0=CE=CA=FD=D7=B0=CF=C2=A1=A3 <BR><BR>PROGRAM NAME: runround =
<BR><BR>INPUT=20
FORMAT <BR><BR>=BD=F6=BD=F6=D2=BB=D0=D0, =B0=FC=C0=A8M =
<BR><BR>SAMPLE INPUT (file runround.in)=20
<BR><BR>81361 <BR><BR>OUTPUT FORMAT =
<BR><BR>=BD=F6=BD=F6=D2=BB=D0=D0=A3=AC=B0=FC=C0=A8=B5=DA=D2=BB=B8=F6=B1=C8=
M=B4=F3=B5=C4=D1=AD=BB=B7=CA=FD=A1=A3=20
<BR><BR>SAMPLE OUTPUT (file runround.out) <BR><BR>81362</DIV>
<P></P>
<HR>
<P></P>
<P>USACO 2.2.3 Runaround =
Numbers<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE</P>
=
<P>=C4=A3=C4=E2=BC=B4=BF=C9=A3=AC=C5=D0=B6=CF=D2=BB=B8=F6=CA=FD=CB=FC=CA=C7=
=B2=BB=CA=C7=D1=AD=BB=B7=CA=FD=A3=AC=B2=BB=CA=C7=BE=CD+1=D4=D9=C5=D0=B6=CF=
=A3=AC=C5=D0=B6=CF=B5=C4=CB=B3=D0=F2=D3=A6=B8=C3=C8=B7=B6=A8=BA=C3=BF=C9=D2=
=D4=BD=DA=CA=A1=CA=B1=BC=E4=A3=AC=B1=C8=C8=E7=CF=C8=C5=D0=B6=CF=D3=D0=C3=BB=
=D3=D00=A1=A3</P>
<P>{<BR>TASK:runround<BR>LANG:PASCAL<BR>}<BR>program=20
runround;<BR>const<BR> valn:array['1'..'9'] of=20
integer=3D(1,2,3,4,5,6,7,8,9);<BR>var<BR> =20
n:longint;<BR>procedure init;<BR>begin<BR> =20
assign(input,'runround.in');reset(input);<BR> =20
readln(n);<BR> close(input);<BR>end;<BR>function =
check(x:longint):boolean;<BR>var<BR> =20
i,len,count:integer;<BR> =
s:string;<BR> =20
visit:array['1'..'9'] of boolean;<BR>begin<BR> =20
str(x,s);<BR> if pos('0',s)>0 then=20
exit(false);<BR> =
len:=3Dlength(s);<BR> =20
count:=3D0;<BR> =20
fillchar(visit,sizeof(visit),false);<BR> =20
i:=3D1;<BR> while count<len=20
do<BR> =20
begin<BR> if=20
visit[s[i]]and(count<len) then=20
exit(false)<BR> else=20
visit[s[i]]:=3Dtrue;<BR> =
i:=3D(i+valn[s[i]]) mod len;if i=3D0 then=20
i:=3Dlen;<BR> =20
inc(count);<BR> =20
end;<BR> if s[i]<>s[1] then=20
exit(false);<BR> =
exit(true);<BR>end;<BR>procedure=20
work;<BR>begin<BR> =20
=
assign(output,'runround.out');rewrite(output);<BR> =20
inc(n);<BR> while not check(n) do=20
inc(n);<BR> writeln(n);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</P>
<P></P>
<HR>
=
<P>USACO=B5=C4=B7=D6=CE=F6=A3=AC=BA=F3=C3=E6=C4=C7=B8=F6=CA=C7=D3=C3=CA=FD=
=D7=E9=BC=D3=A3=AC=D6=BB=C5=D0=B6=CF=BF=C9=C4=DC=B5=C4=CA=FD=D7=D6=A3=AC=B5=
=AB=CA=C7=B1=E0=B3=CC=B8=B4=D4=D3=C1=CB=B5=E3=A3=AC=D0=D4=BC=DB=B1=C8=B2=BB=
=B8=DF=A1=A3</P>
<CENTER><BR>Russ Cox </CENTER>
<P>The trick to this problem is noticing that since runaround =
numbers must=20
have unique digits, they must be at most 9 digits long. There are =
only 9!=20
=3D 362880 nine-digit numbers with unique digits, so there are =
fewer than=20
9*362880 numbers with up to 9 unique digits. Further, they are =
easy to=20
generate, so we generate all of them in increasing order, test to =
see if=20
they are runaround, and then take the first one bigger than our =
input.</P><PRE>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
int m;
FILE *fout;
/* check if s is a runaround number; mark where we've been by writing =
'X' */
int
isrunaround(char *s)
{
int oi, i, j, len;
char t[10];
strcpy(t, s);
len =3D strlen(t);
i=3D0;
while(t[i] !=3D 'X') {
oi =3D i;
i =3D (i + t[i]-'0') % len;
t[oi] =3D 'X';
}
/* if the string is all X's and we ended at 0, it's a runaround */
if(i !=3D 0)
return 0;
for(j=3D0; j<len; j++)
if(t[j] !=3D 'X')
return 0;
return 1;
}
/*
* create an md-digit number in the string s.
* the used array keeps track of which digits are already taken.
* s already has nd digits.
*/
void
permutation(char *s, int *used, int nd, int md)
{
int i;
if(nd =3D=3D md) {
s[nd] =3D '\0';
if(atoi(s) > m && isrunaround(s)) {
fprintf(fout, "%s\n", s);
exit(0);
}
return;
}
for(i=3D1; i<=3D9; i++) {
if(!used[i]) {
s[nd] =3D i+'0';
used[i] =3D 1;
permutation(s, used, nd+1, md);
used[i] =3D 0;
}
}
}
void
main(void)
{
FILE *fin;
char s[10];
int i, used[10];
fin =3D fopen("runround.in", "r");
fout =3D fopen("runround.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &m);
for(i=3D0; i<10; i++)
used[i] =3D 0;
for(i=3D1; i<=3D9; i++)
permutation(s, used, 0, i);
assert(0); /* not reached */
}</PRE>
<H3>Another look</H3>
<P><EM>Diego Exactas from Argentina has a better solution that =
runs=20
extremely quickly.</EM></P>
<P>This is my solution, with doesn't generate all solutions, but =
just=20
looks for the next one.</P><PRE>#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#define INPUT_FILE "runround.in"
#define OUTPUT_FILE "runround.out"
using namespace std;
void NextNumber(std::vector<int>& number, int Digits) {
number[Digits - 1]++;
for (int i =3D Digits - 1; i >=3D 0; i--) {
if (number[i] =3D=3D 10) {
number[i] =3D 1;
if (i =3D=3D 0) {
number.insert (number.begin(),1);
return;
} else=20
number[i - 1]++;
}
}
return;
}
bool CheckElement(std::vector<int>::iterator first,
std::vector<int>::iterator last, int val) {
while (first < last) {
if (*first =3D=3D val)=20
return true;
++first;
}
return false;
}
void NextUniqueNumber(std::vector<int>& number) {
std::vector<int> old =3D number;
for (int i =3D 1; i < number.size(); ++i) {
if (number[i] =3D=3D 0) number[i]++;
while (CheckElement (number.begin(),number.begin() + =
i,number[i])) {
number[i]++;
if (number[i] =3D=3D 10) {
number[i] =3D 1;
NextNumber (number,i);
i =3D 1;
continue;
}
}
}
return;
}
bool IsRoundNumber(std::vector<int>& number) {
std::vector<bool> used(10,false);
for (int i =3D 0, pos =3D 0, val =3D number[0]; i < =
number.size(); i++) {
pos =3D (pos + val) % number.size();
val =3D number[pos];
if (used[pos] =3D=3D true) return false;
used[pos] =3D true;
}
return true;
}
unsigned int NextRoundNumber(unsigned int number) {
std::vector<int> digits;
for (int i =3D 0, tens =3D 1; i <=3D 10; ++i, tens *=3D 10) {
int partial =3D number / tens;
if (partial =3D=3D 0) break;
partial %=3D 10;
digits.push_back(partial);
}
std::reverse (digits.begin(),digits.end());
NextNumber (digits,digits.size());
NextUniqueNumber (digits);
while (!IsRoundNumber(digits)) {
NextNumber (digits,digits.size());
NextUniqueNumber (digits);
}
number =3D 0;
for (int i =3D 0; i < digits.size(); i++)=20
number =3D 10 * number + digits[i];
return number;
}
int main(int argc, char *argv[]) {
ifstream FileInput (INPUT_FILE);
ofstream FileOutput (OUTPUT_FILE);
unsigned int Number;
FileInput >> Number;
FileOutput << NextRoundNumber(Number) << "\n";
return 0;
}</PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/9837adeccdcc0e3926979197">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/9837adeccdcc0e3926979197.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3D9837adeccdcc0e3926979197=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -