Contest Link: Intra Department Programming Contest 2023, CSE-BU
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
int arr[n];
for (auto &u : arr) cin >> u;
int ans = 0;
for (int i = 0; i < (1 << n); i++) {
long long int multiple = 1;
for (int j = 0; j < n; j++) if (i & (1 << j)) multiple *= arr[j];
int prime[4] = {2, 3, 5, 7}, cnt = 0;
for (auto &u : prime) if (multiple % u == 0) cnt++;
if (cnt == 4) ans++;
}
cout << ans;
}
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> Pair;
const ll M = 1e9+7;
const ll N = 1e4+7;
map<Pair, bool> cnt;
ll n, dp[N][2][2][2][2];
ll func(ll i, ll two, ll three, ll five, ll seven) {
if (i > n) return (two and three and five and seven);
if (dp[i][two][three][five][seven] != -1) return dp[i][two][three][five][seven];
ll firstWay = func(i+1, two, three, five, seven);
ll secondWay = func(i+1, min(1LL, two+cnt[{i, 2}]), min(1LL, three+cnt[{i, 3}]), min(1LL, five+cnt[{i, 5}]), min(1LL, seven+cnt[{i, 7}]));
return dp[i][two][three][five][seven] = (firstWay + secondWay) % M;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
ll prime[4] = {2, 3, 5, 7};
vector<bool> check(8);
for (ll i = 1; i <= n; i++) {
ll a; cin >> a;
for (auto &u : prime) {
if (a % u == 0) {
cnt[{i, u}] = true;
check[u] = true;
}
}
}
if (!check[2] or !check[3] or !check[5] or !check[7]) {
cout << 0 << endl;
return 0;
}
memset(dp, -1, sizeof(dp));
cout << func(1, 0, 0, 0, 0);
}
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n; cin >> n;
ll arr[n];
for (auto &u : arr) cin >> u;
if (n < 4) {
cout << -1 << endl;
return 0;
}
sort(arr, arr+n);
cout << arr[n-4]*arr[n-4];
return 0;
}
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
map<int, int> cnt;
for (int i = 1; i <= n; i++) {
int a; cin >> a;
cnt[a]++;
}
priority_queue<int> pq;
for (auto &u : cnt) pq.push(u.second);
int total = 0;
while (pq.size() > 2) {
int it1 = pq.top();
pq.pop();
int it2 = pq.top();
pq.pop();
int it3 = pq.top();
pq.pop();
if (it1 > 1) pq.push(it1 - 1);
if (it2 > 1) pq.push(it2 - 1);
if (it3 > 1) pq.push(it3 - 1);
total++;
}
cout << total;
}
Tutorial
Just print the word "Correctly" without quotes.
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout << "Correctly";
}
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll N = 1e7;
bool check[N+5];
ll total[N+5];
void sieve() {
for (ll i = 2; i*i <= N; i++) {
if (!check[i]) {
for (ll j = i*i; j <= N; j += i) check[j] = true;
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
sieve();
for (ll i = 5; i <= N; i++) total[i] += total[i-1] + (!check[i] and !check[i-2]);
ll q; cin >> q;
while (q--) {
ll l, r; cin >> l >> r;
ll ans = total[r];
if (l) ans -= total[l-1];
cout << ans << "\n";
}
}
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, k; cin >> n >> k;
if (n * (n+1) / 2 > k) {
cout << "No\n";
return 0;
}
ll extra = k - (n*(n+1)/2);
if (extra % n == 0) cout << "Yes";
else cout << "No";
}
Tutorial
...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, k; cin >> n >> k;
cout << (n+k) / (k+1);
return 0;
}
Solution With Binary Search
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, k; cin >> n >> k;
ll low = 1, high = n, ans = 1;
while (low <= high) {
ll mid = low + (high - low) / 2;
if (mid + k*mid >= n) {
ans = mid;
high = mid-1;
}
else low = mid+1;
}
cout << ans;
return 0;
}
hello, what type of Dp problem is problem B ? Can you recommend any classical problem ?
Thanks
Bitmask DP
Auto comment: topic has been updated by Nocturnality (previous revision, new revision, compare).