zoj Continuous Login
Continuous Login
Time Limit: 2 Seconds Memory Limit: 131072 KB Special Judge
Pierre is recently obsessed with an online game. To encourage users to log in, this game will give users a continuous login reward. The mechanism of continuous login reward is as follows: If you have not logged in on a certain day, the reward of that day is 0, otherwise the reward is the previous day's plus 1.
On the other hand, Pierre is very fond of the number N. He wants to get exactly N points reward with the least possible interruption of continuous login.
Input
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
There is one integer N (1 <= N <= 123456789).
Output
For each test case, output the days of continuous login, separated by a space.
This problem is special judged so any correct answer will be accepted.
Sample Input
4
20
19
6
9
Sample Output
4 4
3 4 2
3
2 3
Hint
20 = (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4)
19 = (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2)
6 = (1 + 2 + 3)
9 = (1 + 2) + (1 + 2 + 3)
Some problem has a simple, fast and correct solution.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue> int val[];
bool hash[];
struct node
{
int val;
int i;
struct node *next;
}f[]; void Insert(int x,int i)
{
int k;
node *p;
k=x%;
p=&f[k];
while(p!=NULL && p->val!=x)
{
p=p->next;
}
if(p==NULL)
{
p=(struct node*)malloc(sizeof(struct node));
p->val=x;
p->i=i;
p->next=f[k].next;
f[k].next=p;
}
}
bool found(int x,int &i)
{
int k;
node *p;
k=x%;
p=&f[k];
while(p!=NULL && p->val!=x)
{
p=p->next;
}
if(p==NULL) return false;
if(p->val==x)
{
i=p->i;
return true;
}
return false;
}
void prepare()
{
int i;
val[]=;
for(i=;i<=;i++)
{
f[i].val=;
f[i].i=;
f[i].next=NULL;
}
for(i=;i<=;i++)
{
val[i]=val[i-]+i;
Insert(val[i],i);
}
}
void solve(int n)
{
int i,wz,k,j,s;
//one
if(found(n,wz)==true)
{
printf("%d\n",wz);
return;
}
for(i=;;i--)
{
if(val[i]<n)
{
s=i;
break;
}
}
for(i=;i<=s;i++)
{
k=n-val[i];
if(found(k,wz)==true)
{
printf("%d %d\n",i,wz);
return;
}
}
for(i=;i<=s;i++)
{
for(j=s;j>=;j--)
{
k=n-val[i]-val[j];
if(k<)continue;
if(found(k,wz)==true)
{
printf("%d %d %d\n",i,j,wz);
return;
}
}
}
}
int main()
{
int T,n;
prepare();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
solve(n);
}
return ;
}
最新文章
- 修改.net mvc中前端验证信息的显示方式
- 深入理解JavaScript运行机制
- JavaMail和James的秘密花园
- 开始研究web,mark一下
- C++ 数字转换为string类型
- 常州培训 day4 解题报告
- 【原】rsync的详细参数
- vim使用总结
- 数据结构(主席树,Bit):XTU 1247/COGS 2344. pair-pair
- android 分辨率自适应
- java中的==、equals()、hashCode()源码分析
- 算法:JavaScript两数之和
- [Nginx]单机环境的多应用配置
- linux rsync实时同步
- Java泛型和通配符那点事
- typescript的函数
- H5 32-百度首页
- 引入kaptcha实现验证码验证
- kali 解决Metasploit拿到shell后显示中文乱码问题
- Docker学习笔记之常用的 Docker Compose 配置项