[1074]Z

NAVER漫画第三題のカタツムリを思い出しましたもちろん、これはもう一つの問題ですが、あまりできないようなので、やってみたいと思います.
△やっぱり1時間かかりました.
この問題はsilver 1です.
-1074号:Z
Z形状を探索する.配列の大きさは2^Nx 2^Nです.
N>1の場合は配列を2^(N−1)x 2^(N−1)等分して再帰的に順次アクセスする.

問題から取得する情報:Nが与えられた場合、

のr行c列への最初のアクセスが出力される

草の考え

まず何番目の格に属するかを見つけなければならない.

順序を再帰的に探す.

四等分なので、角ごとに何番目の格に属するかを見つけます.最後にZ順で2 x 2を回る場合は、何度目の訪問を要求すればよいか.

n=3,r=5,c=5.四等分矩形がZでアクセスされていると思う場合は、まず何番目の格子に属しているかを知る必要があります.

ファーストコール

→ 2^3/2 = 4

r≧4&&c≧4→第4格に属する.→2^2 x 2^2 x 3個が先にあります.

セカンドコール

→ 2^2/2 = 2

4+2 = 6

最初のセルは(4,4)から始まります.

r<6&&c<6→第1格に属する.

if,r<6&&c≧6→第2格

に属する

if,r≧6&c<6→第3格に属する.

if,r≧6&&c≧6→第4格に属する.

つまり、次のように解けばいいのです.

始点(0,0)=(preR, preC)

len=2^(N−1)からlenが2より大きいまで開始する.

は、最終的にwhileゲートを出て、2 x 2格子内で数番目のビットを計算します.

prer+(2^Nx 2^N/2→2^(N−1)を基準とする.検索するRがその値+prec++(2^Nx 2^N/2→2^(N-1))より小さいかどうか.検索するC値がその値より小さいか大きいかによって、何番目の格かがわかります.

が何時間目か知っていれば

現在、起点は

最初のセル:(prer,prec)

第2格:(prer,prec+2^(N−1)→cntに2^(N−1)x 2^(N−1)を加える.

第3格:(prer+2^(N−1),prec)→cntに2^(N−1)x 2^(N−1)x 2を加える.

第4格:(prer+2^(N-1),prec+2^(N-1))→cntに2^(N-1)x 2^(N-1)x 3を加える.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int n,r,c;
    public static void Setting() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
    }
    public static int solve(){
        int preR =0,preC =0;
        int nextR=0,nextC=0;
        int cnt=0;
        int len = (int)Math.pow(2,n);
        // len 은 2의 n승인 것들만 온다.
        while(len>2){
            len/=2;
            preR = nextR; preC = nextC;
            if( r< preR +len){
                // 첫 번째 칸
                if(c<preC +len){
                    nextR = preR;
                    nextC = preC;
                }
                // 두 번째 칸
                else{
                    nextR = preR;
                    nextC = preC + len;
                    cnt += (len*len);
                }
            }else{
                // 세 번째 칸
                if(c<preC +len){
                    nextR = preR +len;
                    nextC = preC;
                    cnt += (len*len)<<1;
                }
                // 네 번째 칸
                else{
                    nextR = preR +len;
                    nextC = preC + len;
                    cnt += (len*len)*3;
                }
            }
        }
        // nextR, nextC 에서 ,r,c의 위치를 찾아야함
        if(r<nextR+1){
            if(c<nextC+1)return cnt;
            else return cnt+1;
        }else{
            if(c<nextC+1)return cnt+2;
            else return cnt+3;
        }

    }
    public static void main(String[] args) throws IOException {
        Setting();
        int res = solve();
        System.out.println(res);
    }
}