TopCoder SRM620 DIV1 EASY - PairGame

Source

TopCoder SRM620 DIV1 EASY (250pt)
Problem Statement

問題概要

$2$ つの正整数の組 $(x,y)$ があるとき,$(x+y, y)$ か $(x, x+y)$ に変更することができる.
($(x,y)$ と $(y,x)$ は違うものとみなす)
$0$ 回以上の変更で $(A,B)$ に到達でき,かつ,$(C,D)$ にも到達できるような $(x,y)$ のうち,$x+y$ の最大値を求める問題.
そのような $(x,y)$ がなければそれを指摘する.

解法

$(A,B)$ に変更することができるのは,$A > B$ のとき $(A-B,B)$ のみで,$A < B$ のとき $(A,B-A)$ のみと,一意に定まる.
よって,$(A,B) \neq (C,D)$ であるとき,$A+B$ と $C+D$ を比べて大きい方を $1$ ステップ前に巻き戻す,というのを繰り返して行けば良い.
最初に一致した時の $A+B$ が求める答えで,一致せずに $A,B,C,D$ のどれかが $0$ になったら存在しない.
時間計算量は $O(\max(A,B,C,D))$ 程度.

C++によるスパゲッティなソースコード

// #includeなどは略しています
class PairGame {
public:
int maxSum(int a, int b, int c, int d) {
  for(;;){
    if(a<=0 || b<=0 || c<=0 || d<=0) break;
    if(a==c && b==d) return a+b;

    if(a+b < c+d) swap(a,c), swap(b,d);
    if(a <= b) b -= a; else a -= b;
  }

  return -1;
}

}

Current time: 2017年09月25日08時01分39秒
Last modified: 2014年05月11日03時34分56秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM620 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: