/*20150315 hanting*/
#include <iostream>
using namespace std;
class BigNum
{
private:
long long num[15];
int digit;
public:
BigNum():num{0},digit(0){}
BigNum(int a);
void digitCount();
BigNum operator*(BigNum a);
friend BigNum operator+(BigNum Num,int a);
friend BigNum operator-(BigNum Num,int a);
BigNum operator-(BigNum a);
friend bool operator>(BigNum a,BigNum b);
friend bool operator==(BigNum a,BigNum b);
friend BigNum pow(int a,int i);
friend istream& operator>>(istream& in,BigNum &a);
friend ostream& operator<<(ostream& out,BigNum a)
{
out<<a.num[a.digit-1];
for(int i=a.digit-2;i>=0;i--)
{
out.width(4);
out.fill('0');
out<<a.num[i];
}
return out;
}
};
int tower[3];
void hanoi(int n,int from,int temp,int to,BigNum &m)
{
for(int i=n,j=0;i>=0;i--,j++)
{
BigNum t;
t=pow(2,i)-1;
if(m>t)
{
m=m-(t+1);
tower[from]-=i+1;
if(i&1)
{
tower[temp]+=i;
tower[to]++;
hanoi(i,temp,to,from,m);
}
else
{
tower[to]+=i;
tower[temp]++;
hanoi(i,to,from,temp,m);
}
break;
}
else if(m==t)
{
m=m-(t+1);
tower[from]-=i;
if(i&1)
{
tower[temp]+=i;
}
else
{
tower[to]+=i;
}
break;
}
}
}
int main()
{
int n;
BigNum m;
while(cin>>n>>m && n)
{
tower[0]=n;
for(int i=1;i<3;i++) tower[i]=0;
hanoi(n,0,1,2,m);
for(int i=0;i<2;i++)
{
cout<<tower[i]<<" ";
}
cout<<tower[2]<<endl;
}
}
BigNum::BigNum(int a)
{
digit=0;
for(int i=0;i<15;i++) num[i]=0;
while(a)
{
num[digit++]=a%10000;
a/=10000;
}
}
void BigNum::digitCount()
{
for(int i=14;i>=0;i--)
{
if(num[i])
{
digit=i+1;
break;
}
}
}
BigNum pow(int a,int i)
{
BigNum temp;
while(a)
{
temp.num[temp.digit++]+=a%10000;
a/=10000;
}
BigNum ans;
ans=temp;
for(int j=0;j<i-1;j++)
{
ans=ans*temp;
}
return ans;
}
BigNum BigNum::operator*(BigNum a)
{
BigNum ans;
for(int i=0;i<digit;i++)
{
for(int j=0;j<a.digit;j++)
{
ans.num[i+j]+=num[i]*a.num[j];
}
}
for(int i=1;i<15;i++)
{
ans.num[i]+=ans.num[i-1]/10000;
ans.num[i-1]%=10000;
}
ans.digitCount();
return ans;
}
BigNum operator+(BigNum Num,int a)
{
Num.num[0]+=a;
for(int i=1;i<15;i++)
{
Num.num[i]+=Num.num[i-1]/10000;
Num.num[i-1]%=10000;
}
Num.digitCount();
return Num;
}
BigNum operator-(BigNum Num,int a)
{
BigNum ans;
BigNum temp(a);
ans=Num-temp;
return ans;
}
BigNum BigNum::operator-(BigNum a)
{
BigNum ans;
for(int i=0;i<15;i++)
{
ans.num[i]=num[i]-a.num[i];
}
for(int i=0;i<14;i++)
{
if(ans.num[i]<0)
{
ans.num[i]+=10000;
ans.num[i+1]--;
}
}
ans.digitCount();
return ans;
}
bool operator>(BigNum a,BigNum b)
{
for(int i=14;i>=0;i--)
{
if(a.num[i]>b.num[i]) return 1;
else if(a.num[i]<b.num[i]) return 0;
}
}
bool operator==(BigNum a,BigNum b)
{
for(int i=0;i<15;i++)
{
if(a.num[i]!=b.num[i]) return 0;
}
return 1;
}
istream& operator>>(istream& in,BigNum &a)
{
BigNum temp;
a=temp;
string str;
in>>str;
if(str.size()%4!=0)
for(int i=0;i<str.size()%4;i++)
{
str='0'+str;
}
for(int i=str.size()-1;i>=0;i-=4)
{
a.num[a.digit++]=(str[i]-48) + 10*(str[i-1]-48) + 100*(str[i-2]-48) + 1000*(str[i-3]-48);
}
return in;
}
2015年3月15日 星期日
[UVA] 254 - Towers of Hanoi
2015年3月10日 星期二
[UVA] 10008 - What's Cryptanalysis?
/*20150310 hanting*/
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(pair<char,int> a,pair<char,int> b)
{
if(a.second==b.second) return a.first<b.first;
else return a.second>b.second;
}
int main()
{
int N;
cin>>N;
cin.get();
string str[N];
string total="";
for(int i=0;i<N;i++)
{
getline(cin,str[i]);
for(int j=0;j<str[i].size();j++)
{
if(isalpha(str[i][j])) total+=toupper(str[i][j]);
}
}
pair<char,int> letter[26];//< 字母 , 字母出現的次數 >
for(int i=0;i<26;i++) letter[i].first=i+'A';
for(int i=0;i<total.size();i++)
{
letter[total[i]-'A'].second++;
}
sort(letter,letter+26,compare);
for(int i=0;letter[i].second;i++)//次數是0就停止輸出
{
cout<<letter[i].first<<" "<<letter[i].second<<endl;
}
return 0;
}
----------------------------------------
/* 20151012
* hanting
* UVa 10008 - What's Cryptanalysis?
* C++
*/
#include <iostream>
#include <algorithm> //transform,sort
using namespace std;
struct Letter
{
char ch;
int cnt;
Letter():cnt(0){}
bool operator<(const Letter& another)const
{
return cnt>another.cnt or (cnt==another.cnt and ch<another.ch);
}
};
int main()
{
int N;
while(cin>>N)
{
string str;
cin.get();
Letter letter[26];//A~Z
for(int i=0;i<26;i++)
{
letter[i].ch='A'+i;
}
for(int i=0;i<N;i++)
{
getline(cin,str);
transform(str.begin(),str.end(),str.begin(),::toupper);
for(int i=0;i<str.size();++i)
{
if(isalpha(str[i])) letter[ str[i]-'A' ].cnt++;
}
}
sort(letter,letter+26);
for(int i=0;i<26;i++)
{
if(letter[i].cnt)
{
cout<<letter[i].ch<<" "<<letter[i].cnt<<endl;
}
}
}
return 0;
}
2015年3月2日 星期一
[UVA] 10420 - List of Conquests
/*20150302 hanting*/
#include <iostream>
#include <map>
using namespace std;
int main()
{
int N;
while(cin>>N)
{
map<string,int> store;
string country,temp;
for(int i=0;i<N;i++)
{
cin>>country;
getline(cin,temp);
store[country]++;
}
for(map<string,int>::iterator it=store.begin();it!=store.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
}
return 0;
}
2015年3月1日 星期日
[UVA] 10101 - Bangla Numbers
/*20150302 hanting*/
#include <iostream>
#include <iomanip>//setw
using namespace std;
int main()
{
long long N=0;
int times=0;
long long numbers[]={1e2,1e3,1e5,1e7,1e9,1e10,1e12,1e14};
while(cin>>N)//23764//45897458973958
{
string Bangla[]={"shata","hajar","lakh","kuti","shata","hajar","lakh","kuti"};
int x=0;//Bangla[]//numbers[]
cout<<setw(4)<<++times<<". ";
int ans[8]={0};
for(int i=0;i<8;i++)
{
if(i<7)ans[i]=N/numbers[i]-N/numbers[i+1]*(numbers[i+1]/numbers[i]);
else ans[i]=N/numbers[i];
}
int i=7;
bool space=0;
if(ans[3]==0)
{
for(int i=4;i<8;i++)
{
if(ans[i])
{
Bangla[i]+=" kuti";
break;
}
}
}
for(;i>=0;i--)
{
if(ans[i])
{
cout<<ans[i]<<" "<<Bangla[i];
i--;
space=1;
break;
}
}
for(;i>=0;i--)
{
if(ans[i]) cout<<" "<<ans[i]<<" "<<Bangla[i];
}
if(N%100||N==0) cout<<(space ? " ":"")<<N%100;
cout<<endl;
}
return 0;
}
訂閱：
文章 (Atom)