排序之后再扫描。。SB死了。。。#include<iostream>#include<string>#include<algorithm>#include<string.h>using namespace std;int n;const int maxn=1000;const int maxl=520;struct bignum{ int Q[maxl],last; bignum(){memset(Q,0,sizeof(Q));last=0;} void Read() { string a;cin>>a;last=a.size()-1; for(int i=0;i<=last;i++) Q[i]=a[last-i]-‘0’; } void Write() { for(int i=last;i>=0;i–) cout<<Q[i]; } bool operator<(const bignum&x) const { if(last!=x.last) return last<x.last; for(int i=last;i>=0;i–) { if(Q[i]<x.Q[i]) return true; if(Q[i]>x.Q[i]) return false; } return false; } bignum operator+(const bignum&x) const { bignum n; n.last=max(x.last,last);int d=0; for(int i=0;i<=n.last;i++) { d+=x.Q[i]+Q[i]; n.Q[i]=d%10; d/=10; } if(d) n.Q[++n.last]=d; return n; }}A[maxn];int main(){ cin>>n; for(int i=0;i<n;i++) A[i].Read(); sort(A,A+n); for(int i=0;i+2<n;i++) if(A[i+2]<(A[i]+A[i+1])) { A[i].Write();cout<<" ";A[i+1].Write();cout<<" "; A[i+2].Write();cout<<endl; return 0; } cout<<"0 0 0"<<endl; }

这道题只能用brainfuck之类的BT语言做。。。
你可能会想，都快NOIP了那个SB去做这种无聊题目。。
你说对了。。我就是那个SB。。
++++++++++++++++++++++++[->>>>>>>>>>>++++++++++[->>,—————————-
——————–<<[->>>>>>>>>>+<<<<<<<<<<]>>>>[-]+>[-]>>[-]+<<<<<<<>>>>>>>>>
>]++++++++++[-[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<]<<<<<<<<<<>>,<<>>>>>>>>>><<<<<<
<<<<>>>>>>>>>>+++++[->>>>>,————————————————<<<<<
[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>]+++++[-[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<]<<<
<<<<<<<>>,<<>>>>>>>>>><<<<<<<<<<++++++[-[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>>>>>>>
>>+<<<<<<<<<<<<<<<<<+++++[-[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>>>>>[<<<->>>>]>[<]<
<<<[>>>>>>[-]<<<<<]>[<]>>[<<<+>>>>]>[<]>>[->>>>>>>>>>+<<<<<<<<<<]<<<<<<<]>>>>>>>
>>>>>>>>>>[>[-]+<-]><<<<<<<<<<[->>>>>>>>>>[-]+<<<<<<<<<<]<<<<<<<<+++++[-[-<<<<<<
<<<<+>>>>>>>>>>]>>>>[->>>>>>>>>>+<<<<<<<<<<]<<<<<<<<<<<<<<]<>>>>>>>>>>]>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++++++++++++++++++++++
++++++++++++++++++.[-]<++++++++++.[-]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<++++++[-[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<]<]

在ＳＰＯＪ上逛的时候看到了Query on a tree居然一共有５个版本。。
I,II,III,IV,V。。太ＮＢ了。。
我只知道I和II使用路径剖分的。。II要用树套树。。
其他我就囧了。。。

http://www.spoj.pl/problems/COWCAR/
实际上我最近做的SPOJ的题目都是一些ＵＳＡＣＯ月赛的老题。。。
感觉ＵＳＡＣＯ月赛的题目跟我们ＯＩ是比较贴近的。。
不过中国就是没有美国开放。。连stl都不能用。。
说实话我连heap也不会写。。要是ＮＯＩＰ要用我只好写左偏树了。。
这道题实际上很水。。把所有牛按速度排序。。再一个个处理。。
很明显要把每个牛放到当前能承受值最小的轨道。。放不了就扔掉。。。
Code。。
我为了图方便把所有数取负了。。。
#include<queue>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<functional>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxm=50000;
int N,M,D,L;
int S[maxm];
void init()
{
cin>>N>>M>>D>>L;
REP(i,N) scanf("%d",S+i);
sort(S,S+N);
}
int main()
{
init();
priority_queue<int> Q;
REP(i,M) Q.push(-L);
int ans=0;
for(int i=0;i<N;i++)
{
int cur=-Q.top();
if(cur>S[i])
continue;
Q.pop();cur+=D;Q.push(-cur);ans++;
}
cout<<ans<<endl;
}

水题。。直接暴力DP。。。
dp(pos,last)表示当前在pos。。上一次拿了last。最多能拿多少钱。。
Code。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=2010,maxlast=1010;
int dp[maxn][maxlast]={0};
int C[maxn],n;
void init()
{
cin>>n;
REP(i,n) REP(j,n/2+1)
dp[i][j]=-1;
for(int i=0;i<n;i++)
{
cin>>C[i];
C[i]+=i?C[i-1]:0;
}
}
int DP(int i,int last)
{
int rest=C[n-1]-C[i-1];
last<<=1;
if(n-i-1<=last)
return rest;
if(dp[i][last]!=-1)
return dp[i][last];
int get,ans=0;
for(int take=1;take<=last;take++)
{
get=rest-DP(i+take,take)+C[i+take]-C[i-1];
ans=max(ans,get);
}
return dp[i][last]=ans;
}
int main()
{
init();
cout<<DP(0,1)<<endl;
}

ＭＳ官网上没有了。。。
发这吧。。。
**********************************************************************
GREEN PROBLEMS
**********************************************************************
Four problems numbered 1 through 4
**********************************************************************

PROBLEM 1: Cow Exhibition [Brian Jacokes, 2003]

"Fat and docile, big and dumb, they look so stupid, they aren’t much
fun…"
– Cows with Guns by Dana Lyons

The cows want to prove to the public that they are both smart and fun.
In order to do this, Bessie has organized an exhibition that will be put
on by the cows. She has given each of the N (1 <= N <= 100) cows a
thorough interview and determined two values for each cow: the smartness
Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <=
1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She
believes that the total smartness TS of the group is the sum of the Si’s
and, likewise, the total funness TF of the group is the sum of the Fi’s.
Bessie wants to maximize the sum of TS and TF, but she also wants both of
these values to be non-negative (since she must also show that the cows
are well-rounded; a negative TS or TF would ruin this). Help Bessie
maximize the sum of TS and TF without letting either of these values
become negative.

PROBLEM NAME: smrtfun

INPUT FORMAT:

* Line 1: A single integer N, the number of cows

* Lines 2..N+1: Two space-separated integers Si and Fi, respectively
the smartness and funness for each cow.

SAMPLE INPUT (file smrtfun.in):

5
-5 7
8 -6
6 -3
2 1
-8 -5

OUTPUT FORMAT:

* Line 1: One integer: the optimal sum of TS and TF such that both TS
and TF are non-negative. If no subset of the cows has
non-negative TS and non- negative TF, print 0.

SAMPLE OUTPUT (file smrtfun.out):

8

OUTPUT DETAILS:

Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value
of TS+TF to 10, but the new value of TF would be negative, so it is not
allowed.

**********************************************************************

PROBLEM 2: Milking Grid [Tom Widland, 2003]

Every morning when they are milked, the Farmer John’s cows form a
rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <=
75) columns. As we all know, Farmer John is quite the expert on cow
behavior, and is currently writing a book about feeding behavior in
cows. He notices that if each cow is labeled with an uppercase letter
indicating its breed, the two-dimensional pattern formed by his cows
during milking sometimes seems to be made from smaller repeating
rectangular patterns.

Help FJ find the rectangular unit of smallest area that can be
repetitively tiled to make up the entire milking grid. Note that the
dimensions of the small rectangular unit do not necessarily need to
divide evenly the dimensions of the entire milking grid, as indicated
in the sample input below.

PROBLEM NAME: mgrid

INPUT FORMAT:

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: The grid that the cows form, with an uppercase letter
denoting each cow’s breed. Each of the R input lines has C
characters with no space or other intervening character.

SAMPLE INPUT (file mgrid.in):

2 5
ABABA
ABABA

OUTPUT FORMAT:

* Line 1: The area of the smallest unit from which the grid is formed

SAMPLE OUTPUT (file mgrid.out):

2

OUTPUT DETAILS:

The entire milking grid can be constructed from repetitions of the
pattern ‘AB’.

**********************************************************************

PROBLEM 3: Popular Cows [Brian Dean, 2003]

Every cow’s dream is to become the most popular cow in the herd. In a
herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <=
50,000) ordered pairs of the form (A, B) that tell you that cow A thinks
that cow B is popular. Since popularity is transitive, if A thinks B is
popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in
the input. Your task is to compute the number of cows that are
considered popular by every other cow.

PROBLEM NAME: popular

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A
thinks B is popular.

SAMPLE INPUT (file popular.in):

3 3
1 2
2 1
2 3

OUTPUT FORMAT:

* Line 1: A single integer that is the number of cows who are
considered popular by every other cow.

SAMPLE OUTPUT (file popular.out):

1

OUTPUT DETAILS:

Cow 3 is the only cow of high popularity.

**********************************************************************

PROBLEM 4: Beauty Contest [Quynh Tran, 2003]

Bessie, Farmer John’s prize cow, has just won first place in a bovine
beauty contest, earning the title ‘Miss Cow World’. As a result, Bessie
will make a tour of N (2 <= N <= 50,000) farms around the world in order
to spread goodwill between farmers and their cows. For simplicity, the
world will be represented as a two-dimensional plane, where each farm is
located at a pair of integer coordinates (x,y), each having a value in
the range -10,000 … 10,000. No two farms share the same pair of
coordinates.

Even though Bessie travels directly in a straight line between pairs of
farms, the distance between some farms can be quite large, so she wants to
bring a suitcase full of hay with her so she has enough food to eat on
each leg of her journey. Since Bessie refills her suitcase at every farm
she visits, she wants to determine the maximum possible distance she
might need to travel so she knows the size of suitcase she must bring.
Help Bessie by computing the maximum distance among all pairs of farms.

PROBLEM NAME: msworld

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Two space-separated integers x and y specifying
coordinate of each farm

SAMPLE INPUT (file msworld.in):

4
0 0
0 1
1 1
1 0

OUTPUT FORMAT:

* Line 1: A single integer that is the squared distance between the
pair of farms that are farthest apart from each other.

SAMPLE OUTPUT (file msworld.out):

2

OUTPUT DETAILS:

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of
2)

**********************************************************************

为了热身NOIP做了这个比赛。。
Fall 2003
水平有限。。我是沙茶。。
Problem 1:
有限制的背包问题。。
首先把S、B都大于0的选了。。
首先把S、B都小于或等于0的扔掉。。
那么所剩的就是一项正一项负了。。
按照其中的一项从大到小排序。。必然是如下形式。。
S B
＋ －
＋ －
。。。以（S的正负性为划分线）
－  +
－  ＋
。。。
设S已经有了HaveS（来源于先前已经选的东西。。肯定为正。。）
对上下两个分别运行背包。。求出上下两个容量各个选择容量时B和的最大值。。
为了方便把下面的那个背包价格S值全部取反。。这样当上面背包S为和X时。。下面的最多为X＋HaveS个。。
那么可以枚举上面的背包的S值。并用个变量记录下面的最小值。。若B和的最大值加上原来先前选的B的和大于0的话。。
用于更新最优解。。
P.S实际上直接暴力背包也可以。。但我估计要TLE。。进行一些优化之后可以快N多。。
几个小优化。。
首先若上面S的和为SumS，则不需要考虑下面SumS＋HaveS以后的状态。。因为根本不会用到。。
那么上面的的和自然要小。。
故在下面比上面短的时候可以交换上下两个。。（也就是交换S和B的位置）
众所周知DP需要一个序
直接的暴力DP没有考虑到题目的特性而运用了盲目的序。。
而结合题目的特性可以得出更好的序从而更高效的算法俄。。
Problem 2:
好难阿。。应该要用到分治吧。。我不会阿。。教教我阿。。
Promblem 3：
比较水的问题。。首先很明显要求出强连同分量。。然后转化成DAG。。
题目就是求一个节点到其他所有节点都有路径。。
因为没有环。。故一个节点如果有入度那么一定不能到达射向他的那个顶点。。不然就有环了。。
故只有没有入度的节点可能满足条件。。
如果有两个或以上的话。。那么这两个节点必不能互达。。故无解
如果有一个的话。。那个节点就是答案了。。
Problem 4:
OI中数据范围不一样的题目真不是一道题目阿。。
题目就是求N个点中最长的两点间距离。。假如N<1000的话直接暴力就OK了。。可惜N<50000
先求出凸包。。那么最长距离一定在凸包上。。
尽管平均意义上凸包上的点为N的三次方根的数量级。。那么直接枚举凸包上的点对就是N的三分之二次方。。
可惜那是平均意义上的。。很容易就可以构造出所有点都在凸包上的BT数据。。显然不行。。
实际上求凸包上的最远点利用对重点可以做到O（N）但我不会。。
我发现凸包上的点的距离是有单峰性的。。故可以用ternary查找其最值。。是logn的。。
加上排序。。还是NlogN。。勉强过吧。。

都说叫分段HASH。。
我觉得还是有点块状数组的感觉。。
用stl写平衡数很方便不过还是块状数组爽。。
可以是负数的阿。。好贱。。。
Code。。
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1000001,maxv=maxn*2,maxsize=1000,maxL=maxv/maxsize+10;
int C[maxv]={0};
int D[maxL]={0};
int n,Blocks;
void insert(int n)
{
C[n]++;
D[n/maxsize]++;
}
void del(int n)
{
C[n]–;
D[n/maxsize]–;
}
int getMin()
{
int i,j;
for(i=0;i<maxL;i++)
if(D[i]) break;
for(j=i*maxsize;;j++)
if(C[j]) break;
return j;
}
int getMax()
{
int i,j;
for(i=maxL-1;i>=0;i–)
if(D[i]) break;
for(j=(i+1)*maxsize-1;;j–)
if(C[j]) break;
return j;
}
int main()
{
cin>>n;int k,t;
long long ans=0;
while(n–)
{
scanf("%d",&k);
while(k–)
scanf("%d",&t),insert(t+maxn);
int Max=getMax(),Min=getMin();
ans+=Max-Min;
del(Max);del(Min);
}
cout<<ans<<endl;
}

356。。。
实际上求的就是N的排列中多少个排列只有K个不在位置上。。
那么答案就是C(N,K)*D(N-K)。。D是错排。。错排不知道者可以google之。。
但是高精十分BT。。实际上我怎么会没时间写模拟题呢？都是栽在这题上了。。555
不过总算是在比赛结束前过了。。
由于输出居然是要用不可约分数。。莫非要写一个高精度欧几里得算法吗？天阿。。
如果你真去写那你就傻了。。。
答案是D(n-k)/((n-k)!(k)!)
换句话说公约数的素因子《＝100。。。
那么一个个化就OK了。。
不过程序还是很长。。好羡慕JAVA阿。。自带高精度运算功能的。。
#include<iostream>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=110;
int Prime[]=
{2,3,5,7,11,
13,17,19,23,29
,31,37,41,43,47
,53,59,61,67,71
,73,79,83,89,97};
const int ps=25;
int N,K;
struct Num
{
int P;
Num(){memset(P,0,sizeof(P));}
void mult(int a)
{
for(int i=0;i<ps;i++)
{
if(a==1) break;
while(a%Prime[i]==0)
a/=Prime[i],P[i]++;
}
}
void divide(int a)
{
for(int i=0;i<ps;i++)
{
if(a==1) break;
while(a%Prime[i]==0)
a/=Prime[i],P[i]–;
}
}
};
const int maxlen=200;
struct BigNum
{
int Q[maxlen],last;
BigNum(int x=0)
{memset(Q,0,sizeof(Q));Q[0]=x;last=0;}
int operator[](int v) const
{return Q[v];}
int& operator[](int v)
{return Q[v];}
BigNum operator+(const BigNum&x)
{
BigNum now;now.last=max(last,x.last);
int d=0;
for(int i=0;i<=now.last;i++)
{
d+=Q[i]+x[i];
now[i]=d%10;
d/=10;
}
while(d)
{
now[++now.last]=d%10;
d/=10;
}
return now;
}
void operator*=(int x)
{
int d=0;
for(int i=0;i<=last;i++)
{
d+=Q[i]*x;
Q[i]=d%10;
d/=10;
}
while(d>0)
{
Q[++last]=d%10;
d/=10;
}
}
BigNum operator*(const BigNum&x)
{
BigNum now;now.last=x.last+last;
memset(now.Q,0,sizeof(Q));
for(int i=0;i<=last;i++)
for(int j=0;j<=x.last;j++)
now[i+j]+=Q[i]*x[j];
int d=0;
for(int i=0;i<=now.last;i++)
{
d+=now[i];
now[i]=d%10;
d/=10;
}
while(d)
{
now[++now.last]=d%10;
d/=10;
}
}
int Mod(int x)
{
int d=0;
for(int i=last;i>=0;i–)
{
d*=10;
d+=Q[i];
d%=x;
}
return d;
}
void Divide(int x)
{
int rest=0;
for(int i=last;i>=0;i–)
{
rest=rest*10+Q[i];
Q[i]=rest/x;
rest%=x;
}
while(Q[last]==0)
last–;
}
void operator=(const BigNum&x)
{
last=x.last;
memmove(Q,x.Q,sizeof(Q));
}
void show()
{
for(int i=last;i>=0;i–)
cout<<Q[i];
}
};
BigNum Get(Num x)
{
BigNum now(1);
for(int i=0;i<ps;i++)
{
for(int j=0;j<x.P[i];j++)
now*=Prime[i];
}
return now;
}
BigNum D[maxn];
void CalD(int n)
{
D[0][0]=1;D[1][0]=0;
for(int i=2;i<=n;i++)
{
D[i]=D[i-1]+D[i-2];
D[i]*=(i-1);
}
}
Num C;
int main()
{
cin>>K>>N;
if(N-K==1)
{
cout<<0<<endl;
return 0;
}
CalD(N-K);
for(int i=1;i<=K;i++)
C.mult(i);
for(int i=1;i<=N-K;i++)
C.mult(i);
BigNum left,right;
left=D[N-K];
for(int i=0;i<ps;i++)
{
while(left.Mod(Prime[i])==0&&C.P[i]>0)
left.Divide(Prime[i]),C.P[i]–;
}
right=Get(C);
left.show();cout<<"/";right.show();
}
357。。。好无聊的水题阿。。要是能跳明显一开始就跳。。
然后枚举每个开始UP or DOWN的点算答案。。。
Code。。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>2;
bool Digit[10]={0};
bool UP,DOWN,FLY;
int dist[100],s,t;
void init()
{
cin>>Digit[1]>>Digit[2]>>Digit[3]>>UP>>
Digit[4]>>Digit[5]>>Digit[6]>>DOWN>>
Digit[7]>>Digit[8]>>Digit[9]>>FLY>>Digit[0];
}
void renew(int&x,int c)
{
x=min(x,c);
}
void Fly()
{
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
if(Digit[i]&&Digit[j])
renew(dist[i*10+j],3);
}
void Go(int j)
{
int c=dist[j];
if(UP)
renew(dist[(j+1)%100],c+1);
if(DOWN)
renew(dist[(j+99)%100],c+1);
}
int main()
{
init();cin>>s>>t;
REP(i,100) dist[i]=inf;
dist[s]=0;
if(FLY)
Fly();
for(int i=0;i<10;i++)
if(Digit[i])
renew(dist[i],1);
int ans=dist[t];
for(int i=0;i<100;i++)
if(dist[i]!=inf)
{
if(UP)
renew(ans,(t-i+100)%100+dist[i]);
if(DOWN)
renew(ans,(i-t+100)%100+dist[i]);
}
if(ans==inf)
cout<<-1<<endl;
else
cout<<ans<<endl;
}

参加了虚拟比赛11道只做了5道。。SB阿。。
346和353都是模拟的题目。。懒得做了。。
347。。看代码吧。。
Code。。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=100+10;
string A[maxn];
bool cmp(const string&A,const string&B)
{
return (A+B)<(B+A);
}
int main()
{
int N;cin>>N;
for(int i=0;i<N;i++)
cin>>A[i];
sort(A,A+N,cmp);
for(int i=0;i<N;i++)
cout<<A[i];
cout<<endl;
}
350。。
有点意思的题目。。
首先如果有一个解。。那么把这些数全部xor上一个数的话。。还是一个解。。
因为(a xor x) xor (b xor x)=(a xor b) xor (x xor x)= a xor b xor 0= a xor b。。。
所以就当里面有一个0好了。。
然后特判掉M＝1的情况。。
那么注意到。。如果B中有两个数A和B。。A xor B＝另一个数C。。
那么A和B必然有公共的元素。。
那么就很简单了。。找两个有公共元素的B中的数i,j。。强行将它们的公共元素设为0。。
那么现在就有3个数了0，i,j。。
那么只要找其他的有0的元素就可以求出一个解了。。怎么求找呢？
如果B中数x不是i xor j。。又跟i和j都有公共元素。。那么这个公共元素只能是0了。。那么这个数就属于解了。。。
就这样找数。。。
#include<iostream>

#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100;
int M,B[maxn];
bool HaveCommon(int i,int j,int&k)
{
int now=B[i]^B[j];
for(k=0;k<M;k++)
if(B[k]==now)
return true;
return false;
}
int main()
{
cin>>M;
REP(i,M) cin>>B[i];
if(M==1)
{
cout<<(B[0]-1)<<" "<<(B[0]^(B[0]-1))<<endl;
return 0;
}
int ans[maxn];ans[0]=0;int i,j,k;
bool mark[maxn]={0};
for(i=0;i<M;i++)
for(j=i+1;j<M;j++)
if(HaveCommon(i,j,k))
{
ans[1]=B[i],ans[2]=B[j],mark[i]=mark[j]=mark[k]=true;
goto out;
}
out:
int cnt=3,t;
for(int o=0;o<M;o++) if(!mark[o])
if(HaveCommon(o,i,t)&&HaveCommon(o,j,t))
ans[cnt++]=B[o];
cout<<ans[0];
for(int i=1;i<cnt;i++)
cout<<" "<<ans[i];
cout<<endl;
}355。。。
构造题。。很明显答案是logN+1…
染色的话只要染成素因数个数就OK了。。
#include<iostream>
using namespace std;
int num(int p)
{
int cnt=0;
while(p%2==0)
{cnt++;p/=2;}
while(p%3==0)
{cnt++;p/=3;}
for(int i=5,j=25,k=4;j<=p;i+=(k=6-k),j+=(i*2-k)*k)
{
while(p%i==0)
{cnt++;p/=i;}
}
if(p!=1)
cnt+=2;
else
cnt+=1;
return cnt;
}
int main()
{
int N,x,cnt=0;cin>>N;x=1;
while(x<=N){cnt++;x*=2;}
cout<<cnt<<endl;
for(int i=1;i<N;i++)
cout<<num(i)<<" ";
cout<<num(N)<<endl;
}