#include <iostream> #include <vector> #include <string> #include <sstream> #include <climits> #include <algorithm> using namespace std; const int INF = 1e9; int main() { int L; cin >> L; cin.ignore(); vector<string> words; string line, word; while (getline(cin, line)) { istringstream iss(line); while (iss >> word) { words.push_back(word); } } int n = words.size(); vector<int> len(n); for (int i = 0; i < n; ++i) len[i] = words[i].size(); // cost[i][j] = 把单词 i~j 放一行的丑陋度 vector<vector<int>> cost(n, vector<int>(n, INF)); for (int i = 0; i < n; ++i) { int sum_len = 0; for (int j = i; j < n; ++j) { sum_len += len[j]; int gaps = j - i; int total = sum_len + gaps; if (total > L) break; if (j == i) { cost[i][j] = 500; } else { int spaces = L - sum_len; int base = spaces / gaps; int extra = spaces % gaps; int bad = 0; for (int k = 0; k < gaps; ++k) { int s = base + (k < extra ? 1 : 0); bad += (s - 1) * (s - 1); } cost[i][j] = bad; } } } // dp[i] = 前 i 个单词（0~i-1）的最小丑陋度 vector<int> dp(n + 1, INF); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (cost[j][i - 1] != INF) { dp[i] = min(dp[i], dp[j] + cost[j][i - 1]); } } } cout << "Minimal badness is " << dp[n] << "." << endl; return 0; }