p528.in3
======================
3
i2

=================
p528.in4
======================
18
dli1eei1ei1eli1eee

=================
p528.in2
======================
10
i-1e

=================
p528.ans4
======================
ok

=================
p528.ans3
======================
Error at position 2!

=================
p528.ans2
======================
Error at position 1!

=================
p528.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int m;
string c;

void read() { cin >> m >> c; }

void solve() {
    // Single linear scan with a state machine. The state has two parts:
    //   frames   - stack of open containers, each LIST, DICT_K (boundary inside
    //              a dict, expecting next key item or 'e') or DICT_V (just saw
    //              a key, must read a value item next; 'e' not allowed)
    //   progress - what we're in the middle of parsing: NONE (at a clean
    //              boundary), INT (digits then 'e'), STR_LEN (digits then ':',
    //              accumulated length in str_val) or STR_BODY (str_val chars of
    //              raw body left to consume)
    //
    // To answer "can the prefix be completed within m chars?" we maintain
    // g_sum, the sum of per-frame g_cost values for all open frames. g_cost is
    // the cost to close a frame assuming whatever sits inside it will complete
    // on its own (just needs the trailing chars): 1 for LIST ('e'), 3 for
    // DICT_K ("0:" filler value + 'e'), 1 for DICT_V ('e' after the pending
    // value finishes). f_cost is the cost to close from a clean boundary
    // *inside* that frame, with no item lined up: 1 for LIST/DICT_K, 3 for
    // DICT_V (must add "0:" then 'e'). Then min_remaining is finish_cost +
    // g_sum when an item is in progress, or f_cost(top) + (g_sum -
    // g_cost(top)) at a clean boundary. Special case: empty stack and no item
    // started yet needs 2 chars for the smallest object.
    //
    // A prefix length j is feasible iff parsing c[0..j-1] never violated a rule
    // and j + min_remaining <= m; we track the largest such j, and print "ok"
    // only when the whole string parsed and the root object closed.

    enum Frame { LIST, DICT_K, DICT_V };
    enum Progress { NONE, INT, STR_LEN, STR_BODY };

    vector<Frame> frames;
    Progress progress = NONE;
    int int_digits = 0;
    bool int_zero = false;
    long long str_val = 0;
    int str_len_digits = 0;
    bool str_len_zero = false;
    bool root_started = false;
    bool root_completed = false;
    long long g_sum = 0;

    auto g_cost = [](Frame f) -> int { return (f == DICT_K) ? 3 : 1; };

    auto f_cost = [](Frame f) -> int { return (f == DICT_V) ? 3 : 1; };

    auto min_remaining = [&]() -> long long {
        if(root_completed) {
            return 0;
        }

        if(progress == NONE) {
            if(!root_started) {
                return 2;
            }

            if(frames.empty()) {
                return 0;
            }

            Frame top = frames.back();
            return f_cost(top) + (g_sum - g_cost(top));
        }

        long long finish_cost = 0;
        if(progress == INT) {
            finish_cost = (int_digits == 0 ? 1 : 0) + 1;
        } else if(progress == STR_LEN) {
            finish_cost = 1 + str_val;
        } else {
            finish_cost = str_val;
        }

        return finish_cost + g_sum;
    };

    auto item_completed = [&]() {
        if(frames.empty()) {
            root_completed = true;
        } else {
            Frame& top = frames.back();
            if(top == DICT_K) {
                g_sum -= g_cost(DICT_K);
                top = DICT_V;
                g_sum += g_cost(DICT_V);
            } else if(top == DICT_V) {
                g_sum -= g_cost(DICT_V);
                top = DICT_K;
                g_sum += g_cost(DICT_K);
            }
        }
    };

    auto start_item = [&](char ch) -> bool {
        if(ch == 'i') {
            progress = INT;
            int_digits = 0;
            int_zero = false;
            return true;
        }

        if(ch == 'l') {
            frames.push_back(LIST);
            g_sum += g_cost(LIST);
            return true;
        }

        if(ch == 'd') {
            frames.push_back(DICT_K);
            g_sum += g_cost(DICT_K);
            return true;
        }

        if(ch >= '0' && ch <= '9') {
            progress = STR_LEN;
            str_val = ch - '0';
            str_len_digits = 1;
            str_len_zero = (ch == '0');
            return true;
        }

        return false;
    };

    auto process = [&](char ch) -> bool {
        if(root_completed) {
            return false;
        }

        if(progress == INT) {
            if(ch >= '0' && ch <= '9') {
                if(int_zero && int_digits >= 1) {
                    return false;
                }

                if(ch == '0' && int_digits == 0) {
                    int_zero = true;
                }

                int_digits++;
                return true;
            }

            if(ch == 'e') {
                if(int_digits == 0) {
                    return false;
                }

                progress = NONE;
                item_completed();
                return true;
            }

            return false;
        }

        if(progress == STR_LEN) {
            if(ch >= '0' && ch <= '9') {
                if(str_len_zero && str_len_digits >= 1) {
                    return false;
                }

                str_val = str_val * 10 + (ch - '0');
                str_len_digits++;
                return true;
            }

            if(ch == ':') {
                progress = STR_BODY;
                if(str_val == 0) {
                    progress = NONE;
                    item_completed();
                }

                return true;
            }

            return false;
        }

        if(progress == STR_BODY) {
            str_val--;
            if(str_val == 0) {
                progress = NONE;
                item_completed();
            }

            return true;
        }

        if(frames.empty()) {
            if(root_started) {
                return false;
            }

            root_started = true;
            return start_item(ch);
        }

        Frame top = frames.back();
        if(top == LIST || top == DICT_K) {
            if(ch == 'e') {
                g_sum -= g_cost(top);
                frames.pop_back();
                item_completed();
                return true;
            }

            return start_item(ch);
        }

        if(ch == 'e') {
            return false;
        }

        return start_item(ch);
    };

    int n = (int)c.size();
    int j_max = 0;

    for(int i = 0; i < n; i++) {
        if(!process(c[i])) {
            break;
        }

        long long new_j = i + 1;
        if(new_j + min_remaining() > (long long)m) {
            break;
        }

        j_max = (int)new_j;
    }

    if(j_max == n && root_completed) {
        cout << "ok\n";
    } else {
        cout << "Error at position " << j_max << "!\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p528.in1
======================
14
li10e11:abcdefghijke

=================
statement.txt
======================
528. Bencoding
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Bencoding is a modern technique which is used for representing data structures as sequences of characters. It it capable of encoding strings, integers, lists and dictionaries as specified below:


every string s is encoded as "<k>:<s>", where "<s>" is the string itself and "<k>" is its length written with no leading zeros (with the exception of integer zero, which is always represented as "0"). Bencoding is capable of encoding empty strings, so s is allowed to be empty.

For example, "4:spam" represents the string "spam", "0:" represents an empty string.

every integer n is encoded as "i<n>e", where "<n>" is the number itself written with no leading zeros (with the exception of integer zero, which is always represented as "0"). Bencoding is capable of encoding very large integers, so n doesn't necessarily fit into any of the standard integer data types provided by programming languages. Only non-negative integers can be encoded using bencoding.

For example, "i1024e" represents the number 1024.

every list items containing n elements item0, item1,..., itemn-1 is encoded as "l<item0><item1> <itemn-1>e". Each item of the list itemi is a supported data structure encoded using bencoding technique. Lists are allowed to be empty.

For example, "li101el4:spami1024eee" represents the list "[ 101, [ "spam", 1024 ] ]".

every dictionary dict consisting of n keys key0, key1,..., keyn-1 mapped into n values value0, value1,..., valuen-1 correspondingly is encoded as "d<key0><value0><key1><value1> <keyn-1><valuen-1>e". All keys and values are supported data structures encoded using bencoding technique. A dictionary may have duplicate keys and/or values. Dictionaries are allowed to be empty.

For example, "d1:a0:1:pl1:b2:cdee" represents the dictionary with string key "a" mapped into an empty string "", and key "p" mapped into the list "[ "b", "cd" ]".


A character sequence c is called a  if the following two conditions are met:
c is a correct bencoded representation of a single string, integer, list or dictionary;
the number of characters in c doesn't exceed a given number m.


For example, when m=3, the sequence c="2:bc" is not considered a valid bencoded object even though it represents a correctly encoded string "bc".

Given m and c you have to write a program which should determine whether c is a . If c is not a , it also has to find the longest prefix of c which could be a prefix of some . Formally, you should find a maximal position j within the given character sequence c, such that a prefix of c up to, but not including, character at position j could be a prefix of some . If the given character sequence c is not a , but the entire sequence c is a prefix of some , then j is considered equal to the length of c.

Input
The first line of the input contains one integer m (2 ≤ m ≤ 109)  — the maximum possible length of a valid bencoded object. The second line contains a character sequence which you are to process. The sequence will only contain characters with ASCII codes from 33 to 127, inclusive. Its length will be between 1 and 106 characters.

Output
Print a single line containing word "ok" (without quotes) if the given input character sequence is a valid bencoded object. Otherwise, print message "Error at position j!". The first character of the input sequence is considered to have position "0".

Example(s)
sample input
sample output
14
li10e11:abcdefghijke
Error at position 6!

sample input
sample output
10
i-1e
Error at position 1!

sample input
sample output
3
i2
Error at position 2!

sample input
sample output
18
dli1eei1ei1eli1eee
ok



Note
In the first sample test the given sequence is not a valid bencoded object. But its prefix "li10e1" can be extended to a valid bencoded object while not exceeding 14 characters in length (for example, "li10e1:xe"). It's not the case with longer prefixes of length 7 and more, so j=6 in this case.


=================
p528.ans1
======================
Error at position 6!

=================
