#include <iostream>
#include <vector>
#include <string>
#include <cstdint>
#include <map>
#include <limits>
#include <algorithm>
typedef std::vector<std::int64_t> DType;
typedef std::tuple < DType, std::int64_t,std::int64_t> VType;
typedef std::vector<VType> SType;
typedef std::map<DType, std::int64_t> MType;
DType MakeVector(const std::string& S) {
DType D;
for (auto& o : S) {
if (o != '_') {
char S[]{ o,'\0' };
D.push_back(std::atoi(S));
}
else {
D.push_back(-1);
}
}
return D;
}
std::int64_t CountNext(const DType& D, std::size_t P) {
std::int64_t C = 0;
for (std::size_t i = 0; i < D.size(); i++) {
if (D[(P + i) % D.size()] == -1) {
C++;
}
else {
break;
}
}
return C;
}
bool MemoOut(const MType& M) {
std::cout << "--Memo--" << std::endl;
for (auto& oo : M) {
std::cout << oo.second << ':';
for (auto& o : oo.first) {
std::cout << o<<',';
}
std::cout << std::endl;
}
std::cout << "--End--" << std::endl;
return true;
}
std::int64_t Solvar(DType D) {
SType S;
MType M;
VType V;
std::int64_t C;
std::int64_t Sc;
std::int64_t Min = std::numeric_limits<std::int64_t>::max();
S.push_back({ D,0,0 });
while (S.size() != 0) {
std::tie(D, Sc, C) = S.back();
S.pop_back();
if (Min <= Sc) continue;
if (C == 2)continue;
if (S.size() >= D.size() / 2) {
std::int64_t T = M[D];
if (T == 0) {
M[D] = Sc;
}
else {
if (T+2 <= Sc) continue;//ここいじると厳密解と近似値が変わる。T+X => X>=2(厳密解)、X<2(近似解?)
M[D] = Sc;
}
}
S.push_back({ D,Sc,C + 1 });
if (C == 0) {
std::int64_t T = D[Sc%D.size()];
if (T == -1) {
Sc++;
}
else {
D[Sc%D.size()] = -1;
Sc += T;
}
if (std::find_if_not(D.begin(), D.end(), [](auto& o) {return o == -1; }) == D.end()) {
if (Min > Sc) {
Min = Sc;
//M[D] = Sc;
}
}
else {
S.push_back({ D,Sc + CountNext(D,Sc%D.size()),0 });
}
}
else {
Sc++;
S.push_back({ D,Sc + CountNext(D,Sc%D.size()),0 });
}
}
// MemoOut(M);
return Min;
}
/**/
bool PrinTemp(DType D, std::int64_t Sc,std::int64_t Min) {
std::cout << Sc<<','<<Min<<':';
for (auto&o : D) {
if (o == -1) {
std::cout << '_'<< ',';
}
else {
std::cout << o << ',';
}
}
std::cout << std::endl;
return true;
}
std::int64_t Solver_r(DType D, MType& M,std::int64_t Sc,std::int64_t& Min) {
std::int64_t N = 0;
if (Sc >= Min) return false;
std::int64_t T = M[D];
if (T == 0) {
M[D] = Sc;
}
else {
if (T <= Sc)return false;
M[D] = Sc;
}
//PrinTemp(D, Sc,Min);
for (std::size_t i = 0; i < D.size(); i++) {
std::int64_t Id = (Sc + i) % D.size();
N = D[Id];
if (N == -1)continue;
D[Id] = -1;
if (std::find_if_not(D.begin(), D.end(), [](auto& o) {return o == -1; }) == D.end()) {
if (Min > Sc+N+i) {
Min = Sc + N+i;
//PrinTemp(D, Sc+N+i, Min);
//M[D] = Sc;
}
return true;
}
else {
Solver_r(D, M, Sc + N+i, Min);
}
D[Id] = N;
}
return false;
}
std::int64_t Solvar_Rec(const DType& D) {
MType M;
std::int64_t R = std::numeric_limits<std::int64_t>::max();
Solver_r(D, M, 0, R);
return R;
}
std::int64_t MakeHoge(const std::string& S) {
DType D = MakeVector(S);
return Solvar_Rec(D);
}
bool Show(const std::string& S, std::int64_t N) {
std::cout << N << ':' << S << std::endl;
return true;
}
int main() {
std::string S;
std::int64_t V = 0;
S = "12_3";
V=MakeHoge(S);
Show(S, V);
S = "14432";
V=MakeHoge(S);
Show(S, V);
S = "887654329";
V=MakeHoge(S);
Show(S, V);
S = "313__";
V=MakeHoge(S);
Show(S, V);
S = "4_35_1264_23_434";
V=MakeHoge(S);
Show(S, V);
S = "123456789123456789";
V=MakeHoge(S);
Show(S, V);
S = "88967472612377988186";
V=MakeHoge(S);
Show(S, V);
S = "19898693316679441672";
V=MakeHoge(S);
Show(S, V);
S = "93769682716711132249893";
V=MakeHoge(S);
Show(S, V);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y3N0ZGludD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPGxpbWl0cz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdHlwZWRlZiBzdGQ6OnZlY3RvcjxzdGQ6OmludDY0X3Q+IERUeXBlOwp0eXBlZGVmIHN0ZDo6dHVwbGUgPCBEVHlwZSwgc3RkOjppbnQ2NF90LHN0ZDo6aW50NjRfdD4gVlR5cGU7CnR5cGVkZWYgc3RkOjp2ZWN0b3I8VlR5cGU+IFNUeXBlOwp0eXBlZGVmIHN0ZDo6bWFwPERUeXBlLCBzdGQ6OmludDY0X3Q+IE1UeXBlOwoKRFR5cGUgTWFrZVZlY3Rvcihjb25zdCBzdGQ6OnN0cmluZyYgUykgewoJRFR5cGUgRDsKCWZvciAoYXV0byYgbyA6IFMpIHsKCQlpZiAobyAhPSAnXycpIHsKCQkJY2hhciBTW117IG8sJ1wwJyB9OwoJCQlELnB1c2hfYmFjayhzdGQ6OmF0b2koUykpOwoJCX0KCQllbHNlIHsKCQkJRC5wdXNoX2JhY2soLTEpOwoJCX0KCX0KCglyZXR1cm4gRDsKfQoKc3RkOjppbnQ2NF90IENvdW50TmV4dChjb25zdCBEVHlwZSYgRCwgc3RkOjpzaXplX3QgUCkgewoJc3RkOjppbnQ2NF90IEMgPSAwOwoJZm9yIChzdGQ6OnNpemVfdCBpID0gMDsgaSA8IEQuc2l6ZSgpOyBpKyspIHsKCQlpZiAoRFsoUCArIGkpICUgRC5zaXplKCldID09IC0xKSB7CgkJCUMrKzsKCQl9CgkJZWxzZSB7CgkJCWJyZWFrOwoJCX0KCX0KCXJldHVybiBDOwp9Cgpib29sIE1lbW9PdXQoY29uc3QgTVR5cGUmIE0pIHsKCXN0ZDo6Y291dCA8PCAiLS1NZW1vLS0iIDw8IHN0ZDo6ZW5kbDsKCWZvciAoYXV0byYgb28gOiBNKSB7CgkJc3RkOjpjb3V0IDw8IG9vLnNlY29uZCA8PCAnOic7CgkJZm9yIChhdXRvJiBvIDogb28uZmlyc3QpIHsKCQkJc3RkOjpjb3V0IDw8IG88PCcsJzsKCQl9CgkJc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCX0KCXN0ZDo6Y291dCA8PCAiLS1FbmQtLSIgPDwgc3RkOjplbmRsOwoKCXJldHVybiB0cnVlOwp9CgpzdGQ6OmludDY0X3QgU29sdmFyKERUeXBlIEQpIHsKCVNUeXBlIFM7CglNVHlwZSBNOwoJVlR5cGUgVjsKCXN0ZDo6aW50NjRfdCBDOwoJc3RkOjppbnQ2NF90IFNjOwoJc3RkOjppbnQ2NF90IE1pbiA9IHN0ZDo6bnVtZXJpY19saW1pdHM8c3RkOjppbnQ2NF90Pjo6bWF4KCk7CgoKCVMucHVzaF9iYWNrKHsgRCwwLDAgfSk7Cgl3aGlsZSAoUy5zaXplKCkgIT0gMCkgewoJCXN0ZDo6dGllKEQsIFNjLCBDKSA9IFMuYmFjaygpOwoJCVMucG9wX2JhY2soKTsKCgkJaWYgKE1pbiA8PSBTYykgY29udGludWU7CgkJaWYgKEMgPT0gMiljb250aW51ZTsKCQlpZiAoUy5zaXplKCkgPj0gRC5zaXplKCkgLyAyKSB7CgkJCXN0ZDo6aW50NjRfdCBUID0gTVtEXTsKCQkJaWYgKFQgPT0gMCkgewoJCQkJTVtEXSA9IFNjOwoJCQl9CgkJCWVsc2UgewoJCQkJaWYgKFQrMiA8PSBTYykgY29udGludWU7Ly/jgZPjgZPjgYTjgZjjgovjgajljrPlr4bop6Pjgajov5HkvLzlgKTjgYzlpInjgo/jgovjgIJUK1ggPT4gWD49Mu+8iOWOs+Wvhuino++8ieOAgVg8Mu+8iOi/keS8vOino++8n++8iQoJCQkJTVtEXSA9IFNjOwoJCQl9CgkJfQoKCQlTLnB1c2hfYmFjayh7IEQsU2MsQyArIDEgfSk7CgkJaWYgKEMgPT0gMCkgewoJCQlzdGQ6OmludDY0X3QgVCA9IERbU2MlRC5zaXplKCldOwoJCQlpZiAoVCA9PSAtMSkgewoJCQkJU2MrKzsKCQkJfQoJCQllbHNlIHsKCQkJCURbU2MlRC5zaXplKCldID0gLTE7CgkJCQlTYyArPSBUOwoJCQl9CgkJCWlmIChzdGQ6OmZpbmRfaWZfbm90KEQuYmVnaW4oKSwgRC5lbmQoKSwgW10oYXV0byYgbykge3JldHVybiBvID09IC0xOyB9KSA9PSBELmVuZCgpKSB7CgkJCQlpZiAoTWluID4gU2MpIHsKCQkJCQlNaW4gPSBTYzsKCQkJCQkvL01bRF0gPSBTYzsKCQkJCX0KCQkJfQoJCQllbHNlIHsKCQkJCVMucHVzaF9iYWNrKHsgRCxTYyArIENvdW50TmV4dChELFNjJUQuc2l6ZSgpKSwwIH0pOwoJCQl9CgkJfQoJCWVsc2UgewoJCQlTYysrOwoJCQlTLnB1c2hfYmFjayh7IEQsU2MgKyBDb3VudE5leHQoRCxTYyVELnNpemUoKSksMCB9KTsKCQl9CgoJfQoJLy8JTWVtb091dChNKTsKCXJldHVybiBNaW47Cn0KLyoqLwpib29sIFByaW5UZW1wKERUeXBlIEQsIHN0ZDo6aW50NjRfdCBTYyxzdGQ6OmludDY0X3QgTWluKSB7CglzdGQ6OmNvdXQgPDwgU2M8PCcsJzw8TWluPDwnOic7Cglmb3IgKGF1dG8mbyA6IEQpIHsKCQlpZiAobyA9PSAtMSkgewoJCQlzdGQ6OmNvdXQgPDwgJ18nPDwgJywnOwoJCX0KCQllbHNlIHsKCQkJc3RkOjpjb3V0IDw8IG8gPDwgJywnOwoJCX0KCX0KCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CglyZXR1cm4gdHJ1ZTsKfQpzdGQ6OmludDY0X3QgU29sdmVyX3IoRFR5cGUgRCwgTVR5cGUmIE0sc3RkOjppbnQ2NF90IFNjLHN0ZDo6aW50NjRfdCYgTWluKSB7CglzdGQ6OmludDY0X3QgTiA9IDA7CgoJaWYgKFNjID49IE1pbikgcmV0dXJuIGZhbHNlOwoKCXN0ZDo6aW50NjRfdCBUID0gTVtEXTsKCWlmIChUID09IDApIHsKCQkJTVtEXSA9IFNjOwoJCX0KCWVsc2UgewoJCWlmIChUIDw9IFNjKXJldHVybiBmYWxzZTsKCQlNW0RdID0gU2M7Cgl9CgoJLy9QcmluVGVtcChELCBTYyxNaW4pOwoKCWZvciAoc3RkOjpzaXplX3QgaSA9IDA7IGkgPCBELnNpemUoKTsgaSsrKSB7CgkJc3RkOjppbnQ2NF90IElkID0gKFNjICsgaSkgJSBELnNpemUoKTsKCgkJTiA9IERbSWRdOwoJCWlmIChOID09IC0xKWNvbnRpbnVlOwoJCURbSWRdID0gLTE7CQoJCWlmIChzdGQ6OmZpbmRfaWZfbm90KEQuYmVnaW4oKSwgRC5lbmQoKSwgW10oYXV0byYgbykge3JldHVybiBvID09IC0xOyB9KSA9PSBELmVuZCgpKSB7CgkJCWlmIChNaW4gPiBTYytOK2kpIHsKCQkJCU1pbiA9IFNjICsgTitpOwoJCQkJLy9QcmluVGVtcChELCBTYytOK2ksIE1pbik7CgkJCQkvL01bRF0gPSBTYzsKCQkJfQoJCQlyZXR1cm4gdHJ1ZTsKCQl9CgkJZWxzZSB7CgkJCVNvbHZlcl9yKEQsIE0sIFNjICsgTitpLCBNaW4pOwoJCX0KCQlEW0lkXSA9IE47Cgl9CglyZXR1cm4gZmFsc2U7Cn0Kc3RkOjppbnQ2NF90IFNvbHZhcl9SZWMoY29uc3QgRFR5cGUmIEQpIHsKCU1UeXBlIE07CglzdGQ6OmludDY0X3QgUiA9IHN0ZDo6bnVtZXJpY19saW1pdHM8c3RkOjppbnQ2NF90Pjo6bWF4KCk7CglTb2x2ZXJfcihELCBNLCAwLCBSKTsKCXJldHVybiBSOwp9CnN0ZDo6aW50NjRfdCBNYWtlSG9nZShjb25zdCBzdGQ6OnN0cmluZyYgUykgewoJRFR5cGUgRCA9IE1ha2VWZWN0b3IoUyk7CgoJcmV0dXJuIFNvbHZhcl9SZWMoRCk7Cn0KYm9vbCBTaG93KGNvbnN0IHN0ZDo6c3RyaW5nJiBTLCBzdGQ6OmludDY0X3QgTikgewoJc3RkOjpjb3V0IDw8IE4gPDwgJzonIDw8IFMgPDwgc3RkOjplbmRsOwoJcmV0dXJuIHRydWU7Cn0KCmludCBtYWluKCkgewoJc3RkOjpzdHJpbmcgUzsKCXN0ZDo6aW50NjRfdCBWID0gMDsKCglTID0gIjEyXzMiOwoJVj1NYWtlSG9nZShTKTsKCVNob3coUywgVik7CglTID0gIjE0NDMyIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoJUyA9ICI4ODc2NTQzMjkiOwoJVj1NYWtlSG9nZShTKTsKCVNob3coUywgVik7CglTID0gIjMxM19fIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoJUyA9ICI0XzM1XzEyNjRfMjNfNDM0IjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwkKCVMgPSAiMTIzNDU2Nzg5MTIzNDU2Nzg5IjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoJUyA9ICI4ODk2NzQ3MjYxMjM3Nzk4ODE4NiI7CglWPU1ha2VIb2dlKFMpOwoJU2hvdyhTLCBWKTsKCVMgPSAiMTk4OTg2OTMzMTY2Nzk0NDE2NzIiOwoJVj1NYWtlSG9nZShTKTsKCVNob3coUywgVik7CglTID0gIjkzNzY5NjgyNzE2NzExMTMyMjQ5ODkzIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoKCXJldHVybiAwOwp9