推个公式
由于具体剩下哪几个坏人和问题并没关系
f(a,b,m,pos)表示有a个好人,b个坏人,报数为m,当前处理pos位置
=false (pos+m-1)%(k+bad)<k
or=true b==0
or=f(a,b-1,m,(pos+m-1)%(k+bad) ) else
以下程序是生成提交代码的,由于有很多重复数据,直接打表更快
- /**********************************************************************
- * Online Judge : POJ
- * Problem Title : Joseph
- * ID : 1012
- * Date : 12/9/2008
- * Time : 16:43:6
- * Computer Name : EVERLASTING-PC
- ***********************************************************************/
- #include<iostream>
- using namespace std;
- #define MAXN 14
- int n,k,m;
- //圈内还有bad个坏人,目前从pos位置开始数
- bool OK(int bad,int pos)
- {
- if (bad==0)
- {
- return true;
- }
- pos=(pos+m-1)%(k+bad);
- if (pos<k)
- {
- return false;
- }
- else
- {
- return OK(bad-1,pos);
- }
- }
- int main()
- {
- freopen("out_1012.txt","w",stdout);
- cout<<"#include<iostream>/nusing namespace std;/n/n#define MAXN 14/n/nint ans[MAXN]={0";
- for (k=1;k<14;++k)
- {
- for (m=1;;++m)
- {
- if (OK(k,0))
- {
- cout<<','<<m;
- break;
- }
- }
- }
- cout<<"};/nint n;/n/nint main()/n{/n while(cin>>n&&n) cout<<ans[n]<<endl;/n return 0;/n}/n";
- return 0;
- }