7143. TreasureConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
One day, MXWai found a treasure map. The map was divided into 2^n * 2^n grids. The top left corner was (0, 0) and the down right corner was (2^n-1, 2^n-1). The grids and their coordinates are displayed below.
(0, 0)
(0, 1)
……
(0, 2^n-1)
……
……
……
……
(2^n-2, 0)
(2^n-2,1)
……
(2^n-2, 2^n-1)
(2^n-1, 0)
(2^n-1,1)
……
(2^n-1, 2^n-1)
Moreover, she found a secret sequence of length n, and a secret article saying that
"Repeat these operations n times then you will find the treasure.
1、divide the map into four 2^(n-1) * 2^(n-1) parts: the top left part labeled 0, the top right part labeled 1, the down left part labeled 2 and the down right part labeled 3
2、select the corresponding part according to the first digit of the sequence
3、erase the first digit of the sequence
4、decrease n by one
finally you will find out where the treasure is"
You know MXWai is just a majia, so you know she is stupid. Now it is your task to find out the location of the treasure.
Input
An integer T (1<=T<=1000000), indicating the number of test cases.
For each test case, there is only one line, containing an integer n (1<=n<=31), and a sequence of length n (the sequence only contains digits ‘0’, ‘1’, ‘2’ and ’3’).
Output
Output two integers, indicating the coordinates of the treasure.
Sample Input31 32 002 01Sample Output1 10 00 1Hint
This problem has huge input data, usescanf()instead ofcinto read data to avoid time limit exceed.
Problem Source
“星海通杯”第四届中山大学ICPC新手赛 by 黄文浩
这道题其实就是无限划分。。
#include <string.h>#include <vector>#include <queue>#include <stdio.h>#include <stack>#include <math.h>using namespace std;int main() {int t, n;scanf("%d", &t);while (t–) {char dir[35] = {0};long long i_min = 0, j_min = 0, i_max, j_max;scanf("%d %s", &n, dir);i_max = (long long)pow(2, n) – 1;j_max = (long long)pow(2, n) – 1;for (int i = 0; i < n; i++) {if (dir[i] == '0') {i_max = i_min + (i_max – i_min) / 2;j_max = j_min + (j_max – j_min) / 2;} else if (dir[i] == '1') {i_max = i_min + (i_max – i_min) / 2;j_min = j_max – (j_max – j_min) / 2;} else if (dir[i] == '2') {i_min = i_max – (i_max – i_min) / 2;j_max = j_min + (j_max – j_min) / 2;} else {i_min = i_max – (i_max – i_min) / 2;j_min = j_max – (j_max – j_min) / 2;}}printf("%lld %lld\n", i_min, j_min);}return 0;}
，你能给的也只有这么多，在这个狭小的圈子里，
