UCF Local Programming Contest 2018 D. Rounding Many Ways

Timothy and Alex’s hopes and dreams of running for UCF's Student Government Association have been crushed by the realization that their campaign ticket would not be alliterative. So, they have decided to analyze statistics from many different polls given to students to determine what pair of programming team members would be best situated to win the election. However, there is a problem. All of the statistics have been rounded off. This would not be an issue apart from the fact that the pollsters forgot to mention how the number was rounded! (Math Terminology Note: if we round, say, 198 to 200, then 198 is called the “true value” and 200 is called the “rounded value”.) 

For example, the rounded value 750 could have come from a true value rounded to the nearest 10 or maybe even the nearest 250. It may also have come from a true value rounded to the nearest 1 (thus not rounding it at all). Thus, the true value could have been something like 625 or maybe much closer like 748. 

Luckily for Timothy and Alex, after some reconnaissance work, they have discovered the general rounding methods used:

● The original statistic was a positive integer S

● Then a positive integer X was chosen such that X is a divisor of some power of 10, i.e., there exist non-negative integers Y and Z such that X * Y = 10^Z

● Finally the statistic S was rounded to the nearest positive multiple of X to get the rounded value N, i.e., there exists a positive integer W such that X * W = N and |S – N| is minimized.

The Problem:

Given the rounded value, find all the different ways it could have been      rounded(derived). In other words, given N and using the above constraints, you are to find all values of X that satisfy both of the following two equations:

● X * Y = 10^Z 

● X * W = N

The Input:

The first and only line of input contains an integer, N (1 ≤ N ≤ 1e18), representing the rounded value.

The Output:

First print out a single line containing an integer representing the number of different X values that the rounded value N could have been derived from. Then print out all of these values of X, in increasing order, on separate lines.

输出时每行末尾的多余空格,不影响答案正确性

样例输入1复制

30

样例输出1复制

4 
1 
2 
5 
10

样例解释1

Output: 1  

X = 1, Y = 10, Z = 1, W = 30   

Rounded to nearest multiple of 1: 1*10=10, 1*30=30   

Output: 2   

X = 2, Y = 5, Z = 1, W = 15  

Rounded to nearest multiple of 2: 2*5=10, 2*15=30   

Output: 5   

X = 5, Y = 2, Z = 1, W = 6   

Rounded to nearest multiple of 5: 5*2=10, 5*6=30   

Output: 10   

X = 10, Y = 1, Z = 1, W = 3   

Rounded to nearest multiple of 10: 10*1=10, 10*3=30 

样例输入2复制

120

样例输出2复制

8
1
2
4
5
8
10
20
40

样例输入3复制

8

样例输出3复制

4
1
2
4
8

思路:

求出 n 中 2 的数量和 5 的数量,进行组合

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans *= a;
        }
        a *= a;
        b /= 2;
    }
    return ans;
}

int main()
{
    ll n;
    while(~scanf("%lld", &n))
    {
        ll a = 0, b = 0;
        while(n % 2 == 0)
        {
            n /= 2;
            a++;
        }
        while(n % 5 == 0)
        {
            n /= 5;
            b++;
        }
//        cout<<a<<' '<<b<<'\n';
        priority_queue<ll, vector<ll>, greater<ll> >q;
        for(int i = 0; i <= a; ++i)
        {
            for(int j = 0; j <= b; ++j)
            {
                q.push(qpow(2, i) * qpow(5, j));
            }
        }
        cout<<q.size()<<'\n';
        while(q.size())
        {
            cout<<q.top()<<'\n';
            q.pop();
        }
    }
    return 0;
}

 

 

 

全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务