首页 > 学院 > 开发设计 > 正文

Codeforces 514A Chewbaсca and Number【贪心】这题好劲啊

2019-11-14 10:39:47
字体:
来源:转载
供稿:网友

A. Chewbaсca and Numbertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Luke Skywalker gave Chewbacca an integer number x. Chewbacca isn't good at numbers but he loves inverting digits in them. Inverting digitt means replacing it with digit 9 - t.

Help Chewbacca to transform the initial number x to the minimum possiblepositive number by inverting some (possibly, zero) digits. The decimal rePResentation of the final number shouldn't start with a zero.

Input

The first line contains a single integer x(1 ≤ x ≤ 1018) — the number that Luke Skywalker gave to Chewbacca.

Output

Print the minimum possible positive number that Chewbacca can obtain after inverting some digits. The number shouldn't contain leading zeroes.

ExamplesInput
27Output
22Input
4545Output
4444

题目大意:

给你一个LL范围内的数字X,每一位子上的数字t都可以替换为9-t,让你输出最小的,不含有前导0的正整数,不能以0开头。

思路:

贪心角度很好想,ans【i】=min(a【i】,9-a【i】);

一开始读题没看到正整数三个字,那么990的ans我认为是0.Wa一发、

后来发现了,那么990的ans我认为是9.又Wa一发、

哦,结果要求没有0开头啊。那么ans==900.

这是一道A题.恩.满满的Hack点,我不禁开始幻想当时打这场比赛的小伙伴们会Hack多少发。

Ac代码:

#include<stdio.h>#include<string.h>#include<iostream>using namespace std;#define ll __int64char a[200];int ans[200];ll output;int n;int main(){    while(~scanf("%s",a))    {        n=strlen(a);        output=0;        int f=0;        for(int i=0;i<n;i++)        {            ans[i]=min(a[i]-'0',9-a[i]+'0');            if(ans[i]!=0&&f==0)f=1;            if(ans[i]==0&&f==0)ans[i]=max(a[i]-'0',9-a[i]+'0'),f=1;        }        for(int i=0;i<n;i++)        {            output=output*10+ans[i];        }        printf("%I64d/n",output);    }}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表