[Java]伯俊1074号[J]Java


白峻1074号です.
https://www.acmicpc.net/problem/1074

質問する


1つの数字の大きさは2 N^NN× 2 N^NNの2次元配列をZ形状に探索した.たとえば、2×2左上、右上、左下、右下の順にアクセスしてZ形に並べます.

N>1の場合、配列サイズは2 N-1^N-1 N 1× 2 N∮1^N−1 N∮1を4等分して再帰的に順次アクセスする.
次の例は222^222を示します.× アクセス222^222サイズの並び順.

Nが与えられた場合、プログラムを記述し、r行c列に何回目のアクセスを出力する.
以下に、N=3の場合の例を示す.

入力


第1行は整数N,r,cを与える.

しゅつりょく


数回目のアクセスr行c列を出力します.

考える


私たちが探している形自体が正方形であることを利用することができます.
また、それを2 x 2コード繰り返しと考え、縮小すればよい.

アクション


まず、片面寸法sizeの値について理解する.
どうせ正方形だから、一面の値を知るだけで十分
この値を4等分して、小さな正方形を作ります.
このsize値/2を,上下4等分の値として推定した.
私たちが探している位置rcがどの方面にあるかを知っています.
検索位置の座標値(rc)がサイズの始点x+sizey+sizeより大きい場合
私たちが探している位置が前にあることを意味します.
これらの条件に従ってsizeで座標値を知ると、
サイズを小さくすることで、目的の値を見つけることができます.

TMI


考えてみれば、通常、2 Dアレイを作成するときもzシェイプ順に作成されます.
どうしてそんなことを思わなかったのですか.

コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	static int size = 1;
	static int N, r, c;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		size = (int) Math.pow(2, N);

		int count = 0;
		int x = 0;
		int y = 0;

		while(size > 0) {
			size /= 2;			
			if(r < x+size && c < y+size) {
				count += 0;
			}
			else if(r < x+size) {
				count += size * size;
				y += size;
			}
            else if (c < y+size) {
                count += size * size * 2;
                x += size;
            }
            else {
                count += size * size * 3;
                x += size;
                y += size;
            }
	

			 // size가 1이 되면 종료.
			 if(size == 1) {
	                System.out.println(count);
	                break;
	         }
		}

	}

}