2 shunfurh shunfurh 于 2017.01.02 22:38 提问

Binary Witch

Description

Once upon a time in the silent depths of digital forests there lived a Binary Witch. She was able to forecast weather, telling for any day in the future whether it will be rainy or sunny.

Her magic was based on the following ancient rule: let a1, a2, ..., aN be the sequence of binary digits, where ai = 0 indicates that i-th day was rainy, and ai = 1 -- that it was sunny. To predict the weather in day N+1, consider the t-postfix aN-t+1, aN-t+2, ..., aN consisting of the last t elements. If that postfix is encountered somewhere before the position N-t+1, i.e. if there is such k <= N-t, that ak = aN-t+1, ak+1 = aN-t+2, ..., ak+t-1 = aN then the predicted value will be ak+t.

If there is more than one occurrence of t-postfix, then the rightmost one (with maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she predicted rain ("0"). If prediction for more than one day is needed, it is assumed that all previous days are predicted correctly, so if first predicted value is b, then we make forecast for day N+2 based on N+1 values, where aN+1 = b.

Because the witch was burned long ago, your task is to write a program to perform her arcane job.
Input

First line of input file contains two integers N (1 <= N <= 1000000) and L (1 <= L <= 1000), separated by space. Second line contains a string of N characters "0" and "1".
Output

Output file must contain a single string of L characters, which are forecasts for days N+1, N+2, ..., N+L.
Sample Input

10 7
1101110010
Sample Output

0100100

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.07 23:52
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Binary Witch
Description Once upon a time in the silent depths of digital forests there lived a Binary Witch. She was able to forecast weather, telling for any day in the future whether it will be rainy or sunn
poj 2541 Binary Witch
#include #include char str[1001000]; int next[1001000]; int n,m; int main() { while(scanf("%d%d%s",&n,&m,str)!=EOF) { int end=n+m; while(n<end) {
poj 2541 binary witch
做kmp专题遇到了这题,专题里说用逆序kmp,我觉得会超时...找了一份逆序kmp代码试了一下0ms!.. 不清楚为什么,求解释... 我觉得正确的做法是状态压缩dphttp://www.cnblogs.com/swm8023/archive/2012/08/03/2621288.html,这个人说的靠谱! dp[i][j]代表长度为i,状态为j的最晚出现位置,当前字符为第i个的话,需要i-2
POJ 2541 Binary Witch
比较水的一题,正解觉得是状压,但是第一眼看去就觉得是hash,其实本题hash状压是一样的。 #include //hash #include #include #include #include #include using namespace std; typedef long long LL; #define lson l, m, rt << 1 #define rson m +
MATALB——多if语句、多if..else语句和witch语句的用法及区别
先举上栗子: 1、多if语句: a=2; if(a==1) b=1; end if(a==2) b=2; end if(mod(a,2)==0) b=3; %求余 end 此结果为:b=3 2、多if..else语句: a=2; if(a==1) b=1; else if(a==2) b=2; else if(mod(a,2)==0) b=3; end end e
poj 2541 Binary Witch(状态压缩)
Binary Witch Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 1521   Accepted: 558 Description Once upon a time in the silent depths of digital forests there
【英文原著 02】- The Lion the witch and the wardrobe
英文原著 02 The Lion the witch and the wardrobe 读书记录 【时间】 用时3天,总6.1h 1、10-54 45页 查了10个单词 1.6h2、55-99 45页 查了9个生词 2h3、100-165 66页,查词12个,用时2.5h 【精彩句子】 1 Faun’s brown eyes had filled with tears a
CSU-1008-Horcrux
Description A Horcrux is an object in which a Dark wizard or witch hashidden a fragment of his or her soul for the purpose of attaining immortality.Constructing a Horcrux is considered Dark magic of
COJ-1008-Horcrux
1008: HorcruxSubmit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 610 Solved: 165 Description A Horcrux is an object in which a Dark wizard or witch has hidden a f
[150227]
donmai Y “保科柊史”有着一个一直隐藏在心中的秘密。 那就是,自己拥有「可以感受他人的心情」的不可思议的力量。 他的同班同学“綾地寧々”。 这位少女也抱有一个无法对他人倾诉的秘密。 那就是,她的身体会「不关自己的意愿而发情」。 这俩人本应该只不过是同班同学而已. 可某日,柊史因某个意外事故而目击到了冲击性的画面。 映入他眼帘的是,处于发情中寧々的OB>C场面