ZOJ 3768 Continuous Login

本文主要是介绍ZOJ 3768 Continuous Login，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5231

题目：

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.

解题思路：

连续登陆的天数最多不超过3组，具体是问什么，我也不清楚，听人家说是打表发现的规律。可以分成3种情况：1组、2组、3组，直接暴力枚举。

代码 ：

/*wa*/ 
#include <iostream>
#include <cstring>
#include <map>
using namespace std;const int MAXN = 50000;
map<int, int> m;
int a[MAXN];int main()
{std::ios::sync_with_stdio(false);int t, n;for(int i = 0; i < MAXN; i++){a[i]    = i * (i + 1) / 2;m[a[i]] = i;}while(cin >> t){while(t--){cin >> n;if(m[n]){cout << m[n] << endl;}else{int flag = 1;for(int i = 1; a[i] <= n; i++){if(m[n - a[i]]){flag = 0;cout << i << " " << m[n-a[i]] << endl;break;}}if(flag){for(int i = 1; a[i] <= n && flag; i++){for(int j = 1; a[j] <= n && flag; j++){if(m[n - a[i] - a[j]]){flag = 0;cout << i << " " << j << " " << m[n - a[i] - a[j]] << endl;}}}}}}}return 0;
}

这篇关于ZOJ 3768 Continuous Login的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---