//Solution by Mikołaj Kołek
#include "bits/stdc++.h"
#define intin *istream_iterator<int>(cin)
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int h = intin, w = intin, n = intin;
vector<int> d(n);
copy_n(istream_iterator<int>(cin), n, d.begin());
sort(d.begin(), d.end());
if(h % d[0] != 0 or w % d[0] != 0) {
cout << -1;
return 0;
}
function<long long(int, int)> check = [&] (long long curH, long long curW) {
if(curH == 0 or curW == 0)
return 0ll;
for(int i = d.size() - 1; i >= 0; i--) {
if(d[i] <= curH and d[i] <= curW) {
long long result = (curH / d[i]) * (curW / d[i]);
result += check(curH - (curH % d[i]), curW % d[i]);
result += check(curH % d[i], curW);
return result;
}
}
return 0ll;
};
cout << check(h, w);
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | //Solution by Mikołaj Kołek #include "bits/stdc++.h" #define intin *istream_iterator<int>(cin) using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int h = intin, w = intin, n = intin; vector<int> d(n); copy_n(istream_iterator<int>(cin), n, d.begin()); sort(d.begin(), d.end()); if(h % d[0] != 0 or w % d[0] != 0) { cout << -1; return 0; } function<long long(int, int)> check = [&] (long long curH, long long curW) { if(curH == 0 or curW == 0) return 0ll; for(int i = d.size() - 1; i >= 0; i--) { if(d[i] <= curH and d[i] <= curW) { long long result = (curH / d[i]) * (curW / d[i]); result += check(curH - (curH % d[i]), curW % d[i]); result += check(curH % d[i], curW); return result; } } return 0ll; }; cout << check(h, w); return 0; } |
English