SGU 108 Self-numbers II(ふるい+列挙)
1976 ワード
配列をスクロールしないと超空間になり、処理後も様々なテクニックで超時間防止を最適化します.
各数字kの皆さんの加算とpsumは、前の数k-1の加算と一定の関係があります.
k%10!=0でpsum++;
k 10の倍数であればpsum-=8
kが100の倍数であればpsum-=17
………………
各数字kの皆さんの加算とpsumは、前の数k-1の加算と一定の関係があります.
k%10!=0でpsum++;
k 10の倍数であればpsum-=8
kが100の倍数であればpsum-=17
………………
//SGU 108 Self-numbers II
// +
//by night_watcher
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 5000
struct NODE{
int ul;
int id;
int num;
} node[N];
int n,m,psum;
bool a[64];
bool cmp1(const NODE x,const NODE y){
return x.id<y.id;
}
bool cmp2(const NODE x,const NODE y){
return x.ul<y.ul;
}
void cnt(int k){
if(k%10){
psum+=1;
return ;
}
k/=10;
psum-=8;
while(k%10==0){
psum-=9;
k/=10;
}
return ;
}
int main(){
int i,j,nid,selfcnt;
while(cin>>n>>m){
memset(a,1,sizeof(a));
for(i=0;i<m;i++){
cin>>node[i].id;
node[i].ul=i;
}
sort(node,node+m,cmp1);
selfcnt=0;
psum=0;
nid=0;
for(i=1,j=0;i<=n;i++,j=(j+1)%64){
if(a[j]){
selfcnt++;
while(selfcnt==node[nid].id){
node[nid++].num=i;
}
}
cnt(i);
a[(j+psum)%64]=0;
a[j]=1;
}
sort(node,node+m,cmp2);
cout<<selfcnt<<endl;
cout<<node[0].num;
for(i=1;i<m;i++){
cout<<" "<<node[i].num;
}
cout<<endl;
}
return 0;
}