codeforces-scrape

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

1141D.md (2621B)


      1 Source: https://codeforces.com/problemset/problem/1141/D
      2 
      3 D. Colored Boots
      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 There are $n$ left boots and $n$ right boots. Each boot has a color which is denoted as a lowercase Latin letter or a question mark ('?'). Thus, you are given two strings $l$ and $r$, both of length $n$. The character $l_i$ stands for the color of the $i$-th left boot and the character $r_i$ stands for the color of the $i$-th right boot.
     22 
     23 A lowercase Latin letter denotes a specific color, but the question mark ('?') denotes an indefinite color. Two specific colors are compatible if they are exactly the same. An indefinite color is compatible with any (specific or indefinite) color.
     24 
     25 For example, the following pairs of colors are compatible: ('f', 'f'), ('?', 'z'), ('a', '?') and ('?', '?'). The following pairs of colors are not compatible: ('f', 'g') and ('a', 'z').
     26 
     27 Compute the maximum number of pairs of boots such that there is one left and one right boot in a pair and their colors are compatible.
     28 
     29 Print the maximum number of such pairs and the pairs themselves. A boot can be part of at most one pair.
     30 
     31 Input
     32 
     33 The first line contains $n$ ($1 \le n \le 150000$), denoting the number of boots for each leg (i.e. the number of left boots and the number of right boots).
     34 
     35 The second line contains the string $l$ of length $n$. It contains only lowercase Latin letters or question marks. The $i$-th character stands for the color of the $i$-th left boot.
     36 
     37 The third line contains the string $r$ of length $n$. It contains only lowercase Latin letters or question marks. The $i$-th character stands for the color of the $i$-th right boot.
     38 
     39 Output
     40 
     41 Print $k$ — the maximum number of compatible left-right pairs of boots, i.e. pairs consisting of one left and one right boot which have compatible colors.
     42 
     43 The following $k$ lines should contain pairs $a_j, b_j$ ($1 \le a_j, b_j \le n$). The $j$-th of these lines should contain the index $a_j$ of the left boot in the $j$-th pair and index $b_j$ of the right boot in the $j$-th pair. All the numbers $a_j$ should be distinct (unique), all the numbers $b_j$ should be distinct (unique).
     44 
     45 If there are many optimal answers, print any of them.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 10
     53 codeforces
     54 dodivthree
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 5
     61 7 8
     62 4 9
     63 2 2
     64 9 10
     65 3 1
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 7
     72 abaca?b
     73 zabbbcc
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 5
     80 6 5
     81 2 3
     82 4 6
     83 7 4
     84 1 2
     85 ```
     86 
     87 Input
     88 
     89 ```
     90 9
     91 bambarbia
     92 hellocode
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 0
     99 ```
    100 
    101 Input
    102 
    103 ```
    104 10
    105 code??????
    106 ??????test
    107 ```
    108 
    109 Output
    110 
    111 ```
    112 10
    113 6 2
    114 1 6
    115 7 3
    116 3 5
    117 4 8
    118 9 7
    119 5 1
    120 2 4
    121 10 9
    122 8 10
    123 ```