250p DoorsGame(一行并列的格子,每個(gè)格子中有某種顏色的障礙物,最多15種顏色.A在最左端,B在最右端...)
15種顏色,可以直接極大極小狀態(tài)DP.
可以直接貪心,計(jì)數(shù)只有A需要拿走的顏色數(shù),只有B需要拿走的,和兩都要拿走的.
500p DrawingLines(兩排點(diǎn),每排n個(gè).上排的和下排的連線.事先已經(jīng)有些線連好了.求考慮所有的連線方案時(shí),連線交點(diǎn)個(gè)數(shù)的期望)
三類(lèi)計(jì)數(shù):事先已經(jīng)連好的線間的交點(diǎn)數(shù).新增連線和原有連線的交點(diǎn)數(shù)期望.新增連線之間交點(diǎn)期望.
1000p BuildingRoads若干個(gè)點(diǎn)(<=2500)和若干條邊的無(wú)向圖.每個(gè)點(diǎn)有點(diǎn)權(quán).現(xiàn)在有4對(duì)特殊的點(diǎn).要求選一些路徑出來(lái),使每對(duì)點(diǎn)連通(不同對(duì)間不要求連通),總代價(jià)是經(jīng)過(guò)的所有點(diǎn)權(quán)之和.
雖然只有4對(duì)點(diǎn),但是也不要一口咬定是狀態(tài)DP(250p血的教訓(xùn)),雖然的確是狀態(tài)DP...
最后不同點(diǎn)對(duì)是可以不屬于同一連通分量的,所以只1次DP不容易設(shè)計(jì)狀態(tài).
第1次dp: dp[mask][i], mask表示連通子樹(shù)中包含的特殊點(diǎn), i表示這棵子樹(shù)的代表節(jié)點(diǎn)(or根節(jié)點(diǎn)).
第2次dp: dp2[mask], mask表示已經(jīng)包含的特殊點(diǎn), 不要求是連通的, 但是對(duì)應(yīng)的2個(gè)點(diǎn)要在同一分量.
這個(gè)過(guò)程就像,先把每個(gè)子模塊做好, 再將他們拼接整合.
ps.1000p與steiner tree有關(guān)聯(lián).
http://acm.hdu.edu.cn/showproblem.php?pid=3311
給定6個(gè)基礎(chǔ)點(diǎn)，和1000個(gè)輔助點(diǎn)，以及無(wú)向邊若干。
求一棵代價(jià)最小的生成子樹(shù)，使得6個(gè)基礎(chǔ)點(diǎn)連通。
http://en.wikipedia.org/wiki/Steiner_tree_problem
方法一：
狀態(tài)DP。
一棵樹(shù)，實(shí)際上可以看成是由兩棵子樹(shù)拼接而成，或者一棵樹(shù)擴(kuò)展一條邊篩選。而要完整地表示一棵子樹(shù)，需要記錄它的根，和對(duì)6個(gè)基礎(chǔ)點(diǎn)的覆蓋狀態(tài)。
這樣求一棵大樹(shù)，可以枚舉接合點(diǎn)，以及兩個(gè)子樹(shù)的覆蓋狀態(tài)。
若dp[i][j]，i表示接合點(diǎn)，j表示覆蓋狀態(tài)，那么dp[i][j]=min{dp[i][k]+dp[i][j^k]}。
直接擴(kuò)展一條邊, 可以在保持j不變的情況下, 優(yōu)先隊(duì)列廣搜, 大大降低復(fù)雜度.
方法二：
spfa。
dp[i][j]意義同上。一個(gè)點(diǎn)(i,j)，對(duì)每個(gè)鄰接點(diǎn)i'，枚舉那一頭的狀態(tài)j'，然后用dp[i][j]+dp[i'][j']+way[i][i']去更新dp[i][j|j']和dp[i'][j|j']。
ps. topcoder srm 470 div1 level3是此題升級(jí)版.
??1?#include?<string>
??2?#include?<vector>
??3?#include?<list>
??4?#include?<map>
??5?#include?<queue>
??6?#include?<stack>
??7?#include?<set>
??8?#include?<iostream>
??9?#include?<sstream>
?10?#include?<numeric>
?11?#include?<algorithm>
?12?#include?<cmath>
?13?#include?<cctype>
?14?#include?<cstdlib>
?15?#include?<cstdio>
?16?#include?<cstring>
?17?using?namespace?std;
?18?
?19?#define?CLR(x)?memset((x),0,sizeof(x))
?20?#define?SET(x,y)?memset((x),(y),sizeof(x))
?21?#define?REP(i,x)?for(int?i=0;i<(x);i++)
?22?#define?FOR(i,x,y)?for(int?i=(x);i<(y);i++)
?23?#define?VI?vector<int>?
?24?#define?PB(i,x)?(i).push_back(x)
?25?#define?MP(x,y)?make_pair((x),(y))
?26?
?27?struct?EDGE{
?28?????int?v,e,d;
?29?}edg[20000];
?30?int?ecnt,?gg[1006];
?31?
?32?struct?HEAP{
?33?????int?v,d;
?34?????void?set(int?nv,?int?nd){v=nv;d=nd;}
?35?}hp[1006*(1<<6)*10];
?36?int?sz;
?37?bool?vis[1006];
?38?
?39?int?dp[1006][1<<6];
?40?int?N,?M,?P;
?41?
?42?bool?cmp(const?HEAP?&a,?const?HEAP?&b)
?43?{?return?a.d>b.d;?}
?44?
?45?void?addedge(int?u,?int?v,?int?d)
?46?{
?47?????edg[ecnt].v=v;?edg[ecnt].d=d;?edg[ecnt].e=gg[u];?gg[u]=ecnt++;
?48?????edg[ecnt].v=u;?edg[ecnt].d=d;?edg[ecnt].e=gg[v];?gg[v]=ecnt++;
?49?}
?50?
?51?int?steiner()
?52?{
?53?????int?up?=?1<<(N+1);
?54?????SET(dp,-1);
?55?????REP(i,N+1)?dp[i][1<<i]=0;
?56?????FOR(i,N+1,N+M+1)?dp[i][0]=0;
?57?????REP(i,up){
?58?????????REP(j,N+M+1){
?59?????????????for(int?k=i;?k>0;?k=(k-1)&i){
?60?????????????????if(dp[j][k]!=-1?&&?dp[j][i^k]!=-1)
?61?????????????????????if(dp[j][i]==-1?||?dp[j][i]>dp[j][k]+dp[j][i^k])
?62?????????????????????????dp[j][i]=dp[j][k]+dp[j][i^k];
?63?????????????}
?64?????????}
?65?????????sz=0;
?66?????????CLR(vis);
?67?????????REP(j,N+M+1)?if(dp[j][i]!=-1){
?68?????????????hp[sz++].set(j,dp[j][i]);
?69?????????????push_heap(hp,?hp+sz,?cmp);
?70?????????}
?71?????????while(sz){
?72?????????????int?now=hp[0].v;
?73?????????????pop_heap(hp,?hp+sz--,cmp);
?74?????????????if(vis[now])continue;
?75?????????????vis[now]=true;
?76?????????????for(int?e=gg[now];?~e;?e=edg[e].e){
?77?????????????????int?to=edg[e].v,?td=dp[now][i]+edg[e].d;
?78?????????????????if(dp[to][i]==-1?||?dp[to][i]>td){
?79?????????????????????dp[to][i]=td;
?80?????????????????????hp[sz++].set(to,td);
?81?????????????????????push_heap(hp,?hp+sz,?cmp);
?82?????????????????}
?83?????????????}
?84?????????}
?85?????}
?86?????return?dp[0][up-1];
?87?}
?88?
?89?int?main()
?90?{
?91?????while(~scanf("%d?%d?%d",?&N,?&M,?&P)){
?92?????????int?u,?v,?d;
?93?????????SET(gg,-1);?ecnt=0;
?94?????????REP(i,N+M){
?95?????????????scanf("%d",?&d);
?96?????????????addedge(0,i+1,?d);
?97?????????}
?98?????????REP(i,P){
?99?????????????scanf("%d?%d?%d",?&u,?&v,?&d);
100?????????????addedge(u,v,d);
101?????????}
102?????????int?ret=steiner();
103?????????printf("%d\n",?ret);
104?????}
105?????return?0;
106?}
#line
?$NEXTLINENUMBER$?"$FILENAME$"
#include?
<
string
>
#include?
<
vector
>
#include?
<
list
>
#include?
<
map
>
#include?
<
queue
>
#include?
<
stack
>
#include?
<
set
>
#include?
<
iostream
>
#include?
<
sstream
>
#include?
<
numeric
>
#include?
<
algorithm
>
#include?
<
cmath
>
#include?
<
cctype
>
#include?
<
cstdlib
>
#include?
<
cstdio
>
#include?
<
cstring
>
using
?
namespace
?std;
#define
?CLR(x)?memset((x),0,sizeof(x))
#define
?SET(x,y)?memset((x),(y),sizeof(x))
#define
?REP(i,x)?for(int?i=0;i<(x);i++)
#define
?FOR(i,x,y)?for(int?i=(x);i<(y);i++)
#define
?VI?vector<int>?
#define
?PB(i,x)?(i).push_back(x)
#define
?MP(x,y)?make_pair((x),(y))
class
?$CLASSNAME$?{
public
:
????$RC$?$METHODNAME$($METHODPARMS$)?
????{
????????
//
have?some?fun?here
????}
????$TESTCODE$
};
//
?BEGIN?CUT?HERE?
int
?main()
{
????$CLASSNAME$?___test;?
????___test.run_test(
-
1
);?
????system(
"
pause
"
);
}?
?
//
?END?CUT?HERE?
Two Professors
CERC 2008
題目大意:給n條線段,要求劃分成盡可能少的子集,使得在同一個(gè)子集中的線段兩兩不重疊.
同時(shí)限定線段1和線段2不能在同一子集中.
記每條線段為[Li,Ri], 每個(gè)子集的最右端為Bi.
記線段1和2中,L較小的那個(gè)為X,另一個(gè)為Y.
如果沒(méi)有那個(gè)限定,容易想到貪心的方法:將所有線段按L從小到大排序.然后依次處理線段k,如果當(dāng)前存在某個(gè)集合的Bi<=Lk,就將Lk加入此集合中,并更新Bi=Rk.否則新開(kāi)一個(gè)集合放入k.模擬這個(gè)過(guò)程,最后的集合數(shù)就是答案.用堆維護(hù)已有集合的信息,時(shí)間復(fù)雜度是O(nlgn).
有了限制條件后,原方法不適用了,因?yàn)樵赬與Y之間處理的線段,對(duì)Y有后效性.這會(huì)使得單純按照剛才的方法隨意貪心,可能輪到Y(jié)時(shí),只有X所在集合的Bi<=LY,迫使必須開(kāi)新集合.但實(shí)際上,有可能可以通過(guò)調(diào)整X與Y之間的線段排列結(jié)構(gòu),使Y避開(kāi)X.
問(wèn)題關(guān)鍵就是如何判斷能否調(diào)整(并不用關(guān)心詳細(xì)的調(diào)整步驟).
當(dāng)一條線段(P)面臨多個(gè)可插入的集合時(shí),之前的方法是隨意選一個(gè),而不合適的決策正在此產(chǎn)生.下面構(gòu)造一個(gè)情景:
假設(shè)P可以在兩個(gè)集合s,t中選擇,而X在s中.
現(xiàn)在P選擇加入t.
接下來(lái)按部就班地處理.
輪到Y(jié)選時(shí),它只能選擇加入s,或者開(kāi)新的集合.
這時(shí)候,我們能得知,如果當(dāng)初P選擇的是s,緊隨其后的其它選擇也相應(yīng)地對(duì)調(diào),那么Y此時(shí)肯定面臨的是只能加入t,或者開(kāi)新的集合.
這樣Y當(dāng)然直接加入t就行了.
這說(shuō)明,只要存在一個(gè)這樣的P,當(dāng)Y遭遇X時(shí),肯定存在形狀對(duì)稱(chēng)的另一個(gè)局面使Y避開(kāi)X,而P就是關(guān)鍵先生.
所以只需稍微改造之前的算法,在處理X與Y之間的線段時(shí),判斷并記錄下是否出現(xiàn)過(guò)可選局面.這樣就能正確處理Y遭遇X的情形了.
其它情形時(shí)策略不變(可以證明這樣的解是最優(yōu)的).
代碼略...
1. 如果其中一個(gè)操作數(shù)為long double類(lèi)型,則另一個(gè)操作數(shù)被轉(zhuǎn)換為long double.
2. 否則,如果其中一個(gè)操作數(shù)為double, 則另一個(gè)操作數(shù)被轉(zhuǎn)換為double.
3. 否則,如果其中一個(gè)操作數(shù)為float, 則另一個(gè)操作數(shù)也轉(zhuǎn)換為float.
4. 否則,兩個(gè)操作數(shù)進(jìn)行 "整型升級(jí)":
a. 如果其中一個(gè)操作數(shù)為unsigned long int, 則另一個(gè)操作數(shù)也被視為unsigned long int.
b. 否則,如果其中一個(gè)操作數(shù)為long int,而另一個(gè)操作數(shù)類(lèi)型是unsigned int, 并且long int能夠表示unsigned int的所有值,則另一個(gè)操作數(shù)也被視為long int;如果long int不能表示unsigned int的所有值,則兩個(gè)數(shù)都被視為unsigned long int.
c. 否則, 如果其中一個(gè)操作數(shù)是long int,則另一個(gè)操作數(shù)也被視為long int.
d. 否則, 如果其中一個(gè)操作數(shù)是unsigned int, 則另一個(gè)操作數(shù)也被視為unsigned int.
e. 否則, 兩個(gè)操作數(shù)都被視為int.
Maximal Cliques on Circular-arc Graph
合肥2008現(xiàn)場(chǎng)賽, 2009網(wǎng)賽 Guarders
In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. --wiki
uestc_floyd的做法是搜+剪枝.
zzh@bupt大牛想出二分圖匹配的做法:
固定某個(gè)區(qū)間Li肯定選中, 則剩下的區(qū)間里, 可能被選擇的只有與Li有交集的那些.
(*)將那些區(qū)間分兩類(lèi): 與Li的左邊界交的, 與Li的右邊界交的.
易知與Li兩邊界都交的是肯定可以選的, 不會(huì)產(chǎn)生不合要求的局面.
不合要求的情況只可能是, 某個(gè)一類(lèi)區(qū)間和某個(gè)二類(lèi)區(qū)間沒(méi)有交, 卻同時(shí)選了它們.
所以二分圖建圖方法為, 若某個(gè)一類(lèi)區(qū)間和某個(gè)二類(lèi)區(qū)間沒(méi)有交, 則連一條邊.
二分圖的頂點(diǎn)數(shù)+1-最大匹配數(shù)即為L(zhǎng)i對(duì)應(yīng)的最優(yōu)解.
枚舉每個(gè)Li.
理論時(shí)間復(fù)雜度相當(dāng)高, O(n)*O(匹配), 實(shí)現(xiàn)上可以加入排序, 最優(yōu)解剪枝等方案.
ps. (*)非常巧妙的想法! 非常藝術(shù)!
摘要: 題目給出一棵樹(shù)(N<=10000)以及所有邊的權(quán)(<=10000). 現(xiàn)在要求對(duì)任意查詢(xún)Q(<=10^8), 判斷是否存在一條邊權(quán)之和恰好為Q的路徑.標(biāo)程的方法暫時(shí)沒(méi)看懂= =... 我用樹(shù)的分治做(更多相關(guān)內(nèi)容見(jiàn)09國(guó)家集訓(xùn)隊(duì)漆子超的論文)考慮一棵以root為根的子樹(shù), 那么在這棵子樹(shù)中, 有多少條 v1->root->v2 的路徑長(zhǎng)恰好為Q呢?...
閱讀全文
后綴數(shù)組,KMP擴(kuò)展,自動(dòng)機(jī)
題目要求4000個(gè)長(zhǎng)度為200的字串的最長(zhǎng)公共子串.
只需選一個(gè)串作為基串, 枚舉它的所有后綴串S[i..len], 求出其它串與這個(gè)子串的LCP. 最后選最大的輸出.
關(guān)于求串S與串T所有后綴的LCP, 林希德的論文講了擴(kuò)展KMP算法. 不過(guò)我想出另一種方法:
把S和T直接連接得到新串U. 按正常KMP的方法求U的next數(shù)組, 不過(guò)當(dāng)p指向U[len[S]+1]即原T串的首字母時(shí), 直接將此位的next置為0.
最后min(len[S], next[k]) 就是串T[1..(k-len[S])]與串S的lcp長(zhǎng)度.
代碼如下:
1
#include <iostream>
2using namespace std;
3
4char wd[4000][201];
5int cnt[201][201], vis[201][201];
6char ss[401];
7int next[401];
8int N;
9
10bool readin()
11
{
12
scanf("%d",&N);
13 if(N==0)return false;
14
15 for(int i=0; i<N; i++)
16 scanf("%s",wd[i]);
17 return true;
18
}
19
20int mycmp(char *s1, int l1, char *s2, int l2)
21{
22 if(l1!=l2) return (l2-l1);
23 while(--l1 && *s1==*s2) s1++, s2++;
24 return (*s1-*s2);
25}
26
27void mycpy(char *s1, char *s2, int l)
28{
29 while(l--) *(s1++)=*(s2++);
30 *s1=0;
31}
32
33void solve()
34{
35 memset(cnt,0,sizeof(cnt));
36 memset(vis,0,sizeof(vis));
37
38 int l0=strlen(wd[0]);
39 strcpy(ss,wd[0]);
40 char ans[201]="";
41
42
for(int p=0; p<l0; p++){
43 char *s=&ss[p];
44 for(int i=1; i<N; i++){
45 strcpy(&ss[l0], wd[i]); //連接兩個(gè)串
46 int l1=l0-p+strlen(wd[i]);
47 next[0]=-1;
48 int p0=-1, p1=0;
49 while(p1<l1){
50 while(p0>=0 && s[p0]!=s[p1])
51 p0=next[p0];
52 next[++p1]=++p0;
53 if(p1==l0-p) //此位置0
54 next[p1]=0, p0=0;
55 if(p1>=l0-p){
56 int len=min(l0-p, next[p1]);
57 if(vis[p][p+len-1]!=i)
58 vis[p][p+len-1]=i, cnt[p][p+len-1]++;
59
}
60 }
61 }
62
63 for(int j=l0-1; j>=p; j--){
64 if(cnt[p][j]==N-1){
65 if(mycmp(&ss[p], j-p+1, ans, strlen(ans))<0)
66 mycpy(ans, &ss[p], j-p+1);
67 }
68 }
69 }
70
71 if(ans[0]==0)
72 puts("IDENTITY LOST");
73 else
74 puts(ans);
75}
76
77int main()
78{
79 while(readin()){
80 solve();
81 }
82}
83
幾道線性的題目
Tanks a Lot
題意:
一個(gè)圓,周長(zhǎng)為整數(shù)n(n<=10^7).圓周上有k(k<=n)個(gè)加油站,每個(gè)加油站有整數(shù)的油量w[i],所有加油站總油量恰好為n. 行車(chē)單位路程耗油量為1, 車(chē)的初始油量為0. 問(wèn),以哪些加油站為起點(diǎn)可以走完一周? 分別判斷順時(shí)針和逆時(shí)針的情況.
解:
棧的應(yīng)用.
考慮單個(gè)點(diǎn)v1,沿路徑v1,v2,v3,...走,則從v1能完成一周的充要條件是對(duì)任意的k,S[1,k-1]-C[1,k]>=0,其中S[1,k-1]為這段路上總加油量,C[1,k]為總耗油量.
再考慮先后2個(gè)點(diǎn)vk1,vk2. 設(shè)沿路徑vk1,vp1,vp2,...,vk2,...vpm走.如果vk1和vk2都能到達(dá)vpm,肯定vk1必需先能夠達(dá)到vk2. 這說(shuō)明從vk1到vpm時(shí)的剩余油量肯定>=vk2到vpm時(shí)的剩余油量. 有了這個(gè)單調(diào)性,再加上油余量的區(qū)間性以及區(qū)間可合并性, 就可以維護(hù)一個(gè)單調(diào)的棧.棧中頂點(diǎn)的訪問(wèn)次序遞增,剩余油量遞減且不小于0.正掃一遍反掃一遍分別判斷順時(shí)針和逆時(shí)針.
A Walk in the Park
題意:
二維平面上有一些(N<=10^5)無(wú)限長(zhǎng)的水平線和豎直線(M<=10^5), 以及一些不在線上的點(diǎn). 人可以沿任意線走.
稱(chēng)某個(gè)點(diǎn)是可見(jiàn)的, 當(dāng)且僅當(dāng)人能站在某條線上, 以垂直于線的方向正對(duì)此點(diǎn),并且人與點(diǎn)的連線上沒(méi)有其它點(diǎn)阻礙視線.
求可見(jiàn)的點(diǎn)的個(gè)數(shù).
解:
排序+離散化+線性掃描; 二分
先考慮能否從水平線上看到某個(gè)點(diǎn).
將點(diǎn)按y坐標(biāo)排序.
對(duì)同一x上的所有點(diǎn),考慮不是起始或末尾的相鄰的兩個(gè)點(diǎn),它們能被看到,當(dāng)且僅當(dāng)它們之間有直線.
這樣可以把直線也按y排序, 順序掃一遍.對(duì)某個(gè)坐標(biāo)x,記錄它上一個(gè)點(diǎn)的y值.
離散化和排序都是nlogn的, 但是線性掃描的思路很巧,值得注意.
直接二分更簡(jiǎn)單,對(duì)每對(duì)相鄰的點(diǎn),二分查找它們之間是否有線段.
uva4031 Integer Transmission (DP)題意:傳送一個(gè)長(zhǎng)度在64之內(nèi)的01串,第i時(shí)刻發(fā)送出第i字節(jié)(i=0,1,...,L-1).對(duì)任意第i時(shí)刻發(fā)出的字節(jié),它有可能在i+1,i+2,...,i+d+1(d<=L)中的任一時(shí)刻到達(dá)接收端.當(dāng)同一時(shí)刻有多個(gè)字節(jié)同時(shí)到達(dá)時(shí),這些字節(jié)可以任意排列.問(wèn)接收端可能收到多少種不同串? 并求出二進(jìn)制最小的和最大的串.按位DP, 關(guān)鍵是確定前i位至多能有多少個(gè)0/1,至少必須有多少個(gè)0/1. 此題與windy's abc很相似, 但多了處變化.考慮 d=3, 原串為 1101011, 顯然第1個(gè)1永遠(yuǎn)不可能跑到第2個(gè)0右邊. 字符串的錯(cuò)位,本質(zhì)上是某些1把它右邊d之內(nèi)的0擠到左邊了. 因此對(duì)1, 它實(shí)際能向右移多少位,取決于它右邊d之內(nèi)有多少個(gè)0.這樣預(yù)處理后按位DP即可.構(gòu)造最小/最大數(shù),只需盡量把1/0往低位扔就行了.代碼:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 #include <cmath>
7 using namespace std;
8
9 typedef unsigned long long ull;
10
11 int mi[2][130], mx[2][130];
12 ull dp[65][65];
13 int b[65];
14 int N,D;
15 ull K;
16 int CAS;
17
18 void init()
19 {
20 int i,j,k;
21 ull t;
22 memset(b,0,sizeof(b));
23 for(t=K, i=N; t; i--){
24 b[i] = t&1;
25 t>>=1;
26 }
27 int c[2][130];
28 memset(c,0,sizeof(c));
29 for(i=1; i<=N; i++)
30 c[b[i]][i]++;
31 for(i=N; i>=1; i--)
32 c[0][i] += c[0][i+1], c[1][i] += c[1][i+1];
33 memset(mi, 0, sizeof(mi));
34 memset(mx, 0, sizeof(mx));
35 for(i=1; i<=N; i++){
36 mx[b[i]][ min(N, i+c[b[i]^1][i+1]-c[b[i]^1][i+D+1]) ] ++;
37 }
38 for(i=N; i>=1; i--){
39 mx[0][i] += mx[0][i+1];
40 mx[1][i] += mx[1][i+1];
41 mi[0][i] = max(0, N+1-i-mx[1][i]);
42 mi[1][i] = max(0, N+1-i-mx[0][i]);
43 }
44 }
45
46 ull dodp()
47 {
48 int i,j,k,p;
49 ull ret = 0;
50 memset(dp,0,sizeof(dp));
51 for(i=0; i<=N; i++)
52 dp[N][i] = 1;
53 for(p=N; p>=1; p--){
54 for(i=mi[0][p]; i<=mx[0][p]; i++){
55 j=N+1-p-i;
56 if(j<mi[1][p] || j>mx[1][p]) continue;
57 if(dp[p][i]==0)continue;
58 if(p==1){ ret += dp[p][i]; continue; }
59 dp[p-1][i] += dp[p][i];
60 dp[p-1][i+1] += dp[p][i];
61 }
62 }
63 return ret;
64 }
65
66 void getans(ull &xx, ull &ii)
67 {
68 int i,j,k;
69 int c0[2][65],c1[2][65];
70 memset(c0,0,sizeof(c0));
71 memset(c1,0,sizeof(c1));
72 for(i=1; i<=N; i++){
73 if(b[i]==0)
74 c0[0][i]++, c1[0][min(N,i+D)]++;
75 else
76 c1[1][i]++, c0[1][min(N,i+D)]++;
77 }
78 //for(i=1; i<=N; i++
79 xx = ii = 0;
80 for(i=1; i<=N; i++){
81 while(c0[0][i]--) ii = (ii<<1);
82 while(c0[1][i]--) ii = (ii<<1)|1;
83
84 while(c1[1][i]--) xx = (xx<<1)|1;
85 while(c1[0][i]--) xx = (xx<<1);
86 }
87 }
88
89 void solve()
90 {
91 int i,j,k;
92 printf("Case %d: ", ++CAS);
93 printf("%llu ", dodp());
94 ull xx,ii;
95 getans(xx, ii);
96 printf("%llu %llu\n", ii, xx);
97 }
98
99 int main()
100 {
101 CAS = 0;
102 while(scanf("%d",&N)!=EOF && N){
103 scanf("%d %llu",&D,&K);
104 init();
105 solve();
106 }
107 }
108