ID #123 · Colecția InfoAs · Operatori și expresii

Problema Loterie binara

Într-o țară din Balcani se organizează o loterie mai _bi**z** ară_. Aceasta se desfășoară astfel: în fiecare săptămână, participanții aleg `n` cifre binare, iar în funcție de numărul câștigător extras (alcătuit de asemenea din `n` cifre binare), aceștia primesc un scor, care, cu cât este mai **mic** , cu atât este mai valoros (participantul poate câștiga sume mai mari de bani). Scorul unui participant se calculează astfel: fie șirul participantului `p`, iar șirul câștigător `c` (vom nota `p<sub>i</sub>`, respectiv `c<sub>i</sub>`, a `i`-a cifră binară a lui `p`, respectiv `c`, pentru `1 ≤ i ≤ n`). Atunci scorul participantului este egal cu costul minim de a transforma șirul `p` în șirul `c`, folosind următoarele operații: 1. Inversăm valoarea unui element `p<sub>i</sub>` din `0` în `1` sau invers (pentru `1 ≤ i ≤ n`). Această operație are costul `1`; 2. Schimbăm între ei oricare doi biți `p<sub>i</sub>` și `p<sub>j</sub>` (pentru `1 ≤ i ≤ j ≤ n`). Această operație are costul `j - i` (diferența dintre `j` și `i`). ## Cerință Jean participă săptămâna aceasta la această loterie, însă nu este deloc bun la calcule (cum se întâmplă deseori cu protagoniștii problemelor de info). Știind șirul ales de el, `p`, și cel câștigător, `c`, ajutați-l pe Jean prin a-i afla scorul. ## Date de intrare Pe prima linie a fișierului de intrare `loterie-binara.in` se află numărul natural `n`. Pe a doua linie a fișierului de intrare se află șirul `p` (al lui Jean), iar pe a treia linie se află șirul `c` (cel câștigător). Cele două șiruri sunt neseparate prin spații, au lungimea `n` și sunt alcătuite doar din valori de `0` și de `1`. ## Date de ieșire Programul afișează în fișierul de ieșire `loterie-binara.out` scorul lui Jean. ## Restricții și precizări * `1 ≤ n ≤ 1.000.000` * Al doilea nume al lui Jean este Pierre