博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CF 988E Divisibility by 25 思维 第十二
阅读量:6328 次
发布时间:2019-06-22

本文共 3826 字,大约阅读时间需要 12 分钟。

Divisibility by 25
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer nn from 11 to 10181018 without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by 2525? Print -1 if it is impossible to obtain a number that is divisible by 2525.

Input

The first line contains an integer nn (1n10181≤n≤1018). It is guaranteed that the first (left) digit of the number nn is not a zero.

Output

If it is impossible to obtain a number that is divisible by 2525, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.

Examples
input
Copy
5071
output
Copy
4
input
Copy
705
output
Copy
1
input
Copy
1241367
output
Copy
-1
Note

In the first example one of the possible sequences of moves is 5071 → 5701 → 7501 → 7510 → 7150.

 

 题意: 可以移动每位数的位置,使得移动后的数字是25的倍数,问最小需要移动多少位?

emmmmm,好多特殊情况,wa了很多发

能整除25,则最后两位只能是00,25,50,75

枚举0,2,5,7的个数

然后判断这四种情况,需要注意的是如果处于后面的数在前面了,如果此时另一个数不在末位则移动次数需加一

还有如果从第二位开始有连续的0的话且要移动的数位置在第一位此时移动可能导致开头为0,需要多移动0的个数次,还有特判要用到的0在第二位此时需要加的次数少一

#include #include 
#include
#include
#include
#include
#include
#include
#include
#include
#define debug(a) cout << #a << " " << a << endlusing namespace std;const int maxn = 3*1e3 + 10;const int mod = 1e9 + 7;typedef long long ll;int main(){ std::ios::sync_with_stdio(false); string s; while( cin >> s ) { ll a = -1, b = -1, c = -1, d = -1, num = 0, ta; for( ll i = 0; i < s.length(); i ++ ) { if( s[i] == '0' ) { num ++; if( num >= 2 ) { ta = a; } a = i; } else if( s[i] == '2' ) { b = i; } else if( s[i] == '5' ) { c = i; } else if( s[i] == '7' ) { d = i; } } ll ans1 = 1e12, ans2 = 1e12, ans3 = 1e12, ans4 = 1e12; bool flag = false; //debug(a), debug(b), debug(c),debug(d),debug(num); if( a != -1 && c != -1 ) { if( a < c ) { if( c == s.length() - 1 ) { ans1 = min( s.length() - 1 - a, ans1 ); } else { ans1 = min( s.length() - 1 - a + s.length() - 2 - c + 1, ans1 ); } } else { ans1 = min( s.length() - 1 - a + s.length() - 2 - c, ans1 ); } ll t = 0, i = 1; while( s[i] == '0' ) { t ++; i ++; } if( s[1] == '0' && ( a == 0 || c == 0 ) ) { if( s.length() == 3 ) { flag = true; } else { ans1 += t; if( a == 1 ) { ans1 --; } } } } if( c != -1 && b != -1 ) { if( c < b ) { if( b == s.length() - 1 ) { ans2 = min( s.length() - 1 - c, ans2 ); } else { ans2 = min( s.length() - 1 - c + s.length() - 2 - b + 1, ans2 ); } } else { ans2 = min( s.length() - 1 - c + s.length() - 2 - b, ans2 ); } ll t = 0, i = 1; while( s[i] == '0' ) { t ++; i ++; } if( s[1] == '0' && ( b == 0 || c == 0 ) ) { if( s.length() == 3 ) { flag = true; } else { ans2 += t; } } } if( c != -1 && d != -1 ) { if( c < d ) { if( d == s.length() - 1 ) { ans3 = min( s.length() - 1 - c, ans3 ); } else { ans3 = min( s.length() - 1 - c + s.length() - 2 - d + 1, ans3 ); //debug(ans); } } else { ans3 = min( s.length() - 1 - c + s.length() - 2 - d, ans3 ); } ll t = 0, i = 1; while( s[i] == '0' ) { t ++; i ++; } if( s[1] == '0' && ( d == 0 || c == 0 ) ) { if( s.length() == 3 ) { flag = true; } else { ans3 += t; } } } //debug(ans); if( num >= 2 ) { ans4 = min( ans4, s.length() - 1 - a + s.length() - 2 - ta ); } ll ans = min( min( ans1, ans2 ), min( ans3, ans4 ) ); if( ans == 1e12 && !flag ) { cout << -1 << endl; } else { cout << ans << endl; } } return 0;}

 

转载于:https://www.cnblogs.com/l609929321/p/9221787.html

你可能感兴趣的文章
Unity-2017.3官方实例教程Space-Shooter(一)
查看>>
makefile中重载与取消隐藏规则示例
查看>>
Linux 内核版本号查看
查看>>
4-3 简单求和 (10分)
查看>>
Python环境部署
查看>>
[BZOJ1927]星际竞速(费用流)
查看>>
为运维人员插上腾飞更远的翅膀!
查看>>
Word 2003中编辑标记与格式标记大讨论
查看>>
从国内向海外转移域名经验谈
查看>>
浅谈apache与tomact的整合
查看>>
SQL Server vNext CTP1 on Linux
查看>>
1-为 Lync Server 2010 准备 Active Directory 域服务
查看>>
SELinux安全
查看>>
NetBackup下ORACLE恢复测试方案实例解析
查看>>
【有奖征文】“失业”程序员的苦辣酸甜
查看>>
IE9是如何被FireFox4超越全球市场份额的?
查看>>
linux bunzip2命令
查看>>
敏捷个人:通过实践TOGAF来思考如何学习并应用新的方法?
查看>>
Android系统的开机画面显示过程分析(6)
查看>>
vivo Hi-Fi+QQ音乐 数字音乐市场的一剂良方
查看>>