SDNU_ ACM_ ICPC_ 2022_ Winter_ Practice_ 4th [individual]

A

A Funny Game - POJ 2484 - Virtual Judge

A game

AC Code ：

#include <iostream>
using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		if (n <= 2) {
			cout << "Alice" << endl;
		}
		else {
			cout << "Bob" << endl;
		}
	}
	return 0;
}

B

Redundant Paths The path of separation - Dark explosion 1718 - Virtual Judge

B Double connected components

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
const int N = 100010;
int head[N], low[N], fa[2 * N], p, dfn[N], in[N], s[N], top, idx, cnt, num, col[N], du[N], ans, n, m;
struct node {
	int f, to, next;
}edge[200010];
void add(int x, int y) {
	edge[++cnt].to = y;
	edge[cnt].f = x;
	edge[cnt].next = head[x];
	head[x] = cnt;
}
void tarjan(int x, int f) {
	dfn[x] = low[x] = ++idx;
	s[++top] = x;
	in[x] = 1;
	for (int i = head[x]; i; i = edge[i].next) {
		int y = edge[i].to;
		if (fa[i] == f) {
			continue;
		}
		if (!dfn[y]) {
			tarjan(y, fa[i]);
			low[x] = min(low[x], low[y]);
		}
		else if (in[y]) {
			low[x] = min(dfn[y], low[x]);
		}
	}
	if (low[x] == dfn[x]) {
		num++;
		int a = -1;
		do {
			a = s[top--];
			in[a] = 0;
			col[a] = num;
		} while(a != x);
	}
}
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		fa[cnt] = ++p;
		add(y, x);
		fa[cnt] = p;
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i, 0);
		}
	}
	for (int i = 1; i <= cnt; i++) {
		int x = edge[i].f;
		int y = edge[i].to;
		if (col[x] == col[y]) continue;
		du[col[x]]++;
		du[col[y]]++;
	}
	for (int i = 1; i <= num; i++) {
		if (du[i] == 2) {
			ans++;
		}
	}
	cout << ((ans + 1) >> 1) << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

C

Girls and Boys - POJ 1466 - Virtual Judge

C Maximum independent set of bipartite graph

AC Code ：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 100010;
vector<int> a[N];
bool vis[N];
int link[N];
bool get(int x) {
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (!vis[y]) {
			vis[y] = true;
			if (link[y] == -1 || get(link[y])) {
				link[y] = x;
				return true;
			}
		}
	}
	return false;
}
void solve() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			a[i].clear();
		}
		for (int i = 0; i < n; i++) {
			int x, y, num;
			scanf("%d: (%d)", &x, &num);
			while (num--) {
				scanf("%d", &y);
				a[x].push_back(y);
			}	
		}
		memset(link, -1, sizeof(link));
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			memset(vis, false, sizeof(vis));
			if (get(i)) {
				cnt++;
			}
		}
		cout << n - cnt / 2 << endl;
	}
	return;
}
int main() {
	// ios::sync_with_stdio(0);
	// cin.tie(0);cout.tie(0);
	int t = 1;
	// cin >> t;
	for (int i = 0; i < t; i++){
		solve();
	}

	return 0;
}

D

Red and Blue - CodeForces 1469B - Virtual Judge

D The prefix and

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	int ans1 = 0;
	int ans2 = 0;
	vector<int> r(n + 5);
	for (int i = 1; i <= n; i++) {
		cin >> r[i];
		ans1 += r[i];
		ans2 = max(ans1, ans2);
	}
	int m;
	int ans3 = 0, ans4 = 0;
	cin >> m;
	vector<int> b(m + 5);
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		ans3 += b[i];
		ans4 = max(ans3, ans4);
	}
	cout << ans2 + ans4 << endl;
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

E

Expanding Rods - POJ 1905 - Virtual Judge

E Mathematics, computational geometry

AC Code ：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iomanip>
using namespace std;
const double eps = 1e-6;
void solve() {
	double x, y, z;
	while (cin >> x >> y >> z) {
		if (x < 0 || y < 0 || z < 0) {
			break;
		}
		double x1;
		x1 = (1 + y * z) * x;
		double l,r,mid, R;
		l = 0, r = x / 2;
		while (r - l > eps) {
			mid = (l + r) / 2;
			R = (4 * mid * mid + x * x) / (8 * mid);
			if (2 * R * (asin(x / (2 * R))) < x1) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
		cout << fixed << setprecision(3) << mid << endl;
	}
    return;
}
int main() {
	solve();

	return 0;
}

F

The XOR Largest Pair - LibreOJ 10050 - Virtual Judge

F Dictionary tree (trie Trees )

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
vector<int> a(100010);
vector<vector<int>> son(4000050, vector<int> (2));
int pos;
void insert(int x) {
	int p = 0;
	for (int i = 30; ~i; i--) {
		int &s = son[p][x >> i & 1];
		if(!s) {
			s = ++pos;
		}
		p = s;
	}
}
int query(int x) {
	int p = 0, res = 0;
	for (int i = 30; ~i; i--) {
		int s = x >> i & 1;
		if (son[p][!s]) {
			res += 1 << i;
			p = son[p][!s];
		}
		else {
			p = son[p][s];
		}
	}
	return res;
}
void solve() {
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		insert(a[i]);
	}
	for (int i = 1; i <= n; i++) {
		ans = max(ans, query(a[i]));
	}
	cout << ans << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

G

Teleporter - AtCoder abc167_d - Virtual Judge

G Recurrence finding law

AC Code ：

#include <iostream>
#include <vector>
using namespace std;
void solve() {
	long long n, k;
	cin >> n >> k;
	vector<int> a(n + 5);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	vector<bool> vis(n + 5, false);
	int pass = 1, cnt = 1;
	vis[1] = true;
	while (!vis[a[pass]]) {
		pass = a[pass];
		vis[pass] = true;
		cnt++;
	}
	int ans = 1;
	while (k && ans != a[pass]) {
		ans = a[ans];
		k--;
		cnt--;
	}
	k %= cnt;
	for (int j = 1; j <= k; j++) {
		ans = a[ans];
	}
	cout << ans << endl;
	return;
}
int main() {
	solve();
	return 0;
}

H

Bracket Sequencing - AtCoder abc167_f - Virtual Judge

H Greedy thinking

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	string s;
	int sum = 0;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		cin >> s;
		int cnt = 0, mn = 0;
		int len = s.size();
		for (int j = 0; j < len; j++) {
			if (s[j] == '(') {
				cnt++;
			}
			else {
				cnt--;
			}
			mn = min(mn, cnt);
		}
		v.emplace_back(cnt, mn);
		sum += cnt;
	}
	if (sum != 0) {
		cout << "No" << endl;
		return;
	}
	auto cmp = [&](pair<int, int> x,pair<int, int> y) {
		return min(x.second, x.first + y.second) > min(y.second, y.first + x.second);
	};
	sort(v.begin(), v.end(), cmp);
	int res = 0;
	for (pair<int, int> it : v) {
		if (res < -it.second) {
			cout << "No" << endl;
			return;
		}
		res += it.first;
	}
	cout << "Yes" << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

I

Regular Bracket Sequence - CodeForces 1469A - Virtual Judge

I Parentheses matching

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	string s;
	cin >> s;
	if (s.size() % 2 == 1 || s[0] == ')' || s[s.size() - 1] == '(') {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

J

Ceil Divisions - CodeForces 1469D - Virtual Judge

J recursive

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector<int> x, y;
	int m = 0;
	if (n > 32) {
		for (int i = 32; i <= n - 2; i++) {
			x.push_back(i);
			y.push_back(n - 1);
			m++;
		}
		int L = n;
		while (L > 1) {
			x.push_back(n - 1);
			y.push_back(31);
			m++;
			L = (L + 31) / 32;
		}
		n = 32;
	}
	for (int i = 2; i <= n - 2; i++) {
		x.push_back(i);
		y.push_back(n - 1);
		m++;
	}
	for (int i = 0; i < 5; i++) {
		x.push_back(n - 1);
		y.push_back(1);
		m++;
	}
	cout << m << endl;
	for (int i = 0; i < m; i++) {
		cout << x[i] + 1 << " " << y[i] + 1 << endl;
	}
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

K

Building a Fence - CodeForces 1469C - Virtual Judge

K

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 5);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int maxx = a[0], minn = a[0];
	bool ok = true;
	for (int i = 1; i < n; i++) {
		if (maxx <= a[i] - k) {
			ok = false;
		}
		else {
			minn = max(minn - k + 1, a[i]);
			maxx = min(maxx + k - 1, a[i] + k - 1);
			if (minn > maxx) {
				ok = false;
			}
		}
	}
	if (!(minn <= a[n - 1] && a[n - 1] <= maxx)) {
		ok = false;
	}
	cout << (ok ? "YES" : "NO") << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

L

: (Colon) - AtCoder abc168_c - Virtual Judge

L

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	double a, b, h, m;
	cin >> a >> b >> h >> m;
	double x, y;
	x = 30 * h + 0.5 * m;
	y = 6 * m;
	double c = fabs(x - y);
	if (c > 180) {
		c = 360 - c;
	}
	double ans = sqrt(a * a + b * b - 2 * a * b * cos(c / 180 * 2 * asin(1)));
	cout << fixed << setprecision(20) << ans << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

M

Colorful Blocks - AtCoder abc167_e - Virtual Judge

M Combinatorial mathematics DP

AC Code ：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
const long long mode = 998244353;
long long power1(long long a, long long b) {
	return b ? power1(a * a % mode, b / 2) * (b % 2 ? a : 1) % mode : 1;
}
void solve() {
	long long n, m, k, ans = 0, tmp = 1;
	cin >> n >> m >> k;
	for (int i = 0; i <= k; i++) {
		ans = (ans + (tmp * m % mode) * power1(m - 1, n - i - 1)) % mode;
		tmp = tmp * (n - i - 1) % mode * power1(i + 1, mode - 2) % mode;
	}
	cout << ans << endl;
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/