Подразделы

Другие разделы

Дата и время

16/10/2024 03:50:07

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи 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";
}
loading