#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+CountNext(D,Sc%D.size())) continue;
//if (Min <= Sc) continue;
if (C == 2)continue;
std::int64_t X = M[D];
/**/
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;
}
std::int64_t MakeHoge(const std::string& S) {
DType D = MakeVector(S);
return Solvar(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+IE1UeXBlOwoKRFR5cGUgTWFrZVZlY3Rvcihjb25zdCBzdGQ6OnN0cmluZyYgUykgewoJRFR5cGUgRDsKCWZvciAoYXV0byYgbyA6IFMpIHsKCQlpZiAobyAhPSAnXycpIHsKCQkJY2hhciBTW117IG8sJ1wwJyB9OwoJCQlELnB1c2hfYmFjayhzdGQ6OmF0b2koUykpOwoJCX0KCQllbHNlIHsKCQkJRC5wdXNoX2JhY2soLTEpOwoJCX0KCX0KCglyZXR1cm4gRDsKfQoKc3RkOjppbnQ2NF90IENvdW50TmV4dChjb25zdCBEVHlwZSYgRCwgc3RkOjpzaXplX3QgUCkgewoJc3RkOjppbnQ2NF90IEMgPSAwOwoJZm9yIChzdGQ6OnNpemVfdCBpID0gMDsgaSA8IEQuc2l6ZSgpOyBpKyspIHsKCQlpZiAoRFsoUCArIGkpICUgRC5zaXplKCldID09IC0xKSB7CgkJCUMrKzsKCQl9CgkJZWxzZSB7CgkJCWJyZWFrOwoJCX0KCX0KCXJldHVybiBDOwp9Cgpib29sIE1lbW9PdXQoY29uc3QgTVR5cGUmIE0pIHsKCXN0ZDo6Y291dCA8PCAiLS1NZW1vLS0iIDw8IHN0ZDo6ZW5kbDsKCWZvciAoYXV0byYgb28gOiBNKSB7CgkJc3RkOjpjb3V0IDw8IG9vLnNlY29uZCA8PCAnOic7CgkJZm9yIChhdXRvJiBvIDogb28uZmlyc3QpIHsKCQkJc3RkOjpjb3V0IDw8IG88PCcsJzsKCQl9CgkJc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCX0KCXN0ZDo6Y291dCA8PCAiLS1FbmQtLSIgPDwgc3RkOjplbmRsOwoKCXJldHVybiB0cnVlOwp9CgpzdGQ6OmludDY0X3QgU29sdmFyKERUeXBlIEQpIHsKCVNUeXBlIFM7CglNVHlwZSBNOwoJVlR5cGUgVjsKCXN0ZDo6aW50NjRfdCBDOwoJc3RkOjppbnQ2NF90IFNjOwoJc3RkOjppbnQ2NF90IE1pbiA9IHN0ZDo6bnVtZXJpY19saW1pdHM8c3RkOjppbnQ2NF90Pjo6bWF4KCk7CgoKCVMucHVzaF9iYWNrKHsgRCwwLDAgfSk7Cgl3aGlsZSAoUy5zaXplKCkgIT0gMCkgewoJCXN0ZDo6dGllKEQsIFNjLCBDKSA9IFMuYmFjaygpOwoJCVMucG9wX2JhY2soKTsKCQlpZiAoTWluIDw9IFNjK0NvdW50TmV4dChELFNjJUQuc2l6ZSgpKSkgY29udGludWU7CgkJLy9pZiAoTWluIDw9IFNjKSBjb250aW51ZTsKCQlpZiAoQyA9PSAyKWNvbnRpbnVlOwoJCXN0ZDo6aW50NjRfdCBYID0gTVtEXTsKLyoqLwoJCWlmIChTLnNpemUoKSA+IEQuc2l6ZSgpLzIpIHsKCQkKCQkJc3RkOjppbnQ2NF90IFQgPSBNW0RdOwoJCQlpZiAoVCA9PSAwKSB7CgkJCQlNW0RdID0gU2M7CgkJCX0KCQkJZWxzZSB7CgkJCQlpZiAoVCsyIDw9IFNjKSBjb250aW51ZTsvL+OBk+OBk+OBhOOBmOOCi+OBqOWOs+Wvhuino+OBqOi/keS8vOWApOOBjOWkieOCj+OCi+OAglQrWCA9PiBYPj0y77yI5Y6z5a+G6Kej77yJ44CBWDwy77yI6L+R5Ly86Kej77yf77yJ44CACgkJCQlNW0RdID0gU2M7CgkJCX0KCQl9Ci8qKi8KCQlTLnB1c2hfYmFjayh7IEQsU2MsQysxIH0pOwoJCWlmIChDID09IDApIHsKCQkJc3RkOjppbnQ2NF90IFQgPSBEW1NjJUQuc2l6ZSgpXTsKCQkJaWYgKFQgPT0gLTEpIHsKCQkJCVNjKys7CgkJCX0KCQkJZWxzZSB7CgkJCQlEW1NjJUQuc2l6ZSgpXSA9IC0xOwoJCQkJU2MrPVQ7CQkJCQkKCQkJfQoJCQlpZiAoc3RkOjpmaW5kX2lmX25vdChELmJlZ2luKCksIEQuZW5kKCksIFtdKGF1dG8mIG8pIHtyZXR1cm4gbyA9PSAtMTsgfSkgPT0gRC5lbmQoKSkgewoJCQkJaWYgKE1pbiA+IFNjKSB7CgkJCQkJTWluID0gU2M7CgkJCQkJTVtEXSA9IFNjOwoJCQkJfQoJCQl9CgkJCWVsc2UgewoJCQkJUy5wdXNoX2JhY2soeyBELFNjICsgQ291bnROZXh0KEQsU2MlRC5zaXplKCkpLDAgfSk7CgkJCX0KCQl9CgkJZWxzZSB7CgkJCVNjKys7CgkJCVMucHVzaF9iYWNrKHsgRCxTYysgQ291bnROZXh0KEQsU2MlRC5zaXplKCkpLDAgfSk7CgkJfQoKCX0KLy8JTWVtb091dChNKTsKCXJldHVybiBNaW47Cn0Kc3RkOjppbnQ2NF90IE1ha2VIb2dlKGNvbnN0IHN0ZDo6c3RyaW5nJiBTKSB7CglEVHlwZSBEID0gTWFrZVZlY3RvcihTKTsKCglyZXR1cm4gU29sdmFyKEQpOwp9CmJvb2wgU2hvdyhjb25zdCBzdGQ6OnN0cmluZyYgUywgc3RkOjppbnQ2NF90IE4pIHsKCXN0ZDo6Y291dCA8PCBOIDw8ICc6JyA8PCBTIDw8IHN0ZDo6ZW5kbDsKCXJldHVybiB0cnVlOwp9CgppbnQgbWFpbigpIHsKCXN0ZDo6c3RyaW5nIFM7CglzdGQ6OmludDY0X3QgViA9IDA7CgoJUyA9ICIxMl8zIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwovKiovCglTID0gIjE0NDMyIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwovKiovCglTID0gIjg4NzY1NDMyOSI7CglWPU1ha2VIb2dlKFMpOwoJU2hvdyhTLCBWKTsKLyoqLwovKiovCglTID0gIjMxM19fIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoJUyA9ICI0XzM1XzEyNjRfMjNfNDM0IjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwkKCVMgPSAiMTIzNDU2Nzg5MTIzNDU2Nzg5IjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoJUyA9ICI4ODk2NzQ3MjYxMjM3Nzk4ODE4NiI7CglWPU1ha2VIb2dlKFMpOwoJU2hvdyhTLCBWKTsKCVMgPSAiMTk4OTg2OTMzMTY2Nzk0NDE2NzIiOwoJVj1NYWtlSG9nZShTKTsKCVNob3coUywgVik7CglTID0gIjkzNzY5NjgyNzE2NzExMTMyMjQ5ODkzIjsKCVY9TWFrZUhvZ2UoUyk7CglTaG93KFMsIFYpOwoKCXJldHVybiAwOwp9CgoK