Date : 11 April, 2019
Contest Link : Intra Metropolitan University Junior Programming Contest Spring 2019 (Replay)
Standings : https://toph.co/c/intra-mu-junior-spring-2019-r/standings
Problem : A. Nirapod Shorok Chai
Category : Add Hoc
Type : Implementation
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
puts("Nirapod Shorok Chai");
}
Problem : B. Nusrat's Treat
Category : Number Theory
Type : Basic Math
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
int n;
cin >> n;
int sum = n * (n + 1) / 2;
cout << sum << '\n';
}
Problem : C. Sasha, Misha & Their String Fight
Category : Dynamic Programing
Type : Longest Common Subsequence
#include "bits/stdc++.h"
using namespace std;
static const int maxn = 1000 + 5;
int dp[maxn][maxn];
bool memoize[maxn][maxn];
string s, t;
int lens, lent;
int lcs(int i, int j)
{
if (i >= lens or j >= lent) return 0;
int &ret = dp[i][j];
bool &mem = memoize[i][j];
if (mem) return ret;
mem = 1;
int res = 0;
if (s[i] == t[j]) res = 1 + lcs(i+1, j+1);
else res = max(lcs(i+1, j), lcs(i, j+1));
return ret = res;
}
string ans;
void solution(int i, int j)
{
if (i >= lens or j >= lent) return;
if (s[i] == t[j])
{
ans += s[i];
solution(i+1, j+1);
}
else
{
if (lcs(i+1, j) > lcs(i, j+1)) solution(i+1, j);
else solution(i, j+1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
cin >> s >> t;
lens = s.size();
lent = t.size();
memset(memoize, 0, sizeof memoize);
int maxlen = lcs(0, 0);
ans = "";
solution(0, 0);
cout << ans << '\n';
}
}
Problem : D. Issue'r Desh
Category : Add Hoc
Type : Implementation
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
int n, m;
cin >> n >> m;
string ans;
int maxi = -10000;
vector <string> vec;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
int score;
cin >> score;
if (score >= maxi)
{
maxi = score;
ans = s;
}
vec.emplace_back(ans);
}
for (int i = 0; i < min(m, n); i++)
{
cout << "Day " << i+1 << ": " << vec[i] << '\n';
}
if (m > n)
{
for (int i = n+1; i <= m; i++)
{
cout << "Day " << i << ": " << vec.back() << '\n';
}
}
}
Problem : E. Master Plan
Category : Search, Data Structure
Type : Binary Search
#include "bits/stdc++.h"
using namespace std;
static const int maxn = 1e5 + 5;
int cumsum[maxn][30];
int val(char ch)
{
if (ch == '#') return 27;
return ch - 'a' + 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
// freopen("in.txt", "r", stdin);
int n;
cin >> n;
string s;
cin >> s;
reverse(s.begin(), s.end());
for (int i = 0; i < n; i++)
{
cumsum[i][val(s[i])]++;
if (i)
{
for (int j = 1; j <= 27; j++) cumsum[i][j] += cumsum[i-1][j];
}
}
int m;
cin >> m;
int inf = n + 5;
while (m--)
{
string str;
cin >> str;
int len = str.length();
int cnt = 0;
int pos = 0;
int ind = len-1;
bool ok = true;
while (1)
{
int lo = pos;
int hi = n-1;
int ans = inf;
int v = val(str[ind]);
int bad = 0;
if (pos) bad = cumsum[pos-1][v];
while (lo <= hi)
{
int mid = (hi + lo) / 2;
int sum = cumsum[mid][v] - bad;
if (sum <= 0) lo = mid + 1;
else ans = mid, hi = mid - 1;
}
//cerr << "which " << ind << " " << ans << " ";
int lo1 = pos;
int hi1 = n-1;
int ans1 = inf;
char ch = '#';
int v1 = val(ch);
int bad1 = 0;
if (pos) bad1 = cumsum[pos-1][v1];
while (lo1 <= hi1)
{
int mid1 = (hi1 + lo1) / 2;
int sum1 = cumsum[mid1][v1] - bad1;
//cerr << "mid " << mid1 << " " << sum1 << endl;
if (sum1 <= 0) lo1 = mid1 + 1;
else ans1 = mid1, hi1 = mid1 - 1;
}
//cerr << ans1 << '\n';
int new_ind = min(ans, ans1);
//cerr << "new ind " << new_ind << endl;
if (new_ind == inf)
{
ok = false;
break;
}
pos = new_ind + 1;
--ind;
cnt++;
if (pos >= n) break;
if (ind < 0) break;
}
//cerr << ind << " " << cnt << endl;
if (cnt != len) ok = false;
if (ok) cout << "Plan will be successful\n";
else cout << "Plan should be changed\n";
}
}
Problem : F. Practice Time
Category : Add Hoc
Type : Implementation
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
int main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
int n;
scanf("%d", &n);
ll sum = 0;
while (n--)
{
int m;
scanf("%d", &m);
vector < pair <int, int> > vec;
while (m--)
{
int h1, m1, h2, m2;
scanf("%d:%d", &h1, &m1);
scanf("%d:%d", &h2, &m2);
if (!vec.empty())
{
int h = vec.back().first;
int m = vec.back().second;
sum += (h1 * 60 + m1) - (h * 60 + m);
}
vec.emplace_back(h2, m2);
}
}
ll h = sum / 60;
ll m = sum - h * 60;
if (h < 10) cout << "0";
cout << h << ":";
if (m < 10) cout << "0";
cout << m << '\n';
}
Problem : G. Tree Queries
Category : Graph Theory, Tree
Type : Euler Tour On Tree, Wavelet Tree
#include "bits/stdc++.h"
using namespace std;
static const int maxn = 5e5 + 5;
vector <int> graph[maxn];
int dfsTime, in[maxn], out[maxn];
void dfs(int u)
{
in[u] = ++dfsTime;
for (int v : graph[u]) dfs(v);
out[u] = dfsTime;
}
struct WAVELET_TREE
{
#define vi vector <int>
#define pb push_back
int lo, hi;
WAVELET_TREE *l, *r;
vi b;
WAVELET_TREE(int *from, int *to, int x, int y)
{
lo = x;
hi = y;
if (lo == hi || from >= to)
return;
int mid = (lo + hi) >> 1;
auto f = [mid](int x)
{
return x <= mid;
};
b.reserve(to - from + 1);
b.pb(0);
for (auto it = from; it != to; it++)
{
b.pb(b.back() + f(*it));
}
auto pivot = stable_partition(from, to, f);
l = new WAVELET_TREE(from, pivot, lo, mid);
r = new WAVELET_TREE(pivot, to, mid + 1, hi);
}
int LTE(int l, int r, int k)
{
if(l > r or k < lo) return 0;
if(hi <= k) return r - l + 1;
int lb = b[l-1], rb = b[r];
return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
}
int Count(int l, int r, int k)
{
if(l > r or k < lo or k > hi) return 0;
if(lo == hi) return r - l + 1;
int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
if(k <= mid) return this->l->Count(lb+1, rb, k);
return this->r->Count(l-lb, r-rb, k);
}
~WAVELET_TREE()
{
delete l;
delete r;
}
};
int arr[maxn], temp[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
int n, m;
cin >> n >> m;
for (int v = 2; v <= n; v++)
{
int u;
cin >> u;
graph[u].emplace_back(v);
}
dfs(1);
int maxi = 1;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
maxi = max(maxi, x);
int ind = in[i];
arr[ind] = temp[ind] = x;
}
WAVELET_TREE *T;
T = new WAVELET_TREE(temp+1, temp+n+1, 1, maxi);
while (m--)
{
int v, x;
cin >> v >> x;
int cnt = out[v] - in[v] + 1;
cnt -= T->LTE(in[v], out[v], x);
cnt += T->Count(in[v], out[v], x);
cout << cnt << '\n';
}
}
Problem : H. Another Query on String
Category : Data Structure
Type : Segment Tree
#include "bits/stdc++.h"
using namespace std;
static const int maxn = 1e5 + 5;
struct SegmentTree
{
int occ[27];
SegmentTree()
{
memset(occ, 0, sizeof occ);
}
void assignLeaf(char ch)
{
++occ[ ch - 'a' + 1 ];
}
void marge(const SegmentTree &lchild, const SegmentTree &rchild)
{
for (int i = 1; i <= 26; i++)
{
occ[i] = lchild.occ[i] + rchild.occ[i];
}
}
} Tree[maxn * 4];
string s;
void build(int node, int a, int b)
{
if (a == b)
{
Tree[node] = SegmentTree();
Tree[node].assignLeaf(s[a-1]);
return;
}
int lft = node << 1;
int rgt = lft | 1;
int mid = (a + b) >> 1;
build(lft, a, mid);
build(rgt, mid+1, b);
Tree[node].marge(Tree[lft], Tree[rgt]);
}
void update(int node, int a, int b, int pos, char ch)
{
if (a > pos || b < pos) return;
if (a >= pos && b <= pos)
{
Tree[node] = SegmentTree();
Tree[node].assignLeaf(ch);
return;
}
int lft = node << 1;
int rgt = lft | 1;
int mid = (a + b) >> 1;
update(lft, a, mid, pos, ch);
update(rgt, mid+1, b, pos, ch);
Tree[node].marge(Tree[lft], Tree[rgt]);
}
int query(int node, int a, int b, int i, int j, char ch)
{
if (a > j || b < i) return 0;
if (a >= i && b <= j) return Tree[node].occ[ ch - 'a' + 1 ];
int lft = node << 1;
int rgt = lft | 1;
int mid = (a + b) >> 1;
int p = query(lft, a, mid, i, j, ch);
int q = query(rgt, mid+1, b, i, j, ch);
return p + q;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
int n, m;
cin >> n >> m;
cin >> s;
build(1, 1, n);
while (m--)
{
int type;
cin >> type;
if (type == 1)
{
int pos;
cin >> pos;
char ch;
cin >> ch;
update(1, 1, n, pos, ch);
}
else
{
int l, r;
cin >> l >> r;
char ch;
cin >> ch;
cout << query(1, 1, n, l, r, ch) << '\n';
}
}
}
Problem : I. Wakanda Forever
Category : Graph Theory, Minimum Spanning Tree
Type : Kruskal Algorithm
#include "bits/stdc++.h"
using namespace std;
static const int maxn = 5e5 + 5;
#define ll long long int
struct Edge
{
int u, v;
ll w;
Edge(int u = 0, int v = 0, ll w = 0)
: u(u)
, v(v)
, w(w) {}
friend bool operator < (Edge A, Edge B)
{
return A.w < B.w;
}
};
vector <Edge> graph;
struct Node
{
int v;
ll w;
Node(int v = 0, ll w = 0) : v(v), w(w) {}
};
vector <Node> Tree[maxn];
int father[maxn];
int tnode, tedge;
ll d;
void makeSet()
{
for (int i = 1; i < maxn; i++) father[i] = i;
}
int findRep(int r)
{
if (r == father[r]) return r;
return father[r] = findRep(father[r]);
}
void kruskal()
{
makeSet();
sort(graph.begin(), graph.end());
int take = 0;
for (Edge E : graph)
{
int u = E.u;
int v = E.v;
ll w = E.w;
int p = findRep(u);
int q = findRep(v);
if (p != q)
{
++take;
Tree[u].emplace_back(v, w);
Tree[v].emplace_back(u, w);
father[q] = p;
}
if (take == tnode-1) break;
}
}
bool vis[maxn];
ll dfs(int u)
{
ll sum = 0;
vis[u] = 1;
for (Node E : Tree[u])
{
int v = E.v;
ll w = E.w;
if (vis[v]) continue;
sum += w + dfs(v);
}
return sum;
}
ll cost[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
cin >> tnode >> tedge >> d;
for (int i = 1; i <= tnode; i++) cin >> cost[i];
for (int i = 1; i <= tedge; i++)
{
int u, v;
ll w;
cin >> u >> v >> w;
if (u == v) continue;
if (cost[u] > 0 && cost[v] > 0)
{
graph.emplace_back(u, v, w);
}
}
kruskal();
long long sum = 0;
int cnt = 0;
for (int i = 1; i <= tnode; i++)
{
if (cost[i] == 0) continue;
if (!vis[i])
{
++cnt;
sum += dfs(i);
}
}
if (cnt) sum += (cnt-1) * d;
cout << sum << '\n';
}
Problem : J. N Factorial!
Category : Pattern
Type : Pattern
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
ll fact[100000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
fact[0] = 1;
for (int i = 1; i <= 20; i++)
{
fact[i] = (i * fact[i-1] * 1LL) % 10000;
// cerr << i << " " << fact[i] << endl;
}
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
ll n;
cin >> n;
if (n <= 20)
{
ll ans = fact[n];
string s = to_string(ans);
while (s.size() < 4) s = '0' + s;
cout << s << '\n';
}
else
{
cout << "0000\n";
}
}
}
Problem : K. Very Easy Geometry
Category : Geometry
Type : Basic Geometry
#include "bits/stdc++.h"
using namespace std;
#define PI 2*acos(0.0)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(8);
cout << fixed;
//freopen("in.txt", "r", stdin);
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
long double rad, r, a;
cin >> rad >> r >> a;
long double area = sin(rad) * a * a;
long double bad = r * r * rad;
long double ans = abs(area - bad) / 2.0;
cout << "Case " << tcase << ": " << ans << '\n';
}
}
Problem : L. Is It a Perfect Square?
Category : Number Theory
Type : Prime Factorization
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
bool isPrime(int num)
{
if (num <= 1) return 0;
if (num == 2) return 1;
if (~num & 1) return 0;
for (int i = 3; i*i <= num; i++)
{
if (num % i == 0) return 0;
}
return 1;
}
vector <int> prime, flist[105];
int factor[105][105];
void preCalc()
{
for (int i = 1; i <= 100; i++)
{
if (isPrime(i)) prime.emplace_back(i);
}
for (int i = 1; i <= 100; i++)
{
int num = i;
for (int p : prime)
{
if (p*p > num) break;
if (num % p) continue;
int cnt = 0;
while (num % p == 0) ++cnt, num /= p;
factor[i][p] = cnt;
flist[i].emplace_back(p);
}
if (num > 1)
{
factor[i][num]++;
flist[i].emplace_back(num);
}
}
}
int tfactor[105];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
//freopen("in.txt", "r", stdin);
preCalc();
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
int n;
cin >> n;
ll num = 1;
memset(tfactor, 0, sizeof tfactor);
while (n--)
{
ll x;
cin >> x;
for (int f : flist[x]) tfactor[ f ] += factor[x][f];
}
bool ok = true;
for (int p : prime) if (tfactor[p] & 1) ok = false;
if (ok == true) cout << "YES\n";
else cout << "NO\n";
}
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.