Anti-Theft Road Planning Solution | Codeforces Problem Solution 2022

Anti-Theft Road Planning Solution | Codeforces Problem Solution 2022

F. Anti-Theft Road Planning

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

This is an interactive problem.

A city has 𝑛2$n^2$ 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 48000$48000$.

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 0$0$. 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\oplus 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 0$0$.

Solution Click Below:- CLICK HERE

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.

Interaction

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

Lost Arithmetic Progression Solution | Codeforces Problem Solution 2022

Power or XOR? Solution | Codeforces Problem Solution 2022 

Anti-Theft Road Planning Solution | Codeforces Problem Solution 2022 

A Perfectly Balanced String? Solution | Codeforces Problem Solution 2022 

Palindrome Basis Solution | Codeforces Problem Solution 2022 

Subtle Substring Subtraction Solution | Codeforces Problem Solution 2022 

Let's denote the 𝑗$j$-th building in the 𝑖$i$-th row by 𝐵𝑖,𝑗$B_{i,j}$.

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

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

Remember that the total length of the roads must not exceed 48000$48000$.

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.

Hacks

You cannot make hacks in this problem.

Join Now for Solution:-