int main()
{
int tc = read();
FOR(tcase, tc)
{
int n = read();
if (n <= 10) printf("Avenger %d Rocks\n", n);
else printf("Avenger %d Sucks\n", n);
}
}
B. That's 1 minute see you tomorrow
Category : Add Hoc
Complexity : O(1)
int main()
{
int n = read();
int m = read();
int sum = 0;
bool ok = true;
FOR(i, n)
{
int s = read();
if (s < m) ok = false;
sum += m;
}
if (ok && sum == 60) puts("YES");
else puts("NO");
}
C. Function is Fun
Category : Sorting
Complexity : O(nlogn)
static const int maxn = 2e6 + 5;
static const int logn = 18;
int arr[maxn];
int main()
{
int n = read();
For(i, n) arr[i] = read();
sort(arr, arr+n);
int q = read();
while (q--)
{
int k = read();
printf("%d\n", arr[k]);
}
}
D. The Will of King
Category : Geometry
Complexity : O(1)
int main()
{
int tc;
cin >> tc;
FOR(tcase, tc)
{
ll A, B, C;
cin >> A >> B >> C;
double a = sqrt(A * 1.0);
double b = sqrt(B * 1.0);
double c = sqrt(C * 1.0);
double s = (a + b + c) / 2.0;
double area = sqrt(s * (s - a) * (s - b) * (s - c));
double all_four_triangle = 4 * area;
double whole_area = A + B + C + all_four_triangle;
cout << fixed << setprecision(6) << whole_area << endl;
}
}
E. Sabiha and Her Pocket Money
Category : Binary Lifting
Complexity: O(qlogn)
This problem was setting by shahidul bhai. I got 3 TLE's because of not noticed huge testcases.
inline int getMin(ll S, ll M)
{
if (S < M) swap(S, M);
ll steps = 0;
for (int i = 62; i >= 0; i--)
{
ll num = (1LL << i);
if (S - num >= M)
{
steps++;
S -= num;
}
}
if (S == M) return steps;
}
int main()
{
int tc = read();
FOR(tcase, tc)
{
ll S = readLL();
ll M = readLL();
if (S == M)
{
puts("0");
continue;
}
printf("%d\n", getMin(S, M));
}
}
F. Noogler Mamun & his Adjophobia
Category :
Complexity:
I could not manage to solve the problem during contest time. I coded 2 hours but finally got TLE.
#include "bits/stdc++.h"
using namespace std;
#define FI freopen("in.txt", "r", stdin)
#define FO freopen("out.txt", "w", stdout)
#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define FOR(i, n) for (int i = 1; i <= n; i++)
#define For(i, n) for (int i = 0; i < n; i++)
#define ROF(i, n) for (int i = n; i >= 1; i--)
#define Rof(i, n) for (int i = n-1; i >= 0; i--)
#define FORI(i, n) for (auto i : n)
#define ll long long
#define ull unsigned long long
#define vi vector <int>
#define vl vector <ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mk make_pair
#define ff first
#define ss second
#define eb emplace_back
#define em emplace
#define pb push_back
#define ppb pop_back
#define All(a) a.begin(), a.end()
#define memo(a, b) memset(a, b, sizeof a)
#define Sort(a) sort(All(a))
#define ED(a) Sort(a), a.erase(unique(All(a)), a.end())
#define rev(a) reverse(All(a))
//#define sz(a) (int)a.size()
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define maxAll(a) *max_element(All(a))
#define minAll(a) *min_element(All(a))
#define allUpper(a) transform(All(a), a.begin(), :: toupper)
#define allLower(a) transform(All(a), a.begin(), :: tolower)
#define endl '\n'
#define nl puts("")
#define ub upper_bound
#define lb lower_bound
#define Exp exp(1.0)
#define PIE 2*acos(0.0)
#define Sin(a) sin(((a)*PIE)/180.0)
#define EPS 1e-9
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template <typename T> using orderset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "ext/rope"
using namespace __gnu_cxx;
// rope <int> Rope;
int dr[] = {1, -1, 0, 0}; // 4 Direction
int dc[] = {0, 0, 1, -1};
// int dr[] = {0, 0, 1, -1, 1, 1, -1, -1}; // 8 Direction
// int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
// int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
// int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
inline int setbit(int mask, int pos) { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos) { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos) { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos) { return (bool)(mask & (1 << pos)); }
#define popcount(mask) __builtin_popcount(mask) // count set bit
#define popcountLL(mask) __builtin_popcountll(mask) // for long long
inline int read() { int a; scanf("%d", &a); return a; }
inline ll readLL() { ll a; scanf("%lld", &a); return a; }
inline double readDD() { double a; scanf("%lf", &a); return a; }
template <typename T> string toString(T num) { stringstream ss; ss << num; return ss.str(); }
int toInt(string s) { int num; istringstream iss(s); iss >> num; return num; }
ll toLLong(string s) { ll num; istringstream iss(s); iss >> num; return num; }
#define inf 1e17
#define mod 1000000007
static const int maxn = 2e5 + 5;
static const int logn = 18;
int koybar[27];
int which[27];
inline void precalc()
{
int cnt = 0;
int type = 2;
for (int i = 1; i <= 15; i++)
{
koybar[i] = ++cnt;
which[i] = type;
if (cnt >= 3) cnt = 0, type++;
}
cnt = 0;
for (int i = 16; i <= 19; i++)
{
which[i] = type;
koybar[i] = ++cnt;
}
type++;
cnt = 0;
for (int i = 20; i <= 22; i++)
{
which[i] = type;
koybar[i] = ++cnt;
}
type++;
cnt = 0;
for (int i = 23; i <= 26; i++)
{
which[i] = type;
koybar[i] = ++cnt;
}
}
int dir[] = {-1, -3, +1, +3};
inline bool inside(int r)
{
return r >= 2 && r <= 9;
}
int vis[20];
int dist[20];
int father[20];
inline vi getDist(int src, int des, char des_char)
{
for (int i = 0; i < 12; i++)
{
father[i] = -1;
dist[i] = 0;
vis[i] = 0;
}
queue <int> PQ;
PQ.push(src);
vis[src] = 1;
dist[src] = 0;
while (!PQ.empty())
{
int u = PQ.front(); PQ.pop();
if (u == 2)
{
int v = 3;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
//trace2(u, v);
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 5;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 3)
{
int v = 2;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 6;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 4)
{
int v = 5;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 7;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 5)
{
int v = 2;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 4;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 6;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 8;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 6)
{
int v = 3;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 5;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 9;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 7)
{
int v = 4;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 8;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 8)
{
int v = 5;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 7;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 9;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
else if (u == 9)
{
int v = 6;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
v = 8;
if (inside(v) && !vis[v])
{
dist[v] = dist[u] + 1;
vis[v] = 1;
father[v] = u;
PQ.em(v);
}
}
}
int press = 0;
int u = des;
vi vec;
do {
if (u == des)
{
for (int i = 0; i < koybar[des_char - 'a' + 1]; i++)
{
vec.eb(des);
}
}
else vec.eb( u );
u = father[u];
} while (u != -1);
return vec;
}
using pcc = pair <char, char>;
int koto[30][30];
pcc koto_num[26*26+1000];
vi kikiache[26*26+1000];
char s[maxn];
int main()
{
precalc();
int id = 0;
for (char i = 'a'; i <= 'z'; i++)
{
for (char j = 'a'; j <= 'z'; j++)
{
int u = i - 'a' + 1;
int v = j - 'a' + 1;
++id;
koto[u][v] = id;
koto_num[id] = pcc(i, j);
kikiache[id] = getDist(which[u], which[v], j);
}
}
int tc = read();
FOR(tcase, tc)
{
scanf("%s", s);
int len = strlen(s);
vi path;
int u = s[0] - 'a' + 1;
int v = s[0] - 'a' + 1;
int kotote_ache = koto[u][v];
int sum = kikiache[kotote_ache].size();
for (int i = sum - 1; i >= 0; i--)
{
path.eb(kikiache[kotote_ache][i]);
}
for (int i = 0; i < len-1; i++)
{
int u = s[i] - 'a' + 1;
int v = s[i+1] - 'a' + 1;
int kotote_ache = koto[u][v];
int lenTemp = kikiache[kotote_ache].size();
if (which[u] != which[v])
{
sum += lenTemp-1;
for (int j = lenTemp-2; j >= 0; j--) path.eb(kikiache[kotote_ache][j]);
}
else
{
sum += lenTemp;
for (int j = lenTemp-1; j >= 0; j--) path.eb(kikiache[kotote_ache][j]);
}
}
printf("%d\n", sum);
for (int i = 0; i < sum; i++)
{
printf("%d", path[i]);
if (i == sum-1) puts("");
else printf(" ");
}
path.clear();
}
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.