Divisibility by 25 CodeForces - 988E
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 (1≤n≤10181≤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
5071
4
705
1
1241367
-1
Note
In the first example one of the possible sequences of moves is 5071 →→ 5701 →→ 7501 →→ 7510 →→ 7150.
题意:一个大数,只能移动相邻的两位,问移动几次后可以除以25后没有余数
思路:一个模拟,末尾是00,25,50,75就可以了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define INF 0x3f3f3f3f
const long long int maxn=2e5+;
string str;
int ans;
void solve(char a,char b)
{
string s=str;
int cnt1=s.rfind(a),cnt2=s.rfind(b);
if(a=='' && b=='')
cnt1=s.rfind(a,cnt1-);
if(cnt1==string::npos || cnt2==string::npos)
return ;
int cnt=;
if (cnt1 > cnt2)
{
cnt++;
swap(cnt1, cnt2);
}
for (int i = cnt2; i+ < s.size(); i++)
{
cnt++;
swap(s[i], s[i+]);
}
for (int i = cnt1; i+ < s.size()-; i++)
{
cnt++;
swap(s[i], s[i+]);
}
cnt += find_if(s.begin(), s.end(), [](char c){return c != '';}) - s.begin();
ans = min(ans, cnt);
} int main()
{
cin>>str;
ans=INF;
solve('','');
solve('','');
solve('','');
solve('','');
if(ans == INF)
ans=-;
cout<<ans<<endl;
return ;
}
最新文章
- android Animation介绍
- TCP滑动窗口机制
- o-sync-and-o-direct
- signalR制作微信墙 开源
- CI邮箱中SMTP的一些端口
- MyEclipse 启动tomcat时报错:Cannot change deployment state from ERROR to REDEPLOYING.ds
- (一)Angularjs - 入门
- Android_NFC_开发介绍
- CATALINA_BASE与CATALINA_HOME的区别(转)
- Jsp连接Mysql数据库取数方法
- 如何开始使用bootstrap
- Nginx学习——Nginx简单介绍和Linux环境下的安装
- 五、Redis持久化配置
- Nginx实战-后端应用健康检查
- Helm使用详解
- 关于ř与tableau的集成---- k均值聚类
- Django--ORM--模型增删改查--备忘
- POJ 1684 Corn Fields(状压dp)
- spring-cloud-sleuth+zipkin追踪服务实现(四)
- ES6 主要的新特性
热门文章
- DotNetAnywhere
- 过流监测芯片ADS720/723
- Java 数字数组随机数工具类 NumberUtils、ArrayUtils、RandomUtils用法
- SpringMVC02 AbstractController And MultiActionController
- 《超实用的Node.js代码段》连载一:获取Buffer对象字节长度
- javascript对象的学习
- jsp之数据提交与获取(传统方法)
- 使用nodejs消费SAP Cloud for Customer上的Web service
- 用NPOI操作EXCEL-锁定列CreateFreezePane()
- Verilog设计分频器(面试必看)