Page Contents

**RPD and Rap Sheet Hard Version 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*

*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)*

*Codeforces Round #730 (Div. 2)*

*Exciting Bets**Customising the Track**Need for Pink Slips**RPD and Rap Sheet (Easy Version)**RPD and Rap Sheet (Hard Version)**The Final Pursuit*