#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k, x = -1;
cin >> n >> k;
for (int i = 0; i <= n; i++) {
if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) {
x = i;
}
}
if (x == -1)
cout << "NO\n";
else {
cout << "YES\n";
for (int i = 0; i < n; i++) {
if (i < x)
cout << 1 << ' ';
else
cout << -1 << ' ';
}
cout << '\n';
}
}
return 0;
}
for tt in range(int(input())):
n, k = map(int, input().split())
x = -1
for i in range(0, n + 1):
if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k:
x = i
if x == -1:
print("NO")
else:
print("YES")
for i in range(0, n):
if i < x:
print("1 ", end = '')
else:
print("-1 ", end = '')
print("")
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector <int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--;
}
int bad = 0;
for (int i=0; i<n; i++) {
if (p[i] % k != i % k) {
bad++;
}
}
if(bad == 0)
cout << 0 << '\n';
else if(bad == 2)
cout << 1 << '\n';
else
cout << -1 << '\n';
}
return 0;
}
for tt in range(int(input())):
n, k = map(int, input().split())
p = list(map(int, input().split()))
for i in range(0, n):
p[i] -= 1
bad = 0
for i in range(0, n):
if p[i] % k != i % k:
bad += 1
if bad == 0:
print(0)
elif bad == 2:
print(1)
else:
print(-1)
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
map <int,int> a;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
for (int j = 2; j * j <= x; j++) {
while (x % j == 0) {
x /= j;
a[j]++;
}
}
if (x != 1) {
a[x]++;
}
}
int res = 0, rem = 0;
for (pair <int, int> p : a) {
int num = p.first;
int cnt = p.second;
res += cnt / 2;
rem += cnt % 2;
}
res += rem / 3;
cout << res << '\n';
}
return 0;
}
def is_prime(x):
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
def is_strongly_composite(x):
m = []
i = 2
while i * i <= x:
while x % i == 0:
x = x // i
m.append(i)
i += 1
if not x == 1:
m.append(i)
return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1]))
for tt in range(int(input())):
n = int(input())
lst = list(map(int, input().split()))
a = {}
for x in lst:
i = 2
while i * i <= x:
while x % i == 0:
x = x // i
if i in a:
a[i] += 1
else:
a[i] = 1
i += 1
if x != 1:
if x in a:
a[x] += 1
else:
a[x] = 1
res, rem = 0, 0
for num in a:
cnt = a[num]
res += cnt // 2
rem += cnt % 2
res += rem // 3
print(res)
There were initially more complex version of this task. Can you solve it?
You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). You can perform the following operation with array $$$a$$$ any number of times:
choose two indices $$$i$$$ and $$$j$$$ ($$$i < j$$$);
erase elements $$$a_i$$$ and $$$a_j$$$ from $$$a$$$;
insert element $$$a_i \cdot a_j$$$ in $$$a$$$.
After performing one such operation, the length of $$$a$$$ decreases by one.
Let's say that array $$$a$$$ is good, if it contains only strongly composite numbers.
What is the minimum number of operation you need to perform to make array $$$a$$$ good?
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector <int> x(k), c(k);
for (int i = 0; i < k; i++)
cin >> x[i];
for (int i = 0; i < k; i++)
cin >> c[i];
if (c[0] < 3 || c[0] > x[0]) {
cout << "NO\n";
continue;
}
string s;
char cur = 'a';
for (int i = 0; i < c[0] - 3; i++)
s.push_back('a');
for (int i = c[0] - 3; i < x[0]; i++) {
s.push_back(cur);
cur++;
if (cur == 'd') cur = 'a';
}
bool good = true;
for (int j = 1; j < k; j++) {
int dx = x[j] - x[j - 1];
int dc = c[j] - c[j - 1];
if (dc > dx) {
good = false;
break;
}
for (int i = 0; i < dc; i++)
s.push_back('c' + j);
for (int i = dc; i < dx; i++) {
s.push_back(cur);
cur++;
if (cur == 'd') cur = 'a';
}
}
if (good)
cout << "YES" << endl << s << endl;
else
cout << "NO" << endl;
}
return 0;
}
for tt in range(int(input())):
n, k = map(int, input().split())
x = list(map(int, input().split()))
c = list(map(int, input().split()))
if c[0] < 3 or c[0] > x[0]:
print("NO")
continue
s = ""
cur = 'a'
for i in range(0, c[0] - 3):
s += "a"
for i in range(c[0] - 3, x[0]):
s += cur
cur = chr(ord(cur) + 1)
if cur == 'd':
cur = 'a'
good = True
for j in range(1, k):
dx = x[j] - x[j - 1]
dc = c[j] - c[j - 1]
if dc > dx:
good = False
break
for i in range(0, dc):
s += chr(ord('c') + j)
for i in range(dc, dx):
s += cur
cur = chr(ord(cur) + 1)
if cur == 'd':
cur = 'a'
if good:
print("YES")
print(s)
else:
print("NO")
There were initially simpler version of this problem with $$$k = 1$$$, but it coincided with other problem.
Also, how does checker in this problem works?
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, l, r;
cin >> n >> l >> r;
vector < vector <int> > g(n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
int res=0, size;
vector <int> used(n);
function <void(int)> dfs = [&] (int v) {
used[v] = true;
size++;
for (int to : g[v]) {
if (!used[to])
dfs(to);
}
};
for (int i = 0; i < n; i++) {
if (!used[i]) {
size = 0;
dfs(i);
if (size <= l + r - 1) {
res ^= size / l;
}
}
}
if (res)
cout << "Alice\n";
else
cout << "Bob\n";
return 0;
}
from sys import setrecursionlimit
import threading
def main():
n, l, r = map(int, input().split())
g = [[] for i in range(0, n)]
for i in range(0, n):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
res = 0
used = [False for i in range(0, n)]
def dfs(v):
used[v] = True
size = 1
for to in g[v]:
if not used[to]:
size += dfs(to)
return size
for i in range(0, n):
if not used[i]:
size = dfs(i)
if size <= l + r - 1:
res ^= size // l
if res:
print("Alice")
else:
print("Bob")
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main(){
int n, s, t;
cin >> n >> s >> t;
s--, t--;
vector < vector <int> > g(n);
vector <int> previous(n, -1);
vector <int> inPath(n);
vector <long long> res(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
function <void (int, int)> dfs = [&] (int v, int p) {
for (int to : g[v]) {
if (to == p) continue;
previous[to] = v;
dfs(to, v);
}
};
function <void (int, int, long long)> dfs2 = [&] (int v, int p, long long k) {
res[v] = k * (long long)g[v].size();
for (int to : g[v]) {
if (to == p) continue;
dfs2(to, v, k);
}
};
dfs(s, -1);
int ptr = t;
inPath[t] = true;
while (ptr != s) {
res[previous[ptr]] = res[ptr] + 2;
ptr = previous[ptr];
inPath[ptr] = true;
}
for (int v = 0; v < n; v++) {
if (inPath[v]) {
res[v] = res[v] / 2 * (long long)g[v].size();
for (int to : g[v]) {
if (!inPath[to]) {
dfs2(to, v, res[v] / (int)g[v].size());
}
}
}
}
res[t]++;
for (long long i : res)
cout << i % mod << ' ';
cout<<'\n';
return 0;
}
from sys import setrecursionlimit
import threading
mod = 998244353
def main():
n, s, t = map(int, input().split())
s -= 1
t -= 1
g = [[] for i in range(0, n)]
previous = [-1 for i in range(0, n)]
inPath = [False for i in range(0, n)]
res = [0 for i in range(0, n)]
for i in range(0, n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
def dfs(v, p):
for to in g[v]:
if to == p:
continue
previous[to] = v
dfs(to, v)
def dfs2(v, p, k):
res[v] = k * len(g[v])
for to in g[v]:
if to == p:
continue
dfs2(to, v, k)
dfs(s, -1)
ptr = t
inPath[t] = True
while ptr != s:
res[previous[ptr]] = res[ptr] + 2
ptr = previous[ptr]
inPath[ptr] = True
for v in range(0, n):
if inPath[v]:
res[v] = res[v] // 2 * len(g[v])
for to in g[v]:
if not inPath[to]:
dfs2(to, v, res[v] // len(g[v]))
res[t] += 1
for i in res:
print(i % mod, end = ' ')
print("")
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()