https://codeforces.com/gym/101982/attachments
K 打表暴力
/*#include<bits/stdc++.h> using namespace std; map<int,double> dmin,dmax; bool legal(int n){ int a[10]={}; int cur=10; while(n){ int t=n%10; if(t==0||a[t]||t>=cur) return false; cur=t; a[t]++; n/=10; } return true; } int main(){ int cnt=0; freopen("Yinku.out","w",stdout); for(int i=1;i<=123456789;i++){ if(legal(i)){ //calc(i); printf("%d,",i); cnt++; } } cerr<<cnt<<endl; }*/ /*int num[]={1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19,23,24,25,26,27,28,29,34,35,36,37,38,39,45,46,47,48,49,56,57,58,59,67,68,69,78,79,89, 123,124,125,126,127,128,129,134,135,136,137,138,139,145,146,147,148,149,156,157,158,159,167,168,169,178,179,189,234,235,236,237,238,239,245, 246,247,248,249,256,257,258,259,267,268,269,278,279,289,345,346,347,348,349,356,357,358,359,367,368,369,378,379,389,456,457,458,459,467,468, 469,478,479,489,567,568,569,578,579,589,678,679,689,789,1234,1235,1236,1237,1238,1239,1245,1246,1247,1248,1249,1256,1257,1258,1259,1267,1268, 1269,1278,1279,1289,1345,1346,1347,1348,1349,1356,1357,1358,1359,1367,1368,1369,1378,1379,1389,1456,1457,1458,1459,1467,1468,1469,1478,1479, 1489,1567,1568,1569,1578,1579,1589,1678,1679,1689,1789,2345,2346,2347,2348,2349,2356,2357,2358,2359,2367,2368,2369,2378,2379,2389,2456,2457, 2458,2459,2467,2468,2469,2478,2479,2489,2567,2568,2569,2578,2579,2589,2678,2679,2689,2789,3456,3457,3458,3459,3467,3468,3469,3478,3479,3489, 3567,3568,3569,3578,3579,3589,3678,3679,3689,3789,4567,4568,4569,4578,4579,4589,4678,4679,4689,4789,5678,5679,5689,5789,6789,12345,12346,12347, 12348,12349,12356,12357,12358,12359,12367,12368,12369,12378,12379,12389,12456,12457,12458,12459,12467,12468,12469,12478,12479,12489,12567,12568, 12569,12578,12579,12589,12678,12679,12689,12789,13456,13457,13458,13459,13467,13468,13469,13478,13479,13489,13567,13568,13569,13578,13579,13589, 13678,13679,13689,13789,14567,14568,14569,14578,14579,14589,14678,14679,14689,14789,15678,15679,15689,15789,16789,23456,23457,23458,23459,23467, 23468,23469,23478,23479,23489,23567,23568,23569,23578,23579,23589,23678,23679,23689,23789,24567,24568,24569,24578,24579,24589,24678,24679,24689, 24789,25678,25679,25689,25789,26789,34567,34568,34569,34578,34579,34589,34678,34679,34689,34789,35678,35679,35689,35789,36789,45678,45679,45689, 45789,46789,56789,123456,123457,123458,123459,123467,123468,123469,123478,123479,123489,123567,123568,123569,123578,123579,123589,123678,123679, 123689,123789,124567,124568,124569,124578,124579,124589,124678,124679,124689,124789,125678,125679,125689,125789,126789,134567,134568,134569, 134578,134579,134589,134678,134679,134689,134789,135678,135679,135689,135789,136789,145678,145679,145689,145789,146789,156789,234567,234568, 234569,234578,234579,234589,234678,234679,234689,234789,235678,235679,235689,235789,236789,245678,245679,245689,245789,246789,256789,345678, 345679,345689,345789,346789,356789,456789,1234567,1234568,1234569,1234578,1234579,1234589,1234678,1234679,1234689,1234789,1235678,1235679, 1235689,1235789,1236789,1245678,1245679,1245689,1245789,1246789,1256789,1345678,1345679,1345689,1345789,1346789,1356789,1456789,2345678,2345679, 2345689,2345789,2346789,2356789,2456789,3456789,12345678,12345679,12345689,12345789,12346789,12356789,12456789,13456789,23456789,123456789}; double p[13]; map<int,double> dmin,dmax; int link(vector<int> s,int ex1,int ex2=-1,int ex3=-1,int ex4=-1){ int ans=0; int n=s.size(); for(int i=0;i<n;i++){ if(i==ex1||i==ex2||i==ex3||i==ex4) continue; else{ ans*=10; ans+=s[i]; } } return ans; } vector<int> findnextstate(int state,int sum){ vector<int>ans; //cout<<"state="<<state<<" has next states: "; vector<int> s; while(state){ s.push_back(state%10); state/=10; } reverse(s.begin(),s.end()); int n=s.size(); for(int i=0;i<n;i++){ if(s[i]==sum){ ans.push_back(link(s,i)); break; } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(s[i]+s[j]==sum){ ans.push_back(link(s,i,j)); break; } } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ if(s[i]+s[j]+s[k]==sum){ ans.push_back(link(s,i,j,k)); break; } } } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ for(int l=k+1;l<n;l++){ if(s[i]+s[j]+s[k]+s[l]==sum){ ans.push_back(link(s,i,j,k,l)); break; } } } } } for(auto i:ans){ cout<<i<<","; } cout<<endl; return ans; } void calc(int state){ double minans=0; double maxans=0; vector<int> ns; for(int sum=2;sum<=12;sum++){ ns=findnextstate(state,sum); if(ns.size()==0){ minans+=p[sum]*state; maxans+=p[sum]*state; } else{ double nmax=-1.0; double nmin=1e30; for(auto nsi:ns){ nmax=max(nmax,dmax[nsi]); nmin=min(nmin,dmin[nsi]); } maxans+=p[sum]*nmax; minans+=p[sum]*nmin; } } dmax[state]=maxans; dmin[state]=minans; cerr<<"state="<<state<<" dmax="<<maxans<<" dmin="<<minans<<endl; printf("dmax[%d]=%.10f; dmin[%d]=%.10f; ",state,maxans,state,minans); cout<<"dmax["<<state<<"]="<<maxans<<"; "; cout<<"dmin["<<state<<"]="<<minans<<"; "; } int ntop=511; int main(){ freopen("Yinku.out","w",stdout); for(int sum=2;sum<=7;sum++){ p[sum]=1.0*(sum-1)/36; } for(int sum=8;sum<=12;sum++){ p[sum]=1.0*(13-sum)/36; } for(int sum=2;sum<=12;sum++){ cout<<"p["<<sum<<"]="<<p[sum]<<endl; } for(int i=0;i<ntop;i++){ calc(num[i]); } }*/ #include<bits/stdc++.h> using namespace std; map<int,double> dmax,dmin; void init(){ dmax[1]=1.0000000000; dmin[1]=1.0000000000; dmax[2]=1.9444444444; dmin[2]=1.9444444444; dmax[3]=2.8333333333; dmin[3]=2.8333333333; dmax[4]=3.6666666667; dmin[4]=3.6666666667; dmax[5]=4.4444444444; dmin[5]=4.4444444444; dmax[6]=5.1666666667; dmin[6]=5.1666666667; dmax[7]=5.8333333333; dmin[7]=5.8333333333; dmax[8]=6.8888888889; dmin[8]=6.8888888889; dmax[9]=8.0000000000; dmin[9]=8.0000000000; dmax[12]=11.0277777778; dmin[12]=11.0277777778; dmax[13]=11.2500000000; dmin[13]=11.2500000000; dmax[14]=11.3611111111; dmin[14]=11.3611111111; dmax[15]=11.3611111111; dmin[15]=11.3611111111; dmax[16]=11.2500000000; dmin[16]=11.2500000000; dmax[17]=11.9722222222; dmin[17]=11.9722222222; dmax[18]=13.6388888889; dmin[18]=13.6388888889; dmax[19]=15.4166666667; dmin[19]=15.4166666667; dmax[23]=18.7145061728; dmin[23]=18.7145061728; dmax[24]=18.2638888889; dmin[24]=18.2638888889; dmax[25]=17.7006172840; dmin[25]=17.7006172840; dmax[26]=18.4691358025; dmin[26]=18.4691358025; dmax[27]=19.2361111111; dmin[27]=19.2361111111; dmax[28]=21.4614197531; dmin[28]=21.4614197531; dmax[29]=23.7993827160; dmin[29]=23.7993827160; dmax[34]=24.0509259259; dmin[34]=24.0509259259; dmax[35]=24.8672839506; dmin[35]=24.8672839506; dmax[36]=25.6805555556; dmin[36]=25.6805555556; dmax[37]=26.4907407407; dmin[37]=26.4907407407; dmax[38]=29.2762345679; dmin[38]=29.2762345679; dmax[39]=32.1759259259; dmin[39]=32.1759259259; dmax[45]=32.0277777778; dmin[45]=32.0277777778; dmax[46]=32.8842592593; dmin[46]=32.8842592593; dmax[47]=33.7361111111; dmin[47]=33.7361111111; dmax[48]=37.0833333333; dmin[48]=37.0833333333; dmax[49]=40.5462962963; dmin[49]=40.5462962963; dmax[56]=40.0802469136; dmin[56]=40.0802469136; dmax[57]=40.9722222222; dmin[57]=40.9722222222; dmax[58]=44.8827160494; dmin[58]=44.8827160494; dmax[59]=47.2716049383; dmin[59]=47.2716049383; dmax[67]=48.1990740741; dmin[67]=48.1990740741; dmax[68]=50.7854938272; dmin[68]=50.7854938272; dmax[69]=53.4351851852; dmin[69]=53.4351851852; dmax[78]=56.1250000000; dmin[78]=56.1250000000; dmax[79]=59.0370370370; dmin[79]=59.0370370370; dmax[89]=68.6265432099; dmin[89]=68.6265432099; dmax[123]=72.9483024691; dmin[123]=72.4930555556; dmax[124]=53.4598765432; dmin[124]=53.4598765432; dmax[125]=47.3634259259; dmin[125]=47.3634259259; dmax[126]=48.0941358025; dmin[126]=48.0941358025; dmax[127]=55.7924382716; dmin[127]=55.7924382716; dmax[128]=70.1481481481; dmin[128]=70.1481481481; dmax[129]=84.7322530864; dmin[129]=84.7322530864; dmax[134]=61.6057098765; dmin[134]=60.9737654321; dmax[135]=51.5339506173; dmin[135]=51.5339506173; dmax[136]=52.3125000000; dmin[136]=52.3125000000; dmax[137]=60.5864197531; dmin[137]=60.5864197531; dmax[138]=76.0979938272; dmin[138]=76.0979938272; dmax[139]=91.8425925926; dmin[139]=91.8425925926; dmax[145]=71.3016975309; dmin[145]=70.5331790123; dmax[146]=56.5061728395; dmin[146]=56.5061728395; dmax[147]=65.3541666667; dmin[147]=65.3541666667; dmax[148]=82.0262345679; dmin[148]=82.0262345679; dmax[149]=94.7970679012; dmin[149]=94.7970679012; dmax[156]=81.6242283951; dmin[156]=80.7638888889; dmax[157]=70.0956790123; dmin[157]=70.0956790123; dmax[158]=83.5439814815; dmin[158]=83.5439814815; dmax[159]=92.7901234568; dmin[159]=92.7901234568; dmax[167]=97.0331790123; dmin[167]=96.1304012346; dmax[168]=79.8456790123; dmin[168]=79.8456790123; dmax[169]=89.6550925926; dmin[169]=89.6550925926; dmax[178]=108.4174382716; dmin[178]=107.7114197531; dmax[179]=94.9969135802; dmin[179]=94.9969135802; dmax[189]=130.2307098765; dmin[189]=129.6041666667; dmax[234]=75.8672839506; dmin[234]=75.8672839506; dmax[235]=102.4124657064; dmin[235]=100.8269032922; dmax[236]=90.7445130316; dmin[236]=90.7445130316; dmax[237]=104.7986111111; dmin[237]=104.7986111111; dmax[238]=131.3254458162; dmin[238]=131.3254458162; dmax[239]=151.4512174211; dmin[239]=151.4512174211; dmax[245]=80.6995884774; dmin[245]=80.6995884774; dmax[246]=128.6604938272; dmin[246]=126.8414351852; dmax[247]=109.8263888889; dmin[247]=109.8263888889; dmax[248]=130.6715534979; dmin[248]=130.6715534979; dmax[249]=151.7037037037; dmin[249]=151.7037037037; dmax[256]=99.6547496571; dmin[256]=99.6547496571; dmax[257]=149.5511831276; dmin[257]=147.5733024691; dmax[258]=129.4416152263; dmin[258]=129.4416152263; dmax[259]=144.1989026063; dmin[259]=144.1989026063; dmax[267]=119.7229938272; dmin[267]=119.7229938272; dmax[268]=171.1649519890; dmin[268]=169.5565843621; dmax[269]=150.2122770919; dmin[269]=150.2122770919; dmax[278]=140.3369341564; dmin[278]=140.3369341564; dmax[279]=186.3179012346; dmin[279]=185.0694444444; dmax[289]=177.2290809328; dmin[289]=177.2290809328; dmax[345]=113.5054012346; dmin[345]=113.5054012346; dmax[346]=133.7564300412; dmin[346]=133.7564300412; dmax[347]=201.3310185185; dmin[347]=198.2947530864; dmax[348]=173.6041666667; dmin[348]=173.6041666667; dmax[349]=202.9302983539; dmin[349]=202.9302983539; dmax[356]=148.3471364883; dmin[356]=148.3471364883; dmax[357]=159.3734567901; dmin[357]=159.3734567901; dmax[358]=238.1693244170; dmin[358]=235.6723251029; dmax[359]=209.6433470508; dmin[359]=209.6433470508; dmax[367]=174.8269032922; dmin[367]=174.8269032922; dmax[368]=195.5067729767; dmin[368]=195.5067729767; dmax[369]=256.4344135802; dmin[369]=254.4699074074; dmax[378]=201.5748456790; dmin[378]=201.5748456790; dmax[379]=222.9701646091; dmin[379]=222.9701646091; dmax[389]=249.8924039781; dmin[389]=249.8924039781; dmax[456]=202.5902777778; dmin[456]=202.5902777778; dmax[457]=216.6087962963; dmin[457]=216.6087962963; dmax[458]=254.9200102881; dmin[458]=254.9200102881; dmax[459]=330.7530864198; dmin[459]=328.0833333333; dmax[467]=235.4837962963; dmin[467]=235.4837962963; dmax[468]=261.6674382716; dmin[468]=261.6674382716; dmax[469]=287.9881687243; dmin[469]=287.9881687243; dmax[478]=268.3657407407; dmin[478]=268.3657407407; dmax[479]=295.2870370370; dmin[479]=295.2870370370; dmax[489]=328.1095679012; dmin[489]=328.1095679012; dmax[567]=301.6936728395; dmin[567]=301.6936728395; dmax[568]=333.3815157750; dmin[568]=333.3815157750; dmax[569]=349.3172153635; dmin[569]=349.3172153635; dmax[578]=340.7096193416; dmin[578]=340.7096193416; dmax[579]=356.9629629630; dmin[579]=356.9629629630; dmax[589]=395.4831961591; dmin[589]=395.4831961591; dmax[678]=399.6203703704; dmin[678]=399.6203703704; dmax[679]=418.5442386831; dmin[679]=418.5442386831; dmax[689]=443.6514060357; dmin[689]=443.6514060357; dmax[789]=486.1234567901; dmin[789]=486.1234567901; dmax[1234]=119.4546467764; dmin[1234]=110.0102023320; dmax[1235]=54.2540294925; dmin[1235]=43.0411522634; dmax[1236]=23.1703103567; dmin[1236]=11.6005015432; dmax[1237]=25.5880486968; dmin[1237]=23.2014317558; dmax[1238]=230.4202246228; dmin[1238]=227.6310871056; dmax[1239]=401.2454561043; dmin[1239]=398.0474537037; dmax[1245]=20.0291923868; dmin[1245]=13.9230967078; dmax[1246]=22.9655778464; dmin[1246]=14.9202246228; dmax[1247]=25.8203446502; dmin[1247]=17.8825874486; dmax[1248]=26.5225051440; dmin[1248]=26.5225051440; dmax[1249]=199.7329818244; dmin[1249]=199.7329818244; dmax[1256]=231.4379286694; dmin[1256]=225.4654921125; dmax[1257]=199.9688786008; dmin[1257]=192.4221107682; dmax[1258]=167.3787294239; dmin[1258]=161.7572659465; dmax[1259]=134.0133744856; dmin[1259]=134.0133744856; dmax[1267]=377.3278892318; dmin[1267]=370.9889403292; dmax[1268]=310.0932355967; dmin[1268]=304.0210905350; dmax[1269]=277.7365826475; dmin[1269]=273.2816786694; dmax[1278]=490.5290637860; dmin[1278]=484.6957304527; dmax[1279]=458.3088134431; dmin[1279]=452.8862740055; dmax[1289]=674.2302383402; dmin[1289]=668.2459705075; dmax[1345]=135.5098593964; dmin[1345]=127.9563614540; dmax[1346]=100.7694615912; dmin[1346]=96.2972393690; dmax[1347]=401.0482253086; dmin[1347]=387.5869341564; dmax[1348]=365.5969221536; dmin[1348]=354.5354938272; dmax[1349]=329.1183984911; dmin[1349]=324.7734910837; dmax[1356]=66.5548268176; dmin[1356]=62.2280092593; dmax[1357]=69.6111968450; dmin[1357]=67.8202160494; dmax[1358]=408.8004115226; dmin[1358]=401.5396090535; dmax[1359]=373.7729766804; dmin[1359]=368.9358710562; dmax[1367]=260.4957133059; dmin[1367]=255.6905435528; dmax[1368]=225.5781464335; dmin[1368]=224.2401834705; dmax[1369]=492.1507201646; dmin[1369]=486.5778034979; dmax[1378]=419.4829818244; dmin[1378]=414.8127143347; dmax[1379]=422.7452846365; dmin[1379]=421.8224451303; dmax[1389]=655.1735253772; dmin[1389]=650.1018518519; dmax[1456]=354.8067986968; dmin[1456]=346.6737825789; dmax[1457]=158.3001543210; dmin[1457]=155.2708333333; dmax[1458]=481.0778034979; dmin[1458]=474.8007973251; dmax[1459]=723.4605624143; dmin[1459]=709.9681927298; dmax[1467]=323.5196759259; dmin[1467]=319.3485082305; dmax[1468]=165.5367369684; dmin[1468]=165.5367369684; dmax[1469]=410.0457390261; dmin[1469]=408.5901063100; dmax[1478]=494.4687500000; dmin[1478]=490.3422067901; dmax[1479]=375.7253086420; dmin[1479]=375.7253086420; dmax[1489]=706.0543124143; dmin[1489]=701.3932184499; dmax[1567]=606.5264489026; dmin[1567]=596.4591478052; dmax[1568]=436.6946587791; dmin[1568]=432.0253772291; dmax[1569]=523.6325445816; dmin[1569]=518.0709876543; dmax[1578]=530.5990226337; dmin[1578]=527.0187757202; dmax[1579]=403.3052126200; dmin[1579]=403.3052126200; dmax[1589]=711.9952846365; dmin[1589]=707.8954046639; dmax[1678]=792.9756515775; dmin[1678]=782.5008573388; dmax[1679]=656.6616941015; dmin[1679]=651.4583762003; dmax[1689]=664.9979852538; dmin[1689]=661.9764660494; dmax[1789]=946.1225994513; dmin[1789]=936.8689128944; dmax[2345]=37.1956018519; dmin[2345]=29.5484682213; dmax[2346]=42.9060999657; dmin[2346]=34.3794152949; dmax[2347]=371.8075703018; dmin[2347]=360.2605238340; dmax[2348]=49.6303798011; dmin[2348]=49.6303798011; dmax[2349]=571.8996484911; dmin[2349]=564.3588391632; dmax[2356]=306.9124514175; dmin[2356]=299.3814586191; dmax[2357]=703.6003086420; dmin[2357]=682.3596536351; dmax[2358]=902.0576989026; dmin[2358]=879.6421896433; dmax[2359]=577.4717649749; dmin[2359]=565.7200788752; dmax[2367]=252.3318329904; dmin[2367]=251.6157836077; dmax[2368]=714.7542795496; dmin[2368]=705.4843178441; dmax[2369]=848.5984367856; dmin[2369]=840.1232662704; dmax[2378]=591.2397976680; dmin[2378]=590.8206875857; dmax[2379]=923.0631001372; dmin[2379]=914.6124399863; dmax[2389]=993.9987854367; dmin[2389]=993.6945158893; dmax[2456]=190.4747085048; dmin[2456]=183.9033922039; dmax[2457]=737.3722993827; dmin[2457]=727.2996399177; dmax[2458]=198.4930555556; dmin[2458]=198.4930555556; dmax[2459]=813.4903978052; dmin[2459]=805.7591163695; dmax[2467]=475.5123671125; dmin[2467]=466.6498413923; dmax[2468]=1294.8040123457; dmin[2468]=1269.5820687586; dmax[2469]=888.5467678326; dmin[2469]=874.6962448560; dmax[2478]=485.6350951646; dmin[2478]=485.6350951646; dmax[2479]=1104.2062757202; dmin[2479]=1095.8524091221; dmax[2489]=904.7705332647; dmin[2489]=904.7705332647; dmax[2567]=641.2331532922; dmin[2567]=632.3825017147; dmax[2568]=786.4277692044; dmin[2568]=778.6418348003; dmax[2569]=717.4419295839; dmin[2569]=716.5374371285; dmax[2578]=935.7325531550; dmin[2578]=923.2384116369; dmax[2579]=1363.7049039781; dmin[2579]=1338.0081447188; dmax[2589]=874.0416666667; dmin[2589]=874.0416666667; dmax[2678]=978.0735811043; dmin[2678]=968.9724651349; dmax[2679]=1054.1356310014; dmin[2679]=1046.5969221536; dmax[2689]=1279.2054040924; dmin[2689]=1267.6953446502; dmax[2789]=1254.6332304527; dmin[2789]=1246.4920124600; dmax[3456]=168.6016375171; dmin[3456]=167.8963906036; dmax[3457]=655.1168552812; dmin[3457]=642.1845850480; dmax[3458]=946.7671039095; dmin[3458]=935.4454446731; dmax[3459]=1142.3213305898; dmin[3459]=1132.4689643347; dmax[3467]=1145.1833419067; dmin[3467]=1129.9692858368; dmax[3468]=572.7495070302; dmin[3468]=572.7495070302; dmax[3469]=1249.2494427298; dmin[3469]=1238.7290523548; dmax[3478]=1446.8596965021; dmin[3478]=1426.6103609396; dmax[3479]=1546.8643689986; dmin[3479]=1522.5447959534; dmax[3489]=1361.1638803155; dmin[3489]=1361.0275634431; dmax[3567]=496.1508916324; dmin[3567]=496.1508916324; dmax[3568]=1488.6962162780; dmin[3568]=1474.1989597622; dmax[3569]=1392.6273719707; dmin[3569]=1381.1784788904; dmax[3578]=1402.0408521948; dmin[3578]=1387.2846221994; dmax[3579]=1204.1147976680; dmin[3579]=1203.8704561043; dmax[3589]=1903.6904435299; dmin[3589]=1883.8273319616; dmax[3678]=1039.7095764746; dmin[3678]=1039.7095764746; dmax[3679]=1655.0932784636; dmin[3679]=1641.9003200732; dmax[3689]=1863.1005515546; dmin[3689]=1848.7299001677; dmax[3789]=1500.8286179698; dmin[3789]=1500.8286179698; dmax[4567]=1141.9544324417; dmin[4567]=1141.6019804527; dmax[4568]=1274.9556327160; dmin[4568]=1274.9556327160; dmax[4569]=2039.4982853224; dmin[4569]=2022.5546982167; dmax[4578]=1539.4831532922; dmin[4578]=1539.3751286008; dmax[4579]=2180.6133401920; dmin[4579]=2162.6604080933; dmax[4589]=2566.9612482853; dmin[4589]=2545.8911751257; dmax[4678]=1585.1182913237; dmin[4678]=1585.1182913237; dmax[4679]=1847.5809327846; dmin[4679]=1847.5809327846; dmax[4689]=2112.5674296982; dmin[4689]=2112.5674296982; dmax[4789]=2166.8948902606; dmin[4789]=2166.8948902606; dmax[5678]=2244.1061814129; dmin[5678]=2244.1061814129; dmax[5679]=2401.0883058985; dmin[5679]=2401.0883058985; dmax[5689]=2722.0385230910; dmin[5689]=2722.0385230910; dmax[5789]=2782.1575788752; dmin[5789]=2782.1575788752; dmax[6789]=3261.3257887517; dmin[6789]=3261.3257887517; dmax[12345]=68.8936828418; dmin[12345]=28.7180236435; dmax[12346]=82.1975213382; dmin[12346]=24.5750856148; dmax[12347]=97.8553848022; dmin[12347]=35.8737890089; dmax[12348]=111.0048368198; dmin[12348]=48.2685899634; dmax[12349]=125.3670934309; dmin[12349]=64.0274419867; dmax[12356]=80.2201562738; dmin[12356]=40.8158852976; dmax[12357]=84.8537427602; dmin[12357]=45.9317605929; dmax[12358]=120.4383311424; dmin[12358]=67.5882880373; dmax[12359]=145.4804431489; dmin[12359]=71.4257735101; dmax[12367]=97.2667562109; dmin[12367]=56.4173965954; dmax[12368]=128.7155254534; dmin[12368]=76.6345754029; dmax[12369]=166.5252867322; dmin[12369]=99.9029028064; dmax[12378]=148.2070866198; dmin[12378]=107.8061104443; dmax[12379]=183.2486044429; dmin[12379]=152.6676025949; dmax[12389]=2258.1909436443; dmin[12389]=2217.6901232186; dmax[12456]=105.4605302641; dmin[12456]=60.3787544296; dmax[12457]=101.7739126086; dmin[12457]=59.7399584191; dmax[12458]=110.8298539666; dmin[12458]=75.3271622799; dmax[12459]=135.3230595565; dmin[12459]=96.1446163885; dmax[12467]=130.5791395176; dmin[12467]=88.1089356139; dmax[12468]=131.5596969784; dmin[12468]=87.9305948503; dmax[12469]=152.6949076456; dmin[12469]=111.8062664323; dmax[12478]=150.7718585677; dmin[12478]=121.0528406493; dmax[12479]=178.6185128029; dmin[12479]=138.9066179412; dmax[12489]=205.6409000629; dmin[12489]=184.3991317063; dmax[12567]=1219.8163258745; dmin[12567]=1172.6707116389; dmax[12568]=1212.2984479786; dmin[12568]=1169.0029191196; dmax[12569]=1209.8522066949; dmin[12569]=1171.2606476718; dmax[12578]=1238.1811199703; dmin[12578]=1198.0754386717; dmax[12579]=1239.3773148148; dmin[12579]=1198.6230281207; dmax[12589]=1265.9524891404; dmin[12589]=1248.3427974013; dmax[12678]=3057.8458397634; dmin[12678]=2980.0848217688; dmax[12679]=2696.2922525149; dmin[12679]=2631.3414732891; dmax[12689]=2726.7459455018; dmin[12689]=2670.1675490112; dmax[12789]=4566.0939429012; dmin[12789]=4476.9786784598; dmax[13456]=488.7487925812; dmin[13456]=453.2097276997; dmax[13457]=528.7718121285; dmin[13457]=458.7735982510; dmax[13458]=552.5490612140; dmin[13458]=502.7671253429; dmax[13459]=1312.8041266575; dmin[13459]=1269.4899905693; dmax[13467]=556.9534715078; dmin[13467]=519.6793195588; dmax[13468]=546.3390096308; dmin[13468]=508.0636609797; dmax[13469]=579.0787822931; dmin[13469]=533.8523186252; dmax[13478]=2482.9081575789; dmin[13478]=2375.8243098422; dmax[13479]=2478.6709533608; dmin[13479]=2394.8990697874; dmax[13489]=2500.0781107110; dmin[13489]=2416.7810166133; dmax[13567]=555.4991236092; dmin[13567]=508.4235229957; dmax[13568]=587.4293957667; dmin[13568]=543.0868400873; dmax[13569]=619.1480933737; dmin[13569]=587.4807384545; dmax[13578]=641.5332576017; dmin[13578]=602.0972174592; dmax[13579]=624.8926897577; dmin[13579]=600.7332533150; dmax[13589]=2946.9804169524; dmin[13589]=2873.2640460677; dmax[13678]=2141.9245791895; dmin[13678]=2115.6638910322; dmax[13679]=2196.7535008002; dmin[13679]=2123.1369932175; dmax[13689]=2228.1483243789; dmin[13689]=2201.1028199303; dmax[13789]=4162.9569687357; dmin[13789]=4106.9212391404; dmax[14567]=1443.1123221022; dmin[14567]=1400.8586069673; dmax[14568]=1482.3117462563; dmin[14568]=1412.0010335696; dmax[14569]=3545.0566772405; dmin[14569]=3432.3871694483; dmax[14578]=1502.5136674097; dmin[14578]=1457.1131615798; dmax[14579]=1541.2273662551; dmin[14579]=1515.0383087563; dmax[14589]=4818.8587534294; dmin[14589]=4727.5581728205; dmax[14678]=1534.3182513146; dmin[14678]=1504.4821566358; dmax[14679]=1547.0355366941; dmin[14679]=1513.6037701475; dmax[14689]=1598.6005670344; dmin[14689]=1572.8882411218; dmax[14789]=3676.3401277435; dmin[14789]=3645.2802211934; dmax[15678]=4280.0875878772; dmin[15678]=4206.0998085277; dmax[15679]=2980.3495846670; dmin[15679]=2947.9075526787; dmax[15689]=3011.6955947074; dmin[15689]=2963.5740359701; dmax[15789]=3946.9544753086; dmin[15789]=3924.8462839125; dmax[16789]=6517.5464749085; dmin[16789]=6415.2605667010; dmax[23456]=147.6400986892; dmin[23456]=89.2601963782; dmax[23457]=257.1858496228; dmin[23457]=190.8584128753; dmax[23458]=252.3629270024; dmin[23458]=184.5396681940; dmax[23459]=301.3552002362; dmin[23459]=243.1498175774; dmax[23467]=236.5152820645; dmin[23467]=178.6969825246; dmax[23468]=291.6070982891; dmin[23468]=233.6940568559; dmax[23469]=359.9126717059; dmin[23469]=293.1627371971; dmax[23478]=295.5584764613; dmin[23478]=256.2226520824; dmax[23479]=3669.4914694787; dmin[23479]=3563.7280711782; dmax[23489]=389.4286372599; dmin[23489]=384.4475701589; dmax[23567]=2251.1179483882; dmin[23567]=2205.1296891670; dmax[23568]=3017.6644173430; dmin[23568]=2939.3314326343; dmax[23569]=2338.7110990449; dmin[23569]=2248.7861823443; dmax[23578]=5695.9455101642; dmin[23578]=5460.6340913637; dmax[23579]=5676.9275882106; dmin[23579]=5488.4613840306; dmax[23589]=5710.2617574493; dmin[23589]=5568.1564190863; dmax[23678]=2381.4294815005; dmin[23678]=2362.1686818098; dmax[23679]=2478.9458257125; dmin[23679]=2459.3707668896; dmax[23689]=6466.6833875521; dmin[23689]=6315.4665702690; dmax[23789]=5845.0903730376; dmin[23789]=5798.7655015591; dmax[24567]=1719.2177652511; dmin[24567]=1633.1462167543; dmax[24568]=1780.9554374333; dmin[24568]=1736.6722546503; dmax[24569]=1832.7807022558; dmin[24569]=1753.0964315653; dmax[24578]=1792.3268354195; dmin[24578]=1760.9091959114; dmax[24579]=7407.7422458467; dmin[24579]=7247.6857519814; dmax[24589]=1901.1101156455; dmin[24589]=1886.5162664165; dmax[24678]=4649.3631794410; dmin[24678]=4593.8993716421; dmax[24679]=4677.8817443987; dmin[24679]=4554.0368929565; dmax[24689]=8830.5971626848; dmin[24689]=8673.4565353033; dmax[24789]=4766.5699255068; dmin[24789]=4742.1305679393; dmax[25678]=4162.2289320892; dmin[25678]=4053.2304431489; dmax[25679]=6341.0042771681; dmin[25679]=6247.8671386793; dmax[25689]=4929.2392308718; dmin[25689]=4873.7036055331; dmax[25789]=7872.9425678250; dmin[25789]=7743.7882523942; dmax[26789]=8231.5991750495; dmin[26789]=8090.2792856621; dmax[34567]=1422.0523524425; dmin[34567]=1382.6826488912; dmax[34568]=1505.6993181775; dmin[34568]=1478.7650649514; dmax[34569]=1656.4089029873; dmin[34569]=1629.7378162628; dmax[34578]=6436.6032438367; dmin[34578]=6273.9314998190; dmax[34579]=6505.9448302469; dmin[34579]=6318.7160755792; dmax[34589]=9454.9624938081; dmin[34589]=9256.2829011711; dmax[34678]=5516.1204811100; dmin[34678]=5475.1114921506; dmax[34679]=10468.7030749886; dmin[34679]=10225.8148469650; dmax[34689]=5634.7702939243; dmin[34689]=5604.7104945416; dmax[34789]=10562.7302240512; dmin[34789]=10407.4795965268; dmax[35678]=4804.0017730243; dmin[35678]=4780.5669133103; dmax[35679]=4844.1055098308; dmin[35679]=4823.9204437205; dmax[35689]=13897.8296983755; dmin[35689]=13634.6802623668; dmax[35789]=9971.1276339354; dmin[35789]=9863.9338142369; dmax[36789]=9292.2046039095; dmin[36789]=9226.4675711591; dmax[45678]=4854.2439021776; dmin[45678]=4849.4561197321; dmax[45679]=11383.0826188843; dmin[45679]=11294.3846379172; dmax[45689]=12726.1525396281; dmin[45689]=12628.5057282934; dmax[45789]=15397.3263460219; dmin[45789]=15273.4797548964; dmax[46789]=10532.2069901692; dmin[46789]=10532.2069901692; dmax[56789]=16021.8635211858; dmin[56789]=16021.8635211858; dmax[123456]=194.3717704920; dmin[123456]=40.2302529599; dmax[123457]=369.4698726772; dmin[123457]=46.9140025657; dmax[123458]=371.9810700779; dmin[123458]=75.2925873136; dmax[123459]=478.4578042441; dmin[123459]=149.8941924159; dmax[123467]=352.6189403808; dmin[123467]=70.6543663353; dmax[123468]=422.6110858077; dmin[123468]=70.4962120641; dmax[123469]=531.3186563675; dmin[123469]=158.2084714932; dmax[123478]=506.2029678212; dmin[123478]=202.3029483128; dmax[123479]=659.3351861378; dmin[123479]=223.9294352598; dmax[123489]=794.1044832073; dmin[123489]=348.1515887494; dmax[123567]=465.5540028858; dmin[123567]=139.7917832939; dmax[123568]=580.8660937315; dmin[123568]=233.0884790862; dmax[123569]=556.1440568029; dmin[123569]=294.8483882295; dmax[123578]=625.4961465398; dmin[123578]=263.8479657123; dmax[123579]=642.8518058096; dmin[123579]=323.0687892682; dmax[123589]=1020.9240737168; dmin[123589]=499.9841627822; dmax[123678]=756.9396216159; dmin[123678]=361.4385244736; dmax[123679]=804.2393221625; dmin[123679]=434.8427317778; dmax[123689]=1142.0635114746; dmin[123689]=616.5431549698; dmax[123789]=1358.7606006373; dmin[123789]=910.0163939588; dmax[124567]=590.9853454599; dmin[124567]=285.2257360214; dmax[124568]=684.3316508059; dmin[124568]=300.4752586636; dmax[124569]=829.7499158538; dmin[124569]=453.6492028866; dmax[124578]=648.5562656385; dmin[124578]=398.7582965392; dmax[124579]=904.3724744227; dmin[124579]=419.5800738582; dmax[124589]=952.4708516709; dmin[124589]=607.1082081328; dmax[124678]=986.5068496807; dmin[124678]=580.5497240639; dmax[124679]=995.7816625943; dmin[124679]=617.0753063002; dmax[124689]=1102.6942109916; dmin[124689]=696.1225803332; dmax[124789]=1293.8514094888; dmin[124789]=975.4886042405; dmax[125678]=11757.5867930527; dmin[125678]=11452.5924467921; dmax[125679]=11719.1314496223; dmin[125679]=11389.9265688639; dmax[125689]=11750.2670435782; dmin[125689]=11461.0877875260; dmax[125789]=12089.0516284675; dmin[125789]=11781.1398258755; dmax[126789]=26955.1883466221; dmin[126789]=26097.8127519094; dmax[134567]=4374.7485768572; dmin[134567]=4104.8980572544; dmax[134568]=4510.6907207759; dmin[134568]=4132.7463151961; dmax[134569]=4829.0138829351; dmin[134569]=4404.0240757411; dmax[134578]=4796.2065658658; dmin[134578]=4409.9280139032; dmax[134579]=5022.3018086674; dmin[134579]=4406.8152915111; dmax[134589]=5279.0935696016; dmin[134589]=4884.9633739035; dmax[134678]=4973.2614562892; dmin[134678]=4627.3166211801; dmax[134679]=5163.2132753360; dmin[134679]=4727.1126293153; dmax[134689]=5107.2382390446; dmin[134689]=4820.0923381694; dmax[134789]=24390.2699051450; dmin[134789]=23491.1350201475; dmax[135678]=5153.8803542000; dmin[135678]=4766.2568523599; dmax[135679]=5148.2828131880; dmin[135679]=4740.6162474703; dmax[135689]=5557.1326270740; dmin[135689]=5175.4939360478; dmax[135789]=5940.8348074798; dmin[135789]=5593.7875913966; dmax[136789]=21270.1288526663; dmin[136789]=20884.8449715755; dmax[145678]=13638.4393950760; dmin[145678]=13416.0666316984; dmax[145679]=14081.7711540416; dmin[145679]=13539.5563146576; dmax[145689]=14670.2829646776; dmin[145689]=13898.5369767058; dmax[145789]=14776.8501347927; dmin[145789]=14279.5084507411; dmax[146789]=14695.6440549507; dmin[146789]=14392.6185539830; dmax[156789]=29053.3553291017; dmin[156789]=28658.3706208244; dmax[234567]=967.0998273812; dmin[234567]=483.5995414031; dmax[234568]=1228.8454561439; dmin[234568]=585.4682000727; dmax[234569]=1309.6274611446; dmin[234569]=684.7334850038; dmax[234578]=1656.8527406132; dmin[234578]=1072.5442687164; dmax[234579]=2303.0647797539; dmin[234579]=1699.1091981077; dmax[234589]=2020.5296184101; dmin[234589]=1376.3947773600; dmax[234678]=1512.9856212174; dmin[234678]=993.7750508813; dmax[234679]=2155.2857464643; dmin[234679]=1550.9985436486; dmax[234689]=2371.7101970530; dmin[234689]=1837.9024420639; dmax[234789]=2599.4486582383; dmin[234789]=2212.2162909062; dmax[235678]=22162.2436144135; dmin[235678]=21477.5099521866; dmax[235679]=22132.4416141679; dmin[235679]=21782.1836064513; dmax[235689]=23003.4963691436; dmin[235689]=22027.9335804827; dmax[235789]=56340.2719353048; dmin[235789]=54169.2986552350; dmax[236789]=23532.3702786827; dmin[236789]=23150.4181033376; dmax[245678]=15810.8355875854; dmin[245678]=15570.5119933829; dmax[245679]=17081.2347066896; dmin[245679]=16176.2199818953; dmax[245689]=16940.1203366325; dmin[245689]=16476.9611983621; dmax[245789]=17635.1016233605; dmin[245789]=17329.7402154884; dmax[246789]=45681.4281547422; dmin[246789]=44720.2818710083; dmax[256789]=40643.2785623486; dmin[256789]=39621.6045258978; dmax[345678]=12759.7338033746; dmin[345678]=12484.4791560161; dmax[345679]=13894.7327532007; dmin[345679]=13515.9984748498; dmax[345689]=14749.8415659029; dmin[345689]=14437.8743815606; dmax[345789]=64063.9017266116; dmin[345789]=61720.1351494760; dmax[346789]=54323.2026290533; dmin[346789]=53440.9330337675; dmax[356789]=46896.1137450465; dmin[356789]=46324.5863871398; dmax[456789]=47400.8053412209; dmin[456789]=47139.1641099976; dmax[1234567]=1298.6855006618; dmin[1234567]=187.6007245825; dmax[1234568]=1491.9750650953; dmin[1234568]=223.3673863063; dmax[1234569]=1724.2105056222; dmin[1234569]=282.2148528515; dmax[1234578]=2303.3924378041; dmin[1234578]=266.6182416817; dmax[1234579]=3192.9876480144; dmin[1234579]=344.0873728810; dmax[1234589]=2929.9214445610; dmin[1234589]=563.1113497477; dmax[1234678]=2548.9055060166; dmin[1234678]=434.3364947068; dmax[1234679]=3010.2953998723; dmin[1234679]=493.3574781930; dmax[1234689]=3453.9773810862; dmin[1234689]=569.0726610260; dmax[1234789]=4616.8603062479; dmin[1234789]=1626.5996866744; dmax[1235678]=3783.3213056337; dmin[1235678]=981.6508458749; dmax[1235679]=3717.6187803464; dmin[1235679]=1227.1752886146; dmax[1235689]=4609.1693726184; dmin[1235689]=1842.8698545044; dmax[1235789]=5467.0160719606; dmin[1235789]=2090.4682308705; dmax[1236789]=6793.0866956484; dmin[1236789]=2978.8418392789; dmax[1245678]=3919.1657507496; dmin[1245678]=2052.8523507892; dmax[1245679]=5521.3893153312; dmin[1245679]=2495.3251907094; dmax[1245689]=5737.9434120656; dmin[1245689]=2689.5499365372; dmax[1245789]=5924.6765386321; dmin[1245789]=3245.2574742723; dmax[1246789]=8213.9321715499; dmin[1246789]=4681.7779475531; dmax[1256789]=116672.3144780462; dmin[1256789]=112668.1486653372; dmax[1345678]=42111.7830760788; dmin[1345678]=40791.3714772151; dmax[1345679]=43518.5455490796; dmin[1345679]=40631.9199806627; dmax[1345689]=44863.7229470352; dmin[1345689]=40935.3891463184; dmax[1345789]=47349.6225536736; dmin[1345789]=42691.2014944134; dmax[1346789]=48770.4805365565; dmin[1346789]=45293.4864288149; dmax[1356789]=49207.0078391301; dmin[1356789]=46021.4548904976; dmax[1456789]=134381.6973255373; dmin[1456789]=132102.4887378579; dmax[2345678]=7069.0239066953; dmin[2345678]=3725.9974728167; dmax[2345679]=9321.9322390900; dmin[2345679]=4529.0369525895; dmax[2345689]=10266.3310179930; dmin[2345689]=4712.2985268626; dmax[2345789]=15134.4219958536; dmin[2345789]=9642.9386421078; dmax[2346789]=13294.5607577937; dmin[2346789]=8653.0856382868; dmax[2356789]=220712.4745010794; dmin[2356789]=213214.5674642164; dmax[2456789]=157137.1784207973; dmin[2456789]=153973.0654041489; dmax[3456789]=125797.0641292672; dmin[3456789]=123396.3259225896; dmax[12345678]=10581.3514556698; dmin[12345678]=1552.8631652257; dmax[12345679]=12609.0430973263; dmin[12345679]=1669.5084794961; dmax[12345689]=12888.2430275852; dmin[12345689]=1944.1378473185; dmax[12345789]=22216.2948490446; dmin[12345789]=2282.4925785500; dmax[12346789]=24032.8637932755; dmin[12346789]=3907.5529613813; dmax[12356789]=36149.6295980344; dmin[12356789]=8824.4798164677; dmax[12456789]=37637.2496743769; dmin[12456789]=18418.9426315879; dmax[13456789]=422754.5825671131; dmin[13456789]=404766.7612967730; dmax[23456789]=69551.1413956859; dmin[23456789]=34930.4199082499; dmax[123456789]=104798.3905297908; dmin[123456789]=14762.1738782474; } double p[13]; int link(vector<int> s,int ex1,int ex2=-1,int ex3=-1,int ex4=-1){ int ans=0; int n=s.size(); for(int i=0;i<n;i++){ if(i==ex1||i==ex2||i==ex3||i==ex4) continue; else{ ans*=10; ans+=s[i]; } } return ans; } vector<int> findnextstate(int state,int sum){ vector<int>ans; //cout<<"state="<<state<<" has next states: "; vector<int> s; while(state){ s.push_back(state%10); state/=10; } reverse(s.begin(),s.end()); int n=s.size(); for(int i=0;i<n;i++){ if(s[i]==sum){ ans.push_back(link(s,i)); break; } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(s[i]+s[j]==sum){ ans.push_back(link(s,i,j)); break; } } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ if(s[i]+s[j]+s[k]==sum){ ans.push_back(link(s,i,j,k)); break; } } } } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ for(int l=k+1;l<n;l++){ if(s[i]+s[j]+s[k]+s[l]==sum){ ans.push_back(link(s,i,j,k,l)); break; } } } } } /*for(auto i:ans){ cout<<i<<","; } cout<<endl;*/ return ans; } int antilink(int state,int nstate){ vector<int> s; while(state){ s.push_back(state%10); state/=10; } reverse(s.begin(),s.end()); vector<int> ns; while(nstate){ ns.push_back(nstate%10); nstate/=10; } reverse(ns.begin(),ns.end()); int ans=0; int i=0,j=0; for(int i=0;i<s.size();i++){ int notlink=0; for(int j=0;j<ns.size();j++){ if(ns[j]==s[i]){ notlink=1; break; } } if(notlink==0){ ans*=10; ans+=s[i]; } } return ans; } void calc(int state,int sum){ double maxans=0; double minans=0; int maxansnum=-1; int minansnum=-1; vector<int> ns; /*for(int sum=2;sum<=12;sum++)*/{ ns=findnextstate(state,sum); if(ns.size()==0){ minans+=state; maxans+=state; } else{ double nmax=-1.0; double nmin=1e30; for(auto nsi:ns){ if(dmax[nsi]>nmax){ nmax=dmax[nsi]; maxansnum=antilink(state,nsi); } if(dmin[nsi]<nmin){ nmin=dmin[nsi]; minansnum=antilink(state,nsi); } //nmax=max(nmax,dmax[nsi]); //nmin=min(nmin,dmin[nsi]); } maxans=nmax; minans=nmin; } } //dmax[state]=maxans; //dmin[state]=minans; //cerr<<"state="<<state<<" dmax="<<maxans<<" dmin="<<minans<<endl; //printf("dmax[%d]=%.10f; dmin[%d]=%.10f; ",state,maxans,state,minans); //cout<<"dmax["<<state<<"]="<<maxans<<"; "; //cout<<"dmin["<<state<<"]="<<minans<<"; "; printf("%d %.5f ",minansnum,minans); printf("%d %.5f ",maxansnum,maxans); } int main(){ init(); for(int sum=2;sum<=7;sum++){ p[sum]=1.0*(sum-1)/36; } for(int sum=8;sum<=12;sum++){ p[sum]=1.0*(13-sum)/36; } int state,a,b; while(cin>>state>>a>>b){ calc(state,a+b); } }
dalao的代码：复杂度真的过关吗？
#include <bits/stdc++.h> using namespace std; #define db(x) cerr << #x << "=" << x << endl #define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl #define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl #define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl #define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl typedef long long ll; typedef long double ld; int sumb[1 << 9], score[1 << 9]; ld mindp[1 << 9], maxdp[1 << 9]; char BS[66]; int main() { for (int i = 0; i < (1 << 9); ++i) for (int j = 0; j < 9; ++j) if (i & (1 << j)) { sumb[i] += j + 1; score[i] = score[i] * 10 + (j + 1); } int r1, r2; scanf("%s%d%d", BS, &r1, &r2); int B = 0; for (int i = 0; i < strlen(BS); ++i) B |= 1 << (BS[i] - '1'); int tot = r1 + r2; for (int b = 0; b < (1 << 9); ++b) { for (int i = 1; i <= 6; ++i) for (int j = 1; j <= 6; ++j) { int sum = i + j; // try all subsets that sum to sum ld mn = 1e15; ld mx = -1e15; bool has = false; for (int bb = b; bb; bb = (bb - 1) & b) { if (sumb[bb] == sum) { mn = min(mn, mindp[b ^ bb]); mx = max(mx, maxdp[b ^ bb]); has = true; } } if (!has) { mindp[b] += score[b] / 36.L; maxdp[b] += score[b] / 36.L; } else { mindp[b] += mn / 36; maxdp[b] += mx / 36; } } } bool has = false; ld mn = 1e15; ld mx = -1e15; int mnset, mxset; for (int bb = B; bb; bb = (bb - 1) & B) { if (sumb[bb] == tot) { if (mn > mindp[B ^ bb]) { mnset = bb; mn = mindp[B ^ bb]; } if (mx < maxdp[B ^ bb]) { mxset = bb; mx = maxdp[B ^ bb]; } has = true; } } auto calc = [&](int bb) { int ret = 0; for (int i = 0; i < 9; ++i) if (bb & (1 << i)) ret = ret * 10 + (i + 1); return ret; }; printf("%d %.5Lf ", has ? calc(mnset) : -1, has ? mn : calc(B)); printf("%d %.5Lf ", has ? calc(mxset) : -1, has ? mx : calc(B)); }