This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
各問題の正解している問題の点数の合計が$score$であり，不正解の問題の点数と番号の差の絶対値の最大値を最小化する．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class ScoreRecomposition {
public :
int minError ( string questions , int score ) {
int n = questions . size ();
vector < int > id ;
rep ( i , n ) id . push_back ( i + 1 );
int ans = INF ;
do {
int sum = 0 , res = 0 ;
rep ( i , n ) {
if ( questions [ i ] == 'C' ) {
sum += id [ i ];
}
res = max ( res , abs ( i + 1 - id [ i ]));
}
if ( sum == score ) {
ans = min ( ans , res );
}
} while ( next_permutation ( id . begin (), id . end ()));
if ( ans == INF ) return - 1 ;
return ans ;
}
};