Віталій полюбляє грати в азартні ігри. У його улюблену гру грає n людей. Гравці пронумеровані від 1 до n. У кожного гравця є два баланси: перший — його виграш, другий — нагорода за його голову. Спочатку у кожного гравця виграш — 0, а нагорода за голову — 1. У грі відбувається рівно n−1 послідовних подій такого виду: береться два різні гравці, які ще не вибули з гри, і перший з них вибиває другого. У результаті цієї операції до виграшу першого додається нагорода за голову другого, а до нагороди за голову першого додається половина нагороди за голову другого. Другий гравець вибуває з гри, тобто він вже не може нікого вибивати та бути знову вибитим кимось.
Вам потрібно знайти послідовність подій, таких, щоб сумарний виграш усіх гравців був мінімально (або максимально) можливий.
Входные данные
Перший рядок містить два цілі числа n та t (2≤n≤10
5
,0≤t≤1) — кількість гравців та число, яке вказує для мінімального чи максимального виграшу ви розв'язуєте задачу. Число 0 відповідає задачі для мінімального виграшу, 1 — для максимального.
Выходные данные
Виведіть n−1 рядків. В i-ому рядку повинно бути два цілі числа a
i
та b
i
(1≤a
i
,b
i
≤n), це означає, що гравець під номером a
i
вибив гравця b
i
на кроці i.
Примечание
Розберемо перший приклад. Баланси гравців на кожному кроці:
Баланси на початку: (0,1),(0,1),(0,1).
Баланси після першого кроку: (0,1),(1,1.5),(0,1).
Баланси після другого кроку: (0,1),(2,2),(0,1).
Сумарний виграш гравців: 2+0+0=2
Розберемо другий приклад. Баланси гравців на кожному кроці:
Баланси на початку: (0,1),(0,1),(0,1).
Баланси після першого кроку: (0,1),(0,1),(1,1.5).
Баланси після другого кроку: (0,1),(1.5,1.75),(1,1.5).
Сумарний виграш гравців: 1+0+1.5=2.5
Оценивание
У 50% тестів t=0.
У інших 50% тестів t=1.
timer
Лимит на использование времени: 1000 ms
storage
Лимит на использование памяти: 256 MB
arrow_circle_up
У вас есть еще 50 попыток отправить эту задачу
Примеры
Ниже вы найдете примеры входных данных и ответы которые должна вывести ваша программа.
Пример ввода #1
3 0
Пример ответа #1
2 3
2 1
Пример ввода #2
3 1
Пример ответа #2
3 1
2 3
1. Если алфавит состоит из 64 символов, то для хранения каждого из них необходимо 6 бит, так как 2 ^ 6 = 64, то есть достаточно для хранения алфавита такой размерности.
Для хранения сообщения из 60 символов такого алфавита необходимо 60 * 64 = 3840 бит.
Таким образом, сообщение несет 3840 : 8 = 480 байт информации.
2. 0.25 кбайт = 256 байт = 2048 бит
3. 2.5 кБайт = 2560 байт.
2560 байт / 2560 символов = 1 байт/символ
1 байт = 8 бит
8 бит = 256 вариантов (от 00000000 до 11111111).
ответ: 256 символов в алфавите
0,5 Кбайт = 0,5*1024 байт = 512*8 бит
512*8/128 = 32
2.
Память для одного символа = log(2)64=6 бит
Объем текста = 10*32*64*6 бит = 10*32*64*6/8 байт =
10*4*64*6/1024 Кбайт = 15 Кбайт
3.
3 Кбайт = 3*1024 байт = 3*1024*8 бит
Память для одного символа = 3*1024*8/6144 = 4 бита
Количество символов в алфавите = 2^4 = 16
4.
Память для одного символа = log(2)128=7 бит
Объем сообщения = 10*7 = 70 бит
8.
a) 3 Кбайт=3*1024 Байт = 3072 бАЙТ
b) 2 Мбайт=2*1024 Кбайт = 2*1024*1024 байт = 2*1024*1024*8 бит = 16777216 бит
c) 4,5 Гигабайт=4,5*1024 Мбайт = 4,5*1024*1024 Кбайт = 4718592 Кбайт