← Real problems

ioi18p1

mediuminteractiveconstructiveStatement on DMOJ

CP Lang

16 lineschecks
// ioi18p1 Combo: find a hidden word over A B X Y whose first letter never comes back, in n + 2
// presses. Two presses find the first letter; then one press settles each next letter: with the
// other three letters a, b, c, the press "s a | s b a | s b b | s b c" grows by 1 for a, 2 for b
// and 0 for c. The last letter takes two plain presses.
extern fn press(p: Str) -> Int
@grader
fn guess_sequence(n: Int) -> Str:
    let first = if press("AB") >= 1: (if press("A") == 1: 'A' else: 'B') else: (if press("X") == 1: 'X' else: 'Y')
    let o = "ABXY".filter(ch => ch != first).collect()
    var s = Str.of([first])
    for _ in 2..n:
        let grew = press(s + [o[0]] + s + [o[1], o[0]] + s + [o[1], o[1]] + s + [o[1], o[2]]) - s.len
        s.push(if grew == 1: o[0] else: (if grew == 2: o[1] else: o[2]))
    if n >= 2:
        s.push(if press(s + [o[0]]) == n: o[0] else: (if press(s + [o[1]]) == n: o[1] else: o[2]))
    s

Accepted C++

77 lines · 1.29 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

int press(string p);

const string chars = "ABXY";

char solve1(string s) {
    string poss;
    if (press(s + 'A' + s + 'B') > sz(s)) {
        poss = "AB";
    } else {
        poss = "XY";
    }
    if (press(s + poss[0]) > sz(s)) {
        return poss[0];
    } else {
        return poss[1];
    }
}

string guess_sequence(int n) {
    char first = solve1("");
    string cchars;
    for (auto& a : chars) {
        if (a != first) {
            cchars += a;
        }
    }
    string s {first};
    if (n == 1) {
        return s;
    }
    for (int i = 1; i < n - 1; i++) {
        string buf = s + cchars[0];
        for (auto& a : cchars) {
            buf += s + cchars[1] + a;
        }
        dbg(buf, sz(buf), n);
        int cans = press(buf);
        if (cans == sz(s)) {
            s += cchars[2];
        } else if (cans == sz(s) + 1) {
            s += cchars[0];
        } else {
            s += cchars[1];
        }
    }
    return s + solve1(s);
}