Intra Department Programming Contest, CSE-BU Editorial
Difference between en2 and en3, changed 5 character(s)
**Contest Link**: [Intra Department Programming Contest 2023, CSE-BU](https://codeforces.net/contestInvitation/fa4a356e37997cfb8dfe717ba3106ad11eb693eb)↵




[A. Shopping (Easy Version)](https://codeforces.net/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://codeforces.net/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://codeforces.net/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://codeforces.net/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://codeforces.net/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://codeforces.net/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://codeforces.net/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://codeforces.net/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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Nocturnality 2024-06-25 15:19:50 5 Tiny change: 'ng Contest, CSE-BU](' -> 'ng Contest 2023, CSE-BU]('
en2 English Nocturnality 2024-04-10 16:50:55 42
en1 English Nocturnality 2024-04-10 14:07:31 6470 Initial revision (published)