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
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

struct Pyra {
    int dokad, koszt;
};

const int INF = 1e9;
const int GLUPI = 511;

void pyk(int bit) {
    cout << "+ " << bit << '\n';
    cout.flush();
}

int siorb() {
    cout << "?\n";
    cout.flush();
    char z;
    cin >> z;
    return z - '0';
}

void nadaj(int x, int bity) {
    for (int i = 0; i < bity; i++) pyk((x >> i) & 1);
}

int odbierz(int bity) {
    int x = 0;
    for (int i = 0; i < bity; i++) x |= (siorb() << i);
    return x;
}

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

    string kto;
    cin >> kto;

    int n, m;
    cin >> n >> m;

    vector<vector<Pyra>> bimbaly(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        bimbaly[a].push_back({b, c});
        bimbaly[b].push_back({a, c});
    }

    vector<int> dystans(n + 1, INF), najlepsze(n + 1, INF);
    vector<char> zjedzone(n + 1, 0);

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> kopczyk;

    auto chlup = [&](int v, int d) {
        if (d < najlepsze[v]) {
            najlepsze[v] = d;
            kopczyk.push({d, v});
        }
    };

    zjedzone[1] = 1;
    dystans[1] = 0;

    for (auto [dokad, koszt] : bimbaly[1]) chlup(dokad, koszt);

    int poprzednia = 0;
    bool algosia = (kto == "Algosia");

    for (int runda = 1; runda < n; runda++) {
        while (!kopczyk.empty() && (zjedzone[kopczyk.top().second] || kopczyk.top().first != najlepsze[kopczyk.top().second])) {
            kopczyk.pop();
        }

        int mojeDelta = GLUPI;
        int mojeMiasto = -1;
        int mojaOdleglosc = INF;

        if (!kopczyk.empty()) {
            mojaOdleglosc = kopczyk.top().first;
            mojeMiasto = kopczyk.top().second;
            mojeDelta = mojaOdleglosc - poprzednia;
        }

        nadaj(mojeDelta, 9);
        int cudzeDelta = odbierz(9);

        bool wygrywam = algosia ? (mojeDelta <= cudzeDelta) : (mojeDelta < cudzeDelta);

        int noweMiasto, nowaOdleglosc;

        if (wygrywam) {
            nadaj(mojeMiasto - 1, 11);
            noweMiasto = mojeMiasto;
            nowaOdleglosc = mojaOdleglosc;
        } else {
            noweMiasto = odbierz(11) + 1;
            nowaOdleglosc = poprzednia + cudzeDelta;
        }

        zjedzone[noweMiasto] = 1;
        dystans[noweMiasto] = nowaOdleglosc;
        poprzednia = nowaOdleglosc;

        for (auto [dokad, koszt] : bimbaly[noweMiasto]) {
            if (!zjedzone[dokad]) chlup(dokad, nowaOdleglosc + koszt);
        }
    }

    if (algosia) {
        cout << "!";
        for (int i = 1; i <= n; i++) cout << ' ' << dystans[i];
        cout << '\n';
        cout.flush();
    }

    return 0;
}