SRM 204 DIV1 Easy - Apothecary (復習×○)

February 09, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=2312&rd=5850

ある物体の重さを、天秤を使って測りたい。
天秤の重さは３＾ｘのものが各１つずつ存在する。
このとき、必要な天秤の重さを昇順にソートして返す。

解き方

重さの最大は10^6なので、各３のべき乗に対し３通りの計算と考えると
3^14ほどになり計算量がちょっと怪しい。
※計算
　10^6=3^x
　log10^6=log3^x
　x=6/log3≠13

ここで各３のべき乗xとそこまでのすべてのべき乗の和をsum[x]とすると、
sum[x-1]<abs(W)<sum[x]のときその数xは使わなければならない。
逆にsumが超えてしまうとその数を使ってはいけなくなる。

これをループさせて範囲を狭めていき、答えを求める。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class Apothecary {

public: vector<int> balance(int W) {
vector<int> ans;

int x=1,sum=1;
while(W!=0){
if(sum>=abs(W)){
if(sum-x<abs(W)){
if(abs(W-x)<abs(W+x)){
ans.push_back(x);
W-=x;
}
else{
ans.push_back(-x);
W+=x;
}
}
sum-=x;
x/=3;
}
else{
x*=3;
sum+=x;
}
}
sort(all(ans));

return ans;
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class Apothecary {

public: vector<int> balance(int W) {
vector<int> ans;

while(W!=0){
int sum=0;
for(int i=1;;i*=3){
sum+=i;
if(sum>=abs(W)){
if(W>0){
ans.push_back(i);
W-=i;
}
else {
ans.push_back(-i);
W+=i;
}
break;
}
}
}
sort(all(ans));

return ans;
}

};

実装