1737A - Эла распределяет книги
Author: low_
...
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";
}
...
1737B - Фитнес Элы и роскошные числа
Author: low_
...
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";
}
...
1737C - Эла и сверчки
Author: low_
...
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";
}
}
}
...
1737D - Эла и волшебник
Author: low_
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 bool uin(T &a, T b) { return a > b ? (a = b, true) : false; } template 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 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';
} }
1737E - Эла идет в поход
Author: ngfam_kongu
include
include
include
include
include
include
include
include
include
include
include
include
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 >
// 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 v) { cerr << name << " @size=" << v.size() << ": ["; for (int x: v) cerr << x << " "; cerr << "]\n"; }
void debug_2d_vector(string name, vector <vector > 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 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: [email protected] // ...or codeforces: www.codeforces.com/profiles/low_ // ...or if you're interested in food: www.instagram.com/lowie.exe/
1737F - Эла и GCD и простые числа
Author: blobugh
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:
- 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.
- 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.
- 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:
- Repeat the current sequence twice — 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a.
- 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
import<bits/stdc++.h>
define endl '\n'
using namespace std;
int m, t, b[18], check[18], cnt[5]; vectorv; vector<vector>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);
}
}
1737G - Эла на уроке танцев
Author: magnified