codeforces-scrape

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

524A.md (3639B)


      1 Source: https://codeforces.com/problemset/problem/524/A
      2 
      3 A. Возможно, вы знаете этих людей?
      4 
      5 ограничение по времени на тест
      6 
      7 2 секунды
      8 
      9 ограничение по памяти на тест
     10 
     11 256 мегабайт
     12 
     13 ввод
     14 
     15 стандартный ввод
     16 
     17 вывод
     18 
     19 стандартный вывод
     20 
     21 Основой любой социальной сети является отношение дружбы между двумя пользователями в том или ином смысле. В одной известной социальной сети дружба симметрична, то есть если *a* является другом *b*, то *b* также является другом *a*.
     22 
     23 В этой же сети есть функция, которая демонстрирует множество людей, имеющих высокую вероятность быть знакомыми для пользователя. Эта функция работает следующим образом. Зафиксируем пользователя *x*. Пусть некоторый другой человек *y*, не являющийся другом *x* на текущий момент, является другом не менее, чем для *k*% друзей *x*. Тогда он является предполагаемым другом для *x*.
     24 
     25 У каждого человека в социальной сети есть свой уникальный идентификатор — это целое число от 1 до 109. Вам дан список пар пользователей, являющихся друзьями. Определите для каждого упомянутого пользователя множество его предполагаемых друзей.
     26 
     27 Входные данные
     28 
     29 В первой строке следуют два целых числа *m* и *k* (1 ≤ *m* ≤ 100, 0 ≤ *k* ≤ 100) — количество пар друзей и необходимый процент общих друзей для того, чтобы считаться предполагаемым другом.
     30 
     31 В последующих *m* строках записано по два числа *a**i*, *b**i* (1 ≤ *a**i*, *b**i* ≤ 109, *a**i* ≠ *b**i*), обозначающих идентификаторы пользователей, являющихся друзьями.
     32 
     33 Гарантируется, что каждая пара людей фигурирует в списке не более одного раза.
     34 
     35 Выходные данные
     36 
     37 Для всех упомянутых людей в порядке возрастания id выведите информацию о предполагаемых друзьях. Информация должна иметь вид "*id*:  *k* *id*1 *id*2 ... *id**k*", где *id* — это id самого человека, *k* — количество его предполагаемых друзей, а *id*1, *id*2, ..., *id**k* — идентификаторы его предполагаемых друзей в возрастающем порядке.
     38 
     39 Примеры
     40 
     41 Входные данные
     42 
     43 ```
     44 5 51  
     45 10 23  
     46 23 42  
     47 39 42  
     48 10 39  
     49 39 58
     50 ```
     51 
     52 Выходные данные
     53 
     54 ```
     55 10: 1 42  
     56 23: 1 39  
     57 39: 1 23  
     58 42: 1 10  
     59 58: 2 10 42
     60 ```
     61 
     62 Входные данные
     63 
     64 ```
     65 5 100  
     66 1 2  
     67 1 3  
     68 1 4  
     69 2 3  
     70 2 4
     71 ```
     72 
     73 Выходные данные
     74 
     75 ```
     76 1: 0  
     77 2: 0  
     78 3: 1 4  
     79 4: 1 3
     80 ```