BAEKJOON 2685 - Nim-B Sum

문제: https://www.acmicpc.net/problem/2685

문제

The game of NIM is played with any number of piles of objects with any number of objects in each pile. At each turn, a player takes one or more (up to all) objects from one pile. In the normal form of the game, the player who takes the last object is the winner. There is a well-known strategy for this game based on the nim-2 sum.

The Nim-B sum (nim sum base B) of two non-negative integers X and Y (written NimSum(B, X, Y)) is computed as follows:

Write each of X and Y in base B.
Each digit in base B of the Nim-B sum is the sum modulo B of the corresponding digits in the base B representation of X and Y.

For example:

NimSum(2, 123, 456) = 1111011 ¤ 111001000 = 110110011 = 435
NimSum(3, 123, 456) = 11120 ¤ 121220 = 102010 = 300
NimSum(4, 123, 456) = 1323 ¤ 13020 = 10303 = 307

The strategy for normal form Nim is to compute the Nim-2 sum T of the sizes of all piles. If at any time, you end your turn with T = 0, you are guaranteed a WIN. Any opponent move must leave T not 0 and there is always a move to get T back to 0. This is done by computing NimSum(2, T, PS)for each pile; if this is less than the pile size (PS), compute the difference between the PS and the Nim-2 sum and remove it from that pile as your next move.

Write a program to compute NimSum(B, X, Y).

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by three space separated decimal integers, B, X and Y. 2 <= B <= 2000000, 0 <= X <= 2000000, 0 <= Y <= 2000000.

출력

For each data set there is one line of output. It contains the data set number followed by a single space, followed by N, the decimal representation of the Nim sum in base B of X and Y.

예제 입력 

4
2 123 456
3 123 456
4 123 456
5 123 456

예제 출력 

435
300
307
429

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2010 Greater New York Programming Contest B번

• 문제를 번역한 사람: baekjoon WeissBlume

링크

• ACM-ICPC Live Archive
• Sphere Online Judge

진수 변환으로 간단하게 풀 수 있는 문제네요.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
using namespace std;
 
vector<int> convertToBase(int b, int num)
{
    vector<int> ret;
    while (num != 0)
    {
        int remainder = num % b;
        ret.push_back(remainder);
        num /= b;
    }
    return ret;
}
 
int NimSum(int b, int x, int y)
{
    if (x > y)
        return NimSum(b, y, x);
    vector<int> baseX = convertToBase(b, x);
    vector<int> baseY = convertToBase(b, y);
    vector<int> baseSum;
    for (int i = 0; i < baseX.size(); i++)
        baseSum.push_back((baseX[i] + baseY[i]) % b);
    
    for (int i = 0; i < baseY.size() - baseX.size(); i++)
        baseSum.push_back(baseY[baseX.size() + i]);
 
    int ret = 0;
    for (int i = 0; i < baseSum.size(); i++)
    {
        ret += baseSum[i] * pow(b, i);
    }
    return ret;
}
 
int main() 
{
    int cases, b, x, y;
    cin >> cases;
    for (int c = 0; c < cases; c++)
    {
        cin >> b >> x >> y;
        cout << NimSum(b, x, y) << endl;
    }
    return 0;
}