Problem 1258 : Book Replacement

Problem B: Book Replacement
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1258

• 問題概要

本の置き換えのシミュレーション。
めんどくさい。
コストの計算が非常に分かりにくいが、
どれだけの距離歩くか、とかではなく、
本を取り上げたり置いたりするところの座標の合計がコストである。
まちがって歩く距離でだしてて、非常に時間を無駄にした。

• 解法

書くだけ。
がんばろう。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

class Student{
public:
  int r[50], now;
  bool done;
  Student(){
    rep(i, 50)r[i] = -1;
    now = 0;
    done = false;
  }
  int next(){
    now++;
    if(now == 50 || r[now] == -1){
      done = true;
    }
    return r[now-1];
  }
};

main(){

  int m, c, n;
  
  while(cin >> m >> c >> n){
    if(m + c + n == 0)break;
    Student s[n];
    rep(i, n){
      int k;
      cin >> k;
      rep(j, k){
	cin >> s[i].r[j];
      }
    } 
 
    bool d[m][100];

    rep(i, m){
      rep(j, 100){
	d[i][j] = false;
      }
    }
    int cost = 0;
    int capa[m];
    rep(i, m)capa[i] = 0;
    vint v;
    while(1){
      bool end = true;
      rep(i, n){
	if(s[i].done)continue;
	end = false;
	int r = s[i].next();
	bool finde = false;
	rep(j, m){
	  if(d[j][r]){
	    if(j == 0)v.erase(find(ALL(v), r));
	    cost += j + 1;
	    d[j][r] = false; 
	    finde = true;
	    capa[j]--;
	    break;
	  }
	}

	if(!finde){
	  cost += m+1;
	}
	if(capa[0] < c){  
	  d[0][r] = true;
	  capa[0]++;
	  cost++;
	  v.pb(r);
	  continue;
	}

	int pos = -1;
	rep(j, m){    
	  if(capa[j] < c){
	    cost += (j + 1)*2 +1;
	    pos = j;
	    capa[j]++;
	    break;
	  }
	  if( j == m-1){
	    cost += (m+2)*2 + 1;
	  }
	}
	capa[0]--;
	d[0][v[0]] = false;
	cost++;
	int tmp = v[0];
	v.erase(v.begin());
	REP(j, 1, m){
	  if(capa[j] < c){
	    capa[j]++;
	    d[j][tmp] = true;
	    cost += j+1;
	    break;
	  }
	  if(j == m-1){
	    cost += m+1;
	  }
	}
	if(pos != -1){
	  capa[pos]--;
	}
	d[0][r] = true;
	capa[0]++;
	v.pb(r);
      }  
      if(end)break;
    }
    cout << cost << endl;
  }
}