**Contest Link**: [Intra Department Programming Contest 2023, CSE-BU](https://mirror.codeforces.com/contestInvitation/fa4a356e37997cfb8dfe717ba3106ad11eb693eb)↵
↵
↵
↵
↵
[A. Shopping (Easy Version)](https://mirror.codeforces.com/gym/487767/problem/A)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
[B. Shopping (Hard Version)](https://mirror.codeforces.com/gym/487767/problem/B)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
<spoiler summary="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);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
[C. Create Square](https://mirror.codeforces.com/gym/487767/problem/C)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[D. Team Formation](https://mirror.codeforces.com/gym/487767/problem/D)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[E. Adjuctly or Exactly?](https://mirror.codeforces.com/gym/487767/problem/E)↵
↵
<spoiler summary="Tutorial">↵
Just print the word "Correctly" without quotes.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
cout << "Correctly";↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[F. Good Prime](https://mirror.codeforces.com/gym/487767/problem/F)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[G. Upcoming Exam](https://mirror.codeforces.com/gym/487767/problem/G)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[H. Halal Food](https://mirror.codeforces.com/gym/487767/problem/H)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
[A. Shopping (Easy Version)](https://mirror.codeforces.com/gym/487767/problem/A)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
[B. Shopping (Hard Version)](https://mirror.codeforces.com/gym/487767/problem/B)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
<spoiler summary="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);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
[C. Create Square](https://mirror.codeforces.com/gym/487767/problem/C)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[D. Team Formation](https://mirror.codeforces.com/gym/487767/problem/D)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[E. Adjuctly or Exactly?](https://mirror.codeforces.com/gym/487767/problem/E)↵
↵
<spoiler summary="Tutorial">↵
Just print the word "Correctly" without quotes.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
cout << "Correctly";↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[F. Good Prime](https://mirror.codeforces.com/gym/487767/problem/F)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[G. Upcoming Exam](https://mirror.codeforces.com/gym/487767/problem/G)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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";↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[H. Halal Food](https://mirror.codeforces.com/gym/487767/problem/H)↵
↵
<spoiler summary="Tutorial">↵
...↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
