题目连接:https://www.hackerrank.com/contests/codestorm/challenges/game-with-a-boomerang
上一篇博客不知怎么复制过来题目,排版惨不忍睹。。。所以这个只好直接放链接吧
题意是n个土著人,编号1~n。围成一圈,然后从1号开始扔飞镖,如果是奇数个人的圈的话,那这个扔飞镖的人没有对应的人,扔飞镖的人淘汰。如果是偶数个人的圈的话,将对面编号淘汰。
这样围成一圈之后,进行n-1轮,每一轮淘汰掉一个人,问最终剩下的人的编号。
没做过这样的题,全无思路。然后上离散课的时候拿纸笔画,发现偶数n的时候就是等于奇数n-1的时候加一的情况,然后发现可以递推,奇数的时候也是有规律的。于是写了这么一个程序。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
//const int maxn = 1e18;
ll n;
//ll val[1000000000000000000];
ll cal(ll x)
{
ll i;
ll ori = 1;
for (i = 2; i <= x; i++)
{
if (i & 1)
{
ori = ori + 1;
}
else
{
if (ori < i / 2)
{
ori = ori + 1;
}
else
{
ori = ori + 2;
if (ori > i)
{
ori = ori - i;
}
}
}
}
return ori;
}
int main()
{
//freopen("i.txt","r",stdin);
//freopen("o.txt","w",stdout);
int test;
scanf("%d", &test);
while (test--)
{
scanf("%lld", &n);
printf("%lld\n", cal(n));
}
//system("pause");
return 0;
}
于是举了1000个数找规律,找到的规律就是发现了断点都是4n-2,然后每个数只跟其断点的大小有关系,剩下的也没什么了。
做出来的时候特别高兴,但现在觉得这个题目貌似也不过如此啊。。。果然自己还是。。。。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
ll n;
ll val[100];
void init()
{
ll i;
val[1] = 1;
for (i = 2;; i++)
{
val[i] = val[i - 1] * 4 - 2;
if (val[i] > 1e18)
break;
}
}
ll cal(ll x)
{
int i;
for (i = 1; i <= 32; i++)
{
if (x - val[i] < 0)
break;
}
i--;
ll y = x - val[i];
ll sum;
ll v;
ll temp;
if (y < val[i])
return y + 1;
else
{
temp = x - 2 * val[i];
v = temp / 2;
sum = v + (v + 1) * 2;
if (temp & 1)
{
sum++;
}
return val[i] + sum;
}
}
int main()
{
//freopen("i.txt", "r", stdin);
//freopen("o.txt", "w", stdout);
init();
int test;
scanf("%d", &test);
while (test--)
{
scanf("%lld", &n);
printf("%lld\n", cal(n));
}
//system("pause");
return 0;
}