RPD and Rap Sheet Hard Version Codeforces Solution

RPD and Rap Sheet Hard Version Solution

This is the hard version of the problem. The only difference is that here 2≤k≤1002≤k≤100. You can make hacks only if both the versions of the problem are solved.

Every decimal number has a base kk equivalent. The individual digits of a base kk number are called kk-its. Let’s define the kk-itwise XOR of two kk-its aa and bb as (a+b)modk(a+b)modk.

See Also: Codeforces Round 730 (Div. 2)

The kk-itwise XOR of two base kk numbers is equal to the new number formed by taking the kk-itwise XOR of their corresponding kk-its. The kk-itwise XOR of two decimal numbers aa and bb is denoted by a⊕kba⊕kb and is equal to the decimal representation of the kk-itwise XOR of the base kk representations of aa and bb. All further numbers used in the statement below are in decimal unless specified.

You have hacked the criminal database of Rockport Police Department (RPD), also known as the Rap Sheet. But in order to access it, you require a password. You don’t know it, but you are quite sure that it lies between 00 and n−1n−1 inclusive. So, you have decided to guess it. Luckily, you can try at most nn times without being blocked by the system. But the system is adaptive. Each time you make an incorrect guess, it changes the password. Specifically, if the password before the guess was xx, and you guess a different number yy, then the system changes the password to a number zz such that x⊕kz=yx⊕kz=y. Guess the password and break into the system.Input

The first line of input contains a single integer tt (1≤t≤100001≤t≤10000) denoting the number of test cases. tt test cases follow.

The first line of each test case contains two integers nn (1≤n≤2⋅1051≤n≤2⋅105) and kk (2≤k≤100)(2≤k≤100).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.Interaction

For each test case, first read two integers nn and kk. Then you may ask up to nn queries.

For each query, print a single integer yy (0≤y≤2⋅1070≤y≤2⋅107). Let the current password be xx. After that, read an integer rr.

If x=yx=y, you will read r=1r=1 and the test case is solved. You must then continue solving the remaining test cases.

Else, you will read r=0r=0. At this moment the password is changed to a number zz such that x⊕kz=yx⊕kz=y.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get the Idleness limit exceeded verdict.

To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

If you ask an invalid query or exceed nn queries, you will read r=−1r=−1 and you will receive the Wrong Answer verdict. Make sure to exit immediately to avoid unexpected verdicts.

Note that the interactor is adaptive. That is, the original password is not fixed in the beginning and may depend on your queries. But it is guaranteed that at any moment there is at least one initial password such that all the answers to the queries are consistent.

Hacks:

To use hacks, use the following format of tests:

The first line should contain a single integer tt (1≤t≤100001≤t≤10000) — the number of test cases.

The first and only line of each test case should contain two integers nn (1≤n≤2⋅1051≤n≤2⋅105) and kk (k=2k=2) denoting the number of queries and the base respectively. The optimal original password is automatically decided by the adaptive interactor.

You must ensure that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Example

input

2
5 2

0

0

1
5 3

0

0

1

output

3

4

5


1

4

6

Note

Test Case 1:

In this case, the hidden password is 22.

The first query is 33. It is not equal to the current password. So, 00 is returned, and the password is changed to 11 since 2⊕21=32⊕21=3.

The second query is 44. It is not equal to the current password. So, 00 is returned, and the password is changed to 55 since 1⊕25=41⊕25=4.

The third query is 55. It is equal to the current password. So, 11 is returned, and the job is done.

Test Case 2:

In this case, the hidden password is 33.

The first query is 11. It is not equal to the current password. So, 00 is returned, and the password is changed to 77 since 3⊕37=13⊕37=1. [3=(10)3[3=(10)3, 7=(21)37=(21)3, 1=(01)31=(01)3 and (10)3⊕3(21)3=(01)3](10)3⊕3(21)3=(01)3].

The second query is 44. It is not equal to the current password. So, 00 is returned, and the password is changed to 66 since 7⊕36=47⊕36=4. [7=(21)3[7=(21)3, 6=(20)36=(20)3, 4=(11)34=(11)3 and (21)3⊕3(20)3=(11)3](21)3⊕3(20)3=(11)3].

The third query is 66. It is equal to the current password. So, 11 is returned, and the job is done.

Note that these initial passwords are taken just for the sake of explanation. In reality, the grader might behave differently because it is adaptive.

Solution

Program C++:

#include <bits/stdc++.h>

using namespace std;

int k;

int invert(int x)
{
    int y = 0;
    stack<int> bits;
    while(x > 0)
    {
        bits.push((k - (x%k))%k);
        x /= k;
    }
    while(!bits.empty())
    {
        y *= k;
        y += bits.top();
        bits.pop();
    }
    return y;
}

int XOR(int x, int y)
{
    int z = 0;
    stack<int> bits;
    while(x > 0 || y > 0)
    {
        bits.push((x + y) % k);
        x /= k;
        y /= k;
    }
    while(!bits.empty())
    {
        z *= k;
        z += bits.top();
        bits.pop();
    }
    return z;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n >> k;
        for(int i = 0; i < n; i++)
        {
            int cur = XOR(i, invert(i-1));
            if(i%2 == 1)
                cur = invert(cur);
            cout << cur << endl;
            bool r;
            cin >> r;
            if(r)
                break;
        }
    }
    return 0;
}


Codeforces Round #730 (Div. 2)

Leave a Comment