OpenJudge

L:魔法!真正的魔法!

总时间限制:
3000ms
内存限制:
65536kB
描述

    某日,魔法师教会的n名魔法师(包含一个大魔导师)进行一次重要的大规模施法,用于抵抗敌对阵营。在施法现场,有m个魔法阵排成一行,编号为1~m。然而,由于敌对阵营的情报网十分强大,他们提前摧毁了其中某些魔法阵,使得这些魔法阵不再生效。施法开始时,每位魔法师都需要站到一个有效的魔法阵里,且每个魔法阵里最多只能站一个人。另外,这个教会认为“素数”是一种不吉利的数,故而除了大魔导师以外的人都不愿意站在编号为素数的魔法阵里。为了增强魔法的力量,应当使所有魔法师与大魔导师之间的距离的最大值最小(两个魔法师之间的距离定义为两人所站的魔法阵编号差的绝对值)。现在,教会希望你来帮他们算一下这个最小值。如果这场施法无法进行,你也需要告诉教会这个遗憾的事实。

输入
首先输入一个正整数T,表示测试数据的组数。接下来T组数据,每组数据的第一行是两个正整数n,m,分别表示包含大魔导师在内的魔法师的人数以及魔法阵的个数;第二行是m个整数a_1~a_m,若a_i=1则表示编号为i的魔法阵已经被破坏了,a_i=0表示编号为i的魔法阵尚未被破坏。

数据范围:
1≤T≤1000
2≤n≤10000
1≤m≤10000
a_i∈{0,1}
输出
对于每组测试数据,输出一行“Case #x: answer”,其中x为测试数据的编号,answer为该组样例中最小的距离最大值,若这场施法无法进行,answer为“So Sad”。
样例输入
3
2 3
0 1 0
3 3
0 0 0
3 5
0 0 1 0 0
样例输出
Case #1: 2
Case #2: So Sad
Case #3: 2
提示
对于第一组样例,编号为1和3的魔法阵可以使用,1不是素数,故而可以让大魔导师站在3号魔法阵,另一个魔法师站在1号魔法阵,距离为2;对于第二组样例,虽然三个魔法阵都可以使用,但是2和3都是素数,故而不可能使三个魔法师各站到一个魔法阵里;对于第三组样例,可以使用的魔法阵为1,2,4,5,故而两个魔法师必须站在1号和4号,如果大魔导师站在2号,那么他和另外两个魔法师的距离分别为1和2,最大值为2,如果大魔导师站在5号,那么他和另外两个魔法师的距离分别为4和1,最大值为4,从而距离最大值的最小值为2。
来源
NWPU
全局题号
12541
添加于
2016-12-24
提交次数
8
尝试人数
1
通过人数
1