/*20150223 hanting*/
#include <iostream>
using namespace std;
int f[10001][401]={0};
void output(int *f)
{
int i=400;
while(f[i]==0 && i>0) i--;
cout<<f[i];
for(int j=i-1;j>=0;j--)
{
cout.width(3);
cout.fill('0');
cout<<f[j];
}
cout<<endl;
}
int main()
{
f[0][0]=0;
f[1][0]=1;
for(int i=2;i<10001;i++)
{
//f[i]=f[i-1]+f[i-2]
for(int j=0;j<400;j++)
{
f[i][j]=f[i-1][j]+f[i-2][j];
}
for(int j=1;j<400;j++)
{
f[i][j]+=f[i][j-1]/1000;
f[i][j-1]%=1000;
}
}
int N;
while(cin>>N) output(f[N]);
return 0;
}
2015年2月22日 星期日
[UVA] 10579 - Fibonacci Numbers
[UVA] 495 - Fibonacci Freeze
/*20150223 hanting*/
#include <iostream>
using namespace std;
struct BigNum
{
int num[1200];
int digit;
BigNum()
{
fill(num,num+1200,0);
digit=0;
}
int digitCount()
{
for(int i=1200;i>=0;i--)
{
if(num[i]) return i+1;
}
}
void operator=(int n)
{
if(n==0) digit++;
while(n)
{
num[digit++]=n%10;
n/=10;
}
}
BigNum operator+(BigNum a)
{
BigNum sum;
for(int i=0;i<1200;i++)
{
sum.num[i]=num[i]+a.num[i];
}
for(int i=1;i<1200;i++)
{
sum.num[i]+=sum.num[i-1]/10;
sum.num[i-1]%=10;
}
sum.digit=sum.digitCount();
return sum;
}
friend ostream& operator<<(ostream& bout,BigNum b)
{
bout<<b.num[b.digit-1];
for(int i=b.digit-2;i>=0;i--)
{
bout<<b.num[i];
}
return bout;
}
};
BigNum DP[5001];
BigNum f(int N)
{
if(DP[N].digit) return DP[N];
else
{
DP[N]=f(N-1)+f(N-2);
return DP[N];
}
}
int main()
{
DP[0]=0;
DP[1]=1;
for(int i=200;i<=5000;i+=200)
{
DP[i]=f(i);
}
int N;
while(cin>>N)
{
cout<<"The Fibonacci number for "<<N<<" is "<<f(N)<<endl;
}
return 0;
}
2015年2月21日 星期六
[UVA] 485 - Pascal's Triangle of Death
/*20150221 hanting*/
#include <iostream>
using namespace std;
struct BigNum
{
int num[61];
int digit;
BigNum()
{
fill(num,num+61,0);
digit=0;
}
int digitCount()
{
for(int i=60;i>=0;i--)
{
if(num[i]!=0) return i+1;
}
}
BigNum operator+(BigNum a)
{
BigNum sum;
for(int i=0;i<61;i++)
{
sum.num[i]=num[i]+a.num[i];
}
for(int i=1;i<61;i++)
{
sum.num[i]+=sum.num[i-1]/1000;
sum.num[i-1]%=1000;
}
int sumDigit=max(digit,a.digit);
sum.digit=(sum.num[sumDigit] ? sumDigit+1:sumDigit);
return sum;
}
void operator=(int i)
{
digit=0;
while(i)
{
num[digit++]=i%1000;
i/=1000;
}
}
friend ostream& operator<<(ostream& bout,BigNum bnum)
{
bout<<bnum.num[bnum.digit-1];
for(int i=bnum.digit-2;i>=0;i--)
{
bout.width(3);
bout.fill('0');
bout<<bnum.num[i];
}
return bout;
}
};
void output(BigNum *Last,int lastCount,BigNum *This)
{
cout<<Last[0];
for(int i=1;i<lastCount;i++)
{
cout<<" "<<Last[i];
}
cout<<endl;
if(Last[lastCount/2].digit>=21) return ;
int ThisCount=lastCount+1;
This[0]=1;
for(int i=1;i<=lastCount/2;i++)
{
BigNum temp;
temp=Last[i]+Last[i-1];
This[i]=This[lastCount-i]=temp;
}
This[lastCount]=1;
BigNum *Next=Last;
output(This,ThisCount,Next);
}
int main()
{
BigNum Last[1000];
BigNum This[1000];
Last[0]=1;
output(Last,1,This);
return 0;
}
======================================================
# /* 題目: UVa 485 - Pascal’s Triangle of Death
# * https://onlinejudge.org/external/4/485.pdf
# * Language: Python
# * Created on: 2019年12月19日
# * Author: hanting
# */
times = 205
last = [1]
while(times > 0):
times -= 1
print(*last)
cur = [last[x] + (last[x-1] if x>0 else 0) for x in range(len(last))] + [1]
last = cur[:]2015年2月18日 星期三
[UVA] 10176 - Ocean Deep! - Make it shallow!!
/*20150219 hanting*/
//以10進位的11為例，11有2個1，先建立2個盒子A,B，分別代表十位數與個位數，
//假設一個數902，
//要判斷其為11的倍數，
//先從個位數開始，2放個位數，0放十位數，9放個位數，
//盒子值為11，是11的倍數，則902就是11的倍數，
//
//這一題以二進制表示
//131071(十進位)=11111111111111111(二進位) 17個1
//那麼就建立17個盒子，分別代表2的i次方，0<=i<17，
//照此方法將輸入的二進位值放入，再來判斷盒子值是否為131071的倍數
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int N=131071;
string str;
while(getline(cin,str))
{
while(str.find('#')>=str.size())//讀到終止
{
string temp;
getline(cin,temp);
str+=temp;
}
int arr[17]={0};
int StrSize=str.size()-1;//remove #
for(int i=StrSize-1;i>=0;i--)
{
arr[i%17]+=str[i]-48;
}
long long sum=0;
for(int i=0;i<17;i++)
{
sum+=arr[i]*pow(2.,i);
}
if(sum%131071==0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
2015年2月12日 星期四
[UVA] 216 - Getting in Line
/*20150213 hanting*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
struct coordinate
{
int x,y;
friend istream& operator>>(istream& in,coordinate &com)
{
in>>com.x>>com.y;
return in;
}
friend ostream& operator<<(ostream& out,coordinate &com)
{
out<<"("<<com.x<<","<<com.y<<")";
return out;
}
friend double operator-(coordinate &a,coordinate &b)
{
double ans;
ans=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
return sqrt(ans)+16;
}
};
void DFS(int *visit,int N,int now,int parent,coordinate *com,vector<coordinate> &ShortestPath,double &sum,double &Shortsum,vector<coordinate> &path)
{
visit[now]=1;
path.push_back(com[now]);
double distance=0;
if(parent!=-1)
{
distance=(com[parent] - com[now]);
sum+= distance;
}
if(!count(visit,visit+N,0))//形成hamilton path
{
if(Shortsum>sum || Shortsum==-1)
{
Shortsum=sum;
ShortestPath=path;
}
}
else
{
for(int i=0;i<N;i++)
{
if(visit[i]==0) DFS(visit,N,i,now,com,ShortestPath,sum,Shortsum,path);
}
}
visit[now]=0;
path.pop_back();
sum-=distance;
}
int main()
{
int N;
int times=0;
while(cin>>N && N)
{
cout<<"**********************************************************"<<endl;
cout<<"Network #"<<++times<<endl;
coordinate com[N];
for(int i=0;i<N;i++)
{
cin>>com[i];
}
int visit[N];
vector<coordinate> ShortestPath;
fill(visit,visit+N,0);
double pathsum=0;
double Shortsum=-1;
vector<coordinate> path;
for(int i=0;i<N;i++)
{
if(visit[i]==0)
{
DFS(visit,N,i,-1,com,ShortestPath,pathsum,Shortsum,path);
}
}
double sum=0;
for(int i=1;i<ShortestPath.size();i++)
{
double distance=(ShortestPath[i-1]-ShortestPath[i]);
cout<<fixed<<setprecision(2);
cout<<"Cable requirement to connect "<<ShortestPath[i-1]<<" to "<<ShortestPath[i]<<" is "<<distance<<" feet."<<endl;
sum+=distance;
}
cout<<"Number of feet of cable required is "<<sum<<"."<<endl;
}
return 0;
}
2015年2月10日 星期二
[UVA] 10499 - The Land of Justice
/*20150211 hanting*/
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int n;
while(cin>>n && n>0)
{
if(n==1) cout<<"0%"<<endl;
else
{
double ans=n/4.*100.;
cout<<fixed<<setprecision(0)<<ans<<"%"<<endl;
}
}
return 0;
}
[UVA] 10041 - Vito's Family
/*20150210 hanting*/
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N;
cin>>N;
while(N--)
{
int num;
cin>>num;
int relatives[num];
for(int i=0;i<num;i++)
{
cin>>relatives[i];
}
sort(relatives,relatives+num);
int medium=relatives[num/2];
int distance=0;
for(int i=0;i<num;i++)
{
distance+=relatives[i]>medium ? relatives[i]-medium : medium-relatives[i];
}
cout<<distance<<endl;
}
return 0;
}
2015年2月8日 星期日
[UVA] 151 - Power Crisis
/*20150208 hanting*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool Find(vector<int> num,int i)
{
vector<int>::iterator itr=find(num.begin(),num.end(),i);
return (itr!=num.end());
}
int main()
{
int N;
while(cin>>N && N)
{
int ans=1;
for(;ans;ans++)
{
vector<int> num(N);
for(int i=0;i<N;i++)
num[i]=i;
for(int i=0;i<N;)
{
num.erase(num.begin()+i);
i+=ans-1;
i%=num.size();
if(!Find(num,12) || num.size()==1)
{
break;
}
}
if(num.size()==1 && num[0]==12)
{
cout<<ans<<endl;
break;
}
}
}
return 0;
}
[UVA] 612 - DNA Sorting
/*20150208 hanting*/
#include <iostream>
#include <algorithm>
using namespace std;
struct DNA
{
int order;
int time;
};
int sortingTime(string str)
{
int time=0;
for(int i=0;i<str.size();i++)
{
for(int j=i+1;j<str.size();j++)
{
if(str[i]>str[j]) time++;
}
}
return time;
}
bool compare(DNA a,DNA b)
{
if(a.time==b.time) return a.order<b.order;
else return a.time<b.time;
}
int main()
{
int N;
int blank=0;
cin>>N;
while(N--)
{
if(blank) cout<<endl;
int row,col;
cin>>col>>row;
string str[row];
cin.get();
for(int i=0;i<row;i++)
{
getline(cin,str[i]);
}
DNA srt[row];
for(int i=0;i<row;i++)
{
srt[i].order=i;
srt[i].time=sortingTime(str[i]);
}
sort(srt,srt+row,compare);
for(int i=0;i<row;i++)
{
cout<<str[ srt[i].order ]<<endl;
}
blank=1;
}
return 0;
}
[UVA] 264 - Count on Cantor
/*20150208 hanting*/
#include <iostream>
using namespace std;
int main()
{
int N;
while(cin>>N)
{
int sum=0;
int level=1;//第1級(1,1) 第二級(1,2),(2,1)......
while(sum+level<N) sum+=level++;
//N在level級
int step=N-sum;//N在level的第step個
int levelSum=level+1;//N所在的那level，其總和//第n級總和=n+1
int fst,sec;
if(level&1)//奇數級 (遞減,遞增)
{
fst=levelSum-step;
sec=0+step;
}
else//偶數級 (遞增,遞減)
{
fst=0+step;
sec=levelSum-step;
}
cout<<"TERM "<<N<<" IS "<<fst<<"/"<<sec<<endl;
}
return 0;
}
2015年2月5日 星期四
[UVA] 10188 - Automated Judge Script
/*20140205 hanting*/
/*這題的評判標準只看數字部分*/
//AC是team與ans一模一樣
//PE是只要數字部分順序一樣就行了
//
//例如:
// 11 23 和 1 123 這樣算PE
// AABBC 和 AABBB 這樣也算PE
// AABB1 和 AABC1 這樣也算PE
// AA3BB 和 AA4BB 這樣就是WA
#include <iostream>
using namespace std;
int main()
{
int team,ans;
int times=0;
while(cin>>team && team)
{
cin.get();
string TeamOutput="";
for(int i=0;i<team;i++)
{
string temp;
getline(cin,temp);
TeamOutput+=temp;
}
string AnsOutput="";
cin>>ans;
cin.get();
for(int i=0;i<ans;i++)
{
string temp;
getline(cin,temp);
AnsOutput+=temp;
}
string TeamNum="";
string AnsNum="";
for(int i=0;i<TeamOutput.size();i++)
{
if(isdigit(TeamOutput[i])) TeamNum+=TeamOutput[i];
}
for(int i=0;i<AnsOutput.size();i++)
{
if(isdigit(AnsOutput[i])) AnsNum+=AnsOutput[i];
}
bool AC=1,PE=1;
if(TeamNum==AnsNum)
{
if(TeamOutput!=AnsOutput || team!=ans) AC=0;
}
else
{
AC=0;
PE=0;
}
if(AC) cout<<"Run #"<<++times<<": Accepted"<<endl;
else if(PE) cout<<"Run #"<<++times<<": Presentation Error"<<endl;
else cout<<"Run #"<<++times<<": Wrong Answer"<<endl;
}
return 0;
}
2015年2月4日 星期三
[UVA] 10924 - Prime Words
/*20150204 hanting*/
#include <iostream>
#include <cmath>
using namespace std;
inline bool isPrime(unsigned sum,int *prime)
{
unsigned Q=sqrt(sum);
for(unsigned i=0;prime[i]<=Q;i++)
{
if(sum%prime[i]==0) return false;
}
return true;
}
int main()
{
bool Num[50000]={false};
int prime[10000];
int x=0;
for(unsigned i=2;i<50000;i++)
{
if(!Num[i])
{
prime[x++]=i;
for(unsigned j=i+i;j<50000;j+=i)
{
Num[j]=true;
}
}
}
string str;
while(getline(cin,str))
{
unsigned sum=0;
unsigned strSize=str.size();
for(unsigned i=0;i<strSize;i++)
{
sum+=(isupper(str[i]) ? str[i]-=38:str[i]-=96);
}
cout<<(isPrime(sum,prime) ? "It is a prime word.":"It is not a prime word.")<<endl;
}
return 0;
}
2015年2月2日 星期一
[UVA] 315 - Network
/*20150203 hanting*/
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
int DFS(int *visit,vector<int> *place,int me,int parent,bool *critical,int &time)
{
int mini=time;
visit[me]=time++;
for(int i=0;i<place[me].size();i++)
{
int sub=place[me][i];
int temp=mini;
if(visit[sub]==-1)
{
temp=DFS(visit,place,sub,me,critical,time);
if(visit[me]==0)//root 是關節點
{
if(i>0)
{
critical[me]=true;
}
}
else if(temp>=visit[me])//關節點
{
critical[me]=true;
}
}
else if(sub!=parent)
{
temp=visit[sub];
}
if(temp<mini) mini=temp;
}
return mini;
}
int main()
{
int placeNum=0;
while(cin>>placeNum && placeNum)
{
placeNum++;
vector<int> place[placeNum];
string str;
while(getline(cin,str) && str!="0")
{
stringstream sin(str);
int place1;
sin>>place1;
int connect;
while(sin>>connect)
{
place[place1].push_back(connect);
place[connect].push_back(place1);
}
}
int visit[placeNum];
fill(visit,visit+placeNum,-1);
bool critical[placeNum];
fill(critical,critical+placeNum,false);
for(int i=0;i<placeNum;i++)
{
if(visit[i]==-1)
{
int time=0;
DFS(visit,place,i,-1,critical,time);
}
}
cout<<count(critical,critical+placeNum,1)<<endl;
}
return 0;
}
[UVA] 10093 - An Easy Problem!
/*20150202 hanting*/
// 在10進位下，一個數若是9的倍數，則這個數字的每個位數相加的總和一定也是9的倍數;
// 舉個例子，81(10-based)，8+1=9，9%9==0 -> 是9的倍數 ;
// 依此原則推出:
// 當這個數字R的每個位數總和=sum，而sum是n的倍數，
// 則 N=n+1;
#include <iostream>
using namespace std;
int main()
{
string str;
while(getline(cin,str))
{
int sum=0;
int Max=1;
for(int i=0;i<str.size();i++)
{
int R=0;
if(isdigit(str[i])) R=str[i]-48;
else if(isupper(str[i])) R=str[i]-55;//'A'-10
else if(islower(str[i])) R=str[i]-61;//'a'-36
sum+=R;
if(R>Max) Max=R;
}
for(int i=Max;i<=62;i++)
{
if(sum%i==0)
{
cout<<i+1<<endl;//所求N=i+1
break;
}
else if(i==62) cout<<"such number is impossible!"<<endl;
}
}
return 0;
}
2015年2月1日 星期日
[UVA] 11054 - Wine trading in Gergovia
/*20150201 hanting*/
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main()
{
long long int N;
while(cin>>N && N)
{
int a[N];
string s;
cin.get();
getline(cin,s);
stringstream sin(s);
int positive[N],posNum=0;
int negative[N],negNum=0;
for(long long int i=0;i<N;i++)
{
sin>>a[i];
a[i]>0 ? positive[posNum++]=i : negative[negNum++]=i;
}
long long int Count=0;
int temp=0;
for(int i=0;i<posNum;i++)
{
int x=positive[i];
for(long long int j=temp;j<negNum;j++)
{
int y=negative[j];
if(a[x]>-a[y])
{
Count+=-a[y]*(x>y ? x-y:y-x);
a[x]+=a[y];
a[y]=0;
temp=j;
}
else
{
Count+=a[x]*(x>y ? x-y:y-x);
a[y]+=a[x];
a[x]=0;
break;
}
}
}
cout<<Count<<endl;
}
return 0;
}
訂閱：
文章 (Atom)