| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8/11 | O | O | . | O | . | . | O | Ø | O | O | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：2014-2015 neerc-northern-subregional-contest
A Alarm Clock
题目描述
用火柴棒拼出合法时间。
解题思路
爆搜即可。
AC代码
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
typedef long long ll;
using namespace std;
int a[14][14]={{1},{4,7},{2,3,5},{0,6,9},{8},{7}};
int cnt[15]={1,2,3,3,1,1};
int num[15]={2,4,5,6,7,3};
int seq[15];
void dfs(int x,int nu){
if(nu<0)return;
if(!x){
if(nu)return;
if(seq[1]*10+seq[2]<24&&seq[3]*10+seq[4]<60){
printf("%d%d:%d%d",seq[1],seq[2],seq[3],seq[4]);
exit(0);
}
return;
}
int i,j;
for(i=0;i<6;i++){
for(j=0;j<cnt[i];j++){
seq[x]=a[i][j];
dfs(x-1,nu-num[i]);
}
}
}
void solve(int x){
dfs(4,x);
printf("Impossible");
}
int main(){
freopen("alarm.in","r",stdin);
freopen("alarm.out","w",stdout);
int n;
scanf("%d",&n);
solve(n);
return 0;
}
B Buffcraft
题目描述
选$k$个$a_i$中的元素，$l$个$b_i$中的元素，要求$0\leq k+l\leq m$，最大化$(\sum_{i=1}^{k}a_{x_k})\times (d+\sum_{i=1}^{l}b_{y_l})$。
解题思路
排完序枚举即可。
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 50000 + 10;
pair<int, int> dir[ms], per[ms];
ll sd[ms], sp[ms];
int main()
{
freopen("buffcraft.in", "r", stdin);
freopen("buffcraft.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int b, k, n, m;
cin >> b >> k >> n >> m;
//b *= 100;
for (int i = 0; i < n; ++i)
{
cin >> dir[i].first;
dir[i].second = i + 1;
//dir[i].first *= 100;
}
for (int i = 0; i < m; ++i)
{
cin >> per[i].first;
per[i].second = i + 1;
}
sort(dir, dir + n, greater<>());
sort(per, per + m, greater<>());
for (int i = 1; i <= n; ++i)
{
sd[i] = sd[i - 1] + dir[i - 1].first;
}
for (int i = 1; i <= m; ++i)
{
sp[i] = sp[i - 1] + per[i - 1].first;
}
ll mx = 0; int mi = 0;
for (int i = 0; i <= k && i <= n; ++i)
{
ll t = 1ll * (b + sd[i])*(100 + sp[min(m, k - i)]);
if (t > mx)
{
mx = t;
mi = i;
}
}
cout << mi << " " << min(m, k - mi) << "\n";
for (int i = 0; i < mi; ++i)
{
cout << dir[i].second << ' ';
}
cout << '\n';
mi = min(m, k - mi);
for (int i = 0; i < mi; ++i)
{
cout << per[i].second << ' ';
}
}
C Combinator Expression
题目描述
解题思路
AC代码
2
D Digits
题目描述
问$n$个数位和相等的数，最小化它们的和，这个数位和应该为多少。
解题思路
暴力枚举，记录下每个数位和出现的次数，打表即可。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
typedef long long ll;
int main()
{
freopen("digits.in","r",stdin);
freopen("digits.out","w",stdout);
ll ans[]={0,1,11,33,66,110,165,231,308,396,495,603,720,846,981,1125,1278,1440,1611,1791,1998,2214,2439,2673,2916,3168,3429,3699,4005,4320,4644,4977,5319,5670,6030,6435,6849,7272,7704,8139,8572,9014,9465,9925,10430,10944,11467,11999,12540,13090,13694,14307,14929,15560,16200,16903,17615,18336,19066,19868,20613,21344,22084,22887,23699,24520,25350,26252,27163,28083,29102,30130,31167,32213,33268,34332,35405,36487,37578,38687,39804,40896,42015,43143,44280,45426,46581,47745,48918,50100,51291,52500,53718,54945,56181,57426,58680,59943,61215,62496,63786,65094,66411,67737,69072,70416,71769,73131,74502,75882,77289,78705,80130,81564,83007,84459,85920,87390,88896,90411,91935,93468,95010,96561,98121,99726,101340,102963,104595,106236,107886,109590,111303,113025,114756,116496,118299,120111,121932,123762,125664,127575,129495,131514,133542,135579,137625,139557,141487,143516,145554,147601,149657,151722,153796,155879,157971,160090,162218,164355,166501,168656,170820,172993,175175,177366,179575,181793,184020,186256,188501,190755,193018,195290,197571,199861,202169,204486,206812,209147,211491,213844,216206,218577,220957,223364,225780,228205,230639,233082,235534,237995,240465,242971,245486,248010,250543,253085,255636,258196,260801,263415,266038,268670,271311,273961,276665,279378,282100,284831,287571,290374,293186,296007,298837,301739,304650,307570,310589,313617,316654,319700,322755,325819,328892,331974,335065,338174,341292,344419,347555,350700,353854,357017,360189,363370,366560,369768,372985,376211,379446,382690,385943,389205,392476,395756,399063,402379,405704,409038,412381,415733,419094,422464,425870,429285,432709,436142,439584,443035,446495,450000,453514,457037,460569,464110,467660,471264,474821,478336,481860,485393,488935,492486,496046,499651,503265,506888,510520,514161,517811,521515,525228,528950,532681,536421,540224,544036,547857,551687,555589,559500,563420,567439,571467,575504,579550,583605,587669,591742,595824,599915,604024,608142,612269,616405,620550,624704,628867,633039,637220,641410,645618,649835,654061,658296,662540,666793,671055,675326,679606,683913,688229,692554,696888,701231,705583,709944,714314,718720,723135,727559,731992,736434,740885,745345,749850,754364,758887,763419,767960,772510,777114,781727,786349,790980,795620,800323,805035,809756,814486,819288,824099,828919,833820,838730,843739,848757,853784,858820,863865,868919,873982,879054,884135,889225,894333,899450,904576,909711,914855,920008,925170,930341,935521,940728,945944,951169,956403,961646,966898,972159,977429,982735,988050,993374,998707,1004049,1009400,1014760,1020165,1025579,1031002,1036434,1041875,1047325,1052829,1058342,1063864,1069395,1074935,1080538,1086150,1091771,1097401,1103103,1108814,1114534,1120335,1126145,1131879,1137402,1142934,1148475,1154025,1159629,1165242,1170864,1176495,1182135,1187838,1193550,1199271,1205001,1210803,1216614,1222434,1228335,1234245,1240254,1246272,1252299,1258335,1264380,1270434,1276497,1282569,1288650,1294740,1300848,1306965,1313091,1319226,1325370,1331523,1337685,1343856,1350036,1356243,1362459,1368684,1374918,1381161,1387413,1393674,1399944,1406250,1412565,1418889,1425222,1431564,1437915,1444275,1450680,1457094,1463517,1469949,1476390,1482840,1489344,1495857,1502379,1508910,1515450,1522053,1528665,1535286,1541916,1548618,1555329,1562049,1568850,1575660,1582560,1589568,1596585,1603611,1610646,1617690,1624743,1631805,1638876,1645956,1653063,1660179,1667304,1674438,1681581,1688733,1695894,1703064,1710270,1717485,1724709,1731942,1739184,1746435,1753695,1761000,1768314,1775637,1782969,1790310,1797660,1805064,1812477,1819899,1827330,1834770,1842273,1849785,1857306,1864836,1872438,1880049,1887669,1895370,1903080,1910880,1918887,1926903,1934928,1942962,1951005,1959057,1967118,1975188,1983294,1991409,1999533,2007666,2015808,2023959,2032119,2040324,2048538,2056761,2064993,2073234,2081484,2089788,2098101,2106408,2114416,2122433,2130459,2138494,2146538,2154591,2162653,2170724,2178804,2186911,2195027,2203152,2211286,2219429,2227581,2235742,2243912,2252118,2260333,2268557,2276790,2285032,2293283,2301543,2309848,2318162,2326485,2334817,2343158,2351508,2359912,2368325,2376747,2385178,2393618,2402121,2410633,2419154,2427684,2436286,2444897,2453517,2462218,2470928,2479728,2488735,2497751,2506776,2515810,2524853,2533905,2542966,2552036,2561142,2570257,2579381,2588514,2597656,2606807,2615967,2625172,2634386,2643609,2652841,2662082,2671332,2680636,2689949,2699271,2708602,2717942,2727345,2736757,2746178,2755608,2765110,2774621,2784141,2793742,2803352,2813052,2823121,2833199,2843286,2853382,2863541,2873709,2883886,2894072,2904267,2914516,2924774,2935041,2945317,2955602,2965896,2976235,2986583,2996940,3007306,3017681,3028065,3038458,3048887,3059325,3069772,3080228,3090693,3101167,3111650,3122142,3132661,3143189,3153726,3164272,3174827,3185391,3195964,3206546,3217137,3227746,3238364,3248991,3259627,3270272,3280926,3291589,3302261,3312942,3323632,3334340,3345057,3355783,3366518,3377262,3388015,3398777,3409548,3420328,3431135,3441951,3452776,3463610,3474453,3485305,3496166,3507036,3517942,3528857,3539781,3550714,3561656,3572607,3583567,3594626,3605694,3616771,3627857,3638952,3650101,3661259,3672426,3683602,3694787,3705981,3717220,3728468,3739725,3750991,3762266,3773550,3784843,3796172,3807510,3818857,3830213,3841578,3852952,3864335,3875727,3887146,3898574,3910011,3921457,3932912,3944376,3955849,3967331,3978822,3990331,4001849,4013376,4024912,4036457,4048011,4059574,4071146,4082727,4094317,4105925,4117476,4128923,4140379,4151844,4163318,4174801,4186293,4197812,4209340,4220877,4232423,4243978,4255542,4267115,4278697,4290288,4301897,4313515,4325142,4336778,4348423,4360077,4371740,4383412,4395093,4406783,4418491,4430208,4441934,4453669,4465413,4477166,4488928,4500699,4512479,4524286,4536102,4547927,4559761,4571604,4583456,4595317,4607187,4619093,4631008,4642932,4654865,4666807,4678758,4690718,4702777,4714845,4726922,4739008,4751103,4763252,4775410,4787577,4799753,4811938,4824132,4836371,4848619,4860876,4873142,4885417,4897701,4909994,4922323,4934661,4947008,4959364,4971729,4984103,4996486,5008878,5021297,5033725,5046162,5058608,5071063,5083527,5096000,5108482,5120973,5133482,5146000,5158527,5171063,5183608,5196162,5208725,5221297,5233878,5246468,5259076,5271693,5284319,5296954,5309598,5322251,5334913,5347584,5360264,5372971,5385687,5398412,5411146,5423889,5436641,5449402,5462172,5474978,5487793,5500617,5513450,5526292,5539143,5552003,5564908,5577822,5590745,5603677,5616618,5629568,5642617,5655675,5668742,5681818,5694903,5707997,5721136,5734284,5747441,5760607,5773782,5786966,5800159,5813388,5826626,5839873,5853129,5866394,5879668,5892951,5906243,5919562,5932890,5946227,5959573,5972928,5986292,5999665,6013047,6026438,6039847,6053265,6066692,6080128,6093573,6107027,6120490,6133962,6147443,6160933,6174441,6187958,6201484,6215019,6228563,6242116,6255678,6269249,6282829,6296436,6310052,6323677,6337311,6350954,6364606,6378267,6391937,6405643,6419358,6433082,6446815,6460557,6474308,6488068,6501873,6515687,6529510,6543342,6557183,6571033,6584937,6598850,6612772,6626703,6640643,6654682,6668730,6682787,6696853,6710928,6725012,6739105,6753234,6767372,6781519,6795675,6809840,6824014,6838197,6852389,6866608,6880836,6895073,6909319,6923574,6937838,6952111,6966393,6980684,6994993,7009311,7023638,7037974,7052319,7066673,7081036,7095408,7109789,7124179,7138587,7153004,7167430,7181865,7196309,7210762,7225224,7239695,7254175,7268682,7283198,7297723,7312257,7326800,7341352,7355913,7370483,7385089,7399704,7414328,7428961,7443603,7458254,7472914,7487619,7502333,7517056,7531788,7546529,7561279,7576083,7590896,7605718,7620549,7635389,7650292,7665204,7680125,7695055,7710084,7725122,7740169,7755225,7770290,7785364,7800447,7815539,7830658,7845786,7860923,7876069,7891224,7906388,7921561,7936743,7951934,7967143,7982361,7997588,8012824,8028069,8043323,8058586,8073858,8089139,8104429,8119737,8135054,8150380,8165715,8181059,8196412,8211774,8227145,8242525,8257932,8273348,8288773,8304207,8319650,8335102,8350563,8366033,8381539,8397054,8412578,8428111,8443653,8459204,8474764,8490369,8505983,8521606,8537238,8552879,8568529,8584233,8599946,8615668,8631399,8647139,8662942,8678754,8694575,8710405,8726307,8742218,8758138,8774157,8790185,8806222,8822268,8838323,8854387,8870460,8886542,8902633,8918742,8934860,8950987,8967123,8983268,8999422,9015585,9031757,9047938,9064128,9080336,9096553,9112779,9129014,9145258,9161511,9177773,9194044,9210324,9226631,9242947,9259272,9275606,9291949,9308301,9324662,9341032,9357438,9373853,9390277,9406710,9423152,9439603,9456063,9472568,9489082,9505605,9522137,9538678,9555228,9571832,9588445,9605067,9621698,9638338,9655041,9671753,9688474,9705204,9722006,9738817,9755637,9772538,9789448,9806457,9823475,9840502,9857538,9874583,9891637,9908700,9925772,9942853,9959943,9977051,9994168,10011294,10028429,10045573,10062726,10079888,10097059,10114239,10131446,10148662,10165887,10183121,10200364,10217616,10234877,10252147,10269453,10286768,10304092,10321425,10338767,10356118,10373478,10390883,10408297,10425720,10443152,10460593,10478043,10495547,10513060,10530582,10548113,10565653,10583256,10600868,10618489,10636119,10653821,10671532,10689252,10707053,10724863,10742763,10760771,10778788,10796814,10814849,10832893,10850946,10869008,10887079,10905159,10923266,10941382,10959507,10977641,10995784,11013936,11032097,11050267,11068473,11086688,11104912,11123145,11141387,11159638,11177898,11196203,11214517,11232840,11251172,11269513,11287863,11306267,11324680,11343102,11361533,11379973,11398476,11416988,11435509,11454039,11472641,11491252,11509872,11528573,11547283,11566083,11585090,11604106,11623131,11642165,11661208,11680260,11699321,11718391,11737497,11756612,11775736,11794869,11814011,11833162,11852322,11871527,11890741,11909964,11929196,11948437,11967687,11986991,12006304,12025626,12044957,12064297,12083700,12103112,12122533,12141963,12161465,12180976,12200496,12220097,12239707,12259407,12279476,12299554,12319641,12339737,12359896,12380064,12400241,12420427,12440622,12460871,12481129,12501396,12521672,12541957,12562251,12582590,12602938,12623295,12643661,12664036,12684420,12704813,12725242,12745680,12766127,12786583,12807048,12827522,12848005,12868497,12889016,12909544,12930081,12950627,12971182,12991746,13012319,13032901,13053492,13074101,13094719,13115346,13135982,13156627,13177281,13197944,13218616,13239297,13259987,13280695,13301412,13322138,13342873,13363617,13384370,13405132,13425903,13446683,13467490,13488306,13509131,13529965,13550808,13571660,13592521,13613391,13634297,13655212,13676136,13697069,13718011,13738962,13759922,13780981,13802049,13823126,13844212,13865307,13886456,13907614,13928781,13949957,13971142,13992336,14013575,14034823,14056080,14077346,14098621,14119905,14141198,14162527,14183865,14205212,14226568,14247933,14269307,14290690,14312082,14333501,14354929,14376366,14397812,14419267,14440731,14462204,14483686,14505177,14526686,14548204,14569731,14591267,14612812,14634366,14655929,14677501,14699082,14720672,14742280,14763897,14785523,14807158,14828802,14850455,14872117,14893788,14915468,14937175,14958891,14980616,15002350,15024093,15045845,15067606,15089376,15111182,15132997,15154821,15176654,15198496,15220347,15242207,15264112,15286026,15307949,15329881,15351822,15373772,15395821,15417879,15439946,15462022,15484107,15506201,15528340,15550488,15572645,15594811,15616986,15639170,15661363,15683592,15705830,15728077,15750333,15772598,15794872,15817155,15839447,15861766,15884094,15906431,15928758,15950673,15972597,15994530,16016472,16038423,16060383,16082442,16104510,16126587,16148673,16170768,16192917,16215075,16237242,16259418,16281603,16303797,16326036,16348284,16370541,16392807,16415082,16437366,16459659,16481988,16504326,16526673,16549029,16571394,16593768,16616151,16638543,16660962,16683390,16705827,16728273,16750728,16773192,16795665,16818147,16840638,16863147,16885665,16908192,16930728,16953273,16975827,16998390,17020962,17043543,17066133,17088741,17111358,17133984,17156619,17179263,17201916,17224578,17247249,17269929,17292636,17315352,17338077,17360811,17383554,17406306,17429067,17451837,17474643,17497458,17520282,17543115,17565957,17588808,17611668,17634573,17657487,17680410,17703342,17726283,17749233,17772282,17795340,17818407,17841483,17864568,17887662,17910801,17933949,17957106,17980272,18003447,18026631,18049824,18073053,18096291,18119538,18142794,18166059,18189333,18212616,18235908,18259227,18282555,18305892,18329238,18352593,18375957,18399330,18422712,18446103,18469512,18492930,18516357,18539793,18563238,18586692,18610155,18633627,18657108,18680598,18704106,18727623,18751149,18774684,18798228,18821781,18845343,18868914,18892494,18916101,18939717,18963342,18986976,19010619,19034271,19057932,19081602,19105308,19129023,19152747,19176480,19200222,19223973,19247733,19271538,19295352,19319175,19343007,19366848,19390698,19414602,19438515,19462437,19486368,19510308,19534347,19558395,19582452,19606518,19630593,19654677,19678770,19702899,19727037,19751184,19775340,19799505,19823679,19847862,19872054,19896273,19920501,19944738,19968984,19993239,20017503,20041776,20066058,20090349,20114658,20138976,20163303,20187639,20211984,20236338,20260701,20285073,20309454,20333844,20358252,20382669,20407095,20431530,20455974,20480427,20504889,20529360,20553840,20578347,20602863,20627388,20651922,20676465,20701017,20725578,20750148,20774754,20799369,20823993,20848626,20873268,20897919,20922579,20947284,20971998,20996721,21021453,21046194,21070944,21095748,21120561,21145383,21170214,21195054,21219957,21244869,21269790,21294720,21319749,21344787,21369834,21394890,21419955,21445029,21470112,21495204,21520323,21545451,21570588,21595734,21620889,21646053,21671226,21696408,21721599,21746808,21772026,21797253,21822489,21847734,21872988,21898251,21923523,21948804,21974094,21999402,22024719,22050045,22075380,22100724,22126077,22151439,22176810,22202190,22227597,22253013,22278438,22303872,22329315,22354767,22380228,22405698,22431204,22456719,22482243,22507776,22533318,22558869,22584429,22610034,22635648,22661271,22686903,22712544,22738194,22763898,22789611,22815333,22841064,22866804,22892607,22918419,22944240,22970070,22995972,23021883,23047803,23073822,23099850,23125887,23151933,23177988,23204052,23230125,23256207,23282298,23308407,23334525,23360652,23386788,23412933,23439087,23465250,23491422,23517603,23543793,23570001,23596218,23622444,23648679,23674923,23701176,23727438,23753709,23779989,23806296,23832612,23858937,23885271,23911614,23937966,23964327,23990697,24017103,24043518,24069942,24096375,24122817,24149268,24175728,24202233,24228747,24255270,24281802,24308343,24334893,24361497,24388110,24414732,24441363,24468003,24494706,24521418,24548139,24574869,24601671,24628482,24655302,24682203,24709113,24736122,24763140,24790167,24817203,24844248,24871302,24898365,24925437,24952518,24979608,25006716,25033833,25060959,25088094,25115238,25142391,25169553,25196724,25223904,25251111,25278327,25305552,25332786,25360029,25387281,25414542,25441812,25469118,25496433,25523757,25551090,25578432,25605783,25633143,25660548,25687962,25715385,25742817,25770258,25797708,25825212,25852725,25880247,25907778,25935318,25962921,25990533,26018154,26045784,26073486,26101197,26128917,26156718,26184528,26212428,26240436,26268453,26296479,26324514,26352558,26380611,26408673,26436744,26464824,26492931,26521047,26549172,26577306,26605449,26633601,26661762,26689932,26718138,26746353,26774577,26802810,26831052,26859303,26887563,26915868,26944182,26972505,27000837,27029178,27057528,27085932,27114345,27142767,27171198,27199638,27228141,27256653,27285174,27313704,27342306,27370917,27399537,27428238,27456948,27485748,27514755,27543771,27572796,27601830,27630873,27659925,27688986,27718056,27747162,27776277,27805401,27834534,27863676,27892827,27921987,27951192,27980406,28009629,28038861,28068102,28097352,28126656,28155969,28185291,28214622,28243962,28273365,28302777,28332198,28361628,28391130,28420641,28450161,28479762,28509372,28539072,28569141,28599219,28629306,28659402,28689561,28719729,28749906,28780092,28810287,28840536,28870794,28901061,28931337,28961622,28991916,29022255,29052603,29082960,29113326,29143701,29174085,29204478,29234907,29265345,29295792,29326248,29356713,29387187,29417670,29448162,29478681,29509209,29539746,29570292,29600847,29631411,29661984,29692566,29723157,29753766,29784384,29815011,29845647,29876292,29906946,29937609,29968281,29998962,30029652,30060360,30091077,30121803,30152538,30183282,30214035,30244797,30275568,30306348,30337155,30367971,30398796,30429630,30460473,30491325,30522186,30553056,30583962,30614877,30645801,30676734,30707676,30738627,30769587,30800646,30831714,30862791,30893877,30924972,30956121,30987279,31018446,31049622,31080807,31112001,31143240,31174488,31205745,31237011,31268286,31299570,31330863,31362192,31393530,31424877,31456233,31487598,31518972,31550355,31581747,31613166,31644594,31676031,31707477,31738932,31770396,31801869,31833351,31864842,31896351,31927869,31959396,31990932,32022477,32054031,32085594,32117166,32148747,32180337,32211945,32243562,32275188,32306823,32338467,32370120,32401782,32433453,32465133,32496840,32528556,32560281,32592015,32623758,32655510,32687271,32719041,32750847,32782662,32814486,32846319,32878161,32910012,32941872,32973777,33005691,33037614,33069546,33101487,33133437,33165486,33197544,33229611,33261687,33293772,33325866,33358005,33390153,33422310,33454476,33486651,33518835,33551028,33583257,33615495,33647742,33679998,33712263,33744537,33776820,33809112,33841431,33873759,33906096,33938442,33970797,34003161,34035534,34067916,34100307,34132716,34165134,34197561,34229997,34262442,34294896,34327359,34359831,34392312,34424802,34457310,34489827,34522353,34554888,34587432,34619985,34652547,34685118,34717698,34750305,34782921,34815546,34848180,34880823,34913475,34946136,34978806,35011512,35044227,35076951,35109684,35142426,35175177,35207937,35240742,35273556,35306379,35339211,35372052,35404902,35437806,35470719,35503641,35536572,35569512,35602551,35635599,35668656,35701722,35734797,35767881,35800974,35834103,35867241,35900388,35933544,35966709,35999883,36033066,36066258,36099477,36132705,36165942,36199188,36232443,36265707,36298980,36332262,36365553,36398862,36432180,36465507,36498843,36532188,36565542,36598905,36632277,36665658,36699048,36732456,36765873,36799299,36832734,36866178,36899631,36933093,36966564,37000044,37033551,37067067,37100592,37134126,37167669,37201221,37234782,37268352,37301958,37335573,37369197,37402830,37436472,37470123,37503783,37537488,37571202,37604925,37638657,37672398,37706148,37739952,37773765,37807587,37841418,37875258,37909161,37943073,37976994,38010924,38044953,38078991,38113038,38147094,38181159,38215233,38249316,38283408,38317527,38351655,38385792,38419938,38454093,38488257,38522430,38556612,38590803,38625012,38659230,38693457,38727693,38761938,38796192,38830455,38864727,38899008,38933298,38967606,39001923,39036249,39070584,39104928,39139281,39173643,39208014,39242394,39276801,39311217,39345642,39380076,39414519,39448971,39483432,39517902,39552408,39586923,39621447,39655980,39690522,39725073,39759633,39794238,39828852,39863475,39898107,39932748,39967398,40002102,40036815,40071537,40106268,40141008,40175811,40210623,40245444,40280274,40315176,40350087,40385007,40420026,40455054,40490091,40525137,40560192,40595256,40630329,40665411,40700502,40735611,40770729,40805856,40840992,40876137,40911291,40946454,40981626,41016807,41051997,41087205,41122422,41157648,41192883,41228127,41263380,41298642,41333913,41369193,41404500,41439816,41475141,41510475,41545818,41581170,41616531,41651901,41687307,41722722,41758146,41793579,41829021,41864472,41899932,41935437,41970951,42006474,42042006,42077547,42113097,42148701,42184314,42219936,42255567,42291207,42326910,42362622,42398343,42434073,42469875,42505686,42541506,42577407,42613317,42649326,42685344,42721371,42757407,42793452,42829506,42865569,42901641,42937722,42973812,43009920,43046037,43082163,43118298,43154442,43190595,43226757,43262928,43299108,43335315,43371531,43407756,43443990,43480233,43516485,43552746,43589016,43625322,43661637,43697961,43734294,43770636,43806987,43843347,43879752,43916166,43952589,43989021,44025462,44061912,44098416,44134929,44171451,44207982,44244522,44281125,44317737,44354358,44390988,44427690,44464401,44501121,44537922,44574732,44611632,44648640,44685657,44722683,44759718,44796762,44833815,44870877,44907948,44945028,44982135,45019251,45056376,45093510,45130653,45167805,45204966,45242136,45279342,45316557,45353781,45391014,45428256,45465507,45502767,45540072,45577386,45614709,45652041,45689382,45726732,45764136,45801549,45838971,45876402,45913842,45951345,45988857,46026378,46063908,46101510,46139121,46176741,46214442,46252152,46289952,46327959,46365975,46404000,46442034,46480077,46518129,46556190,46594260,46632366,46670481,46708605,46746738,46784880,46823031,46861191,46899396,46937610,46975833,47014065,47052306,47090556,47128860,47167173,47205495,47243826,47282166,47320569,47358981,47397402,47435832,47474334,47512845,47551365,47589966,47628576,47667276,47706282,47745297,47784321,47823354,47862396,47901447,47940507,47979612,48018726,48057849,48096981,48136122,48175272,48214476,48253689,48292911,48332142,48371382,48410685,48449997,48489318,48528648,48568050,48607461,48646881,48686382,48725892,48765492,48805551,48845619,48885696,48925782,48965877,49006026,49046184,49086351,49126527,49166712,49206906,49247145,49287393,49327650,49367916,49408191,49448475,49488768,49529097,49569435,49609782,49650138,49690503,49730877,49771260,49811652,49852071,49892499,49932936,49973382,50013837,50054301,50094774,50135256,50175747,50216256,50256774,50297301,50337837,50378382,50418936,50459499,50500071,50540652,50581242,50621850,50662467,50703093,50743728,50784372,50825025,50865687,50906358,50947038,50987745,51028461,51069186,51109920,51150663,51191415,51232176,51272946,51313752,51354567,51395391,51436224,51477066,51517917,51558777,51599682,51640596,51681519,51722451,51763392,51804342,51845391,51886449,51927516,51968592,52009677,52050771,52091910,52133058,52174215,52215381,52256556,52297740,52338933,52380162,52421400,52462647,52503903,52545168,52586442,52627725,52669017,52710336,52751664,52793001,52834347,52875702,52917066,52958439,52999821,53041212,53082621,53124039,53165466,53206902,53248347,53289801,53331264,53372736,53414217,53455707,53497215,53538732,53580258,53621793,53663337,53704890,53746452,53788023,53829603,53871210,53912826,53954451,53996085,54037728,54079380,54121041,54162711,54204417,54246132,54287856,54329589,54371331,54413082,54454842,54496647,54538461,54580284,54622116,54663957,54705807,54747711,54789624,54831546,54873477,54915417,54957456,54999504,55041561,55083627,55125702,55167786,55209879,55252008,55294146,55336293,55378449,55420614,55462788,55504971,55547163,55589382,55631610,55673847,55716093,55758348,55800612,55842885,55885167,55927458,55969767,56012085,56054412,56096748,56139093,56181447,56223810,56266182,56308563,56350953,56393361,56435778,56478204,56520639,56563083,56605536,56647998,56690469,56732949,56775456,56817972,56860497,56903031,56945574,56988126,57030687,57073257,57115863,57158478,57201102,57243735,57286377,57329028,57371688,57414393,57457107,57499830,57542562,57585303,57628053,57670857,57713670,57756492,57799323,57842163,57885066,57927978,57970899,58013829,58056858,58099896,58142943,58185999,58229064,58272138,58315221,58358313,58400727,58442983,58485248,58527522,58569805,58612097,58654416,58696744,58739081,58781427,58823782,58866146,58908519,58950901,58993292,59035701,59078119,59120546,59162982,59205427,59247881,59290344,59332816,59375297,59417787,59460295,59502812,59545338,59587873,59630417,59672970,59715532,59758103,59800683,59843290,59885906,59928531,59971165,60013808,60056460,60099121,60141791,60184497,60227212,60269936,60312669,60355411,60398162,60440922,60483727,60526541,60569364,60612196,60655037,60697887,60740791,60783704,60826626,60869557,60912497,60955536,60998584,61041641,61084707,61127782,61170866,61213959,61257088,61300226,61343373,61386529,61429694,61472868,61516051,61559243,61602462,61645690,61688927,61732173,61775428,61818692,61861965,61905247,61948538,61991847,62035165,62078492,62121828,62165173,62208527,62251890,62295262,62338643,62382033,62425441,62468858,62512284,62555719,62599163,62642616,62686078,62729549,62773029,62816536,62860052,62903577,62947111,62990654,63034206,63077767,63121337,63164943,63208558,63252182,63295815,63339457,63383108,63426768,63470473,63514187,63557910,63601642,63645383,63689133,63732937,63776750,63820572,63864403,63908243,63952146,63996058,64039979,64083909,64127938,64171976,64216023,64260079,64304144,64348218,64392301,64436393,64480512,64524640,64568777,64612923,64657078,64701242,64745415,64789597,64833788,64877997,64922215,64966442,65010678,65054923,65099177,65143440,65187712,65231993,65276283,65320591,65364908,65409234,65453569,65497913,65542266,65586628,65630999,65675379,65719786,65764202,65808627,65853061,65897504,65941956,65986417,66030887,66075393,66119908,66164432,66208965,66253507,66298058,66342618,66387223,66431837,66476460,66521092,66565733,66610383,66655087,66699800,66744522,66789253,66833993,66878796,66923608,66968429,67013259,67058161,67103072,67147992,67193011,67238039,67283076,67328122,67373177,67418241,67463314,67508396,67553487,67598596,67643714,67688841,67733977,67779122,67824276,67869439,67914611,67959792,68004982,68050190,68095407,68140633,68185868,68231112,68276365,68321627,68366898,68412178,68457485,68502801,68548126,68593460,68638803,68684155,68729516,68774886,68820292,68865707,68911131,68956564,69002006,69047457,69092917,69138422,69183936,69229459,69274991,69320532,69366082,69411686,69457299,69502921,69548552,69594192,69639895,69685607,69731328,69777058,69822860,69868671,69914491,69960392,70006302,70052311,70098329,70144356,70190392,70236437,70282491,70328554,70374626,70420707,70466797,70512905,70559022,70605148,70651283,70697427,70743580,70789742,70835913,70882093,70928300,70974516,71020741,71066975,71113218,71159470,71205731,71252001,71298307,71344622,71390946,71437279,71483621,71529972,71576332,71622737,71669151,71715574,71762006,71808447,71854897,71901401,71947914,71994436,72040967,72087507,72134110,72180722,72227343,72273973,72320675,72367386,72414106,72460907,72507717,72554617,72601625,72648642,72695668,72742703,72789747,72836800,72883862,72930933,72978013,73025120,73072236,73119361,73166495,73213638,73260790,73307951,73355121,73402327,73449542,73496766,73543999,73591241,73638492,73685752,73733057,73780371,73827694,73875026,73922367,73969717,74017121,74064534,74111956,74159387,74206827,74254330,74301842,74349363,74396893,74444495,74492106,74539726,74587427,74635137,74682937,74730944,74778960,74826985,74875019,74923062,74971114,75019175,75067245,75115351,75163466,75211590,75259723,75307865,75356016,75404176,75452381,75500595,75548818,75597050,75645291,75693541,75741845,75790158,75838480,75886811,75935151,75983554,76031966,76080387,76128817,76177319,76225830,76274350,76322951,76371561,76420261,76469267,76518282,76567306,76616339,76665381,76714432,76763492,76812597,76861711,76910834,76959966,77009107,77058257,77107461,77156674,77205896,77255127,77304367,77353670,77402982,77452303,77501633,77551035,77600446,77649866,77699367,77748877,77798477,77848536,77898604,77948681,77998767,78048862,78099011,78149169,78199336,78249512,78299697,78349891,78400130,78450378,78500635,78550901,78601176,78651460,78701753,78752082,78802420,78852767,78903123,78953488,79003862,79054245,79104637,79155056,79205484,79255921,79306367,79356822,79407286,79457759,79508241,79558732,79609241,79659759,79710286,79760822,79811367,79861921,79912484,79963056,80013637,80064227,80114835,80165452,80216078,80266713,80317357,80368010,80418672,80469343,80520023,80570730,80621446,80672171,80722905,80773648,80824400,80875161,80925931,80976737,81027552,81078376,81129209,81180051,81230902,81281762,81332667,81383581,81434504,81485436,81536377,81587327,81638376,81689434,81740501,81791577,81842662,81893756,81944895,81996043,82047200,82098366,82149541,82200725,82251918,82303147,82354385,82405632,82456888,82508153,82559427,82610710,82662002,82713321,82764649,82815986,82867332,82918687,82970051,83021424,83072806,83124197,83175606,83227024,83278451,83329887,83381332,83432786,83484249,83535721,83587202,83638692,83690200,83741717,83793243,83844778,83896322,83947875,83999437,84051008,84102588,84154195,84205811,84257436,84309070,84360713,84412365,84464026,84515696,84567402,84619117,84670841,84722574,84774316,84826067,84877827,84929632,84981446,85033269,85085101,85136942,85188792,85240696,85292609,85344531,85396462,85448402,85500441,85552489,85604546,85656612,85708687,85760771,85812864,85864993,85917131,85969278,86021434,86073599,86125773,86177956,86230148,86282367,86334595,86386832,86439078,86491333,86543597,86595870,86648152,86700443,86752752,86805070,86857397,86909733,86962078,87014432,87066795,87119167,87171548,87223938,87276346,87328763,87381189,87433624,87486068,87538521,87590983,87643454,87695934,87748441,87800957,87853482,87906016,87958559,88011111,88063672,88116242,88168848,88221463,88274087,88326720,88379362,88432013,88484673,88537378,88590092,88642815,88695547,88748288,88801038,88853842,88906655,88959477,89012308,89065148,89118051,89170963,89223884,89276814,89329843,89382881,89435928,89488984,89542049,89595123,89648206,89701298,89754417,89807545,89860682,89913828,89966983,90020147,90073320,90126502,90179693,90232902,90286120,90339347,90392583,90445828,90499082,90552345,90605617,90658898,90712188,90765496,90818813,90872139,90925474,90978818,91032171,91085533,91138904,91192284,91245691,91299107,91352532,91405966,91459409,91512861,91566322,91619792,91673298,91726813,91780337,91833870,91887412,91940963,91994523,92048128,92101742,92155365,92208997,92262638,92316288,92369992,92423705,92477427,92531158,92584898,92638701,92692513,92746334,92800164,92854066,92907977,92961897,93015916,93069944,93123981,93178027,93232082,93286146,93340219,93394301,93448392,93502501,93556619,93610746,93664882,93719027,93773181,93827344,93881516,93935697,93989887,94044095,94098312,94152538,94206773,94261017,94315270,94369532,94423803,94478083,94532390,94586706,94641031,94695365,94749708,94804060,94858421,94912791,94967197,95021612,95076036,95130469,95184911,95239362,95293822,95348327,95402841,95457364,95511896,95566437,95620987,95675591,95730204,95784826,95839457,95894097,95948800,96003512,96058233,96112963,96167765,96222576,96277396,96332297,96387207,96442216,96497234,96552261,96607297,96662342,96717396,96772459,96827531,96882612,96937702,96992810,97047927,97103053,97158188,97213332,97268485,97323647,97378818,97433998,97489205,97544421,97599646,97654880,97710123,97765375,97820636,97875906,97931212,97986527,98041851,98097184,98152526,98207877,98263237,98318642,98374056,98429479,98484911,98540352,98595802,98651306,98706819,98762341,98817872,98873412,98929015,98984627,99040248,99095878,99151580,99207291,99263011,99318812,99374622,99430522,99486530,99542547,99598573,99654608,99710652,99766705,99822767,99878838,99934918,99991025,100047141,100103266,100159400,100215543,100271695,100327856,100384026,100440232,100496447,100552671,100608904,100665146,100721397,100777657,100833962,100890276,100946599,101002931,101059272,101115622,101172026,101228439,101284861,101341292,101397732,101454235,101510747,101567268,101623798,101680400,101737011,101793631,101850332,101907042,101963842,102020849,102077865,102134890,102191924,102248967,102306019,102363080,102420150,102477256,102534371,102591495,102648628,102705770,102762921,102820081,102877286,102934500,102991723,103048955,103106196,103163446,103220750,103278063,103335385,103392716,103450056,103507459,103564871,103622292,103679722,103737224,103794735,103852255,103909856,103967466,104025166,104083172,104141187,104199211,104257244,104315286,104373337,104431397,104489502,104547616,104605739,104663871,104722012,104780162,104838366,104896579,104954801,105013032,105071272,105129575,105187887,105246208,105304538,105362940,105421351,105479771,105538272,105596782,105655382,105714387,105773401,105832424,105891456,105950497,106009547,106068651,106127764,106186886,106246017,106305157,106364360,106423572,106482793,106542023,106601325,106660636,106719956,106779357,106838767,106898267,106958316,107018374,107078441,107138517,107198602,107258696,107318835,107378983,107439140,107499306,107559481,107619665,107679858,107740087,107800325,107860572,107920828,107981093,108041367,108101650,108161942,108222261,108282589,108342926,108403272,108463627,108523991,108584364,108644746,108705137,108765546,108825964,108886391,108946827,109007272,109067726,109128189,109188661,109249142,109309632,109370140,109430657,109491183,109551718,109612262,109672815,109733377,109793948,109854528,109915135,109975751,110036376,110097010,110157653,110218305,110278966,110339636,110400342,110461057,110521781,110582514,110643256,110704007,110764767,110825572,110886386,110947209,111008041,111068882,111129732,111190636,111251549,111312471,111373402,111434342,111495381,111556429,111617486,111678552,111739627,111800711,111861804,111922933,111984071,112045218,112106374,112167539,112228713,112289896,112351088,112412307,112473535,112534772,112596018,112657273,112718537,112779810,112841092,112902383,112963692,113025010,113086337,113147673,113209018,113270372,113331735,113393107,113454488,113515878,113577286,113638703,113700129,113761564,113823008,113884461,113945923,114007394,114068874,114130381,114191897,114253422,114314956,114376499,114438051,114499612,114561182,114622788,114684403,114746027,114807660,114869302,114930953,114992613,115054318,115116032,115177755,115239487,115301228,115362978,115424782,115486595,115548417,115610248,115672088,115733991,115795903,115857824,115919754,115981783,116043821,116105868,116167924,116229989,116292063,116354146,116416238,116478357,116540485,116602622,116664768,116726923,116789087,116851260,116913442,116975633,117037842,117100060,117162287,117224523,117286768,117349022,117411285,117473557,117535838,117598128,117660436,117722753,117785079,117847414,117909758,117972111,118034473,118096844,118159224,118221631,118284047,118346472,118408906,118471349,118533801,118596262,118658732,118721238,118783753,118846277,118908810,118971352,119033903,119096463,119159068,119221682,119284305,119346937,119409578,119472228,119534932,119597645,119660367,119723098,119785838,119848641,119911453,119974274,120037104,120100006,120162917,120225837,120288856,120351884,120414921,120477967,120541022,120604086,120667159,120730241,120793332,120856441,120919559,120982686,121045822,121108967,121172121,121235284,121298456,121361637,121424827,121488035,121551252,121614478,121677713,121740957,121804210,121867472,121930743,121994023,122057330,122120646,122183971,122247305,122310648,122374000,122437361,122500731,122564137,122627552,122690976,122754409,122817851,122881302,122944762,123008267,123071781,123135304,123198836,123262377,123325927,123389531,123453144,123516766,123580397,123644037,123707740,123771452,123835173,123898903,123962705,124026516,124090336,124154237,124218147,124282156,124346174,124410201,124474237,124538282,124602336,124666399,124730471,124794552,124858642,124922750,124986867,125050993,125115128,125179272,125243425,125307587,125371758,125435938,125500145,125564361,125628586,125692820,125757063,125821315,125885576,125949846,126014152,126078467,126142791,126207124,126271466,126335817,126400177,126464582,126528996,126593419,126657851,126722292,126786742,126851246,126915759,126980281,127044812,127109352,127173955,127238567,127303188,127367818,127432520,127497231,127561951,127626752,127691562,127756462,127821470,127886487,127951513,128016548,128081592,128146645,128211707,128276778,128341858,128406965,128472081,128537206,128602340,128667483,128732635,128797796,128862966,128928172,128993387,129058611,129123844,129189086,129254337,129319597,129384902,129450216,129515539,129580871,129646212,129711562,129776966,129842379,129907801,129973232,130038672,130104175,130169687,130235208,130300738,130366340,130431951,130497571,130563272,130628982,130694782,130760789,130826805,130892830,130958864,131024907,131090959,131157020,131223090,131289196,131355311,131421435,131487568,131553710,131619861,131686021,131752226,131818440,131884663,131950895,132017136,132083386,132149690,132216003,132282325,132348656,132414996,132481399,132547811,132614232,132680662,132747164,132813675,132880195,132946796,133013406,133080106,133147112,133214127,133281151,133348184,133415226,133482277,133549337,133616442,133683556,133750679,133817811,133884952,133952102,134019306,134086519,134153741,134220972,134288212,134355515,134422827,134490148,134557478,134624880,134692291,134759711,134827212,134894722,134962322,135030327,135098341,135166364,135234396,135302437,135370487,135438591,135506704,135574826,135642957,135711097,135779300,135847512,135915733,135983963,136052265,136120576,136188896,136257297,136325707,136394207,136463211,136532224,136601246,136670277,136739317,136808420,136877532,136946653,137015783,137084985,137154196,137223416,137292717,137362027,137431427,137501466,137571514,137641571,137711637,137781712,137851796,137921889,137992018,138062156,138132303,138202459,138272624,138342798,138412981,138483173,138553392,138623620,138693857,138764103,138834358,138904622,138974895,139045177,139115468,139185777,139256095,139326422,139396758,139467103,139537457,139607820,139678192,139748573,139818963,139889371,139959788,140030214,140100649,140171093,140241546,140312008,140382479,140452959,140523466,140593982,140664507,140735041,140805584,140876136,140946697,141017267,141087873,141158488,141229112,141299745,141370387,141441038,141511698,141580550,141647062,141713583,141780113,141846715,141913326,141979946,142046647,142113357,142180157,142247164,142314180,142381205,142448239,142515282,142582334,142649395,142716465,142783571,142850686,142917810,142984943,143052085,143119236,143186396,143253601,143320815,143388038,143455270,143522511,143589761,143657065,143724378,143791700,143859031,143926371,143993774,144061186,144128607,144196037,144263539,144331050,144398570,144466171,144533781,144601481,144669487,144737502,144805526,144873559,144941601,145009652,145077712,145145817,145213931,145282054,145350186,145418327,145486477,145554681,145622894,145691116,145759347,145827587,145895890,145964202,146032523,146100853,146169255,146237666,146306086,146374587,146443097,146511697,146580702,146649716,146718739,146787771,146856812,146925862,146994966,147064079,147133201,147202332,147271472,147340675,147409887,147479108,147548338,147617640,147686951,147756271,147825672,147895082,147964582,148034631,148104689,148174756,148244832,148314917,148385011,148455150,148525298,148595455,148665621,148735796,148805980,148876173,148946402,149016640,149086887,149157143,149227408,149297682,149367965,149438257,149508576,149578904,149649241,149719587,149789942,149860306,149930679,150001061,150071452,150141861,150212279,150282706,150353142,150423587,150494041,150564504,150634976,150705457,150775947,150846455,150916972,150987498,151058033,151128577,151199130,151269692,151340263,151410843,151481450,151552066,151622691,151693325,151763968,151834620,151905281,151975951,152046657,152117372,152188096,152258829,152329571,152400322,152471082,152541887,152612701,152683524,152754356,152825197,152896047,152966951,153037864,153108786,153179717,153250657,153321696,153392744,153463801,153534867,153605942,153677026,153748119,153819248,153890386,153961533,154032689,154103854,154175028,154246211,154317403,154388622,154459850,154531087,154602333,154673588,154744852,154816125,154887407,154958698,155030007,155101325,155172652,155243988,155315333,155386687,155458050,155529422,155600803,155672193,155743601,155815018,155886444,155957879,156029323,156100776,156172238,156243709,156315189,156386696,156458212,156529737,156601271,156672814,156744366,156815927,156887497,156959103,157030718,157102342,157173975,157245617,157317268,157388928,157460633,157532347,157604070,157675802,157747543,157819293,157891097,157962910,158034732,158106563,158178403,158250306,158322218,158394139,158466069,158538098,158610136,158682183,158754239,158826304,158898378,158970461,159042553,159114672,159186800,159258937,159331083,159403238,159475402,159547575,159619757,159691948,159764157,159836375,159908602,159980838,160053083,160125337,160197600,160269872,160342153,160414443,160486751,160559068,160631394,160703729,160776073,160848426,160920788,160993159,161065539,161137946,161210362,161282787,161355221,161427664,161500116,161572577,161645047,161717553,161790068,161862592,161935125,162007667,162080218,162152778,162225383,162297997,162370620,162443252,162515893,162588543,162661247,162733960,162806682,162879413,162952153,163024956,163097768,163170589,163243419,163316321,163389232,163462152,163535171,163608199,163681236,163754282,163827337,163900401,163973474,164046556,164119647,164192756,164265874,164339001,164412137,164485282,164558436,164631599,164704771,164777952,164851142,164924350,164997567,165070793,165144028,165217272,165290525,165363787,165437058,165510338,165583645,165656961,165730286,165803620,165876963,165950315,166023676,166097046,166170452,166243867,166317291,166390724,166464166,166537617,166611077,166684582,166758096,166831619,166905151,166978692,167052242,167125846,167199459,167273081,167346712,167420352,167494055,167567767,167641488,167715218,167789020,167862831,167936651,168010552,168084462,168158471,168232489,168306516,168380552,168454597,168528651,168602714,168676786,168750867,168824957,168899065,168973182,169047308,169121443,169195587,169269740,169343902,169418073,169492253,169566460,169640676,169714901,169789135,169863378,169937630,170011891,170086161,170160467,170234782,170309106,170383439,170457781,170532132,170606492,170680897,170755311,170829734,170904166,170978607,171053057,171127561,171202074,171276596,171351127,171425667,171500270,171574882,171649503,171724133,171798835,171873546,171948266,172023067,172097877,172172777,172247785,172322802,172397828,172472863,172547907,172622960,172698022,172773093,172848173,172923280,172998396,173073521,173148655,173223798,173298950,173374111,173449281,173524487,173599702,173674926,173750159,173825401,173900652,173975912,174051217,174126531,174201854,174277186,174352527,174427877,174503281,174578694,174654116,174729547,174804987,174880490,174956002,175031523,175107053,175182655,175258266,175333886,175409587,175485297,175561097,175637104,175713120,175789145,175865179,175941222,176017274,176093335,176169405,176245511,176321626,176397750,176473883,176550025,176626176,176702336,176778541,176854755,176930978,177007210,177083451,177159701,177236005,177312318,177388640,177464971,177541311,177617714,177694126,177770547,177846977,177923479,177999990,178076510,178153111,178229721,178306421,178383427,178460442,178537466,178614499,178691541,178768592,178845652,178922757,178999871,179076994,179154126,179231267,179308417,179385621,179462834,179540056,179617287,179694527,179771830,179849142,179926463,180003793,180081195,180158606,180236026,180313527,180391037,180468637,180546642,180624656,180702679,180780711,180858752,180936802,181014906,181093019,181171141,181249272,181327412,181405615,181483827,181562048,181640278,181718580,181796891,181875211,181953612,182032022,182110522,182189526,182268539,182347561,182426592,182505632,182584735,182663847,182742968,182822098,182901300,182980511,183059731,183139032,183218342,183297742,183377781,183457829,183537886,183617952,183698027,183778111,183858204,183938333,184018471,184098618,184178774,184258939,184339113,184419296,184499488,184579707,184659935,184740172,184820418,184900673,184980937,185061210,185141492,185221783,185302092,185382410,185462737,185543073,185623418,185703772,185784135,185864507,185944888,186025278,186105686,186186103,186266529,186346964,186427408,186507861,186588323,186668794,186749274,186829781,186910297,186990822,187071356,187151899,187232451,187313012,187393582,187474188,187554803,187635427,187716060,187796702,187877353,187958013,188038718,188119432,188200155,188280887,188361628,188442378,188523182,188603995,188684817,188765648,188846488,188927391,189008303,189089224,189170154,189251183,189332221,189413268,189494324,189575389,189656463,189737546,189818638,189899757,189980885,190062022,190143168,190224323,190305487,190386660,190467842,190549033,190630242,190711460,190792687,190873923,190955168,191036422,191117685,191198957,191280238,191361528,191442836,191524153,191605479,191686814,191768158,191849511,191930873,192012244,192093624,192175031,192256447,192337872,192419306,192500749,192582201,192663662,192745132,192826638,192908153,192989677,193071210,193152752,193234303,193315863,193397468,193479082,193560705,193642337,193723978,193805628,193887332,193969045};
int n;
cin >> n;
printf("%lld\n",ans[n]);
}
E Expression
题目描述
解题思路
AC代码
2
F Fragmentation
题目描述
解题思路
AC代码
2
G Grave
题目描述
给一个大长方形$A$，$A$里面有个小长方形$B$，再给一个长方形$C$，问$C$能否位于$A$内且位于$B$外。
解题思路
枚举能不能放到四个角上即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
using namespace std;
int x[10],y[10],w,h;
int main(){
int i;
freopen("grave.in","r",stdin);
freopen("grave.out","w",stdout);
for(i=1;i<=4;i++)scanf("%d%d",&x[i],&y[i]);
scanf("%d%d",&w,&h);
if(h<=y[2]-y[1]&&w<=x[2]-x[1]&&(
x[1]+w<=x[3]||y[2]-h>=y[4]||
x[1]+w<=x[3]||y[1]+h<=y[3]||
x[2]-w>=x[4]||y[1]+h<=y[3]||
x[2]-w>=x[4]||y[2]-h>=y[4]
))printf("Yes");
else printf("No");
return 0;
}
H Hiking in the Hills
题目描述
有一些三角形组成一个曲面，在这个曲面上从$A$走到$B$的路径中，最小化最大高度，并输出路径。
解题思路
显然，只经过点的路径是不劣的。于是连成一个图，二分一下最大高度判断连通性即可。最后输出方案广搜一下。
判断$x$是否在某个平面$ABC$内：$S_{ABC}=S_{ABx}+S_{BCx}+S_{ACx}$。叉积也可，但要判断全为正或负。
AC代码
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
122
123
124
125
126
127
128
129
130
131
132
typedef long long ll;
using namespace std;
int tot;
struct Point{
int x,y,z;
bool operator<(const Point&a)const{
if(x<a.x)return 1;
if(x>a.x)return 0;
if(y<a.y)return 1;
if(y>a.y)return 0;
return z<a.z;
}
void in(){
scanf("%d%d%d",&x,&y,&z);
}
}p[N][3],a,b,aft[N<<2];
Point operator-(Point &a,const Point &p){
return (Point){(ll)a.x-p.x,(ll)a.y-p.y,(ll)a.z-p.z};
}
map<Point,int>id;
ll cha(Point a,Point b){
return 1LL*a.x*b.y-1LL*a.y*b.x;
}
struct Edge{
int e,n;
}e[N<<4];
int hd[N<<2],cnt=1;
void adde(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
void add(int a,int b){
adde(a,b);
adde(b,a);
}
int jud(int i,Point x){
if(cha(p[i][1]-p[i][0],x-p[i][0])<0){
if(cha(p[i][2]-p[i][1],x-p[i][1])>0)return 0;
if(cha(p[i][0]-p[i][2],x-p[i][2])>0)return 0;
return 1;
}else{
if(cha(p[i][2]-p[i][1],x-p[i][1])<0)return 0;
if(cha(p[i][0]-p[i][2],x-p[i][2])<0)return 0;
return 1;
}
}
int vis[N<<2];
int dfs(int mx,int now){
int i;
if(aft[now].z>mx)return 0;
vis[now]=1;
if(now==id[b])return 1;
for(i=hd[now];i;i=e[i].n){
int ed=e[i].e;
if(!vis[ed]&&dfs(mx,ed))return 1;
}
return 0;
}
int check(int mx){
memset(vis,0,sizeof(vis));
return dfs(mx,id[a]);
}
int last[N<<2];
int sta[N<<2],top;
void bfs(int ans){
queue<pair<int,int>>Q;
memset(vis,0,sizeof(vis));
memset(last,-1,sizeof(last));
while(!Q.empty())Q.pop();
Q.push(mp(id[a],1));
while(!Q.empty()){
int tp=Q.front().first,step=Q.front().second;Q.pop();
int i;
for(i=hd[tp];i;i=e[i].n){
int q=e[i].e;
if(aft[q].z<=ans&&last[q]==-1&&q!=tp){
Q.push(mp(q,step+1));
last[q]=tp;
if(q==id[b]){
int now=q;
printf("%d\n",step+1);
while(now!=id[a]){
sta[++top]=now;
now=last[now];
}
sta[++top]=id[a];
for(i=top;i;i--)printf("%d %d %d\n",aft[sta[i]].x,aft[sta[i]].y,aft[sta[i]].z);
return;
}
}
}
}
}
int main(){
int i,j,n;
freopen("hiking.in","r",stdin);
freopen("hiking.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++){
for(j=0;j<3;j++){
p[i][j].in();
if(id[p[i][j]]);
else id[p[i][j]]=++tot;
}
}
for(i=1;i<=n;i++){
add(id[p[i][0]],id[p[i][2]]);
add(id[p[i][1]],id[p[i][2]]);
add(id[p[i][0]],id[p[i][1]]);
}
a.in();b.in();
if(!id[a])id[a]=++tot,aft[tot]=a;
if(!id[b])id[b]=++tot,aft[tot]=b;
int Ain=0,Bin=0;
for(i=1;i<=n;i++)if(jud(i,a))Ain=i;
for(i=1;i<=n;i++)if(jud(i,b))Bin=i;
for(i=0;i<3;i++){
add(id[a],id[p[Ain][i]]);
add(id[b],id[p[Bin][i]]);
}
for(i=1;i<=n;i++)for(j=0;j<3;j++)aft[id[p[i][j]]]=p[i][j];
int l=0,r=1000010,ans=1000000;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
bfs(ans);
return 0;
}
I Instruction
题目描述
没看。
解题思路
不知道。
AC代码 - by Mogg
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
using namespace std;
const int ms = 100 + 10;
struct Node
{
int id, s; string name;
};
vector<int> g[ms];
Node nd[ms];
void dfs1(int x)
{
if (!nd[x].name.empty())
{
return;
}
dfs1(g[x][0]);
if (g[x].size() > 1)
{
if (g[x][1] < g[x][0])
{
nd[x].s = 1;
}
dfs1(g[x][1]);
}
}
pair<int, int> tms[50050]; int cnt;
bool dfs(int x, int t, const string &to)
{
if (!nd[x].name.empty())
{
return nd[x].name == to;
}
if (dfs(g[x][0], t + 1, to))
{
if (nd[x].s == 1)
{
nd[x].s = 0;
tms[cnt++] = { t,x };
}
return true;
}
if (g[x].size() > 1)
{
if (dfs(g[x][1], t + 1, to))
{
if (nd[x].s == 0)
{
nd[x].s = 1;
tms[cnt++] = { t,x };
}
return true;
}
}
return false;
}
int main()
{
freopen("instruction.in", "r", stdin);
freopen("instruction.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string s;
int par;
for (int i = 1; i <= n; ++i)
{
cin >> s >> par;
g[par].push_back(i);
if (s == "s")
{
nd[i] = { i,0,"" };
}
else
{
cin >> s;
nd[i] = { i,0,s };
}
}
dfs1(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
int t; string to;
cin >> t >> to;
dfs(1, t + 1, to);
}
sort(tms, tms + cnt);
cout << cnt << "\n";
for (int i = 0; i < cnt; ++i)
{
cout << tms[i].second << " " << tms[i].first << "\n";
}
}
J Joy of flight
题目描述
一段时间有一种风，给定飞机最大速度，问能否在第$k$秒到达终点。
解题思路
开始读错题了，以为是找出最快到达的方案，枚举每一段风，解了一手一元二次方程，然后$WA$掉了。
WA代码
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
typedef long long ll;
using namespace std;
double sx,sy,fx,fy;
double A,B,v;
int n,k,t[N];
double res,wix[N],wiy[N];
int jud(double a,double b,double c){
double delta=b*b-4*a*c;
if(delta>=0){
double x1=(-b+sqrt(delta))/(2*a);
double x2=(-b-sqrt(delta))/(2*a);
if(fabs(a*x1*x1+b*x1+c)<1e-9&&x1>=0&&x1<=1){
res=x1;
return 1;
}
if(fabs(a*x2*x2+b*x2+c)<1e-9&&x2>=0&&x2<=1){
res=x2;
return 1;
}
return 0;
}else return 0;
}
int main(){
int i,j;
scanf("%lf%lf%lf%lf",&sx,&sy,&fx,&fy);
A=fx-sx;B=fy-sy;
scanf("%d%d%lf",&n,&k,&v);
double lstx=0,lsty=0;
double st=0;
for(i=1;i<=n;i++)scanf("%d%lf%lf",&t[i],&wix[i],&wiy[i]);
t[i]=k;
for(i=1;i<=n+1;i++){
double wx,wy;
wx=lstx+wix[i]*(t[i+1]-t[i]);
wy=lsty+wiy[i]*(t[i+1]-t[i]);
double dT=t[i+1]-t[i];
if(jud((wx-lstx)*(wx-lstx)+(wy-lsty)*(wy-lsty)-v*v*dT*dT,2*(lsty-B)*(wy-lsty)+2*(lstx-A)*(wx-lstx)-2*st*v*v*dT,(lstx-A)*(lstx-A)+(lsty-B)*(lsty-B)-st*st*v*v)){
printf("Yes\n");
double tmpx=lstx+res*(wx-lstx),tmpy=lsty+res*(wy-lsty);
double dis=sqrt((A-tmpx)*(A-tmpx)+(B-tmpy)*(B-tmpy));
double rd=v*(st+res*dT);
double theta=atan2(B-tmpy,A-tmpx);
double vx=v*cos(theta),vy=v*sin(theta);
double nowx=0,nowy=0;
int index=0;
double time=st+t[i+1]*res;
double Tx=time*(wix[i]+vx)+lstx;
double Ty=time*(wiy[i]+vy)+lsty;
for(j=1;j<=time;j++){
if(t[index+1]>=j)index++;
nowx+=wix[index]+vx;
nowy+=wiy[index]+vy;
printf("%.10f %.10f\n",sx+nowx,sy+nowy);
}
return 0;
}
st=t[i];
lstx=wx,lsty=wy;
}
puts("No");
return 0;
}
后来搞懂题意之后，这不是签到题吗….直接算出来风的向量走了多少，飞机就冲着这个点到终点的线飞就行了…
AC代码
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
typedef long long ll;
using namespace std;
double sx,sy,fx,fy;
double A,B,v;
int n,k,t[N];
double res,wix[N],wiy[N];
int main(){
int i;
freopen("joy.in","r",stdin);
freopen("joy.out","w",stdout);
scanf("%lf%lf%lf%lf",&sx,&sy,&fx,&fy);
A=fx-sx;B=fy-sy;
scanf("%d%d%lf",&n,&k,&v);
double lstx=0,lsty=0;
for(i=1;i<=n;i++)scanf("%d%lf%lf",&t[i],&wix[i],&wiy[i]);
t[i]=k;
for(i=1;i<=n;i++)lstx+=wix[i]*(t[i+1]-t[i]),lsty+=wiy[i]*(t[i+1]-t[i]);
double dis=sqrt((A-lstx)*(A-lstx)+(B-lsty)*(B-lsty));
if(dis>k*v)return printf("No"),0;
double theta=atan2(B-lsty,A-lstx);
double tx=dis/k*cos(theta),ty=dis/k*sin(theta);
int index=1;
printf("Yes\n");
for(i=1;i<=k;i++){
if(t[index+1]<i)index++;
sx+=tx+wix[index];
sy+=ty+wiy[index];
printf("%.10f %.10f\n",sx,sy);
}
return 0;
}
K Kebab House
题目描述
有$n$个连续的任务，每个任务一共有$t_i$时间，可以摸鱼，但是必须在这时间内至少有$q_i$的时间不摸鱼。还要求不能在连续的$t+1$秒内摸两次鱼，问方案总数。
解题思路
设$f[i][j]$表示总时间到了$i$秒，当前任务下摸了$j$次鱼的方案数。于是转移方程为$f[i][j]=f[i-1][j]+f[i-t-1][j-1]$，等号右边的两个分别表示这次不摸鱼和这次摸鱼的方案数。
相邻的两个任务$I,I+1$，当$i$已经进入$I+1$个任务的时候，所有$I$任务中摸的鱼都可以被无视掉，也即进入第二个任务的时候，$f[i\in I][0]=\sum_{k=0}^{t[I]-q[I]}f[i\in I][k]$。
为了防止$MLE$，需重复利用数组。
AC代码
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
typedef long long ll;
using namespace std;
ll f[255][255],mod=1000000007;
int q[1010],x[1010],w=255;
int main(){
freopen("kebab.in","r",stdin);
freopen("kebab.out","w",stdout);
int i,j,k,mx=0,n,t;
scanf("%d%d",&n,&t);t++;
for(i=1;i<=n;i++)scanf("%d%d",&q[i],&x[i]);
f[0][0]=1;
for(i=1;i<=n;i++){
mx+=q[i];
for(j=mx-q[i]+1;j<=mx;j++){
for(k=0;k<=q[i]-x[i];k++){
f[j%w][k]=0;
if(j>=1)(f[j%w][k]+=f[(j-1)%w][k])%=mod;//拿
if(k>=1)(f[j%w][k]+=f[max(0,j-t)%w][k-1])%=mod;//不拿
}for(;k<w;k++)f[j%w][k]=0;//清空
}
for(j=max(0,mx-t);j<=mx;j++){//压下去
for(k=1;k<=q[i]-x[i];k++){
(f[j%w][0]+=f[j%w][k])%=mod;
f[j%w][k]=0;
}
for(;k<w;k++)f[j%w][k]=0;
}
}
printf("%lld",f[mx%w][0]%mod);
return 0;
}