Problem Lucky Conversion

Link: http://codeforces.com/problemset/problem/145/A

A. Lucky Conversion

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5,17, 467 are not.

Petya has two strings a and b of the same length n. The strings consist only of lucky digits. Petya can perform operations of two types:

• replace any one digit from string a by its opposite (i.e., replace 4 by 7 and 7 by 4);
• swap any pair of digits in string a.

Petya is interested in the minimum number of operations that are needed to make string a equal to string b. Help him with the task.

Input

The first and the second line contains strings a and b, correspondingly. Strings a and b have equal lengths and contain only lucky digits. The strings are not empty, their length does not exceed 10⁵.

Output

Print on the single line the single number — the minimum number of operations needed to convert stringa into string b.

Sample test(s)

input

47
74

output

1

input

774
744

output

1

input

777
444

output

3

Note

In the first sample it is enough simply to swap the first and the second digit.

In the second sample we should replace the second digit with its opposite.

In the third number we should replace all three digits with their opposites.

Thuật toán bài này khá đơn giản, ta nhận thấy rằng:

• phép di chuyển trên chuỗi được thực hiện khi số kí tự 4 của a bằng số kí tự 4 của b.
• Không cần quan tâm thứ tự của các kí tự di chuyển.
• Và khi thực hiện di chuyển thì ta nên chọn các vị trí mà a[i] != b[i].
• khi số kí tự 4 của a khác số kí tự 4 của b thì ta thực hiện phép đổi.

code:

//Coder : Nguyen Duc Tam

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>


using namespace std;

#define oo 1000000005
#define rep(i,s,e) for(int i = s; i < e; i++)
#define lop(i,s,e) for(int i = s; i != e; i++)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(x) ((int)(x).size())
#define X first
#define Y second

typedef pair<int,int> II;
typedef pair<II,int> D;
typedef long long LL;

vector<int> V;
map<int,int> M;
set<int> S;
queue<int> Q;
stack<int> ST;
string a,b;


int Count4(string _a)
{
int _res = 0;
for(int i=0;i<_a.size();i++)
_res += (_a[i] == '4' ? 1 : 0);
return _res;
}
int Diff(string _a, string _b)
{
int _res = 0;
for(int i = 0; i < _a.size(); i++)
_res += (_a[i] != _b[i] ? 1 : 0);
return _res;
}

int main()
{
#define Off  true
if(Off)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}

cin >> a >> b;
int diff = Diff(a,b);
int ca4 = Count4(a);
int cb4 = Count4(b);
int res = 0;
if(ca4 == cb4)
res = (diff >> 1);
else if(ca4 > cb4)
{
//can thay ca4 - cb4 so 4 thanh so 7
for(int i=0;i<a.size();i++)
if(a[i] != b[i] && a[i] == '4') res++;
}
else
{
for(int i=0;i<a.size();i++)
if(a[i] != b[i] && b[i] == '4') res++;
}
cout << res << endl;
return 0;
}