Here is the editorial. Please provide your feedback on each problem so that we can improve upon them the next time.
1670A - Профессор Слим
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.StringTokenizer;
public class A {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tc = sc.nextInt();
for (int test = 1; test <= tc; test++) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
int i = 0, j = 0;
while (i < n) {
if (arr[i] < 0) {
arr[j++] *= -1;
arr[i] *= -1;
}
i++;
}
if (isSorted(arr)) {
pw.println("YES");
} else
pw.println("NO");
}
pw.flush();
}
private static boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++)
if (arr[i] < arr[i - 1])
return false;
return true;
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(FileReader f) {
br = new BufferedReader(f);
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public int[] nextIntArr(int n) throws IOException {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(next());
}
return arr;
}
}
}
1670B - Общажные войны
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.StringTokenizer;
public class B{
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tests = sc.nextInt();
for (int test = 0; test < tests; test++) {
int n = sc.nextInt();
char[] arr = sc.next().toCharArray();
int k = sc.nextInt();
boolean[] special = new boolean[26];
for (int i = 0; i < k; i++)
special[sc.next().charAt(0) - 'a'] = true;
int idx = -1;
for (int i = 0; i < n; i++)
if (special[arr[i] - 'a'])
idx = i;
int max=0;
for(int i=idx-1;i>=0;i--){
int j=i;
while (j>0&&!special[arr[j]-'a'])
j--;
max=Math.max(max,i+1-j);
i=j;
}
pw.println(max);
}
pw.flush();
}
public static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(String s) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
1670C - Где пицца?
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.HashSet;
import java.util.StringTokenizer;
public class C{
static int mod = (int) 1e9 + 7;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tests = sc.nextInt();
for (int test = 0; test < tests; test++) {
int n = sc.nextInt();
int[] first = new int[n];
int[] second = new int[n];
int[] third=new int[n];
for (int i = 0; i < n; i++)
first[i] = sc.nextInt() - 1;
for (int i = 0; i < n; i++)
second[i] = sc.nextInt() - 1;
for(int i=0;i<n;i++)
third[i]= sc.nextInt()-1;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++)
uf.unionSet(first[i], second[i]);
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++)
set.add(uf.findSet(i));
for(int i=0;i<n;i++){
if(third[i]==-1)
continue;
set.remove(uf.findSet(third[i]));
}
int pow = 0;
for (int x : set)
if (uf.sizeOfSet(x) > 1)
pow++;
int ans = 1;
for (int i = 0; i < pow; i++)
ans = (int) ((2L * ans) % mod);
pw.println(ans);
}
pw.flush();
}
public static class UnionFind {
int[] p, rank, setSize;
int numSets;
public UnionFind(int N) {
p = new int[numSets = N];
rank = new int[N];
setSize = new int[N];
for (int i = 0; i < N; i++) {
p[i] = i;
setSize[i] = 1;
}
}
public int findSet(int i) {
return p[i] == i ? i : (p[i] = findSet(p[i]));
}
public boolean isSameSet(int i, int j) {
return findSet(i) == findSet(j);
}
public void unionSet(int i, int j) {
if (isSameSet(i, j))
return;
numSets--;
int x = findSet(i), y = findSet(j);
if (rank[x] > rank[y]) {
p[y] = x;
setSize[x] += setSize[y];
} else {
p[x] = y;
setSize[y] += setSize[x];
if (rank[x] == rank[y]) rank[y]++;
}
}
public int numDisjointSets() {
return numSets;
}
public int sizeOfSet(int i) {
return setSize[findSet(i)];
}
}
public static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(String s) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
1670D - Очень подозрительно
Tutorial
Tutorial is loading...
Solution
import java.util.*;
import java.io.*;
public class D{
public static void main(String[] args) throws Exception {
int t=sc.nextInt();
while(t-->0) {
pw.println(sol(sc.nextInt()));
}
pw.close();
}
public static int sol(int n) {
int low=0;
int high=(int)1e9;
int mid=(low+high)/2;
while(low<=high) {
if(calc(mid)<n) {
low=mid+1;
}else {
high=mid-1;
}
mid=(low+high)/2;
}
return low;
}
public static long calc(long n) {
n--;
long ans=0;
ans=(n/3)*(n/3)*3;
for (int i = 0; i <= n % 3; i++)
ans += (n / 3) * 2 + i;
return ans*2;
}
static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(FileReader r) {
br = new BufferedReader(r);
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public String nextLine() throws IOException {
return br.readLine();
}
public double nextDouble() throws IOException {
String x = next();
StringBuilder sb = new StringBuilder("0");
double res = 0, f = 1;
boolean dec = false, neg = false;
int start = 0;
if (x.charAt(0) == '-') {
neg = true;
start++;
}
for (int i = start; i < x.length(); i++)
if (x.charAt(i) == '.') {
res = Long.parseLong(sb.toString());
sb = new StringBuilder("0");
dec = true;
} else {
sb.append(x.charAt(i));
if (dec)
f *= 10;
}
res += Long.parseLong(sb.toString()) / f;
return res * (neg ? -1 : 1);
}
public long[] nextlongArray(int n) throws IOException {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public Long[] nextLongArray(int n) throws IOException {
Long[] a = new Long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public int[] nextIntArray(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public Integer[] nextIntegerArray(int n) throws IOException {
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public boolean ready() throws IOException {
return br.ready();
}
}
static Scanner sc = new Scanner(System.in);
static PrintWriter pw = new PrintWriter(System.out);
}
1670E - Хемос на дереве
Tutorial
Tutorial is loading...
Solution
import java.util.*;
import java.io.*;
public class E{
static ArrayList<int[]>[] adj;
static int[] nodeval, edgeval;
static int count, N;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
N = 1 << n;
adj = new ArrayList[N];
for (int i = 0; i < N; i++)
adj[i] = new ArrayList<>();
for (int i = 0; i < N - 1; i++) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
adj[u].add(new int[]{v, i});
adj[v].add(new int[]{u, i});
}
nodeval = new int[N];
edgeval = new int[N];
nodeval[0] = N;
count =0;
dfs(0, -1);
pw.println(1);
for (int i = 0; i < N; i++)
pw.print(nodeval[i] + " ");
pw.println();
for (int i = 0; i < N - 1; i++)
pw.print(edgeval[i] + " ");
pw.println();
}
pw.close();
}
private static void dfs(int u, int p) {
for (int[] nxt : adj[u]) {
int v = nxt[0];
int idx = nxt[1];
if (v == p)
continue;
count++;
edgeval[idx] = count + ((nodeval[u] & N) != 0 ? N : 0);
nodeval[v] = count + ((nodeval[u] & N) != 0 ? 0 : N);
dfs(v, u);
}
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(FileReader f) {
br = new BufferedReader(f);
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public int[] nextIntArr(int n) throws IOException {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(next());
}
return arr;
}
}
}
1670F - Джи, видишь?
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class F {
static final int mod = (int) 1e9 + 7;
static int n;
static long l, r, z;
static long[][] memo;
static long[][] memo2;
public static long nCr(int n, int r) {
if (r == 0)
return 1;
if (n == 0)
return 0;
if (memo[n][r] != -1)
return memo[n][r];
return memo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1)) % mod;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tests = 1;
memo = new long[1001][1001];
for (long[] x : memo)
Arrays.fill(x, -1);
for (int test = 0; test < tests; test++) {
n = sc.nextInt();
l = sc.nextLong();
r = sc.nextLong();
z = sc.nextLong();
long ans = (compute(r) - compute(l - 1) + mod) % mod;
pw.println(ans);
}
pw.flush();
}
private static long compute(long val) {
memo2 = new long[61][2001];
for (long[] x : memo2)
Arrays.fill(x, -1);
return dp(60, 0, val);
}
private static long dp(int idx, int rem, long val) {
if (rem > 2000)
rem = 2000;
if (rem < 0)
return 0;
if (idx == -1)
return 1;
if (memo2[idx][rem] != -1)
return memo2[idx][rem];
long ans = 0;
int currentBitXor = (z & 1L << idx)== 0 ? 0 : 1;
for (int i = currentBitXor == 1 ? 1 : 0; i <= n; i += 2) {
int currentBitSum = (val & 1L << idx) == 0 ? 0 : 1;
int nextRem = 2 * (rem + currentBitSum - i);
long toAdd = (nCr(n, i) * dp(idx - 1, nextRem, val)) % mod;
ans = (ans + toAdd) % mod;
}
return memo2[idx][rem] = ans;
}
public static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(String s) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
