codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1251B.md (2383B)


      1 Source: https://codeforces.com/problemset/problem/1251/B
      2 
      3 B. Binary Palindromes
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A palindrome is a string $t$ which reads the same backward as forward (formally, $t[i] = t[|t| + 1 - i]$ for all $i \in [1, |t|]$). Here $|t|$ denotes the length of a string $t$. For example, the strings 010, 1001 and 0 are palindromes.
     22 
     23 You have $n$ binary strings $s_1, s_2, \dots, s_n$ (each $s_i$ consists of zeroes and/or ones). You can swap any pair of characters any number of times (possibly, zero). Characters can be either from the same string or from different strings — there are no restrictions.
     24 
     25 Formally, in one move you:
     26 
     27 * choose four integer numbers $x, a, y, b$ such that $1 \le x, y \le n$ and $1 \le a \le |s_x|$ and $1 \le b \le |s_y|$ (where $x$ and $y$ are string indices and $a$ and $b$ are positions in strings $s_x$ and $s_y$ respectively),
     28 * swap (exchange) the characters $s_x[a]$ and $s_y[b]$.
     29 
     30 What is the maximum number of strings you can make palindromic simultaneously?
     31 
     32 Input
     33 
     34 The first line contains single integer $Q$ ($1 \le Q \le 50$) — the number of test cases.
     35 
     36 The first line on each test case contains single integer $n$ ($1 \le n \le 50$) — the number of binary strings you have.
     37 
     38 Next $n$ lines contains binary strings $s_1, s_2, \dots, s_n$ — one per line. It's guaranteed that $1 \le |s_i| \le 50$ and all strings constist of zeroes and/or ones.
     39 
     40 Output
     41 
     42 Print $Q$ integers — one per test case. The $i$-th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the $i$-th test case.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 4
     50 1
     51 0
     52 3
     53 1110
     54 100110
     55 010101
     56 2
     57 11111
     58 000001
     59 2
     60 001
     61 11100111
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 1
     68 2
     69 2
     70 2
     71 ```
     72 
     73 Note
     74 
     75 In the first test case, $s_1$ is palindrome, so the answer is $1$.
     76 
     77 In the second test case you can't make all three strings palindromic at the same time, but you can make any pair of strings palindromic. For example, let's make $s_1 = \text{0110}$, $s_2 = \text{111111}$ and $s_3 = \text{010000}$.
     78 
     79 In the third test case we can make both strings palindromic. For example, $s_1 = \text{11011}$ and $s_2 = \text{100001}$.
     80 
     81 In the last test case $s_2$ is palindrome and you can make $s_1$ palindrome, for example, by swapping $s_1[2]$ and $s_1[3]$.