Submission #1361024


Source Code Expand

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct Pair {
    char c;
    int cnt, mid;

    Pair() {}
    Pair(char c, int cnt, int mid) : c(c), cnt(cnt), mid(mid) {}
};

bool comp (const Pair &p1, const Pair &p2) {
    if (p1.cnt == p2.cnt) return p1.mid < p2.mid;
    return p1.cnt > p2.cnt;
}

string s, tmp;
Pair p[27];
int size_, ans, msize;
char ma[50];

bool check(string t) {
    int si = t.size();

    for (int i = 0; i < si - 1; ++i) {
        if (t[i] != t[i + 1]) {
            return false;
        }
    }

    return true;
}

int main() {
    cin >> s;

    for (int i = 0; i < 26; ++i) {
        p[i] = Pair(char('a' + i), 0, 999);
    }

    size_ = s.size();

    for (int i = 0; i < size_; ++i) {
        p[s[i] - 'a'].cnt++;
        p[s[i] - 'a'].mid += abs(size_ / 2 - i);
    }

    sort(p, p + 26, comp);

    ma[0] = p[0].c;
    msize++;
    for (int i = 1; i < 26; ++i) {
        if (p[0].cnt == p[i].cnt) {
            ma[msize] = p[i].c;
            msize++;
        }
    }

    int temp = 0;
    ans = 999;
    string sub = s;

    for (int k = 0; k < msize; ++k) {
        temp = 0;
        s = sub;

        while (!check(s)) {
            temp++;
            tmp = "";
            size_ = s.size();
            for (int i = 0; i < size_ - 1; ++i) {
                if (s[i] == ma[k]) {
                    tmp += s.substr(i,1);
                }
                else {
                    tmp += s.substr(i + 1, 1);
                }
            }
            s = tmp;
        }
        ans = min(temp, ans);
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task A - Shrinking
User otyaduke_117
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1752 Byte
Status WA
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 300
Status
AC × 4
AC × 11
WA × 3
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 2 ms 256 KB
1_02.txt AC 1 ms 256 KB
1_03.txt AC 1 ms 256 KB
1_04.txt AC 1 ms 256 KB
1_05.txt AC 1 ms 256 KB
1_06.txt WA 1 ms 256 KB
1_07.txt WA 1 ms 256 KB
1_08.txt AC 2 ms 256 KB
1_09.txt WA 1 ms 256 KB