分块打表练手题
传送门：https://www.luogu.com.cn/problem/P1662
步骤
先预处理出 (1 imes10^6,2 imes10^6,...,1000 imes10^6) 的状态。（这里的 (10^6) 就是所谓的块长 (len) 了）
这里的状态有两个属性：方向、位置（也就是第几个人）。
然后我们将这 (1000) 个状态存入表中。
结合分块的思想，对于查询 (n) ，我们将 (n) 表述为 (n = 10^6 imes k + r) ，(k) 就是对应的块数，可以用打表出的状态 (O(1)) 求出，然后剩下 (r) 直接暴力模拟求出，因为 (r<10^6) （块长），故复杂度即为 (O(len)) 。
代码实现
generator
#include<bits/stdc++.h>
using namespace std;
const int len=1e6;
bool check(int v){
if(v%7==0) return true;
while(v){
if(v%10==7) return true;
v/=10;
}
return false;
}
int main(){
freopen("table.out", "w", stdout);
int tag=1, p=1337; // 模拟撞到特殊的数而且已经回头了
int tot=0;
for(int i=1; i<=1000; i++){
int L=(i-1)*len+1, R=i*len;
int x=tag, y=p;
for(int j=L; j<=R; j++){
++tot;
if(y==1337 && x==1) y=1;
else if(y==1 && x==-1) y=1337;
else y+=x;
if(check(tot)) x=-x;
}
tag=x, p=y;
cout<<p<<','<<tag<<',';
}
return 0;
}
table
int table[]={
0,469,-1,139,1,1086,-1,768,1,860,-1,1200,1,837,1,837,-1,507,1,117,-1,1136,1,1228,-1,231,1,1205,1,337,-1,7,1,954,1,954,-1,862,1,522,-1,885,-1,416,1,746,-1,1136,1,117,-1,25,1,1022,1,1022,1,154,-1,1161,1,771,-1,453,1,545,-1,885,1,522,1,991,-1,661,-1,661,1,979,-1,887,1,547,-1,910,-1,441,1,771,-1,1161,1,142,-1,50,-1,50,1,1024,1,156,-1,1163,1,773,-1,455,1,547,-1,887,1,524,1,993,1,993,-1,46,1,364,-1,272,1,1269,-1,295,-1,1163,1,156,-1,546,1,864,1,864,-1,1204,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,-1,523,1,615,-1,955,1,592,1,1061,-1,731,1,341,1,341,-1,249,1,1246,-1,272,-1,1140,1,133,-1,523,1,841,-1,749,1,409,1,409,1,878,-1,548,1,158,-1,1177,1,1269,-1,272,1,1246,1,378,-1,48,-1,48,1,366,-1,274,1,1271,-1,297,-1,1165,1,158,-1,548,1,866,-1,774,-1,774,1,411,1,880,-1,550,1,160,-1,1179,1,1271,-1,274,1,1248,1,380,1,380,-1,770,1,1088,-1,996,1,656,-1,1019,-1,550,1,880,-1,1270,1,251,1,251,-1,591,1,228,1,697,-1,367,1,1314,-1,996,1,1088,-1,91,1,1065,1,1065,-1,735,1,345,-1,27,1,119,-1,459,1,96,1,565,-1,235,1,1182,1,1182,-1,1090,1,750,-1,1113,-1,644,1,974,-1,27,1,345,-1,253,1,1250,1,1250,1,382,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,1,1049,-1,75,-1,943,1,1273,-1,326,1,644,-1,552,-1,552,1,189,1,658,-1,328,1,1275,-1,957,1,1049,-1,52,1,1026,1,158,1,158,-1,548,1,866,-1,774,1,434,-1,797,-1,328,1,658,-1,1048,1,29,1,29,-1,369,1,6,1,475,-1,145,1,1092,-1,774,1,866,-1,1206,1,843,1,843,-1,513,1,123,-1,1142,1,1234,-1,237,1,1211,1,343,-1,13,1,960,1,960,-1,868,1,528,-1,891,-1,422,1,752,-1,1142,1,123,-1,31,1,1028,1,1028,1,160,-1,1167,1,777,-1,459,1,551,-1,891,1,528,1,997,-1,667,-1,667,1,985,-1,893,1,553,-1,916,-1,447,1,777,-1,1167,1,148,-1,56,-1,56,1,1030,1,162,-1,1169,1,779,-1,461,1,553,-1,893,1,530,1,999,1,999,-1,52,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,839,-1,509,1,119,-1,1138,1,1230,-1,233,1,1207,1,1207,-1,877,1,487,-1,169,1,261,-1,601,1,238,1,707,-1,377,1,1324,1,1324,-1,1232,1,892,-1,1255,-1,786,1,1116,-1,169,1,487,-1,395,1,55,1,55,1,524,-1,194,1,1141,-1,823,1,915,-1,1255,1,892,1,24,-1,1031,-1,1031,1,12,-1,1257,1,917,-1,1280,-1,811,1,1141,-1,194,1,512,-1,420,-1,420,1,57,1,526,-1,196,1,1143,-1,825,1,917,-1,1257,1,894,1,26,1,26,-1,416,1,734,-1,642,1,302,-1,665,-1,196,1,526,-1,916,1,1234,1,1234,-1,237,1,1211,1,343,-1,13,1,960,-1,642,1,734,-1,1074,1,711,1,711,-1,381,1,1328,-1,1010,1,1102,-1,105,1,1079,1,211,-1,1218,1,828,1,828,-1,736,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,-1,786,1,1104,-1,1012,1,672,-1,1035,-1,566,1,896,1,896,-1,578,1,670,-1,1010,1,647,1,1116,-1,786,1,396,-1,78,1,170,1,170,-1,533,-1,64,1,394,-1,784,1,1102,-1,1010,1,670,-1,1033,-1,564,-1,564,1,174,-1,1193,1,1285,-1,288,1,1262,1,394,-1,64,1,1011,-1,693,-1,693,1,353,-1,716,-1,247,1,577,-1,967,1,1285,-1,1193,1,853,-1,1216,-1,1216,1,209,-1,599,1,917,-1,825,1,485,-1,848,-1,379,1,709,-1,1099,-1,1099,1,1191,-1,194,1,1168,1,300,-1,1307,1,917,-1,599,1,691,-1,1031,-1,1031,-1,562,1,892,-1,1282,1,263,-1,171,1,1168,-1,194,-1,1062,1,55,1,55,-1,1074,1,1166,-1,169,1,1143,1,275,-1,1282,1,892,-1,574,1,666,1,666,-1,1029,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,1,652,-1,992,1,629,1,1098,-1,768,1,378,-1,60,-1,60,1,1057,-1,83,-1,951,1,1281,-1,334,1,652,-1,560,1,220,-1,583,-1,583,1,913,-1,1303,1,284,-1,192,1,1189,-1,215,-1,1083,1,76,-1,466,-1,466,1,558,-1,898,1,535,1,1004,-1,674,1,284,-1,1303,1,58,-1,398,-1,398,-1,1266,1,259,-1,649,1,967,-1,875,1,535,-1,898,-1,429,1,759,1,759,-1,441,1,533,-1,873,1,510,1,979,-1,649,1,259,-1,1278,1,33,1,33,-1,396,-1,1264,1,257,-1,647,1,965,-1,873,1,533,-1,896,-1,427,-1,427,1,37,-1,1056,1,1148,-1,151,1,1125,1,257,-1,1264,1,874,-1,556,-1,556,1,216,-1,579,-1,110,1,440,-1,830,1,1148,-1,1056,1,716,-1,1079,-1,1079,1,72,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,1,99,1,568,-1,238,1,1185,-1,867,1,959,-1,1299,-1,1299,-1,830,1,1160,-1,213,1,531,-1,439,1,99,-1,462,-1,1330,1,323,1,323,-1,5,1,97,-1,437,1,74,1,543,-1,213,1,1160,-1,842,1,934,1,934,-1,1297,-1,828,1,1158,-1,211,1,529,-1,437,1,97,-1,460,-1,1328,-1,1328,1,938,-1,620,1,712,-1,1052,1,689,1,1158,-1,828,1,438,-1,120,-1,120,1,1117,-1,143,-1,1011,1,4,-1,394,1,712,-1,620,1,280,-1,643,-1,643,1,973,-1,26,1,344,-1,252,1,1249,-1,275,-1,1143,1,136,-1,526,-1,526,1,618,-1,958,1,595,1,1064,-1,734,1,344,-1,26,1,118,-1,458,-1,458,-1,1326,1,319,-1,709,1,1027,-1,935,1,595,-1,958,-1,489,1,819,1,819,-1,501,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,-1,263,1,1210,-1,892,1,984,-1,1324,1,961,1,93,1,93,-1,483,1,801,-1,709,1,369,-1,732,-1,263,1,593,-1,983,1,1301,1,1301,-1,304,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,-1,331,1,649,-1,557,1,217,-1,580,-1,111,1,441,1,441,-1,123,1,215,-1,555,1,192,1,661,-1,331,1,1278,-1,960,1,1052,1,1052,-1,78,-1,946,1,1276,-1,329,1,647,-1,555,1,215,-1,578,-1,109,-1,109,1,1056,-1,738,1,830,-1,1170,1,807,1,1276,-1,946,1,556,-1,238,-1,238,1,1235,-1,261,-1,1129,1,122,-1,512,1,830,-1,738,1,398,-1,761,-1,761,1,1091,-1,144,1,462,-1,370,1,30,-1,393,-1,1261,1,254,-1,644,-1,644,1,736,-1,1076,1,713,1,1182,-1,852,1,462,-1,144,1,236,-1,576,-1,576,-1,107,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,-1,777,1,414,1,883,-1,553,1,163,-1,1182,1,1274,1,1274,-1,300,-1,1168,1,161,-1,551,1,869,-1,777,1,437,-1,800,-1,331,-1,331,1,1278,-1,960,1,1052,-1,55,1,1029,1,161,-1,1168,1,778,-1,460,-1,460,1,120,-1,483,-1,14,1,344,-1,734,1,1052,-1,960,1,620,-1,983,-1,983,1,1313,-1,366,1,684,-1,592,1,252,-1,615,-1,146,1,476,-1,866,-1,866,1,958,-1,1298,1,935,1,67,-1,1074,1,684,-1,366,1,458,-1,798,-1,798,-1,329,1,659,-1,1049,1,30,-1,1275,1,935,-1,1298,-1,829,1,1159,1,1159,-1,841,1,933,-1,1273,1,910,1,42,-1,1049,1,659,-1,341,1,433,1,433,-1,796,-1,327,1,657,-1,1047,1,28,-1,1273,1,933,-1,1296,-1,827,-1,827,1,437,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,987,1,1317,-1,370,1,688,-1,596,1,256,-1,619,-1,619,1,949,-1,2,1,320,-1,228,1,1225,-1,251,-1,1119,1,112,-1,502,-1,502,1,594,-1,934,1
};
main
#include<bits/stdc++.h>
using namespace std;
const int len=1e6;
int table[]={
0,469,-1,139,1,1086,-1,768,1,860,-1,1200,1,837,1,837,-1,507,1,117,-1,1136,1,1228,-1,231,1,1205,1,337,-1,7,1,954,1,954,-1,862,1,522,-1,885,-1,416,1,746,-1,1136,1,117,-1,25,1,1022,1,1022,1,154,-1,1161,1,771,-1,453,1,545,-1,885,1,522,1,991,-1,661,-1,661,1,979,-1,887,1,547,-1,910,-1,441,1,771,-1,1161,1,142,-1,50,-1,50,1,1024,1,156,-1,1163,1,773,-1,455,1,547,-1,887,1,524,1,993,1,993,-1,46,1,364,-1,272,1,1269,-1,295,-1,1163,1,156,-1,546,1,864,1,864,-1,1204,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,1,841,-1,523,1,615,-1,955,1,592,1,1061,-1,731,1,341,1,341,-1,249,1,1246,-1,272,-1,1140,1,133,-1,523,1,841,-1,749,1,409,1,409,1,878,-1,548,1,158,-1,1177,1,1269,-1,272,1,1246,1,378,-1,48,-1,48,1,366,-1,274,1,1271,-1,297,-1,1165,1,158,-1,548,1,866,-1,774,-1,774,1,411,1,880,-1,550,1,160,-1,1179,1,1271,-1,274,1,1248,1,380,1,380,-1,770,1,1088,-1,996,1,656,-1,1019,-1,550,1,880,-1,1270,1,251,1,251,-1,591,1,228,1,697,-1,367,1,1314,-1,996,1,1088,-1,91,1,1065,1,1065,-1,735,1,345,-1,27,1,119,-1,459,1,96,1,565,-1,235,1,1182,1,1182,-1,1090,1,750,-1,1113,-1,644,1,974,-1,27,1,345,-1,253,1,1250,1,1250,1,382,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,-1,52,1,1049,-1,75,-1,943,1,1273,-1,326,1,644,-1,552,-1,552,1,189,1,658,-1,328,1,1275,-1,957,1,1049,-1,52,1,1026,1,158,1,158,-1,548,1,866,-1,774,1,434,-1,797,-1,328,1,658,-1,1048,1,29,1,29,-1,369,1,6,1,475,-1,145,1,1092,-1,774,1,866,-1,1206,1,843,1,843,-1,513,1,123,-1,1142,1,1234,-1,237,1,1211,1,343,-1,13,1,960,1,960,-1,868,1,528,-1,891,-1,422,1,752,-1,1142,1,123,-1,31,1,1028,1,1028,1,160,-1,1167,1,777,-1,459,1,551,-1,891,1,528,1,997,-1,667,-1,667,1,985,-1,893,1,553,-1,916,-1,447,1,777,-1,1167,1,148,-1,56,-1,56,1,1030,1,162,-1,1169,1,779,-1,461,1,553,-1,893,1,530,1,999,1,999,-1,52,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,370,1,839,-1,509,1,119,-1,1138,1,1230,-1,233,1,1207,1,1207,-1,877,1,487,-1,169,1,261,-1,601,1,238,1,707,-1,377,1,1324,1,1324,-1,1232,1,892,-1,1255,-1,786,1,1116,-1,169,1,487,-1,395,1,55,1,55,1,524,-1,194,1,1141,-1,823,1,915,-1,1255,1,892,1,24,-1,1031,-1,1031,1,12,-1,1257,1,917,-1,1280,-1,811,1,1141,-1,194,1,512,-1,420,-1,420,1,57,1,526,-1,196,1,1143,-1,825,1,917,-1,1257,1,894,1,26,1,26,-1,416,1,734,-1,642,1,302,-1,665,-1,196,1,526,-1,916,1,1234,1,1234,-1,237,1,1211,1,343,-1,13,1,960,-1,642,1,734,-1,1074,1,711,1,711,-1,381,1,1328,-1,1010,1,1102,-1,105,1,1079,1,211,-1,1218,1,828,1,828,-1,736,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,1,396,-1,786,1,1104,-1,1012,1,672,-1,1035,-1,566,1,896,1,896,-1,578,1,670,-1,1010,1,647,1,1116,-1,786,1,396,-1,78,1,170,1,170,-1,533,-1,64,1,394,-1,784,1,1102,-1,1010,1,670,-1,1033,-1,564,-1,564,1,174,-1,1193,1,1285,-1,288,1,1262,1,394,-1,64,1,1011,-1,693,-1,693,1,353,-1,716,-1,247,1,577,-1,967,1,1285,-1,1193,1,853,-1,1216,-1,1216,1,209,-1,599,1,917,-1,825,1,485,-1,848,-1,379,1,709,-1,1099,-1,1099,1,1191,-1,194,1,1168,1,300,-1,1307,1,917,-1,599,1,691,-1,1031,-1,1031,-1,562,1,892,-1,1282,1,263,-1,171,1,1168,-1,194,-1,1062,1,55,1,55,-1,1074,1,1166,-1,169,1,1143,1,275,-1,1282,1,892,-1,574,1,666,1,666,-1,1029,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,-1,560,1,652,-1,992,1,629,1,1098,-1,768,1,378,-1,60,-1,60,1,1057,-1,83,-1,951,1,1281,-1,334,1,652,-1,560,1,220,-1,583,-1,583,1,913,-1,1303,1,284,-1,192,1,1189,-1,215,-1,1083,1,76,-1,466,-1,466,1,558,-1,898,1,535,1,1004,-1,674,1,284,-1,1303,1,58,-1,398,-1,398,-1,1266,1,259,-1,649,1,967,-1,875,1,535,-1,898,-1,429,1,759,1,759,-1,441,1,533,-1,873,1,510,1,979,-1,649,1,259,-1,1278,1,33,1,33,-1,396,-1,1264,1,257,-1,647,1,965,-1,873,1,533,-1,896,-1,427,-1,427,1,37,-1,1056,1,1148,-1,151,1,1125,1,257,-1,1264,1,874,-1,556,-1,556,1,216,-1,579,-1,110,1,440,-1,830,1,1148,-1,1056,1,716,-1,1079,-1,1079,1,72,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,-1,462,1,99,1,568,-1,238,1,1185,-1,867,1,959,-1,1299,-1,1299,-1,830,1,1160,-1,213,1,531,-1,439,1,99,-1,462,-1,1330,1,323,1,323,-1,5,1,97,-1,437,1,74,1,543,-1,213,1,1160,-1,842,1,934,1,934,-1,1297,-1,828,1,1158,-1,211,1,529,-1,437,1,97,-1,460,-1,1328,-1,1328,1,938,-1,620,1,712,-1,1052,1,689,1,1158,-1,828,1,438,-1,120,-1,120,1,1117,-1,143,-1,1011,1,4,-1,394,1,712,-1,620,1,280,-1,643,-1,643,1,973,-1,26,1,344,-1,252,1,1249,-1,275,-1,1143,1,136,-1,526,-1,526,1,618,-1,958,1,595,1,1064,-1,734,1,344,-1,26,1,118,-1,458,-1,458,-1,1326,1,319,-1,709,1,1027,-1,935,1,595,-1,958,-1,489,1,819,1,819,-1,501,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,1,593,-1,263,1,1210,-1,892,1,984,-1,1324,1,961,1,93,1,93,-1,483,1,801,-1,709,1,369,-1,732,-1,263,1,593,-1,983,1,1301,1,1301,-1,304,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,1,1278,-1,331,1,649,-1,557,1,217,-1,580,-1,111,1,441,1,441,-1,123,1,215,-1,555,1,192,1,661,-1,331,1,1278,-1,960,1,1052,1,1052,-1,78,-1,946,1,1276,-1,329,1,647,-1,555,1,215,-1,578,-1,109,-1,109,1,1056,-1,738,1,830,-1,1170,1,807,1,1276,-1,946,1,556,-1,238,-1,238,1,1235,-1,261,-1,1129,1,122,-1,512,1,830,-1,738,1,398,-1,761,-1,761,1,1091,-1,144,1,462,-1,370,1,30,-1,393,-1,1261,1,254,-1,644,-1,644,1,736,-1,1076,1,713,1,1182,-1,852,1,462,-1,144,1,236,-1,576,-1,576,-1,107,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,1,437,-1,777,1,414,1,883,-1,553,1,163,-1,1182,1,1274,1,1274,-1,300,-1,1168,1,161,-1,551,1,869,-1,777,1,437,-1,800,-1,331,-1,331,1,1278,-1,960,1,1052,-1,55,1,1029,1,161,-1,1168,1,778,-1,460,-1,460,1,120,-1,483,-1,14,1,344,-1,734,1,1052,-1,960,1,620,-1,983,-1,983,1,1313,-1,366,1,684,-1,592,1,252,-1,615,-1,146,1,476,-1,866,-1,866,1,958,-1,1298,1,935,1,67,-1,1074,1,684,-1,366,1,458,-1,798,-1,798,-1,329,1,659,-1,1049,1,30,-1,1275,1,935,-1,1298,-1,829,1,1159,1,1159,-1,841,1,933,-1,1273,1,910,1,42,-1,1049,1,659,-1,341,1,433,1,433,-1,796,-1,327,1,657,-1,1047,1,28,-1,1273,1,933,-1,1296,-1,827,-1,827,1,437,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,119,-1,987,1,1317,-1,370,1,688,-1,596,1,256,-1,619,-1,619,1,949,-1,2,1,320,-1,228,1,1225,-1,251,-1,1119,1,112,-1,502,-1,502,1,594,-1,934,1
};
bool check(int v){
if(v%7==0) return true;
while(v){
if(v%10==7) return true;
v/=10;
}
return false;
}
int main(){
int n; cin>>n;
int y=1337, x=1;
if(n>=len){
y=table[n/len*2-1], x=table[n/len*2];
}
int last=n%len;
int tot=n/len*len;
for(int i=0; i<last; i++){
++tot;
if(y==1337 && x==1) y=1;
else if(y==1 && x==-1) y=1337;
else y+=x;
if(check(tot)) x=-x;
}
cout<<y<<endl;
return 0;
}