ACM:每日一题 abc336 C题

发布时间:2024年01月15日

C - Even Digits?Editorial


Time Limit: 2 sec / Memory Limit: 1024 MB

Score:?300300?points

Problem Statement

A non-negative integer?n?is called a?good integer?when it satisfies the following condition:

  • All digits in the decimal notation of?n?are even numbers (0,?2,?4, 6, and?8).

For example,?0,?68, and?2024?are good integers.

You are given an integer?N. Find the?N-th smallest good integer.

Constraints

  • 1≤N≤10^12
  • N?is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the?N-th smallest good integer.


Sample Input 1

Copy

8

Sample Output 1

Copy

24

The good integers in ascending order are?0,2,4,6,8,20,22,24,26,28,…0,2,4,6,8,20,22,24,26,28,….
The eighth smallest is?2424, which should be printed.


Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

初次编写代码测试:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n;
int fun(int n){
    int p,i=0;
    if(n==1)return i;
    for(p=2,i=0;p<=n;p++){
        i+=2;
        int q=i,cnt=0;
        
        while(q){
        int t=q%10;
        if(t%2!=0){i+=pow(10,cnt);break;}
        q/=10;
        cnt++;
       }
    }
    return i;
}
signed main(){
    cin>>n;
    cout<<fun(n);
}
//这个代码能处理n<=40000000的数据

改进(10^12想都不要想):

要精用vector,数组一般都会超时的啦。

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> a;//类似高精度
int n;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    n-=1;//因为第一位是0嘛
    while(n > 0){//2*5=10进位了
        a.push_back(n%5);
        n /= 5;
    }
    if(a.empty()) a.push_back(0);
    for(int i = a.size()-1; i > -1; i--)//迭代器,也不算吧,vector也是数组
        cout << 2*a[i];
}

也算是运用了算法吧这个题目,高精度还是很重要的(上一次选拔赛就是高精度差一点就提交了ac了)。

这篇不算入每日一题的范畴。是acm作业吧。

文章来源:https://blog.csdn.net/northheng127/article/details/135595784
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。