Problem A. Bot Trust
問題概要
青と橙のロボットがある。
それぞれのロボットは別々の廊下に隔離されてテストを行う。
各々のロボットの初期値は buttun 1 である。(距離が1の場所)
各々のロボットは1秒間で上下どちらの方向かに1進むことができる、
または、指定位置にいる場合は button を押すことができる
テストを完了するために、指定された順序でbuttonを押さなければならない
テストを完了するためにかかる最短時間を求める
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define DEB 0 #define all(x) x.begin(), x.end() int main(){ int T; scanf("%d",&T); rep(x,T){ char r; int n,p,pb=0,po=0,tmp; int blue=1,orange=1,ret=0; scanf("%d ",&n); rep(i,n){ scanf(" %c %d ",&r,&p); if( r=='O' ){ tmp = max(abs(p-orange)-pb,0) + 1; po += tmp; ret += tmp; orange = p; pb = 0; }else{ tmp = max(abs(p-blue)-po,0) + 1; pb += tmp; ret += tmp; blue = p; po = 0; } } printf("Case #%d: %d\n",x+1,ret); } return 0; }
・試行錯誤のめも
単純なシミュレーション
計算量は考える必要ない
とりあえず実装、サンプルあわない、あるぇー
アドホック修正も虚しく。んー、青と橙の総移動距離の和を求めて最大値を返せばいいんじゃね?
だめでした、待つ時間を忘れてた
Cのほうが簡単だろ、と思いつつ、手を動かすがなんかうまくいかない。
うーんうーん、整理するのへたくそだなぁ
p-orange で 距離差(ボタンは含まれてない
pb(prev_blue) が、blueのボタンを押すのにかかった時間だとすると、(これはボタン含んでる
abs(p-orange)-pb これが、必要な操作回数になる
max(abs(p-orange)-pb,1) これで、ボタンを押すのも含めた橙の時間
これを ret に加算して、橙の位置を更新し、青にかかった時間を0にする
まった、pbにボタンを押す時間を含めたらだめな気がする、え、いや、必要だろ
てきとーに修正、small通った。さすがにこのサイズだとオーバーフローしないだろ、largeも提出