当前位置: 代码迷 >> 综合 >> UOJ #82 [UR #7] 水题生成器
  详细解决方案

UOJ #82 [UR #7] 水题生成器

热度:17   发布时间:2024-01-19 01:42:07.0

今天是世界水日,著名的水题资源专家蝈蝈大臣向世界宣布了他的一项新发明 —— 水题生成器。

每道题目都有一个正整数的难度值。水题生成器虽然强大但是功能有限。水题生成器内部有一个参数  n n,你可以告诉水题生成器一个能整除  n! n! 的正整数  d d,水题生成器就会产生一道难度值恰为  d d 的水题。这里  n! n! 表示  n n 的阶乘。

现在蝈蝈大臣的助手欧姆想用水题生成器产生不超过  n n 道水题,且难度值之和恰为  m m。保证  1≤m≤n! 1≤m≤n!。

欧姆当然知道怎么做啦!但是他想考考你。请你给出一组合法方案或输出无解。

输入格式

第一行一个正整数  n n。

第二行一个正整数  m m。保证  1≤m≤n! 1≤m≤n!。

输出格式

不超过  n n 行,每行一个正整数  d d,表示你每次告诉水题生成器的难度值。

输出的每个难度值都必须是  n! n! 的约数,且难度值之和恰为  m m。

如果有多组解,输出任意一组均可。如果无解请直接输出卖萌表情 “>w<”(不含引号)

样例一

input
5
100
output
40
40
20
explanation

5!=1×2×3×4×5=120 5!=1×2×3×4×5=120。 20 20 和  40 40 都是  120 120 的约数,且  40+40+20=100 40+40+20=100。

样例二

input
10
3628800
output
3628800

限制与约定

测试点编号 n n的规模
1, 2, 3, 4, 5, 6 n≤5 n≤5
7, 8, 9, 10, 11, 12, 13, 14 n≤9 n≤9
15, 16, 17, 18, 19, 20 n≤20 n≤20

时间限制: 1s 1s

空间限制: 256MB 256MB

下载

样例数据下载

~~~~~~~~~~~~~~~~~~~~~~~~~~~~

贪心+思路~

从大到小枚举n!/i!的值now判断能否加进答案里,能就直接输出now*(m/now),再从m中减去这个数。这样,m/now的值一定小于i,也就是说now*(m/now)一定是n!的因子,这样做符合要求。


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long longint n;
ll m,now;int main()
{scanf("%d%lld",&n,&m);now=1; for(int i=1;i<=n;i++) now*=i;for(int i=1;i<=n;i++){now/=i;if(m>=now){printf("%lld\n",now*(m/now));m-=now*(m/now);}}return 0;
}

  相关解决方案