> It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today!↵
↵
## [problem:1737A]↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737A]↵
</spoiler>↵
↵
<spoiler summary="Solution(snippet ( low_ C++)">↵
↵
~~~~~↵
...↵
void execute(int test_number)↵
{↵
cin>>n>>k>>str;↵
vector <int> count_char(26, 0);↵
for (char c: str) count_char[c - 'a']++;↵
string ans = "";↵
for (int i = 0; i < min(25, n/k); i++) {↵
while (k - ans.size() > count_char[i]) {↵
ans.push_back(i + 'a');↵
}↵
}↵
↵
char c = 'a' + min(n / k, 25);↵
while (k > ans.size()) {↵
ans += c;↵
}↵
reverse(ans.begin(), ans.end());↵
cout << ans << "\n";↵
}↵
...↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1737B]↵
↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737B]↵
</spoiler>↵
↵
<spoiler summary="Solution(snippet (low_, C++)">↵
↵
~~~~~↵
...↵
ll l, r;↵
↵
ll bs_sqrt(ll x) {↵
ll left = 0, right = 2000000123;↵
while (right > left) {↵
ll mid = (left + right) / 2;↵
↵
if (mid * mid > x) right = mid;↵
else left = mid + 1;↵
}↵
return left - 1;↵
}↵
↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin >> l >> r;↵
ll sql = bs_sqrt(l), sqr = bs_sqrt(r);↵
ll ans;↵
if (sql == sqr) {↵
ans = 0;↵
for (int i = 0; i < 3; i++) {↵
if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;↵
}↵
} else {↵
ans = (sqr - sql - 1) * 3;↵
for (int i = 0; i < 3; i++) {↵
if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;↵
if (l <= sqr * (sqr + i) && sqr * (sqr + i) <= r) ans++;↵
}↵
}↵
cout << ans << "\n";↵
}↵
...↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
## [problem:1737C]↵
↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737C]↵
</spoiler>↵
↵
<spoiler summary="Solution(snippet (low_, C++)">↵
↵
~~~~~↵
...↵
int n;↵
int x[3], y[3];↵
int u, v;↵
↵
pii centralSquare() {↵
int a = (x[0] == x[1]) ? x[0] : x[2];↵
int b = (y[0] == y[1]) ? y[0] : y[2];↵
return {a, b};↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin>>n;↵
for (int i=0; i<3; i++) cin>>x[i]>>y[i];↵
cin>>u>>v;↵
↵
int cx = centralSquare().first, cy = centralSquare().second;↵
↵
if ((cx == 1 || cx == n) && (cy == 1 || cy == n)) { // "corner" case, literally↵
// the crickets can only reach coordinates within the edges that already contains at least 2 crickets,↵
// which contains the centralSquare of the L↵
cout << ((u == cx || v == cy) ? "YES\n" : "NO\n");↵
} else {↵
if ((cx + cy) % 2 == (u + v) % 2) {↵
cout << (cx % 2 == u % 2 ? "YES\n" : "NO\n"); ↵
} else { // can be prove to always reach, since we have ways to align 2 crickets in the same diagonal as target↵
cout << "YES\n"; ↵
}↵
}↵
}↵
...↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1737D]↵
↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737D]↵
</spoiler>↵
↵
<spoiler summary="Solution (magnified, C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define db long double↵
#define ull unsigned long long↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define pb push_back↵
#define all(a) a.begin(), a.end()↵
↵
using namespace std;↵
↵
#define pper(a) cerr << #a << " = " << a << endl;↵
↵
void per() { cerr << endl; }↵
template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); }↵
↵
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }↵
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }↵
↵
template<class U, class V> ↵
ostream& operator<<(ostream& out, const pair<U, V>& a) {↵
return out << "(" << a.x << ", " << a.y << ")";↵
}↵
↵
template<class U, class V> ↵
istream& operator>>(istream& in, pair<U, V>& a) {↵
return in >> a.x >> a.y;↵
}↵
↵
template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type>↵
ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; }↵
↵
template<class T>↵
void readArr(T from, T to) {↵
for (auto i = from; i != to; ++i) cin >> *i;↵
}↵
↵
mt19937 mrand(1337); ↵
unsigned int myRand32() {↵
return mrand() & (unsigned int)(-1);↵
}↵
↵
unsigned ll myRand64() {↵
return ((ull)myRand32() << 32) ^ myRand32();↵
}↵
↵
const int mod = 1000000007;↵
↵
void add(int& a, int b) {↵
a += b; if (a >= mod) a -= mod;↵
}↵
↵
void dec(int &a, int b) {↵
a -= b; if (a < 0) a += mod;↵
}↵
↵
int mult(int a, int b) {↵
return a * (ll)b % mod;↵
}↵
↵
int bp(int a, int b) {↵
int res = 1;↵
while (b > 0) {↵
if (b & 1) res = mult(res, a);↵
a = mult(a, a);↵
b >>= 1;↵
}↵
return res;↵
}↵
↵
const int N = 507;↵
↵
ll f[N][N];↵
↵
int main(){↵
#ifdef LOCAL↵
freopen("N_input.txt", "r", stdin);↵
//freopen("N_output.txt", "w", stdout);↵
#endif↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t;↵
cin >> t;↵
↵
for (int a = 0; a < t; ++a) {↵
↵
int n, m;↵
cin >> n >> m;↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
f[i][j] = 1e18;↵
}↵
f[i][i] = 0;↵
}↵
↵
vector<tuple<int, int, int> > ed;↵
↵
for (int i = 0; i < m; ++i) {↵
int u, v, w;↵
cin >> u >> v >> w;↵
ed.pb(make_tuple(u - 1, v - 1, w));↵
f[u - 1][v - 1] = 1;↵
f[v - 1][u - 1] = 1;↵
}↵
↵
for (int k = 0; k < n; ++k) {↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);↵
}↵
}↵
}↵
↵
ll ans = 1e18;↵
for (auto x : ed) {↵
int u = get<0>(x);↵
int v = get<1>(x);↵
int w = get<2>(x);↵
↵
// per(ans, u, v, w);↵
↵
ans = min(ans, (ll) w * (f[0][u] + f[n - 1][v] + 1));↵
ans = min(ans, (ll) w * (f[0][v] + f[n - 1][u] + 1));↵
↵
// per(ans, u, v, w);↵
↵
for (int i = 0; i < n; ++i) {↵
ans = min(ans, (ll) w * (f[v][i] + 1 + f[i][0] + f[i][n-1] + 1));↵
ans = min(ans, (ll) w * (f[u][i] + 1 + f[i][0] + f[i][n-1] + 1));↵
}↵
↵
}↵
↵
cout << ans << '\n';↵
↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
## [problem:1737E]↵
↵
Author: [user:ngfam_kongu,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737E]↵
</spoiler>↵
↵
<spoiler summary="Solution(C++)">↵
↵
~~~~~↵
#include<iostream>↵
#include<fstream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<cmath>↵
#include<vector>↵
#include<deque>↵
#include<set>↵
#include<map>↵
#include<bitset>↵
#include<ctime>↵
#include<queue>↵
using namespace std;↵
#define ll long long↵
#define pii pair <ll, ll>↵
#define ld long double↵
#define XX first↵
#define YY second↵
#define mattype ll↵
#define matrix vector <vector <mattype> >↵
↵
// constants:↵
const int mn = 1000005;↵
const int mod = 1000000007;↵
const long long inf = 4444444444444444444;↵
const int sminf = 1111111111;↵
const bool is_multitest = 1;↵
const bool is_interactive = 0;↵
↵
// i/o methods:↵
const bool input_from_file = 0;↵
const bool output_to_file = 0;↵
#define filename ""↵
#define in_extension "inp"↵
#define out_extension "out"↵
↵
// debug functions↵
void debug_vector(string name, vector <ll> v) {↵
cerr << name << " @size=" << v.size() << ": [";↵
for (int x: v) cerr << x << " ";↵
cerr << "]\n";↵
}↵
↵
void debug_2d_vector(string name, vector <vector<ll> > v) {↵
↵
cerr << name << " @size=" << v.size() << ": {\n";↵
for (int i = 0; i < v.size(); i++) {↵
cerr << "\t";↵
debug_vector(name + "[" + to_string(i) + "]", v[i]);↵
}↵
cerr << "}\n";↵
}↵
↵
// data preprocessing: (e.g.: divisor generating, prime sieve)↵
ll POW2[mn];↵
void preprocess()↵
{↵
POW2[0] = 1;↵
for (int i = 1; i < mn; i++) POW2[i] = POW2[i — 1] * 2 % mod;↵
}↵
↵
// global variables:↵
ll n;↵
↵
ll POW(ll u, ll v) {↵
if (v == 0) return 1;↵
ll mid = POW(u, v / 2);↵
mid = (mid * mid) % mod;↵
return (v & 1) ? (mid * u % mod) : mid;↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin>>n;↵
↵
if (n == 1) {↵
cout << "1\n";↵
return;↵
}↵
vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);↵
sufsum[n] = ans[n] = POW(POW2[(n — 1) / 2], mod — 2);↵
for (int i = n — 1; i > 1; i--) {↵
ans[i] = POW(POW2[(i + 1) / 2], mod — 2);↵
if (2 * i <= n) ans[i] = ans[i] * (1 — sufsum[i * 2] + mod) % mod;↵
sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;↵
}↵
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";↵
↵
}↵
// REMEMBER TO CHOOSE TEST METHODS↵
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS↵
// Solution by low_↵
↵
signed main()↵
{↵
#ifdef lowie↵
if (!is_interactive)↵
{↵
freopen("test.inp", "r", stdin);↵
freopen("test.out", "w", stdout);↵
}↵
#else↵
if (input_from_file) freopen(filename"."in_extension, "r", stdin);↵
if (output_to_file) freopen(filename"."out_extension, "w", stdout);↵
#endif↵
if (!is_interactive)↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
}↵
↵
preprocess();↵
int ntest;↵
if (is_multitest) cin >> ntest;↵
else ntest = 1;↵
↵
for (int testno = 1; testno <= ntest; testno++)↵
// use for instead of while to serve facebook hacker cup test format↵
{↵
execute(testno); // only start coding in this function, not in main↵
}↵
}↵
// Template by low_↵
// Contact me via mail: ttuandung1803@gmail.com↵
// ...or codeforces: www.codeforces.com/profiles/low_↵
// ...or if you're interested in food: www.instagram.com/lowie.exe/↵
snippet (low_, C++)">↵
↵
~~~~~↵
...↵
// data preprocessing: (e.g.: divisor generating, prime sieve)↵
ll POW2[mn];↵
void preprocess()↵
{↵
POW2[0] = 1;↵
for (int i = 1; i < mn; i++) POW2[i] = POW2[i — 1] * 2 % mod;↵
}↵
↵
// global variables:↵
ll n;↵
↵
ll POW(ll u, ll v) {↵
if (v == 0) return 1;↵
ll mid = POW(u, v / 2);↵
mid = (mid * mid) % mod;↵
return (v & 1) ? (mid * u % mod) : mid;↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin>>n;↵
↵
if (n == 1) {↵
cout << "1\n";↵
return;↵
}↵
vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);↵
sufsum[n] = ans[n] = POW(POW2[(n — 1) / 2], mod — 2);↵
for (int i = n — 1; i > 1; i--) {↵
ans[i] = POW(POW2[(i + 1) / 2], mod — 2);↵
if (2 * i <= n) ans[i] = ans[i] * (1 — sufsum[i * 2] + mod) % mod;↵
sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;↵
}↵
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";↵
↵
}↵
...↵
~~~~~↵
</spoiler>↵
↵
## [problem:1737F]↵
↵
Author: [user:351F44,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
Observation: Assume that x is composite number and divisor of n. Among all the multiples of x, the number of the divisor of n must be less than or equal to m/2.↵
↵
First, factorize n. Assume that w is divisor of n. If w is in the form of a^4, a^3b^2, or a^2b^2c^2, it can be proved that there is no answer. Otherwise, there can be two cases.↵
↵
If the possible maximum exponent of prime factor is 2, place the divisors like this: 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a. And expand the sequence as follows:↵
↵
1. Repeat the current sequence twice — 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a 1 a^2 a.↵
2. Multiply the odd-indexed elements of first half and the even-indexed elements of second half by the new prime factor. Index 1 is exception — 1 a^2b^2 bc a^2b b^2c ab a^2c ab^2 ac c a^2b^2c b a^2bc b^2 abc a^2 ab^2c a / 1 a^2 ab b a^2b a.↵
3. If more prime factor exists, jump to "Otherwise".↵
↵
Otherwise, place the divisors like this: 1 a^3 a a^2 / 1 a. Now the exponents of other prime factors are all 1, and we can expand the sequence as follows: ↵
↵
1. Repeat the current sequence twice — 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a.↵
2. Multiply the even-indexed elements of first half and the odd-indexed elements of second half by the new prime factor — 1 a^3b a a^2b b a^3 ab a^2 / 1 ab b a.↵
3-1. If the maximum exponent is 3, swap a and b — 1 a^3b b a^2b a a^3 ab a^2↵
3-2. Otherwise, swap b and ab — 1 b ab a.↵
↵
Like this, we can expand the sequence↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
~~~~~↵
#import<bits/stdc++.h>↵
#define endl '\n'↵
using namespace std;↵
↵
int m, t, b[18], check[18], cnt[5];↵
vector<int>v;↵
vector<vector<int>>a;↵
↵
void initialize(int m)↵
{↵
fill(b, b + m + 1, 0);↵
fill(check, check + m + 1, 0);↵
fill(cnt, cnt + 5, 0);↵
v.clear();↵
a.clear();↵
}↵
void insert1(int p1, int c1)↵
{↵
v[p1] = c1;↵
a.push_back(v);↵
}↵
void insert2(int p1, int p2, int c1, int c2)↵
{↵
v[p1] = c1;↵
v[p2] = c2;↵
a.push_back(v);↵
}↵
↵
void f1(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 0; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
swap(a[n / 2], a[n]);↵
}↵
void f2(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 1; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
a[n][x] = 1;↵
}↵
void f3(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 0; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
swap(a[n], a[2 * n — 1]);↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
for(cin >> t; t--;)↵
{↵
cin >> m;↵
for(int i = 1; i <= m; i++)↵
{↵
cin >> b[i];↵
cnt[min(b[i], 4)]++;↵
}↵
if(cnt[4] || cnt[3] >= 2 || cnt[3] && cnt[2] || cnt[2] >= 3)↵
{↵
cout << -1 << endl;↵
initialize(m);↵
continue;↵
}↵
↵
for(int i = 1; i <= m; i++)v.push_back(0);↵
a.push_back(v);↵
↵
if(cnt[2])↵
{↵
int p1 = -1, p2 = -1;↵
for(int i = 1; i <= m; i++)↵
{↵
if(b[i] == 2)↵
{↵
if(~p1)p2 = i - 1;↵
else p1 = i - 1;↵
}↵
}↵
if(~p2)↵
{↵
insert2(p1, p2, 2, 2);↵
insert2(p1, p2, 0, 1);↵
insert2(p1, p2, 2, 1);↵
insert2(p1, p2, 0, 2);↵
insert2(p1, p2, 1, 1);↵
insert2(p1, p2, 2, 0);↵
insert2(p1, p2, 1, 2);↵
insert2(p1, p2, 1, 0);↵
check[p1 + 1] = check[p2 + 1] = 1;↵
}↵
else↵
{↵
insert1(p1, 2);↵
insert1(p1, 1);↵
check[p1 + 1] = 1;↵
}↵
for(int i = 1; i <= m; i++)↵
{↵
if(check[i])continue;↵
if(a.size() % 2)f2(i - 1);↵
else f3(i - 1);↵
}↵
}↵
else↵
{↵
if(cnt[3])↵
{↵
int p = 0;↵
for(int i = 1; i <= m; i++)↵
{↵
if(b[i] == 3)p = i - 1;↵
}↵
insert1(p, 3);↵
insert1(p, 1);↵
insert1(p, 2);↵
check[p + 1] = 1;↵
}↵
else↵
{↵
insert1(0, 1);↵
check[1] = 1;↵
}↵
for(int i = 1; i <= m; i++)↵
{↵
if(!check[i])f1(i - 1);↵
}↵
}↵
↵
for(auto &v: a)↵
{↵
if(*max_element(v.begin(), v.end()))↵
{↵
for(auto &p: v)cout << p << ' ';↵
cout << endl;↵
}↵
}↵
initialize(m);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
## [problem:1737G]↵
↵
Author: [user:magnified,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737G]↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
[submission:175031734]↵
</spoiler>↵
↵
↵
## [problem:1737A]↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737A]↵
</spoiler>↵
↵
<spoiler summary="Solution
↵
~~~~~↵
...↵
void execute(int test_number)↵
{↵
cin>>n>>k>>str;↵
vector <int> count_char(26, 0);↵
for (char c: str) count_char[c - 'a']++;↵
string ans = "";↵
for (int i = 0; i < min(25, n/k); i++) {↵
while (k - ans.size() > count_char[i]) {↵
ans.push_back(i + 'a');↵
}↵
}↵
↵
char c = 'a' + min(n / k, 25);↵
while (k > ans.size()) {↵
ans += c;↵
}↵
reverse(ans.begin(), ans.end());↵
cout << ans << "\n";↵
}↵
...↵
~~~~~↵
↵
</spoiler>↵
↵
## [problem:1737B]↵
↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737B]↵
</spoiler>↵
↵
<spoiler summary="Solution
↵
~~~~~↵
...↵
ll l, r;↵
↵
ll bs_sqrt(ll x) {↵
ll left = 0, right = 2000000123;↵
while (right > left) {↵
ll mid = (left + right) / 2;↵
↵
if (mid * mid > x) right = mid;↵
else left = mid + 1;↵
}↵
return left - 1;↵
}↵
↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin >> l >> r;↵
ll sql = bs_sqrt(l), sqr = bs_sqrt(r);↵
ll ans;↵
if (sql == sqr) {↵
ans = 0;↵
for (int i = 0; i < 3; i++) {↵
if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;↵
}↵
} else {↵
ans = (sqr - sql - 1) * 3;↵
for (int i = 0; i < 3; i++) {↵
if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;↵
if (l <= sqr * (sqr + i) && sqr * (sqr + i) <= r) ans++;↵
}↵
}↵
cout << ans << "\n";↵
}↵
...↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
## [problem:1737C]↵
↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737C]↵
</spoiler>↵
↵
<spoiler summary="Solution
↵
~~~~~↵
...↵
int n;↵
int x[3], y[3];↵
int u, v;↵
↵
pii centralSquare() {↵
int a = (x[0] == x[1]) ? x[0] : x[2];↵
int b = (y[0] == y[1]) ? y[0] : y[2];↵
return {a, b};↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin>>n;↵
for (int i=0; i<3; i++) cin>>x[i]>>y[i];↵
cin>>u>>v;↵
↵
int cx = centralSquare().first, cy = centralSquare().second;↵
↵
if ((cx == 1 || cx == n) && (cy == 1 || cy == n)) { // "corner" case, literally↵
// the crickets can only reach coordinates within the edges that already contains at least 2 crickets,↵
// which contains the centralSquare of the L↵
cout << ((u == cx || v == cy) ? "YES\n" : "NO\n");↵
} else {↵
if ((cx + cy) % 2 == (u + v) % 2) {↵
cout << (cx % 2 == u % 2 ? "YES\n" : "NO\n"); ↵
} else { // can be prove to always reach, since we have ways to align 2 crickets in the same diagonal as target↵
cout << "YES\n"; ↵
}↵
}↵
}↵
...↵
~~~~~↵
↵
↵
</spoiler>↵
↵
## [problem:1737D]↵
↵
Author: [user:low_,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737D]↵
</spoiler>↵
↵
<spoiler summary="Solution (magnified, C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define db long double↵
#define ull unsigned long long↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define pb push_back↵
#define all(a) a.begin(), a.end()↵
↵
using namespace std;↵
↵
#define pper(a) cerr << #a << " = " << a << endl;↵
↵
void per() { cerr << endl; }↵
template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); }↵
↵
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }↵
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }↵
↵
template<class U, class V> ↵
ostream& operator<<(ostream& out, const pair<U, V>& a) {↵
return out << "(" << a.x << ", " << a.y << ")";↵
}↵
↵
template<class U, class V> ↵
istream& operator>>(istream& in, pair<U, V>& a) {↵
return in >> a.x >> a.y;↵
}↵
↵
template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type>↵
ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; }↵
↵
template<class T>↵
void readArr(T from, T to) {↵
for (auto i = from; i != to; ++i) cin >> *i;↵
}↵
↵
mt19937 mrand(1337); ↵
unsigned int myRand32() {↵
return mrand() & (unsigned int)(-1);↵
}↵
↵
unsigned ll myRand64() {↵
return ((ull)myRand32() << 32) ^ myRand32();↵
}↵
↵
const int mod = 1000000007;↵
↵
void add(int& a, int b) {↵
a += b; if (a >= mod) a -= mod;↵
}↵
↵
void dec(int &a, int b) {↵
a -= b; if (a < 0) a += mod;↵
}↵
↵
int mult(int a, int b) {↵
return a * (ll)b % mod;↵
}↵
↵
int bp(int a, int b) {↵
int res = 1;↵
while (b > 0) {↵
if (b & 1) res = mult(res, a);↵
a = mult(a, a);↵
b >>= 1;↵
}↵
return res;↵
}↵
↵
const int N = 507;↵
↵
ll f[N][N];↵
↵
int main(){↵
#ifdef LOCAL↵
freopen("N_input.txt", "r", stdin);↵
//freopen("N_output.txt", "w", stdout);↵
#endif↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t;↵
cin >> t;↵
↵
for (int a = 0; a < t; ++a) {↵
↵
int n, m;↵
cin >> n >> m;↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
f[i][j] = 1e18;↵
}↵
f[i][i] = 0;↵
}↵
↵
vector<tuple<int, int, int> > ed;↵
↵
for (int i = 0; i < m; ++i) {↵
int u, v, w;↵
cin >> u >> v >> w;↵
ed.pb(make_tuple(u - 1, v - 1, w));↵
f[u - 1][v - 1] = 1;↵
f[v - 1][u - 1] = 1;↵
}↵
↵
for (int k = 0; k < n; ++k) {↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);↵
}↵
}↵
}↵
↵
ll ans = 1e18;↵
for (auto x : ed) {↵
int u = get<0>(x);↵
int v = get<1>(x);↵
int w = get<2>(x);↵
↵
// per(ans, u, v, w);↵
↵
ans = min(ans, (ll) w * (f[0][u] + f[n - 1][v] + 1));↵
ans = min(ans, (ll) w * (f[0][v] + f[n - 1][u] + 1));↵
↵
// per(ans, u, v, w);↵
↵
for (int i = 0; i < n; ++i) {↵
ans = min(ans, (ll) w * (f[v][i] + 1 + f[i][0] + f[i][n-1] + 1));↵
ans = min(ans, (ll) w * (f[u][i] + 1 + f[i][0] + f[i][n-1] + 1));↵
}↵
↵
}↵
↵
cout << ans << '\n';↵
↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
## [problem:1737E]↵
↵
Author: [user:ngfam_kongu,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737E]↵
</spoiler>↵
↵
<spoiler summary="Solution
↵
~~~~~↵
#include<iostream>↵
#include<fstream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<cmath>↵
#include<vector>↵
#include<deque>↵
#include<set>↵
#include<map>↵
#include<bitset>↵
#include<ctime>↵
#include<queue>↵
using namespace std;↵
#define ll long long↵
#define pii pair <ll, ll>↵
#define ld long double↵
#define XX first↵
#define YY second↵
#define mattype ll↵
#define matrix vector <vector <mattype> >↵
↵
// constants:↵
const int mn = 1000005;↵
const int mod = 1000000007;↵
const long long inf = 4444444444444444444;↵
const int sminf = 1111111111;↵
const bool is_multitest = 1;↵
const bool is_interactive = 0;↵
↵
// i/o methods:↵
const bool input_from_file = 0;↵
const bool output_to_file = 0;↵
#define filename ""↵
#define in_extension "inp"↵
#define out_extension "out"↵
↵
// debug functions↵
void debug_vector(string name, vector <ll> v) {↵
cerr << name << " @size=" << v.size() << ": [";↵
for (int x: v) cerr << x << " ";↵
cerr << "]\n";↵
}↵
↵
void debug_2d_vector(string name, vector <vector<ll> > v) {↵
↵
cerr << name << " @size=" << v.size() << ": {\n";↵
for (int i = 0; i < v.size(); i++) {↵
cerr << "\t";↵
debug_vector(name + "[" + to_string(i) + "]", v[i]);↵
}↵
cerr << "}\n";↵
}↵
↵
// data preprocessing: (e.g.: divisor generating, prime sieve)↵
ll POW2[mn];↵
void preprocess()↵
{↵
POW2[0] = 1;↵
for (int i = 1; i < mn; i++) POW2[i] = POW2[i — 1] * 2 % mod;↵
}↵
↵
// global variables:↵
ll n;↵
↵
ll POW(ll u, ll v) {↵
if (v == 0) return 1;↵
ll mid = POW(u, v / 2);↵
mid = (mid * mid) % mod;↵
return (v & 1) ? (mid * u % mod) : mid;↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin>>n;↵
↵
if (n == 1) {↵
cout << "1\n";↵
return;↵
}↵
vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);↵
sufsum[n] = ans[n] = POW(POW2[(n — 1) / 2], mod — 2);↵
for (int i = n — 1; i > 1; i--) {↵
ans[i] = POW(POW2[(i + 1) / 2], mod — 2);↵
if (2 * i <= n) ans[i] = ans[i] * (1 — sufsum[i * 2] + mod) % mod;↵
sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;↵
}↵
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";↵
↵
}↵
// REMEMBER TO CHOOSE TEST METHODS↵
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS↵
// Solution by low_↵
↵
signed main()↵
{↵
#ifdef lowie↵
if (!is_interactive)↵
{↵
freopen("test.inp", "r", stdin);↵
freopen("test.out", "w", stdout);↵
}↵
#else↵
if (input_from_file) freopen(filename"."in_extension, "r", stdin);↵
if (output_to_file) freopen(filename"."out_extension, "w", stdout);↵
#endif↵
if (!is_interactive)↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
}↵
↵
preprocess();↵
int ntest;↵
if (is_multitest) cin >> ntest;↵
else ntest = 1;↵
↵
for (int testno = 1; testno <= ntest; testno++)↵
// use for instead of while to serve facebook hacker cup test format↵
{↵
execute(testno); // only start coding in this function, not in main↵
}↵
}↵
// Template by low_↵
// Contact me via mail: ttuandung1803@gmail.com↵
// ...or codeforces: www.codeforces.com/profiles/low_↵
// ...or if you're interested in food: www.instagram.com/lowie.exe/↵
↵
~~~~~↵
...↵
// data preprocessing: (e.g.: divisor generating, prime sieve)↵
ll POW2[mn];↵
void preprocess()↵
{↵
POW2[0] = 1;↵
for (int i = 1; i < mn; i++) POW2[i] = POW2[i — 1] * 2 % mod;↵
}↵
↵
// global variables:↵
ll n;↵
↵
ll POW(ll u, ll v) {↵
if (v == 0) return 1;↵
ll mid = POW(u, v / 2);↵
mid = (mid * mid) % mod;↵
return (v & 1) ? (mid * u % mod) : mid;↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
cin>>n;↵
↵
if (n == 1) {↵
cout << "1\n";↵
return;↵
}↵
vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);↵
sufsum[n] = ans[n] = POW(POW2[(n — 1) / 2], mod — 2);↵
for (int i = n — 1; i > 1; i--) {↵
ans[i] = POW(POW2[(i + 1) / 2], mod — 2);↵
if (2 * i <= n) ans[i] = ans[i] * (1 — sufsum[i * 2] + mod) % mod;↵
sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;↵
}↵
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";↵
↵
}↵
...↵
~~~~~↵
</spoiler>↵
↵
## [problem:1737F]↵
↵
Author: [user:351F44,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
Observation: Assume that x is composite number and divisor of n. Among all the multiples of x, the number of the divisor of n must be less than or equal to m/2.↵
↵
First, factorize n. Assume that w is divisor of n. If w is in the form of a^4, a^3b^2, or a^2b^2c^2, it can be proved that there is no answer. Otherwise, there can be two cases.↵
↵
If the possible maximum exponent of prime factor is 2, place the divisors like this: 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a. And expand the sequence as follows:↵
↵
1. Repeat the current sequence twice — 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a 1 a^2 a.↵
2. Multiply the odd-indexed elements of first half and the even-indexed elements of second half by the new prime factor. Index 1 is exception — 1 a^2b^2 bc a^2b b^2c ab a^2c ab^2 ac c a^2b^2c b a^2bc b^2 abc a^2 ab^2c a / 1 a^2 ab b a^2b a.↵
3. If more prime factor exists, jump to "Otherwise".↵
↵
Otherwise, place the divisors like this: 1 a^3 a a^2 / 1 a. Now the exponents of other prime factors are all 1, and we can expand the sequence as follows: ↵
↵
1. Repeat the current sequence twice — 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a.↵
2. Multiply the even-indexed elements of first half and the odd-indexed elements of second half by the new prime factor — 1 a^3b a a^2b b a^3 ab a^2 / 1 ab b a.↵
3-1. If the maximum exponent is 3, swap a and b — 1 a^3b b a^2b a a^3 ab a^2↵
3-2. Otherwise, swap b and ab — 1 b ab a.↵
↵
Like this, we can expand the sequence↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
~~~~~↵
#import<bits/stdc++.h>↵
#define endl '\n'↵
using namespace std;↵
↵
int m, t, b[18], check[18], cnt[5];↵
vector<int>v;↵
vector<vector<int>>a;↵
↵
void initialize(int m)↵
{↵
fill(b, b + m + 1, 0);↵
fill(check, check + m + 1, 0);↵
fill(cnt, cnt + 5, 0);↵
v.clear();↵
a.clear();↵
}↵
void insert1(int p1, int c1)↵
{↵
v[p1] = c1;↵
a.push_back(v);↵
}↵
void insert2(int p1, int p2, int c1, int c2)↵
{↵
v[p1] = c1;↵
v[p2] = c2;↵
a.push_back(v);↵
}↵
↵
void f1(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 0; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
swap(a[n / 2], a[n]);↵
}↵
void f2(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 1; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
a[n][x] = 1;↵
}↵
void f3(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 0; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
swap(a[n], a[2 * n — 1]);↵
}↵
↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
for(cin >> t; t--;)↵
{↵
cin >> m;↵
for(int i = 1; i <= m; i++)↵
{↵
cin >> b[i];↵
cnt[min(b[i], 4)]++;↵
}↵
if(cnt[4] || cnt[3] >= 2 || cnt[3] && cnt[2] || cnt[2] >= 3)↵
{↵
cout << -1 << endl;↵
initialize(m);↵
continue;↵
}↵
↵
for(int i = 1; i <= m; i++)v.push_back(0);↵
a.push_back(v);↵
↵
if(cnt[2])↵
{↵
int p1 = -1, p2 = -1;↵
for(int i = 1; i <= m; i++)↵
{↵
if(b[i] == 2)↵
{↵
if(~p1)p2 = i - 1;↵
else p1 = i - 1;↵
}↵
}↵
if(~p2)↵
{↵
insert2(p1, p2, 2, 2);↵
insert2(p1, p2, 0, 1);↵
insert2(p1, p2, 2, 1);↵
insert2(p1, p2, 0, 2);↵
insert2(p1, p2, 1, 1);↵
insert2(p1, p2, 2, 0);↵
insert2(p1, p2, 1, 2);↵
insert2(p1, p2, 1, 0);↵
check[p1 + 1] = check[p2 + 1] = 1;↵
}↵
else↵
{↵
insert1(p1, 2);↵
insert1(p1, 1);↵
check[p1 + 1] = 1;↵
}↵
for(int i = 1; i <= m; i++)↵
{↵
if(check[i])continue;↵
if(a.size() % 2)f2(i - 1);↵
else f3(i - 1);↵
}↵
}↵
else↵
{↵
if(cnt[3])↵
{↵
int p = 0;↵
for(int i = 1; i <= m; i++)↵
{↵
if(b[i] == 3)p = i - 1;↵
}↵
insert1(p, 3);↵
insert1(p, 1);↵
insert1(p, 2);↵
check[p + 1] = 1;↵
}↵
else↵
{↵
insert1(0, 1);↵
check[1] = 1;↵
}↵
for(int i = 1; i <= m; i++)↵
{↵
if(!check[i])f1(i - 1);↵
}↵
}↵
↵
for(auto &v: a)↵
{↵
if(*max_element(v.begin(), v.end()))↵
{↵
for(auto &p: v)cout << p << ' ';↵
cout << endl;↵
}↵
}↵
initialize(m);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
## [problem:1737G]↵
↵
Author: [user:magnified,2022-10-07]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:1737G]↵
</spoiler>↵
↵
<spoiler summary="Solution (C++)">↵
[submission:175031734]↵
</spoiler>↵
↵
