Odzemanje IBUOI 2019

Zdravo, dali nekoj znae kako se resava ovaa zadaca, ja resiv za test slucaevite kade n<1 000 000, no pagja na vreme za drugite bidejki ja probuvam sekoja kombinacija.

This message was edited 3 times. Last update was at 18/04/2019 14:03:30

Оваа задача, и вакви слични задачи каде што треба да изброиме колку броеви постојат што задоволуваат некое својство кое не е тривијално обично се решаваат со техниката Digit DP.
Бидејќи постојат броеви со различен број на цифри кои би можеле да го задоволат бараното својство, ќе ја повториме техниката на броење за секоја должина на бројот посебно. Да речеме дека имаме дадна разлика S, |S| = k, и цифрите на S се s_k, s_(k-1), ..., s_1. Нека бројот кој тековно го разгледуваме е N, |N| = q, цифрите на N се n_q, n_(q-1), ..., n_1. Значајно е да спомнеме дека N > S и |N| >= |S|, инаку својството не би можело да биде исполнето. За поедноставување на проблемот, сметаме дека |S| = |N|, со тоа што S го пополнуваме со водечки нули.
За да развиеме техника за броење, треба да увидиме како можеме да ги пресметаме сите различни начини за да се добие цифрата на некоја произволна позиција (k) во бројот S. Првото нешто што би ни текнало на памет е да ги најдеме сите можни вредности на n_k и n_(q-k) за кои важи својството: s_k = n_k - n_(q+1-k). Но, тоа не е сосема точно, бидејќи кога одземаме броеви може да дојде до пренесување на десетки ако n_k < n_(q+1-k). Според тоа, нека carry е бит стринг, кај кој k-тиот бит има вредност 1 ако се пренесува десетка од k-тата во (k-1)-та позиција при одземањето. Нека valid(s, n, k, carry) е функција која враќа дали можеме да ја добиеме k-тата цифра во s од бројот n и пренесувањата carry. Тогаш, valid(s, n, k, carry) = true ако и само ако s_k = 10 * getBit(carry, k+1) + n_k - getBit(carry, k) - n_(q+1-k). Конечно, доаѓаме до следната рекурентна равенка за пресметување на сите можни броеви:

ways(k, carry, q) = cnt_k * ways(k+1, carry, q); k <= q / 2; каде што cnt_k се сите подредени парови (a, b), за кои важи valid(s, n, k, carry) и valid(s, n, q+1-k, carry).
ways(k, carry, q) = 1; k > q / 2;

Бидејќи не можеме однапред да знаеме на кои места ќе имаме пренесување на вредноста, ќе ги испробаме сите вредности на carry, кои се 2^(digitLen-1) на број, каде digitLen е бројот на цифри за кој пресметуваме. Псевдо-кодот на решението е следниот:

Да напоменам дека решението работи за MAX_LEN >= 19. Исто така, carry има вкупно 2^(digitLen-1) вредности, а не 2^(digitLen), поради тоа што не можеме да пренесуваме десетки од првата цифра на десно.

Fala