保存されている過去のバージョンの一覧

2014年05月11日03時34分56秒

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: 2024年04月20日06時23分11秒
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)

ログイン：