/*20140729 hanting*/
#include <iostream>
#include <sstream>
using namespace std;
void run(int a[][1000],int,int);
int router_num;
int main()
{
while(cin>>router_num)
{
cout<<"-----"<<endl;
int Net[router_num+2][1000];
for(int i=0;i<router_num+2;i++)
for(int j=0;j<router_num+2;j++)
Net[i][j]=0;
int ID,temp;
char c;
for(int i=0;i<router_num;i++)
{
cin>>ID;
string s;
getline(cin,s);
if(s.size()==1) continue;
istringstream sin(s);
char c;
while(sin>>c)
{
sin>>temp;
Net[ID][temp]=1;
}
}
int connect_num;
cin>>connect_num;
int starting,ending;
for(int i=0;i<connect_num;i++)
{
cin>>starting>>ending;
run(Net,starting,ending);
}
}
return 0;
}
void run(int a[][1000],int starting,int ending)
{
int tempa[router_num+2][router_num+2];
for(int i=0;i<router_num+2;i++)
for(int j=0;j<router_num+2;j++)
tempa[i][j]=a[i][j];
int b[100][1000]={starting};
int m,n=1;
int i;
for(i=1;i>=0;i++)
{
m=n;
n=0;
for(int j=0;j<m;j++)
{
int ID=b[i-1][j];
for(int k=1;k<=router_num;k++)
{
if(tempa[ID][k])
{
b[i][n++]=k;
if(k==ending)
{
m=0;
break;
}
tempa[ID][k]=0;
}
}
}
if(!n)
{
cout<<"connection impossible"<<endl;
return;
}
if(!m) break;
}
int temp=ending;
int route[1000]={temp};
int con=0;
for(int j=i-1;j>=0;j--)
{
for(int k=0;k>=0;k++)
{
int ID=b[j][k];
if(a[ID][temp])
{
temp=ID;
route[con++]=temp;
break;
}
}
}
for(int i=con-1;i>=0;i--)
{
cout<<route[i]<<" ";
}
cout<<ending<<endl;
}
2014年7月29日 星期二
[UVA] 627 - The Net
2014年7月28日 星期一
[UVA] 1225 - Digit Counting
/*20140728 hanting*/
#include <iostream>
using namespace std;
void count(int *a,int i)
{
while(i)
{
a[i%10]++;
i/=10;
}
}
int main()
{
int N;
cin>>N;
while(N--)
{
int n;
cin>>n;
int a[10]={0};
for(int i=1;i<=n;i++)
{
count(a,i);
}
for(int i=0;i<10;i++)
{
cout<<a[i]<<(i!=9 ? ' ':'\n');
}
}
return 0;
}
2014年7月27日 星期日
[UVA] 11687 - Digits
/*20140728 hanting*/
#include <iostream>
#include <sstream>
using namespace std;
int dcount(long long int a)
{
int temp=0;
if(!a) return 1;
while(a)
{
a/=10;
temp++;
}
return temp;
}
int main()
{
string s;
long long int a;
while(cin>>s && s!="END")
{
stringstream ss;
ss<<s;
ss>>a;
int x1=a,x2=dcount(a);
int con=0;
while(x1!=x2)
{
x1=x2;
x2=dcount(x2);
con++;
}
cout<<++con<<endl;
}
return 0;
}
[UVA] 825 - Walking on the Safe Side
/*20140727 hanting*/
#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
int main()
{
int N;
cin>>N;
int blankline=0;
while(N--)
{
if(blankline) cout<<endl;
int w,e;
cin>>w>>e;
int a[500][500]={1};
int temp,temp2;
for(int i=0;i<w;i++)
{
cin>>temp;
string s;
getline(cin,s);
istringstream sin(s);
while(sin>>temp2)
{
a[temp-1][temp2-1]=-1;
}
}
for(int i=0;i<w;i++)
{
for(int j=0;j<e;j++)
{
if(a[i][j]==-1) continue;
if(a[i-1][j]!=-1 && i)
{
a[i][j]+=a[i-1][j];
}
if(a[i+1][j]!=-1)
{
a[i][j]+=a[i+1][j];
}
if(a[i][j-1]!=-1 && j)
{
a[i][j]+=a[i][j-1];
}
if(a[i][j+1]!=-1)
{
a[i][j]+=a[i][j+1];
}
}
}
cout<<a[w-1][e-1]<<endl;
blankline=1;
}
return 0;
}
2014年7月24日 星期四
[UVA] 294 - Divisors
/*20140725 hanting*/
#include <iostream>
using namespace std;
int prime[10000];
int div(int N)
{
int DivSum=1;
for(int i=0;N!=1;i++)
{
int x=0;
if(prime[i]==0)
{
return DivSum*2;
}
while(N%prime[i]==0)
{
x++;
N/=prime[i];
}
DivSum*=x+1;
}
return DivSum;
}
int main()
{
int Num[50000]={0};
int x=0;
for(int i=2;i<50000;i++)
{
if(Num[i]==0)
{
prime[x++]=i;
for(int j=i;j<50000;j+=i)
{
Num[j]=1;
}
}
}
int N;
cin>>N;
while(N--)
{
int m,n;
int num;
int MaxDiv=0;
cin>>m>>n;
for(int i=m;i<=n;i++)
{
int Div=div(i);
if(Div>MaxDiv)
{
MaxDiv=Div;
num=i;
}
}
cout<<"Between "<<m<<" and "<<n<<", "<<num<<" has a maximum of "<<MaxDiv<<" divisors."<<endl;
}
return 0;
}
2014年7月23日 星期三
[UVA] 10465 - Homer Simpson
/*20140723 hanting*/
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int m,n,t;
while(cin>>m>>n>>t)
{
if(m>n) swap(m,n);
if(t<m)/*it's possible that Homer can't eat anything*/
{
cout<<0<<" "<<t<<endl;
continue;
}
vector<int> a(11000);
for(int j=0;j<11000;j+=n)
{
for(int i=j;i<11000;i+=m)
{
if(a[i]==0)a[i]=(i-j)/m+j/n;
}
}
if(a[t])cout<<a[t]<<endl;
else
{
for(int i=0;i<t;i++)
{
if(a[t-i])
{
cout<<a[t-i]<<" "<<i<<endl;
break;
}
}
}
}
return 0;
}
2014年7月22日 星期二
[UVA] 10189 - Minesweeper
/*20140722 hanting*/
#include <iostream>
using namespace std;
int main()
{
int n,m;
int times=0;
while(cin>>n>>m ,n+m)
{
char c[200][200]={0};
int a[200][200]={0};
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>c[i][j];
if(c[i][j]=='*')
{
for(int x=0;x<3;x++)
{
for(int y=0;y<3;y++)
{
a[i-1+x][j-1+y]++;
}
}
}
}
}
if(times!=0) cout<<endl;
cout<<"Field #"<<++times<<":"<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(c[i][j]=='*') cout<<'*';
else cout<<a[i][j];
}
cout<<endl;
}
}
return 0;
}
2014年7月20日 星期日
[UVA] 11185 - Ternary
/*20140721 hanting*/
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
void Itoa(int N,char *s,int ary);
int main()
{
int N;
char s[25];
while(cin>>s && s[0]!='-')
{
char ans[25];
for(int i=0;i<25;i++) ans[i]='-';
N=atoi(s);
Itoa(N,ans,3);
cout<<ans<<endl;
}
return 0;
}
void Itoa(int N,char *ans,int ary)
{
int i=0;
for(i=0;i<25;i++)
{
ans[i]=(N%ary)+48;
N/=ary;
if(N==0) break;
}
reverse(ans,ans+i+1);
ans[i+1]=0;
}
2014年7月19日 星期六
[UVA] 10473 - Simple Base Conversion
/*20140720 hanting*/
#include <iostream>
#include <iomanip>
#include <sstream>
using namespace std;
int main()
{
string s;
while(getline(cin,s) && s[0]!='-')
{
stringstream ss;
long long int a;
if(s[1]=='x')
{
ss<<s;
ss>>hex>>a;
cout<<dec<<a<<endl;
}
else
{
ss<<s;
ss>>a;
cout<<"0x"<<hex<<uppercase<<a<<endl;
}
}
return 0;
}
訂閱：
文章 (Atom)