The language of Australian aborigines anindilyakwa has no numerals. No anindilyakwa can say: “I've hooked eight fishes”. Instead, he says: “I've hooked as many fishes as many stones are in this pile”.
Professor Brian Butterworth found a meadow with three piles of stones. He decided to determine whether aborigines can count. Professor asked one of the aborigines to point at two piles with the minimal
difference of numbers of stones in them and tell what this difference is. The aborigine pointed correctly! He was unable to express the difference with words, so he went to a shore and returned with a pile of the corresponding number of stones.
Professor decided to continue his experiments with other aborigines, until one of them points at two piles with equal number of stones. All piles that aborigines bring from the shore are left at the
meadow. So, the second aborigine will have to deal with one more pile, the one brought by the first aborigine.
Input
The only input line contains space-separated pairwise distinct integersx1,x2andx3<nobr>(1
≤<em>x</em><span style="bottom:-0.4em; position:relative; vertical-align:baseline">1</span>,<em>x</em><span style="bottom:-0.4em; position:relative; vertical-align:baseline">2</span>,<em>x</em><span style="bottom:-0.4em; position:relative; vertical-align:baseline">3</span>≤
10<span style="position:relative; top:-0.4em; vertical-align:baseline">18</span>)</nobr>, which are the numbers of stones in piles that were lying on the meadow at the moment professor Butterworth asked the first aborigine.
Output
Output the number of aborigines that will have to answer a stupid question by professor.
Sample
Hint
The first aborigine will point at piles of 11 and 9 stones and will bring a pile of two stones. The second aborigine will point at the same piles and will bring another pile of two stones. The third
aborigine will point at two piles of two stones, and the experiments will be over.
本题可以使用长整形来记录数据的,因为最长不过10^8,但是如果把这题当做是无穷大数来做的话,难度指数就直线上升了。
这里给出使用string来做无穷大减法的解法。
要处理的问题:
1 string大小比较问题,不能使用原始的<号
2 如何进位的问题
3 符号问题,因为这里只求差异就可以了,所以返回绝对值就够了。
这样做本题还是有一定难度, 而且可以锻炼到一些高级点的知识的运用,挺好。
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
namespace
{
bool sLarger(const string s, const string t)
{
if (s.size() < t.size()) return false;
else if (s.size() > t.size()) return true;
return s > t;
}
string operator-(string s, string t)
{
if (s == t) return "0";
string x;
//bool sign = true;不用sign,求其绝对值即可
if (sLarger(t, s))
{
s.swap(t);
}
bool carry = 0;
for (int i = s.size()-1, j = t.size()-1; i>=0 || j>=0 ; i--, j--)
{
int a = i>=0? s[i] - '0' : 0;
int b = j>=0? t[j] - '0' : 0;
int sub = a - b - carry;
carry = 0;
if (sub < 0)
{
sub += 10;
carry = 1;
}
x.push_back(sub+'0');
}
while (x.size() && '0' == x.back()) x.pop_back();
reverse(x.begin(), x.end());
return x;
}
}//empty namespace end
void Anindilyakwa1777()
{
vector<string> piles(3);
cin>>piles[0]>>piles[1]>>piles[2];
sort(piles.begin(), piles.end(), sLarger);
int c = 0;
while (true)
{
c++;
string minSub = piles[1]-piles[0];
for (int i = 2; i < (int)piles.size(); i++)
{
string sub = piles[i]-piles[i-1];
if (sLarger(minSub, sub)) minSub = sub;
}
if ("0" == minSub) break;
piles.push_back(minSub);
sort(piles.begin(), piles.end(), sLarger);
}
cout<<c;
}
分享到:
相关推荐
Times New Roman.TTF,字体文件
detecing network modules in fMRI times series .pdf
6 Trends on 'Perception' for ADAS_AV _ EE Times.pdf麻省理工AI神经网络ADAS6 Trends on 'Perception' for ADAS_AV _ EE Times.pdf麻省理工AI神经网络ADAS6 Trends on 'Perception' for ADAS_AV _ EE Times.pdf...
The.Essential.Guide.to.SAS.Dates.and.Times.Jun.2006
苦苦寻找的times文件,用于KITTI数据集SLAM测试 苦苦寻找的times文件,用于KITTI数据集SLAM测试 苦苦寻找的times文件,用于KITTI数据集SLAM测试
Android Times Square介绍: 效果不错的日历UI模块。可以设置成只能选择单个日期,或者可以选择多个不连续的日期,或者可以通过点击两个日期来选择之间连续的日期。并且可以将日历放到弹出的对话框中。 测试...
Good Economics For Hard Times.pdf
开源项目-djherbis-times.zip,File Times for Go (atime, mtime, ctime, btime)
SAP ABAP 开发 SMARTFORMS字体,SE73 Times New Roman.ttf
27Modern_Times_ExtraPack.rar 27Modern_Times_ExtraPack.rar
( Times New Roman.rar
Times New Roman .fon
资源来自pypi官网。 资源全名:mo-times-2.27.18331.tar.gz
资源分类:Python库 所属语言:Python 资源全名:mo-times-5.53.21241.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Times
Certainty and Growth in the Times of Change.pdf