読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM 712 DIV 1 easy : LR

SRM

問題概要:
サイズがnであるような2つの数列s,tが与えられる。
数列s,tの各要素には0からn-1まで番号がふられている。
数列sに対して以下の2つの操作を任意の回数だけ適用してtにできるか。
できるならその適用した順序を1つ出力せよ。
操作1. s[i] = s[i] + s[i-1] ( ただし i-1 < 0 なら s[i-1] は s[n-1] )

操作2. s[i] = s[i] + s[i+1] ( ただし i+1 >= n なら s[i+1] は s[0] )

解法:
操作1と操作2の使用回数が同じ場合、その順番によって結果は変わらない。
つまり、(操作1)→(操作2)→(操作1)→(操作2)の結果得られる数列と
(操作1)→(操作1)→(操作2)→(操作2)の結果得られる数列は同じである。
そのため、操作1と操作2を同じ回数で何回適用するか決め打ちする。
その後操作1だけを適用してtを作れるか、また操作2だけを適用してtを作れるかを試す。

注意点::オーバーフロー

s = { 1, 1 }
t = { 0, 0 }

のようなケースでオーバーフローしないか?
私は「そんなうまいケースないでしょ」と手を抜いてしまいeasy落としました。
悔い改めます。

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;

const string NO = "No solution";

class LR {
public:
  vector<ll> tmp;
  void simulateL(vector<long long> &vec) {
    int n = (int)vec.size();
    vector<long long> next(n);
    rep(i,n) next[i] = vec[i] + vec[((i-1)+n)%n];
    vec = next;
  }

  void simulateR(vector<long long> &vec) {
    int n = (int)vec.size();
    vector<long long> next(n);
    rep(i,n) next[i] = vec[i] + vec[(i+1)%n];
    vec = next;
  }

  bool check(vector<ll> &s,vector<ll> &t) {
    rep(i,(int)s.size()) {
      if( s[i] < tmp[i] ) return false;
      if( s[i] != t[i] ) return false;
    }
    return true;
  }

  int checkL(vector<ll> s,vector<ll> t,int rem) {
    if( check(s,t) ) return 0;
    REP(i,1,rem+1) {
      simulateL(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) return -1;
      if( check(s,t) ) return i;
    }
    return -1;
  }

  int checkR(vector<ll> s,vector<ll> t,int rem) {
    if( check(s,t) ) return 0;
    REP(i,1,rem+1) {
      simulateR(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) return -1;
      if( check(s,t) ) return i;
    }
    return -1;
  }

  string construct(vector<long long> s, vector<long long> t) {
    string ans = "";
    tmp = s;
    rep(i,101) {
      if( 100 - 2 * i < 0 ) break;
      if( check(s,t) ) {
	return ans;
      }
      int use;
      if( ( use = checkL(s,t,100-2*i) ) != -1 ) {
	rep(_,use) ans += "L";
	return ans;
      }
      if( ( use = checkR(s,t,100-2*i) ) != -1 ) {
	rep(_,use) ans += "R";
	return ans;
      }
      simulateL(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) break;
      simulateR(s);
      rep(j,(int)s.size()) if( s[j] < tmp[j] ) break;
      ans += "LR";
    }
    return NO;
  }
};

SRM 711 : ConsecutiveOnes

SRM Div1

問題概要:
整数nとkが与えられる
次の条件を満たすような最小の整数mを求めよ:
1. m は n 以上である
2. m を2進数表記にしたとき、1が少なくともk個連続する箇所が存在する

制約 :
1 <= n <= 2^50 - 1
1 <= k <= 50

解法:
mの中で1がk個連続する箇所をループで決める
このとき、mがn以上ならそれを答えの候補にする
そうでないとき、mがn以上でなおかつそのような値の中で最小になるように調整し答えの候補に追加する
答えの候補の中の最小値を答えとして返す

mがn未満の場合にn以上でなおかつ最小になるように調整する 手順は次の通り
m = 0..01..10..0
1. n - mを求める
これをxとする
2. xとmの論理積 x & m が 0 なら、

m = x | m 

として調整終了
そうでないなら、

m = ( m | x ) & ~((1LL<<sp)-1LL)
m += (1LL<<(sp+k))

とする
このとき、
m = 0..01..10..0
の赤くなっている1の位置がsp


注意点:
オーバーフローしないように、ビットをシフトする際には

1<<k 

ではなく

1LL<<k

とすること

コード:

typedef long long ll;
class ConsecutiveOnes {
public:
  ll compute(int sp,ll n,int k) {
    ll v = 0LL;
    rep(i,k) v |= (1LL<<(sp+i));
    if( v >= n ) return v;
    ll need = n - v;
    if( ( v & need ) == 0LL ) {
      return v | need;
    }
    v = ( v | need ) & ~((1LL<<sp)-1LL);
    v += (1LL<<(sp+k));
    return v;
  }
  
  long long get(long long n, int k) {
    ll mini = LLONG_MAX;
    rep(i,100) {
      if( i + k >= 62 ) break;
      mini = min(mini,compute(i,n,k));
    }
    return mini;
  }
};

SRM 709 Div1 easy : Xscoregame

SRM 動的計画法

問題概要 :

長さ n (1 <= n <= 15) の数列 A が与えられる
Aの各要素A[i]は 0 以上 50 以下である
この数列に対して以下の処理を行う

1. 変数 X を用意し、 X に 0 を代入する
2. 数列 A のなかから、まだ使っていない要素 A[i] を選び X の値を次の式で更新する :
X = X + ( X xor A[i] )
  これを選べる要素がなくなるまで続ける
3. X の値を出力する

最終的に X のとりうる最大の値を答えよ

解法 :
ビットDP
dp[Aのどの要素を使ったかをbitで保持, 1<<15][下位6bit x, 1<<6] = 下位6bit が x であるような値の最大値

愚直にやると、bool dp[state1][state2]
bool dp[Aのどの要素を使ったかをbitで保持, 1<<15][ Aの要素を使用した状態が state1 であるときの最大値 ] = state2を作れるか
とやれば良い
ただ、サンプルの最後を見るとわかる通りstate2がかなり大きくなる

Xの値を計算する際に xor をとるため、単純に大きい値だけを保持していてもそれが最終的に最大値になるかどうかはわからない
そのためbitの情報をすべて state2 としてとっていたのだが、A[i] <= 50 であることに注目すればわざわざ全てのbitの情報を保持しておく必要がないことが分かる
なぜなら、( X xor A[i] ) において X の 6bit目以降は xor の計算で影響を受けない
なので6bit目以下だけをdpの状態として保持すれば良い

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

#define MAX 64

int dp[1<<15][MAX];

class Xscoregame {
public:
  int getscore(vector <int> A) {
    int n = A.size();
    sort(A.begin(),A.end());    
    memset(dp,-1,sizeof dp);
    dp[0][0] = 0;
    rep(bit,(1<<n)) {
      rep(bet,MAX) {
	if( dp[bit][bet] == -1 ) continue;
	rep(i,n) {
	  if( (bit>>i) & 1 ) continue;
	  int nbit = bit | (1<<i);
	  int value = dp[bit][bet] + ( dp[bit][bet] ^ A[i] );
	  int beet = value % MAX;
	  dp[nbit][beet] = max(dp[nbit][beet],value);
	}
      }
    }
    int maxi = 0;
    rep(i,MAX) maxi = max(maxi,dp[(1<<n)-1][i]);
    return maxi;
  }
};

SRM 708 : Div1 easy BalancedStrings

SRM Div1

問題概要:
1以上100以下の整数Nが与えられる。
以下の条件を満たすサイズNの文字列の集合Sを1つ見つけよ。
条件を満たすようなものは必ず存在する。

条件 1. 集合Sの要素である文字列の長さは1以上100以下である。
条件 2. 集合Sの要素である文字列は英小文字aからzから構成される。
条件 3. 集合Sの安定度と不安定度は等しい。

集合Sの安定度と不安定度は以下のように定義される。

安定度. Sに属する全ての文字列 s の連続する同じ英小文字を1つにまとめた文字列s'の長さ-1の総和
例 : S = { "aabcccdd", "a", "abccdde" } の安定度は 3 + 0 + 4 = 7

不安定度. Sに属する異なる二つの要素 s, t について、共通に現れる英小文字のペアの数の総和
 例 : S = { "aabcccdd", "a", "abccdde" } の不安定度は 16
"aabcccdd" と "a" から 2
"aabcccdd" と "abccdde" から 2 + 1 + 6 + 4 = 13
"a" と "abccdde" から 1
よって 16

解法:

不安定度を決定した後に安定度をそれに合わせる方針をとる。
以下、うまく説明をまとめることができなかったのでコンテスト中の自分がどのように考えていったのかについて書きます。
~~~ コンテスト中
どうしようか。
まず次のようなサイズNの文字列の集合 { "a", "a", ..., "a" }を用意して、この安定度を増加させていく方針で考えてみようかな。
この段階で不安定度は N * ( N - 1 ) / 2 だから、N が最大のとき、つまり100 なら不安定度は 4950。
さて、後は要素の文字列を変更して安定度を調整しよう。
aを使うと不安定度が変わるから、まだ集合の中にない文字列を二つ選んで追加しよう。
{ "abcbc", "adedede", ..., "ayzyzyz" } みたいな感じでね。
文字列の長さは最大100だから、この方法を使えば一つの文字列で安定度を最大99まで上げることができるな。
一度使った英小文字は別の文字列では使えない (使うと不安定度が上がる) から、最大 25 / 2 = 12 の文字のペアを使えて、 12 * 99 = 1188までは自由に安定度を増加させれるな。
あれ、不安定度は4950だよな。
(安定度が足り)ないじゃん。
不安定度を減らさなきゃ。
じゃあ { "a", ..., "a", "b", ..., "b" } としようかな。
するとN = 100のときの不安定度は ( 50 * 49 / 2 ) * 2 = 2450。
残りの英小文字で作れる安定度の最大は 24 / 2 = 12 ペア * 99 = 1188。
まだ足りない。
...
{ "a", ..., "a", "b", ..., "b", "c", ..., "c", "d", ..., "d", "e", ..., "e" }はどうだろう。
N = 100 のとき不安定度は ( 20 * 19 / 2 ) * 5 = 950。
残りの英小文字で作れる安定度の最大は 21 / 2 = 10 ペア * 99 = 990。
これなら不安定度と安定度を同じにできる!

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

class BalancedStrings {
public:

  int calcS(vector<string> vec) {
    int S = 0;
    rep(i,(int)vec.size()) {
      map<char,int> cnt;
      rep(j,(int)vec[i].size()) ++cnt[vec[i][j]];
      REP(j,i+1,(int)vec.size()) {
	rep(k,(int)vec[j].size()) {
	  S += cnt[vec[j][k]];
	}
      }
    }
    return S;
  }

  vector <string> findAny(int N) {
    vector<string> ret;
    rep(i,N) ret.push_back(string(1,(char)(('a'+i%5))));
    int sim = calcS(ret);
    rep(i,N) if( sim ) {
      char p = (char)('f'+i*2), q = (char)('g'+i*2);
      while( (int)ret[i].size() < 100 && sim ) {
	int len = ret[i].size();
	if( len & 1 ) {
	  ret[i] += string(1,p);
	  --sim;
	} else {
	  ret[i] += string(1,q);
	  --sim;
	}
      }
    }
    return ret;
  }
};

SRM 704 Div1 easy : TreeDistanceConstruction

SRM

問題概要:
次の制約を満たすような木は存在するか?

1. 木の頂点iのeccentricityがちょうどd[i]である.

ここで、頂点iのeccentricityとは、頂点iから最も遠い頂点との距離のことである.
存在するのであればその木の辺集合を配列にして返すこと.
存在しないのであれば空の配列を返すこと.

制約:
頂点数は高々50

解法:
答えとなる木の中で、最も離れている頂点対(i,j)について考える.
この2点をつなぐ長さd[i]のパスが存在するはずなので、そのパスを用意する.
そのパス上の最も離れた頂点対以外の頂点になりうる入力中の頂点が存在するはずなので、
それらを見つけてパスの頂点と対応付ける.
あとは入力中のまだどこにも対応付けられていない頂点を、そのパス上の適切な頂点に繋げればよい.
適切な頂点というのは、頂点iのeccentricityがd[i]であるときeccentricityがd[i]-1であるような頂点のことである.
マイナス1してあるのは、その頂点に辺を張ることでeccentricityが1増えるため.
残った頂点のeccentricityは最もd[i]以下かつ(パスの長さ)/2より大きいはずである.

例えば、Examplesの0)について考えてみる.
Examples 0) の入力は {3,2,2,3}なので、最も離れている頂点対は(0,3)である(0-indexed).
それでは、まず最初にこの2点をつなぐパスを作る.
このパスは以下の図のようになる.
f:id:tei3344:20161230180612j:plain
最も離れている頂点対以外のパス上の頂点のeccentricityは?となっているが、
これらのeccentricityは明らかに2である.
f:id:tei3344:20161230181349j:plain
この例だとこれで条件を満たす木ができたので終わり.

Examples 1)についても考えて見る.
入力は {1,2,2,2}である.
まず最初に最も離れている頂点対からパスを作る.
f:id:tei3344:20161230181739j:plain
次にパスの中のでまだ入力中の頂点と対応付けられていない頂点に対して入力中の頂点を対応付ける.
f:id:tei3344:20161230182312j:plain
あとは、残った入力中の頂点1をパス上の適切な頂点に繋げればよい.
頂点1のeccentricityは2なので、パス上のeccentricityが1の頂点に繋げばよい.
f:id:tei3344:20161230182742j:plain

最後に、Examplesにはないが少し大きめの例について考えて見る.
入力は{4,4,3,2,3,4,4,3}とする.
まず最初に最も離れている頂点対からパスを作る.
f:id:tei3344:20161230183306j:plain
次に、パス上の頂点と入力上の頂点を対応付ける
f:id:tei3344:20161230183440j:plain
最後に、入力中の残った頂点をパス上の適切な頂点に繋げる.
まず、頂点5はeccentricityが4であるため、eccentricityが3であるような頂点に繋げば良い.
f:id:tei3344:20161230183822j:plain
頂点6もeccentricityが4であるため、eccentricityが3であるような頂点に繋げば良い.
f:id:tei3344:20161230184011j:plain
最後に、頂点7のeccentricityは3なので、eccentricityが2であるような頂点に繋ぐ.
f:id:tei3344:20161230184206j:plain
完成である.

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS 1e-10
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

const int IINF = INT_MAX;

struct Data {
  int index;
  int eccentricity;
  bool operator < ( const Data &data ) const {
    return eccentricity > data.eccentricity;
  }
};

class TreeDistanceConstruction {
public:
  vector <int> construct(vector <int> d) {
    deque<Data> deq;
    int n = d.size();
    rep(i,n) deq.push_back((Data){i,d[i]});
    d.clear();
    sort(deq.begin(),deq.end());
    int maxi = deq[0].eccentricity;

    if( maxi != deq[1].eccentricity ) return vector<int>();
    vector<vector<int>> G;
    int root = (maxi+1) / 2;
    rep(i,(maxi+1)) {

      G.push_back(vector<int>());

      G[i].push_back(-1); // G[i][0], index

      if( (maxi+1) & 1 ) { // G[i][1], eccentricity
	if( i <= root ) G[i].push_back(maxi-i);
	else            G[i].push_back(i);
      } else {
	if( i < root ) G[i].push_back(maxi-i);
	else            G[i].push_back(i);
      }
      
      if( i + 1 < (maxi+1) ) G[i].push_back(i+1);
      if( i - 1 >= 0 ) G[i].push_back(i-1);

    }
    
    G[0][0] = deq.front().index; deq.pop_front();
    G[(int)G.size()-1][0] = deq.front().index; deq.pop_front();

    REP(i,1,(int)G.size()-1) {
      int pos = -1;
      rep(j,(int)deq.size()) {
	if( deq[j].eccentricity == G[i][1] ) {
	  pos = j;
	  break;
	}
      }
      if( pos == -1 ) return vector<int>();
      G[i][0] = deq[pos].index;
      deq.erase(deq.begin()+pos);
    }
    
    rep(i,(int)deq.size()) {
      if( deq[i].eccentricity <= root ) return vector<int>();
      G.push_back(vector<int>());
      G[(int)G.size()-1].push_back(deq[i].index);
      G[(int)G.size()-1].push_back(deq[i].eccentricity);
      G[(int)G.size()-1].push_back(deq[i].eccentricity-1);
      G[deq[i].eccentricity-1].push_back((int)G.size()-1);
    }

    vector<int> answer;
    rep(i,(int)G.size()) {
      REP(j,2,(int)G[i].size()) {
	int s = G[i][0];
	int t = G[G[i][j]][0];
	if( s < t ) {
	  answer.push_back(s);
	  answer.push_back(t);
	}
      }
    }
    return answer;
  }
};

LiveArchive 5873 : Tree Inspections

lower_bound 二分探索 LiveArchive

問題リンク : https://icpcarchive.ecs.baylor.edu/external/58/5873.pdf

問題概要 :
2次元平面上にT本の木とH本の道が存在する.
T本の木のうち60%以上を道の上から見ることはできるだろうか?
木は以下の条件を満たすとき、道から見ることができる :
道から垂直に木まで線を引いた際に、その間に他の木が立っていない.

例えば、Sample Input は次のようになる.
黒い点が木を、赤い線が道を表す.
f:id:tei3344:20161031011235p:plain
f:id:tei3344:20161031011305p:plain
f:id:tei3344:20161031011325p:plain

制約 :
1 <= T,P <= 10^5

解法 :
各木について、その木が道から見ることができるかどうかを確かめる
ただし愚直に実装すると T * P ( = 10^10 ) となり間に合わない
そこで、ある木が見えるかどうかを判定する際には、その木に最も近い上下左右の木のみを用いる

つまり、その木に最も近い上下左右の木を求め、その木と最も近い上下左右の木のいずれかとの間に道が存在するかどうかを判定する
これなら全体でもT * 4 * logPとなり間に合う

例えば、以下のようなケースについて考える
f:id:tei3344:20161031012227p:plain
赤い点が今見えるかどうかを判定したい木とする
このとき、この木が見えるかどうかの判定に必要な木は青い点として表されている以下の3本である
f:id:tei3344:20161031012422p:plain
これらの青い点はlower_boundで求めることができる
f:id:tei3344:20161031013257p:plain
f:id:tei3344:20161031013554p:plain
あとはその木とlower_boundで求めた木の間に道があるかどうかをlower_boundで求める

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LTE(double a,double b) { return equals(a,b) || a < b; }

const int IINF = INT_MAX;

struct Data {
  int x,y;
};

int dx[] = {0,1,0,-1}; // ↓→↑←
int dy[] = {1,0,-1,0};

int T, P;

bool cmp_x(const Data &v1, const Data &v2) {
  if( v1.x != v2.x ) return v1.x < v2.x;
  return v1.y < v2.y;
}

bool cmp_y(const Data &v1, const Data &v2) {
  if( v1.y != v2.y ) return v1.y < v2.y;
  return v1.x < v2.x;
}

#define ALL(x) x.begin(),x.end()

void compute(vector<Data> &vec, vector<int> &hs, vector<int> &vs) {
  vector<Data> adj[4];
  vector<Data> xs,ys;
  rep(i,T) xs.push_back(vec[i]), ys.push_back(vec[i]);
  sort(ALL(xs),cmp_x);
  sort(ALL(ys),cmp_y);
  sort(ALL(hs));
  sort(ALL(vs));

  rep(i,T) {
    // ↓ xは同じ y+
    int ptr = lower_bound(ALL(xs),vec[i],cmp_x) - xs.begin();
    ++ptr;
    if( ptr < T && xs[ptr-1].x == xs[ptr].x ) {
      adj[0].push_back(xs[ptr]);
    } else {
      adj[0].push_back((Data){vec[i].x,IINF});
    }
    
    // → yは同じ x+
    ptr = lower_bound(ALL(ys),vec[i],cmp_y) - ys.begin();
    ++ptr;
    if( ptr < T && ys[ptr-1].y == ys[ptr].y ) {
      adj[1].push_back(ys[ptr]);
    } else {
      adj[1].push_back((Data){IINF,vec[i].y});
    }


    // ↑ xは同じ y-
    ptr = lower_bound(ALL(xs),vec[i],cmp_x) - xs.begin();
    --ptr;
    if( ptr >= 0 && xs[ptr+1].x == xs[ptr].x ) {
      adj[2].push_back(xs[ptr]);
    } else {
      adj[2].push_back((Data){vec[i].x,-IINF});
    }

    // ← yは同じ x-
    ptr = lower_bound(ALL(ys),vec[i],cmp_y) - ys.begin();
    --ptr;
    if( ptr >= 0 && ys[ptr+1].y == ys[ptr].y ) {
      adj[3].push_back(ys[ptr]);
    } else {
      adj[3].push_back((Data){-IINF,vec[i].y});
    }
  }

  vector<bool> ok(T,false);
  rep(i,T) {
    bool see = false;
    rep(j,4) {
      Data point = adj[j][i];
      if( point.x == vec[i].x ) {
	int pos = lower_bound(ALL(hs),min(vec[i].y,point.y)) - hs.begin();

	if( pos >= (int)hs.size() ) continue;
	if( min(point.y,vec[i].y) <= hs[pos] && hs[pos] <= max(point.y,vec[i].y) ) {
	  see = true;
	  break;
	}
      } else {
      	int pos = lower_bound(ALL(vs),min(vec[i].x,point.x)) - vs.begin();
	if( pos >= (int)vs.size() ) continue;
	if( min(point.x,vec[i].x) <= vs[pos] && vs[pos] <= max(point.x,vec[i].x) ) {
	  see = true;
	  break;
	}
      }
    }
    if( see ) ok[i] = true;
  }
  double cnt = 0;
  rep(i,T) cnt += ok[i];
  if( LTE(0.6,cnt/(double)T) ) {
    puts("PASSED");
  } else {
    puts("FAILED");
  }
}

int main() {
  int F;
  while( cin >> F ) {
    rep(_,F) {
      cin >> T >> P;
      vector<Data> vec(T);
      vector<int> hs,vs;
      rep(i,T) cin >> vec[i].x >> vec[i].y;
      rep(i,P) {
	char c;
	int v;
	cin >> c >> v;
	if( c == 'H' ) hs.push_back(v);
	else           vs.push_back(v);
      }
      compute(vec,hs,vs);
    }
  }
  return 0;
}

CODE FESTIVAL 2016 予選B : D - Greedy customers

CODE FESTIVAL

問題リンク :
D: Greedy customers - CODE FESTIVAL 2016 qual B | AtCoder

問題概要 : 日本語なので略

解法 :
(備忘録)
貪欲法。

1ずつ引いていけば良い?1を引けなくなったら2を、それもダメなら3を、...という流れで、
=> Sample Input 2 の答えが13になる
これでダメなケースとは?
...
Sample Input X

4
1
2
6
10

Sample Output X

4

Why?

1 2 6 10  P
1 2 3 10 (3)
1 2 3 6  (4)
1 2 3 2  (4)
Ans : 3.

1 2 6 10  P
1 2 1 10 (5)
1 2 1 7  (3)
1 2 1 4  (3)
1 2 1 1  (3)
Ans : 4.

引ける最小の値が大きくなってしまうような場合は一気に1まで値を引いてしまえばよいネ



コード :

#include<bits/stdc++.h>
 
using namespace std;

#define MAX 100010

int N;
long long A[MAX];
 
int main(){
  long long answer = 0, lower = 1LL;
  cin >> N;
  for(int i=0;i<N;++i) cin >> A[i];

  for(int i=0;i<N;++i) {
    if( lower == 1LL ) {
      answer += (A[i]-1LL);
      lower = 2LL;
      continue;
    }
    
    if( lower == A[i] ) {
      ++lower;
      continue;
    }
 
    if( lower > A[i] ) continue;    
 
    long long coef = A[i] / lower;
    if( ( A[i] - coef * lower ) == 0LL ) {
      --coef;
    }
    answer += coef;
  }
  cout << answer << endl; 
  return 0;
}