...
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";
}
...

...
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";
}
...

...
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"; 
    }
  }
}
...

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';

} }

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/

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

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);
}

}

175031734