Anti-Theft Road Planning solution codeforces

Anti-Theft Road Planning solution codeforces

A city has 𝑛2n2 buildings divided into a grid of 𝑛n rows and 𝑛n columns. You need to build a road of some length 𝐷(𝐴,𝐵)D(A,B) of your choice between each pair of adjacent by side buildings 𝐴A and 𝐵B. Due to budget limitations and legal restrictions, the length of each road must be a positive integer and the total length of all roads should not exceed 4800048000.

Anti-Theft Road Planning solution codeforces

There is a thief in the city who will start from the topmost, leftmost building (in the first row and the first column) and roam around the city, occasionally stealing artifacts from some of the buildings. He can move from one building to another adjacent building by travelling through the road which connects them.

You are unable to track down what buildings he visits and what path he follows to reach them. But there is one tracking mechanism in the city. The tracker is capable of storing a single integer 𝑥x which is initially 00. Each time the thief travels from a building 𝐴A to another adjacent building 𝐵B through a road of length 𝐷(𝐴,𝐵)D(A,B), the tracker changes 𝑥x to 𝑥𝐷(𝐴,𝐵)x⊕D(A,B). Each time the thief steals from a building, the tracker reports the value 𝑥x stored in it and resets it back to 00.

It is known beforehand that the thief will steal in exactly 𝑘k buildings but you will know the values returned by the tracker only after the thefts actually happen. Your task is to choose the lengths of roads in such a way that no matter what strategy or routes the thief follows, you will be able to exactly tell the location of all the buildings where the thefts occurred from the values returned by the tracker.

Anti-Theft Road Planning solution codeforces

First read a single line containing two integers 𝑛n (2𝑛32)(2≤n≤32) and 𝑘k (1𝑘1024)(1≤k≤1024) denoting the number of rows and number of thefts respectively.

Let’s denote the 𝑗j-th building in the 𝑖i-th row by 𝐵𝑖,𝑗Bi,j.

Then print 𝑛n lines each containing 𝑛1n−1 integers. The 𝑗j-th integer of the 𝑖i-th line must be the value of 𝐷(𝐵𝑖,𝑗,𝐵𝑖,𝑗+1)D(Bi,j,Bi,j+1).

Then print 𝑛1n−1 lines each containing 𝑛n integers. The 𝑗j-th integer of the 𝑖i-th line must be the value of 𝐷(𝐵𝑖,𝑗,𝐵𝑖+1,𝑗)D(Bi,j,Bi+1,j).

Remember that the total length of the roads must not exceed 4800048000.

Then answer 𝑘k queries. First read the value 𝑥x returned by the tracker. Then print two integers denoting the row number and column number of the building where the theft occurred. After that you will be able to answer the next query (if such exists).

After printing the answers do not forget to output end of line and flush the output buffer. Otherwise you will get the verdict Idleness limit exceeded. To flush the buffer, use:

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

Anti-Theft Road Planning solution codeforces

You cannot make hacks in this problem.



2 4






2 4

1 2

1 1

1 2

2 1

For the sample test, 𝑛=2n=2 and 𝑘=4k=4.

You choose to build the roads of the following lengths:


Anti-Theft Road Planning solution codeforces
The thief follows the following strategy:

  1. Start at 𝐵1,1B1,1.
  2. Move Right to 𝐵1,2B1,2.
  3. Move Down to 𝐵2,2B2,2.
  4. Move Left to 𝐵2,1B2,1.
  5. Move Up to 𝐵1,1B1,1.
  6. Move Right to 𝐵1,2B1,2.
  7. Steal from 𝐵1,2B1,2.
  8. Move Left to 𝐵1,1B1,1.
  9. Steal from 𝐵1,1B1,1.
  10. Move Down to 𝐵2,1B2,1.
  11. Move Right to 𝐵2,2B2,2.
  12. Move Up to 𝐵1,2B1,2.
  13. Steal from 𝐵1,2B1,2.
  14. Move Left to 𝐵1,1B1,1.
  15. Move Down to 𝐵2,1B2,1.
  16. Steal from 𝐵2,1B2,1.

Anti-Theft Road Planning solution codeforces

The tracker responds in the following way:

  1. Initialize 𝑥=0x=0.
  2. Change 𝑥x to 𝑥1=01=1x⊕1=0⊕1=1.
  3. Change 𝑥x to 𝑥4=14=5x⊕4=1⊕4=5.
  4. Change 𝑥x to 𝑥8=58=13x⊕8=5⊕8=13.
  5. Change 𝑥x to 𝑥2=132=15x⊕2=13⊕2=15.
  6. Change 𝑥x to 𝑥1=151=14x⊕1=15⊕1=14.
  7. Return 𝑥=14x=14 and re-initialize 𝑥=0x=0.
  8. Change 𝑥x to 𝑥1=01=1x⊕1=0⊕1=1.
  9. Return 𝑥=1x=1 and re-initialize 𝑥=0x=0.
  10. Change 𝑥x to 𝑥2=02=2x⊕2=0⊕2=2.
  11. Change 𝑥x to 𝑥8=28=10x⊕8=2⊕8=10.
  12. Change 𝑥x to 𝑥4=104=14x⊕4=10⊕4=14.
  13. Return 𝑥=14x=14 and re-initialize 𝑥=0x=0.
  14. Change 𝑥x to 𝑥1=01=1x⊕1=0⊕1=1.
  15. Change 𝑥x to 𝑥2=12=3x⊕2=1⊕2=3.
  16. Return 𝑥=3x=3 and re-initialize 𝑥=0x=0

Leave a Comment