codeforces-scrape

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

1118E.md (2896B)


      1 Source: https://codeforces.com/problemset/problem/1118/E
      2 
      3 E. Yet Another Ball Problem
      4 
      5 time limit per test
      6 
      7 3 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 The king of Berland organizes a ball! $n$ pair are invited to the ball, they are numbered from $1$ to $n$. Each pair consists of one man and one woman. Each dancer (either man or woman) has a monochrome costume. The color of each costume is represented by an integer from $1$ to $k$, inclusive.
     22 
     23 Let $b_i$ be the color of the man's costume and $g_i$ be the color of the woman's costume in the $i$-th pair. You have to choose a color for each dancer's costume (i.e. values $b_1, b_2, \dots, b_n$ and $g_1, g_2, \dots g_n$) in such a way that:
     24 
     25 1. for every $i$: $b_i$ and $g_i$ are integers between $1$ and $k$, inclusive;
     26 2. there are no two completely identical pairs, i.e. no two indices $i, j$ ($i \ne j$) such that $b_i = b_j$ and $g_i = g_j$ at the same time;
     27 3. there is no pair such that the color of the man's costume is the same as the color of the woman's costume in this pair, i.e. $b_i \ne g_i$ for every $i$;
     28 4. for each two consecutive (adjacent) pairs both man's costume colors and woman's costume colors differ, i.e. for every $i$ from $1$ to $n-1$ the conditions $b_i \ne b_{i + 1}$ and $g_i \ne g_{i + 1}$ hold.
     29 
     30 Let's take a look at the examples of bad and good color choosing (for $n=4$ and $k=3$, man is the first in a pair and woman is the second):
     31 
     32 Bad color choosing:
     33 
     34 * $(1, 2)$, $(2, 3)$, $(3, 2)$, $(1, 2)$ — contradiction with the second rule (there are equal pairs);
     35 * $(2, 3)$, $(1, 1)$, $(3, 2)$, $(1, 3)$ — contradiction with the third rule (there is a pair with costumes of the same color);
     36 * $(1, 2)$, $(2, 3)$, $(1, 3)$, $(2, 1)$ — contradiction with the fourth rule (there are two consecutive pairs such that colors of costumes of men/women are the same).
     37 
     38 Good color choosing:
     39 
     40 * $(1, 2)$, $(2, 1)$, $(1, 3)$, $(3, 1)$;
     41 * $(1, 2)$, $(3, 1)$, $(2, 3)$, $(3, 2)$;
     42 * $(3, 1)$, $(1, 2)$, $(2, 3)$, $(3, 2)$.
     43 
     44 You have to find any suitable color choosing or say that no suitable choosing exists.
     45 
     46 Input
     47 
     48 The only line of the input contains two integers $n$ and $k$ ($2 \le n, k \le 2 \cdot 10^5$) — the number of pairs and the number of colors.
     49 
     50 Output
     51 
     52 If it is impossible to find any suitable colors choosing, print "NO".
     53 
     54 Otherwise print "YES" and then the colors of the costumes of pairs in the next $n$ lines. The $i$-th line should contain two integers $b_i$ and $g_i$ — colors of costumes of man and woman in the $i$-th pair, respectively.
     55 
     56 You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.
     57 
     58 Examples
     59 
     60 Input
     61 
     62 ```
     63 4 3
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 YES
     70 3 1
     71 1 3
     72 3 2
     73 2 3
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 10 4
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 YES
     86 2 1
     87 1 3
     88 4 2
     89 3 4
     90 4 3
     91 3 2
     92 2 4
     93 4 1
     94 1 4
     95 3 1
     96 ```
     97 
     98 Input
     99 
    100 ```
    101 13 4
    102 ```
    103 
    104 Output
    105 
    106 ```
    107 NO
    108 ```