Віталій полюбляє грати в азартні ігри. У його улюблену гру грає 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. У Scratch 2 виконавців також називають спрайтами (англ. sprite — уявний герой). Усі спрайти мають свої властивості: ім'я, положення на Сцені, розміри, напрямок, у якому вони будуть рухатися, колір костюма та інші.
2. Переглянути та змінити значення властивостей об'єктів можна в розділі Інформація або у вбудованому графічному редакторі. Створити новий спрайт або вибрати тло для сцени можна кількома обрати готовий об'єкт із бібліотеки, намалювати у графічному редакторі, уставити з файла, сфотографувати камерою.
3. Сцена має такі властивості: розмір (480 на 360 кроків виконавця) і тло. Якщо вибрати цей об'єкт, то на вкладці Тло можна змінити зображення на тлі Сцени, використавши кнопки на панелі інструментів: обрати з бібліотеки, намалювати у графічному редакторі, завантажити з будь-якого файла з графічним зображенням.
4. обрати готовий об'єкт із бібліотеки, намалювати у графічному редакторі, уставити з файла, сфотографувати камерою.
5. Програмними об'єктами середовища Scratch є спрайти (виконавці) та Сцена. Усі спрайти мають свої властивості: ім'я, положення на Сцені, розміри, напрямок, у якому вони будуть рухатися, колір костюма та інші. Сцена як об'єкт середовища Scratch має властивості Тло та розмір. Кожна із цих властивостей має своє значення.
6. ?
7. Сцена як об'єкт середовища Scratch має властивості Тло та розмір. ... У середовищі Scratch вибрати дії зі спрайтами (вилучити, дублювати, сховати, збільшити, зменшити, переглянути інформацію) можна в контекстному меню об'єкта або в Рядку меню програми.
Объяснение:
#include <iostream>
using namespace std;
int main()
{
int arr[]{10,8,3,9,15,25,38};
int buff; // временная переменная для обмена элементов местами
// Сортировка массива пузырьком
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// меняем элементы местами
buff = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = buff;
}
}
}
// Вывод отсортированного массива на экран
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}