Начало
Соревнования
Разбор задачи F. Деление
Метод решения – встреча в середине.
Пусть число `n` содержит `nu` цифр (`nu\ ≤12`). Делим цифры числа примерно пополам – `k=|__nu//2__|` цифр и `nu-k` цифр. Вариантов для первой части не более `10^6`, для второй – также не более `10^6`. Нужно найти такую комбинацию цифр первой части `v_1` и второй части `v_2`, что `(v_1*10^{nu-k}+v_2)\ mod\ m\ =\ 0`, при этом количество цифр, не совпадающих с `n` должно быть минимально.
Так как `(X+Y)mod\ m=((X\ mod\ m)+(Y\ mod\ m))\ mod\ m`, перебор можно выполнить отдельно для каждой части.
Перебираем последние `nu-k` цифр и запоминаем для каждого возможного остатка минимальную разницу в количестве несовпадающих цифр и вариант, на котором она достигается.
Перебираем первые `k` цифр и, найдя `(v_1*10^{nu-k})\ mod\ m`, смотрим, есть ли вариант второй части, который дополняет полученный остаток до 0. Среди найденных вариантов выбираем минимальный по количеству несовпадающих цифр.
Время работы алгоритма `O(nu//2*10^{nu//2})`.
typedef long long ll; ll n,m; vector<int> vn; // разложение числа n на цифры int difnum(int z, int i1, int i2) // количество несовпадающих цифр при наложении z с позиции i1 по i2-1 { int d=0; for(;i1<i2;++i1) { if(vn[i1]!=z%10) ++d; z/=10; } return d; } int main() { cin>>n>>m; // разделяем n на цифры while(n>0) { vn.push_back(n%10); n/=10; } if(vn.size()==0) vn.push_back(0); int nc=vn.size(); int k=nc/2; int t2=pow(10,nc-k), t1=pow(10,k); vector<int> dif(t2,100), part(t2); // массивы для хранения лучшего варианта второй части для некоторого остатка for(int v2=0;v2<t2;++v2) { int d=difnum(v2,0,nc-k), r=v2%m; if(d<dif[r]) // лучше? { dif[r]=d; part[r]=z; } } int dmin=100; // минимальное количество несовпадающих цифр ll zmin=-1; // если не будет найден, то -1 for(int v1=t1/10;v1<t1;++v1) { ll r=(ll(v1)*t2)%m; // остаток для варианта int d=difnum(v1,nc-k,nc); // несовпадение в первой части ll r2=(m-r)%m; // нужное дополнение до 0 int d2=100; if(r2<t2) d2=dif[r2]; // если существует, то берем if(d+d2<dmin) // лучше? { dmin=d+d2; zmin=ll(v1)*t2+part[r2]; // запоминаем } } cout<<zmin<<"\n"; }
