#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cassert>
class ThirteenCoins
{
public:
ThirteenCoins(int coinWeight, int fakeCoinWeight, int fakeCoinId)
: coinWeight(coinWeight), coinWeightDiff(fakeCoinWeight-coinWeight),
fakeCoinId(fakeCoinId) {}
char compare(const std::set<int>& lhs, const std::set<int>& rhs)const
{
std::vector<int> commonCoins;
std::set_intersection(begin(lhs), end(lhs), begin(rhs), end(rhs),
std::back_inserter(commonCoins));
if (!commonCoins.empty()) throw "Some coins appear on both sides";
int lhsWeight = lhs.size() * coinWeight;
int rhsWeight = rhs.size() * coinWeight;
if (lhs.find(fakeCoinId) != end(lhs)) lhsWeight += coinWeightDiff;
if (rhs.find(fakeCoinId) != end(rhs)) rhsWeight += coinWeightDiff;
if (lhsWeight == rhsWeight) return 'B';
return lhsWeight < rhsWeight ? 'R' : 'L';
}
private:
int coinWeight;
int coinWeightDiff;
int fakeCoinId;
};
int fakeCoinId(const ThirteenCoins& p)
{
static std::vector<std::string> codeWords = {
"RRR", "LLL", "BBR", "BBL", "BRL", "BLR", "BRB", "BLB", "BRR",
"BLL", "RLL", "LRR", "RLB", "LRB", "LRL", "RLR", "RBL", "LBR",
"LBB", "RBB", "RBR", "LBL", "LLR", "RRL", "LLB", "RRB", "BBB"
};
std::string comp;
comp += p.compare({ 7, 9,11,12}, { 5, 6, 8,10});
comp += p.compare({ 5, 6,11,12}, { 2, 3, 4, 7});
comp += p.compare({ 2, 5, 7, 8}, { 1, 4,10,11});
return std::distance(begin(codeWords),
std::find(begin(codeWords), end(codeWords), comp)) / 2;
}
int main()
{
for (int i = 1; i <= 13; ++i)
{
assert(fakeCoinId(ThirteenCoins(10, 11, i)) == i);
assert(fakeCoinId(ThirteenCoins(10, 9, i)) == i);
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y2Fzc2VydD4KCmNsYXNzIFRoaXJ0ZWVuQ29pbnMKewpwdWJsaWM6CiAgICBUaGlydGVlbkNvaW5zKGludCBjb2luV2VpZ2h0LCBpbnQgZmFrZUNvaW5XZWlnaHQsIGludCBmYWtlQ29pbklkKQogICAgOiBjb2luV2VpZ2h0KGNvaW5XZWlnaHQpLCBjb2luV2VpZ2h0RGlmZihmYWtlQ29pbldlaWdodC1jb2luV2VpZ2h0KSwKICAgICAgZmFrZUNvaW5JZChmYWtlQ29pbklkKSB7fQogICAgY2hhciBjb21wYXJlKGNvbnN0IHN0ZDo6c2V0PGludD4mIGxocywgY29uc3Qgc3RkOjpzZXQ8aW50PiYgcmhzKWNvbnN0CiAgICB7CiAgICAgICAgc3RkOjp2ZWN0b3I8aW50PiBjb21tb25Db2luczsKICAgICAgICBzdGQ6OnNldF9pbnRlcnNlY3Rpb24oYmVnaW4obGhzKSwgZW5kKGxocyksIGJlZ2luKHJocyksIGVuZChyaHMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdGQ6OmJhY2tfaW5zZXJ0ZXIoY29tbW9uQ29pbnMpKTsKICAgICAgICBpZiAoIWNvbW1vbkNvaW5zLmVtcHR5KCkpIHRocm93ICJTb21lIGNvaW5zIGFwcGVhciBvbiBib3RoIHNpZGVzIjsKICAgICAgICAKICAgICAgICBpbnQgbGhzV2VpZ2h0ID0gbGhzLnNpemUoKSAqIGNvaW5XZWlnaHQ7CiAgICAgICAgaW50IHJoc1dlaWdodCA9IHJocy5zaXplKCkgKiBjb2luV2VpZ2h0OwogICAgICAgIGlmIChsaHMuZmluZChmYWtlQ29pbklkKSAhPSBlbmQobGhzKSkgbGhzV2VpZ2h0ICs9IGNvaW5XZWlnaHREaWZmOwogICAgICAgIGlmIChyaHMuZmluZChmYWtlQ29pbklkKSAhPSBlbmQocmhzKSkgcmhzV2VpZ2h0ICs9IGNvaW5XZWlnaHREaWZmOwogICAgICAgIGlmIChsaHNXZWlnaHQgPT0gcmhzV2VpZ2h0KSByZXR1cm4gJ0InOwogICAgICAgIHJldHVybiBsaHNXZWlnaHQgPCByaHNXZWlnaHQgPyAnUicgOiAnTCc7CiAgICB9CnByaXZhdGU6CiAgICBpbnQgY29pbldlaWdodDsKICAgIGludCBjb2luV2VpZ2h0RGlmZjsKICAgIGludCBmYWtlQ29pbklkOwp9OwoKaW50IGZha2VDb2luSWQoY29uc3QgVGhpcnRlZW5Db2lucyYgcCkKewogICAgc3RhdGljIHN0ZDo6dmVjdG9yPHN0ZDo6c3RyaW5nPiBjb2RlV29yZHMgPSB7CiAgICAgICAgIlJSUiIsICJMTEwiLCAiQkJSIiwgIkJCTCIsICJCUkwiLCAiQkxSIiwgIkJSQiIsICJCTEIiLCAiQlJSIiwKICAgICAgICAiQkxMIiwgIlJMTCIsICJMUlIiLCAiUkxCIiwgIkxSQiIsICJMUkwiLCAiUkxSIiwgIlJCTCIsICJMQlIiLAogICAgICAgICJMQkIiLCAiUkJCIiwgIlJCUiIsICJMQkwiLCAiTExSIiwgIlJSTCIsICJMTEIiLCAiUlJCIiwgIkJCQiIKICAgIH07CiAgICBzdGQ6OnN0cmluZyBjb21wOwogICAgY29tcCArPSBwLmNvbXBhcmUoeyA3LCA5LDExLDEyfSwgeyA1LCA2LCA4LDEwfSk7CiAgICBjb21wICs9IHAuY29tcGFyZSh7IDUsIDYsMTEsMTJ9LCB7IDIsIDMsIDQsIDd9KTsKICAgIGNvbXAgKz0gcC5jb21wYXJlKHsgMiwgNSwgNywgOH0sIHsgMSwgNCwxMCwxMX0pOwogICAgcmV0dXJuIHN0ZDo6ZGlzdGFuY2UoYmVnaW4oY29kZVdvcmRzKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBzdGQ6OmZpbmQoYmVnaW4oY29kZVdvcmRzKSwgZW5kKGNvZGVXb3JkcyksIGNvbXApKSAvIDI7Cn0KCmludCBtYWluKCkKewogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gMTM7ICsraSkKICAgIHsKICAgICAgICBhc3NlcnQoZmFrZUNvaW5JZChUaGlydGVlbkNvaW5zKDEwLCAxMSwgaSkpID09IGkpOwogICAgICAgIGFzc2VydChmYWtlQ29pbklkKFRoaXJ0ZWVuQ29pbnMoMTAsICA5LCBpKSkgPT0gaSk7CiAgICB9Cn0=