Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2131-8aa5f781
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #92 DIV1 B問題/DIV2 D問題 - Squares (この記事を編集する[管理者用])

Source

Codeforces Beta Round #92 DIV1 B問題 (1000pt)
Codeforces Beta Round #92 DIV2 D問題 (2000pt)
Problem description

問題概要

無限に広いグリッドで,上下左右に移動できる.座標(x, y)に対して
 |x+y| = 0 mod 2a もしくは |x-y| = 0 mod 2b
を満たすセルはbadセルと呼ぶ.
(x1, y1)から(x2, y2)に移動するのに通らなければいけないbadセルの最小値を求める問題.
始点,終点はbadセルではない.
a, bは2以上10^9以下,始点・終点の座標の絶対値は10^9以下.

解法

斜めに45度傾けて考えてみると,badセルに囲まれた座標が見えてくる.
それで,縦横何番目のセルにいるかを求めて,縦横斜めに移動できるとして移動距離を求める.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

void get(ll val, ll mod, int *min, int *max){
  ll res = val / mod;

  while(res * mod <= val) res++;
  *max = (int)res;
  while(res * mod >= val+mod) res--;
  *min = (int)res;
}

ll solve(ll x1, ll y1, ll x2, ll y2){
  ll dx = x1 - x2;
  ll dy = y1 - y2;
  if(dx < 0) dx = -dx;
  if(dy < 0) dy = -dy;

  if(dx > dy) return dx;
  return dy;
}

int main(){
  int i,j,k,l,m,n;
  int a,b,x1,y1,x2,y2;
 
  int X1[2], Y1[2], X2[2], Y2[2];
  int a1,a2,a3,a4;
  ll res, tmp;
  int fg1, fg2;

  while(scanf("%d%d%d%d%d%d",&a,&b,&x1,&y1,&x2,&y2)==6){
    get(x1+y1, 2*a, X1, X1+1);
    get(x1-y1, 2*b, Y1, Y1+1);
    get(x2+y2, 2*a, X2, X2+1);
    get(x2-y2, 2*b, Y2, Y2+1);

    fg1 = fg2 = 0;
    if( (x1+y1)%(2*a)==0 || (x1-y1)%(2*b)==0 ) fg1 = 1;
    if( (x2+y2)%(2*a)==0 || (x2-y2)%(2*b)==0 ) fg2 = 1;

    if(x1==x2 && y1==y2){
      printf("%d\n",fg1); continue;
    }

    res = 1000000000000000LL;
    rep(i,1<<4){
      if(i&1<<0) a1 = X1[0]; else a1 = X1[1];
      if(i&1<<1) a2 = Y1[0]; else a2 = Y1[1];
      if(i&1<<2) a3 = X2[0]; else a3 = X2[1];
      if(i&1<<3) a4 = Y2[0]; else a4 = Y2[1];
      tmp = solve(a1,a2,a3,a4);
      if(res > tmp) res = tmp;
    }

    res += fg1 + fg2;
    printf("%d\n",(int)res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2131-8aa5f781
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。