HackerRank Coprime Paths Problem Solution
In this post, we will solve HackerRank Coprime Paths Problem Solution.
You are given an undirected, connected graph, G, with n nodes and m edges where m = n – 1. Each node i is initially assigned a value, node;, that has at most 3 prime divisors.
You must answer q queries in the form u v. For each query, find and print the number of (x, y) pairs of nodes on the path between u and v such that gcd (node, nodey) = 1 and the length of the path between u and is minimal among all paths from u to v.
Input Format
The first line contains two space-separated integers describing the respective values of n
and q.
The second line contains n space-separated integers describing the respective values of node, node2,…,noden.
Each of the n – 1 subsequent lines contains two space-separated integers, u and v. describing an edge between nodes u and v.
Each of the q subsequent lines contains two space-separated integers, u and v, describing a query.
Output Format
For each query, print an integer on a new line denoting the number of (x, y) pairs of nodes on the path between u and v such that gcd (node, node,) = 1 and the length of the path between u and v is minimal among all paths from u to v.
Sample Input 0
6 5
3 2 4 1 6 5
1 2
1 3
2 4
2 5
3 6
4 6
5 6
1 1
1 6
6 1Sample Output 0
9
6
0
3
3
Coprime Paths C Solution
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <time.h>
#define swapI_(x, y) { int z = x; x = y; y = z; }
#define swapIp_(x, y) { int *z = x; x = y; y = z; }
#define nMax 25000
#define xMax 10000000
typedef long long ll;
typedef struct V
{
int parent;
int gc;
int gs[7];
} V;
typedef struct L
{
int val;
int next;
} L;
int n;
V vs[nMax + 1];
int depths[nMax + 1];
int gc = 1;
int primeC = 446;
int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137};
int getG(int p)
{
static int gs[xMax + 1];
if (!gs[p])
{
gs[p] = gc++;
}
return gs[p];
}
void writeFactors()
{
for (int i = 1; i <= n; ++i)
{
int x;
scanf("%d", &x);
int y = (int)sqrt(x);
int *gs = vs[i].gs;
int ps[3];
int s = 0;
for (int t = 0; t < primeC; ++t)
{
int p = primes[t];
if (p > y)
{
break;
}
if (x % p == 0)
{
ps[s] = p;
gs[s++] = getG(p);
x /= p;
while (x % p == 0) x /= p;
y = (int)sqrt(x);
}
}
if (x > 1)
{
ps[s] = x;
gs[s++] = getG(x);
}
if (s == 2)
{
gs[s++] = getG(ps[0] * ps[1]);
}
else if (s == 3)
{
gs[s++] = getG(ps[0] * ps[1]);
gs[s++] = getG(ps[0] * ps[2]);
gs[s++] = getG(ps[1] * ps[2]);
gs[s++] = getG(ps[0] * ps[1] * ps[2]);
}
vs[i].gc = s;
}
}
void writeParents()
{
static int nexts[nMax + 1];
static char hits[nMax + 1];
static L ls[(nMax - 1) * 2 + 1];
static int data[nMax * 2];
int *is = data;
int *js = &data[nMax];
int ic = 0;
int jc = 0;
int t = 1;
for (int s = 0; s < n - 1; ++s)
{
int i, j;
scanf("%d %d", &i, &j);
ls[t].val = j;
ls[t].next = nexts[i];
nexts[i] = t;
t++;
ls[t].val = i;
ls[t].next = nexts[j];
nexts[j] = t;
t++;
}
ic = 1;
is[0] = 1;
hits[1] = 1;
int depth = 0;
while (ic > 0)
{
for (int s = 0; s < ic; ++s)
{
int i = is[s];
depths[i] = depth;
int t = nexts[i];
while (t)
{
int j = ls[t].val;
t = ls[t].next;
if (!hits[j])
{
vs[j].parent = i;
js[jc++] = j;
hits[j] = 1;
}
}
}
swapIp_(is, js);
ic = jc;
jc = 0;
depth++;
}
}
#define run(i) \
{\
sum += vc;\
int *gs = vs[i].gs;\
switch (vs[i].gc)\
{\
case 1:\
sum -= cs[gs[0]]++;\
break;\
case 3:\
sum -= cs[gs[0]]++;\
sum -= cs[gs[1]]++;\
sum += cs[gs[2]]++;\
break;\
case 7:\
sum -= cs[gs[0]]++;\
sum -= cs[gs[1]]++;\
sum -= cs[gs[2]]++;\
sum += cs[gs[3]]++;\
sum += cs[gs[4]]++;\
sum += cs[gs[5]]++;\
sum -= cs[gs[6]]++;\
break;\
}\
vc++;\
i = vs[i].parent;\
}
void solveQuery()
{
int i, j;
static int cs[xMax + 1];
scanf("%d %d", &i, &j);
int vc = 0;
ll sum = 0;
if (depths[i] < depths[j])
{
swapI_(i, j);
}
int m = depths[i] - depths[j];
for (int s = 0; s < m; ++s)
{
run(i);
}
while (i != j)
{
run(i);
run(j);
}
run(i);
printf("%lld\n", sum);
for (int s = 0; s < gc; ++s)
{
cs[s] = 0;
}
}
void print()
{
for (int i = 1; i <= n; ++i)
{
printf("%d: parent=%d, depth=%d, %d, %d, %d\n", i, vs[i].parent, depths[i], vs[i].gs[0], vs[i].gs[1], vs[i].gs[2]);
}
}
int main()
{
int qc;
scanf("%d %d", &n, &qc);
writeFactors();
writeParents();
//print();
for (int q = 0; q < qc; ++q)
{
solveQuery();
}
return 0;
}Coprime Paths C++ Solution
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 25e3 + 5;
const int maxm = 1e7 + 5;
const int logn = log2(maxn) + 1;
const int mod = 1e9 + 7;
struct D{
int cnt[maxm];
int s[maxm];
bool cntbit[20];
D(){
for(int i = 0 ; i < 20 ; ++i)cntbit[i] = (__builtin_popcount(i) & 1);
for(int i = 2 ; i < maxm ; ++i){
if(s[i] == 0){
s[i] = i;
for(ll j = (ll)i * i ; j < maxm ; j += i)if(s[j] == 0)s[j] = i;
}
}
}
int n , tot = 0;
int p[4];
void update(int x , int delta){
tot += delta;
n = 0;
while(x > 1){
if(n == 0 || p[n - 1] != s[x])p[n++] = s[x];
x /= s[x];
}
for(int i = 1 ; i < (1 << n) ; ++i){
int tmp = 1;
for(int j = 0 ; j < n ; ++j){
if(i & (1 << j))tmp *= p[j];
}
cnt[tmp] += delta;
}
}
int query(int x){
int res = tot;
n = 0;
while(x > 1){
if(n == 0 || p[n - 1] != s[x])p[n++] = s[x];
x /= s[x];
}
for(int i = 1 ; i < (1 << n) ; ++i){
int tmp = 1;
for(int j = 0 ; j < n ; ++j){
if(i & (1 << j))tmp *= p[j];
}
if(cntbit[i])res -= cnt[tmp];
else res += cnt[tmp];
}
return res;
}
}s;
int n , q;
int a[maxn];
int in[maxn],out[maxn],id[maxn * 2];
int P[maxn][logn],h[maxn];
ll res[maxn];
ll cur_ans = 0;
const int MAGIC = sqrt(maxn * 2);
vector<int> adj[maxn];
struct Q{
int l , r , lca , id;
bool operator < (const Q other){
if(l / MAGIC == other.l / MAGIC){
if((l / MAGIC) & 1)return r < other.r;
return r > other.r;
// return r < other.r;
}
return l / MAGIC < other.l / MAGIC;
}
}b[maxn];
void dfs(int u , int par){
static int nTime = 0;
in[u] = ++nTime;
id[nTime] = u;
for(auto c : adj[u]){
if(c == par)continue;
h[c] = h[u] + 1;
P[c][0] = u;
for(int i = 1 ; i < logn ; ++i)P[c][i] = P[P[c][i - 1]][i - 1];
dfs(c , u);
}
out[u] = ++nTime;
id[nTime] = u;
}
int lca(int u , int v){
if(h[u] < h[v])swap(u , v);
for(int i = 0 ; i < logn ; ++i){
if((h[u] - h[v]) & (1 << i)){
u = P[u][i];
}
}
if(u == v)return u;
for(int i = logn - 1 ; i >= 0 ; --i){
if(P[u][i] != P[v][i]){
u = P[u][i];
v = P[v][i];
}
}
return P[u][0];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n >> q;
for(int i = 1 ; i <= n ; ++i)cin >> a[i];
for(int i = 1 ; i < n ; ++i){
int u , v;cin >> u >> v;adj[u].pb(v);adj[v].pb(u);
}
dfs(1 , 0);
for(int i = 1 ; i <= q ; ++i){
b[i].id = i;
int u , v;cin >> u >> v;
if(in[u] > in[v])swap(u,v);
b[i].lca = lca(u,v);
if(u == b[i].lca){
b[i].l = in[u];
b[i].r = in[v];
b[i].lca = 0;
}else{
b[i].l = out[u];
b[i].r = in[v];
}
}
sort(b + 1 , b + q + 1);
vector<int> vis(n + 1 , 0);
auto update = [&](int u){
if(u <= 0 || u > n)return;
if(vis[u] == 0){
cur_ans += s.query(a[u]);
s.update(a[u] , 1);
}else{
s.update(a[u] , -1);
cur_ans -= s.query(a[u]);
}
vis[u] ^= 1;
};
int L = b[1].l , H = b[1].l - 1;
for(int i = 1 ; i <= q ; ++i){
while(L < b[i].l)update(id[L++]);
while(L > b[i].l)update(id[--L]);
while(H < b[i].r)update(id[++H]);
while(H > b[i].r)update(id[H--]);
if(b[i].lca > 0)update(b[i].lca);
res[b[i].id] = cur_ans;
if(b[i].lca > 0)update(b[i].lca);
}
for(int i = 1 ; i <= q ; ++i)cout << res[i] << '\n';
}
Coprime Paths Java Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class F {
InputStream is;
PrintWriter out;
String INPUT = "";
long ret;
int[] freq;
int[] pfreq;
EulerTour et;
int[] lpf = enumLowestPrimeFactors(10000005);
int[] mob = enumMobiusByLPF(10000005, lpf);
int[] a;
void solve()
{
int n = ni(), Q = ni();
a = na(n);
for(int i = 0;i < n;i++){
int pre = -1;
int mul = 1;
for(int j = a[i];j > 1;j /= lpf[j]){
if(pre != lpf[j]){
mul *= lpf[j];
pre = lpf[j];
}
}
a[i] = mul;
}
int[] from = new int[n - 1];
int[] to = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
from[i] = ni() - 1;
to[i] = ni() - 1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
et = nodalEulerTour(g, 0);
int[][] spar = logstepParents(par);
int[][] qs = new int[Q][];
int[] special = new int[Q];
Arrays.fill(special, -1);
for(int i = 0;i < Q;i++){
int x = ni()-1, y = ni()-1;
int lca = lca2(x, y, spar, dep);
if(lca == x){
qs[i] = new int[]{et.first[x], et.first[y]};
}else if(lca == y){
qs[i] = new int[]{et.first[y], et.first[x]};
}else if(et.first[x] < et.first[y]){
qs[i] = new int[]{et.last[x], et.first[y]};
special[i] = lca;
}else{
qs[i] = new int[]{et.last[y], et.first[x]};
special[i] = lca;
}
}
long[] pqs = sqrtSort(qs, 2*n-1);
int L = 0, R = -1;
freq = new int[n];
long[] ans = new long[Q];
pfreq = new int[10000005];
for(long pa : pqs){
int ind = (int)(pa&(1<<25)-1);
int ql = qs[ind][0], qr = qs[ind][1];
while(R < qr)change(++R, 1);
while(L > ql)change(--L, 1);
while(R > qr)change(R--, -1);
while(L < ql)change(L++, -1);
if(special[ind] != -1)change(et.first[special[ind]], 1);
ans[ind] = ret;
if(special[ind] != -1)change(et.first[special[ind]], -1);
}
for(long v : ans){
out.println(v);
}
}
public static void trnz(int... o)
{
for(int i = 0;i < o.length;i++)if(o[i] != 0)System.out.print(i+":"+o[i]+" ");
System.out.println();
}
public static int[] enumMobiusByLPF(int n, int[] lpf)
{
int[] mob = new int[n+1];
mob[1] = 1;
for(int i = 2;i <= n;i++){
int j = i/lpf[i];
if(lpf[j] == lpf[i]){
// mob[i] = 0;
}else{
mob[i] = -mob[j];
}
}
return mob;
}
void dfs(int cur, int n, int d)
{
if(n == 1){
if(d > 0)ret += mob[cur] * pfreq[cur];
pfreq[cur] += d;
if(d < 0)ret -= mob[cur] * pfreq[cur];
return;
}
dfs(cur, n/lpf[n], d);
dfs(cur/lpf[n], n/lpf[n], d);
}
void change(int x, int d)
{
int ind = et.vs[x];
if(freq[ind] == 1){
dfs(a[ind], a[ind], -1);
}
freq[ind] += d;
if(freq[ind] == 1){
dfs(a[ind], a[ind], 1);
}
}
public static long[] sqrtSort(int[][] qs, int n)
{
int m = qs.length;
long[] pack = new long[m];
int S = (int)Math.sqrt(n);
for(int i = 0;i < m;i++){
pack[i] = (long)qs[i][0]/S<<50|(long)((qs[i][0]/S&1)==0?qs[i][1]:(1<<25)-1-qs[i][1])<<25|i;
}
Arrays.sort(pack);
return pack;
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static class EulerTour
{
public int[] vs;
public int[] first;
public int[] last;
public EulerTour(int[] vs, int[] f, int[] l) {
this.vs = vs;
this.first = f;
this.last = l;
}
}
public static EulerTour nodalEulerTour(int[][] g, int root)
{
int n = g.length;
int[] vs = new int[2*n];
int[] f = new int[n];
int[] l = new int[n];
int p = 0;
Arrays.fill(f, -1);
int[] stack = new int[n];
int[] inds = new int[n];
int sp = 0;
stack[sp++] = root;
outer:
while(sp > 0){
int cur = stack[sp-1], ind = inds[sp-1];
if(ind == 0){
vs[p] = cur;
f[cur] = p;
p++;
}
while(ind < g[cur].length){
int nex = g[cur][ind++];
if(f[nex] == -1){
inds[sp-1] = ind;
stack[sp] = nex;
inds[sp] = 0;
sp++;
continue outer;
}
}
inds[sp-1] = ind;
if(ind == g[cur].length){
vs[p] = cur;
l[cur] = p;
p++;
sp--;
}
}
return new EulerTour(vs, f, l);
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static int[] enumLowestPrimeFactors(int n) {
int tot = 0;
int[] lpf = new int[n + 1];
int u = n + 32;
double lu = Math.log(u);
int[] primes = new int[(int) (u / lu + u / lu / lu * 1.5)];
for (int i = 2; i <= n; i++)
lpf[i] = i;
for (int p = 2; p <= n; p++) {
if (lpf[p] == p)
primes[tot++] = p;
int tmp;
for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
lpf[tmp] = primes[i];
}
}
return lpf;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new F().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Модные заметки по подбору стильных образов на каждый день.
Заметки стилистов, события, все новинки и мероприятия.
https://megakazan.ru/kzn/403-5-luchshih-sumok-balmain-na-2024-god-stil-i-elegantnost-ot-frantsuzskogo-doma-mody/
Абсолютно важные новинки модного мира.
Абсолютно все новости самых влиятельных подуимов.
Модные дома, лейблы, высокая мода.
Лучшее место для модных хайпбистов.
https://outstreet.ru/yeah/11164-5-stilnyh-modeley-chasov-guess-dlya-devushki-v-2024-godu/