codeforces 1181B

51 阅读 0 评论 34 点赞

我是靠谱客的博主羞涩电源，最近开发中收集的这篇文章主要介绍codeforces 1181B，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目:http://codeforces.com/problemset/problem/1181/B

B. Split a Number

Dima worked all day and wrote down on a long paper strip his favorite number nn consisting of ll digits. Unfortunately, the strip turned out to be so long that it didn't fit in the Dima's bookshelf.

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.

Input

The first line contains a single integer ll (2≤l≤1000002≤l≤100000) — the length of the Dima's favorite number.

The second line contains the positive integer nn initially written on the strip: the Dima's favorite number.

The integer nn consists of exactly ll digits and it does not contain leading zeros. Dima guarantees, that there is at least one valid way to split the strip.

Output

Print a single integer — the smallest number Dima can obtain.

Examples

input

7
1234567

output

input

3
101

output

Note

In the first example Dima can split the number 12345671234567 into integers 12341234 and 567567. Their sum is 18011801.

In the second example Dima can split the number 101101 into integers 1010 and 11. Their sum is 1111. Note that it is impossible to split the strip into "1" and "01" since the numbers can't start with zeros.

题目：一个长度为n的数，分成两个没有前导零并且不等于零的数，求两个数的最小和。

思路：两个数的和最小，那两个数的位数一定是最小的，所以从中间位置遍历就行了。

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define MAX(a,b) a>b?a:b
#define MIN(a,b) a<b?a:b
#define MAX(a,b,c) (a>b?(a>c?a:c):(b>c?b:c))
#define MIN(a,b,c) (a<b?(a<c?a:c):(b<c?b:c))
using namespace std;
/*
??大数加法
?*/
int sum[100005];
int MAX=100005;
int Addition(string num1, string num2)
{
int i, j, len;
int n2[100005] = {0};
int len1 = num1.length();
int len2 = num2.length();
len = len1>len2 ? len1 : len2;
for (i = len1-1, j = 0; i >= 0; i--, j++)
sum[j] = num1[i] - '0';
for (i = len2-1, j = 0; i >= 0; i--, j++)
n2[j] = num2[i] - '0';
// 将两个大数相加
for (i = 0; i <= len; i++)
{
sum[i] += n2[i];
if (sum[i] > 9)
{
sum[i] -= 10;
sum[i+1]++;
}
}
if(sum[len] != 0)
len++;
return len;
}
int suan(string a,int k){
string b="";
string c="";
for(int i=0;i<k;i++){
b+=a[i];
}
for(int i=k;i<a.length();i++){
c+=a[i];
}
return Addition(b,c);
}
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
const int MAXN = 2750131;
ll T,n,m,k,i,j;
ll gcd(ll p,ll q)
{return q==0?p:gcd(q,p%q);}
int main()
{
string a,b;
cin>>n;
cin>>a;
int len;
int mid=n/2,l,r;
//	cout<<mid<<endl;
if(n%2==0){
if(a[mid]!='0'){
len=suan(a,mid);
for(i=len-1;i>=0;i--){
cout<<sum[i];
}
cout<<endl;return 0;
}
else{
l=mid-1;r=mid+1;
}
}
else{
l=mid;r=mid+1;
}
//	cout<<l<<" "<<r<<endl;
while(1){
if(a[r]!='0'){
int s1=0;
int s2=l;
while(a[s1]==a[s2]){
s1++;
s2++;
}
//	cout<<s1<<" "<<a[s1]<<" "<<s2<<" "<<a[s2]<<endl;
if(a[s1]>a[s2]&&a[l]!='0')
{
len=suan(a,l);
for(i=len-1;i>=0;i--){
cout<<sum[i];
}
cout<<endl;return 0;
}
else{
len=suan(a,r);
for(i=len-1;i>=0;i--){
cout<<sum[i];
}
cout<<endl;return 0;
}
}
else{
if(a[l]!='0'){
len=suan(a,l);
for(i=len-1;i>=0;i--){
cout<<sum[i];
}
cout<<endl;return 0;
}
}
l--;
r++;
}
return 0;
}