Вітаю Вас, Гість

Задача А.

   Учні 9-А класу на вихідні виїхали на відпочинок до лісу. Там вони вирішили пограти у гру, де потрібно накидати кільця на кілок. Діти розділились на дві команди та домовились, що виграє та команда, яка накине більше кілець за однаковий час. Для того, щоб зробити кілки, діти зібрали N гілок. Довжини гілок - a1, a2, ..., an см. Для справедливої гри потрібно вибрати зі всіх гілок дві, довжина яких відрізняється не більше, ніж на k. Провідний програміст класу Василь вирішив розрахувати, скільки є способів вибрати дві гілки, що відповідають умові. Допоможіть йому. Способи (1, 2) та (2, 1) вважати різними.

   Вхідні дані:
   В першому рядку записано два цілих числа n і k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 109) - кількість гілок, що зібрали учні, та найбільша допустима різниця довжин відповідно. У другому рядку через пропуск записано n натуральних чисел - довжини гілок. Ці числа не перевищують 109.

   Вихідні дані:
   Виведіть єдине число - кількість способів вибрати дві гілки, довжини яких відрізняються не більше, ніж на k.

   Приклади

Вхідні дані   Результат роботи
5 10
10 20 50 60 65
6
 
5 1
55 30 29 31 55
6
 

 

   Задача В.

    9-А клас все ще відпочиває на природі. Після гри в кільце учні вирішили пограти в м’яч. Всі бажаючі стали у коло. Будемо вважати, що вони пронумеровані за годинниковою стрілкою від 1 до n та перший тримає м’яч. Спочатку перший гравець кидає м’яч наступному за ним по колу, далі другий кидає тому, який стоїть через одного від нього, тобто четвертому, четвертий кидає м’яч тому гравцю, який стоїть через 2 від нього, тобто сьомому, далі м’яч переходить до того, що стоїть через 3 від чергового, далі – через 4 і так далі. При кидках м’яч може переходити через початок кола. Всього робиться n-1 кидок та гра закінчується. Програміст Василь помітив, що не всім дістався м’яч під час гри. Він захотів розрахувати, учням з якими номерами буде діставатись м’яч після першого кидка.

   Вхідні дані:
   В першому рядку міститься ціле число n (2 ≤ n ≤ 100) - кількість учнів у колі.

   Вихідні дані:
   В єдиному рядку виведіть n - 1 число - номера учнів, яким буде діставатись м’яч після кожного кидка. Числа відокремлюйте пропусками.

   Приклади

Вхідні дані   Результат роботи
10 2 4 7 1 6 2 9 7 6
3 2 1

 

   Задача С.
   Після рухливих ігор учні 9-А класу вирішили пограти у щось спокійне. Із гілок, що залишились після гри в кільце, вони захотіли скласти якомога більше прямокутників. В учнів залишилося n гілочок з довжинами a1, a2, ... an. Ламати та склеювати гілки не можна. Тобто, для складання прямокутника x×y необхідно взяти дві гілки довжиною х та дві – довжиною у, а квадрату - чотири гілки однакової довжини. Не обов’язково використати всі гілки, що залишилися. Як завжди, програміст Василь вирішив автоматизувати процес та розрахувати максимальну кількість прямокутників. Допоможіть йому.

   Вхідні дані:
   У першому рядку міститься ціле число n (1 ≤ n ≤ 100) - кількість гілок. У другому рядку міститься n цілих чисел, записаних через пропуск, i-е з яких дорівнює довжині i-ої гілки ai (1 ≤ ai ≤ 100).

   Вихідні дані:
   Виведіть одне ціле число - максимальну кількість прямокутників.

   Приклади

Вхідні дані   Результат роботи
5
2 4 3 2 3
1
 
13
2 2 4 4 4 4 6 6 6 7 7 9 9
3
 
4
3 3 3 5
0
 

 

   Задача 4.
   Вихідні закінчилися, учні 9-А класу повернулися до навчання. Багато з них полюбляє математику, тому бажають записатись у математичний гурток. Всіх бажаючих розділили на N груп. В i-й групі - Xі учнів. В школі є M аудиторій, в j-ту аудиторію можна посадити не більше, ніж Yj учнів. Потрібно розмістити найбільшу кількість груп по аудиторіях так, щоб кожна група помістилася у виділену їй аудиторію.

   Вхідні дані:
   Перший рядок містить числа N и M, 1<N<M<1000. У другому рядку містяться N чисел X1, ..., Xn, у третьому рядку містяться M чисел Y1, ..., Ym. Числа Xi, Yj - натуральні, не перевищують 1000.

   Вихідні дані:
   У першому рядку виведіть кількість груп, які можна розмістити по аудиторіях. У другому рядку виведіть розміщення груп по аудиторіях - N чисел, i-е число повинно відповідати номеру аудиторії, в якій має займатися i-та група. Нумерація як аудиторій, так і груп починається з 1. Якщо i-а група залишилась без аудиторії, то i-те число повинно дорівнювати 0. Якщо допустимих варіантів декілька, вивести такий, щоб в аудиторіях займалось якомога більше дітей.

   Приклади

Вхідні дані   Результат роботи
3 4
5 3 4
2 4 2 5
2
4 0 2

 


   Задача 5.
   Нещодавно Василь дізнався про гру “життя” та вирішив написати свою вдосконалену версію під назвою “життя-2”. Але оскільки програма буде досить велика, Василь попросив свого однокласника Миколу допомогти йому.
   Частину гри, за яку відповідає Микола, можна описати наступним чином. На початку гри є колонія, що складається з n клітин. Деякі клітини мають між собою зв’язки. Після кожного кроку гри всі клітини, що мають рівно один зв’язок, відмирають та більше в грі не беруть участь. Гра продовжується до тих пір, поки колонія не стабілізується (останнім вважати крок, під час якого хоча б одна клітина відмерла). Задача Миколи - порахувати, скільки кроків буде тривати гра.

   Вхідні дані:
   В першому рядку задані два цілих числа n та m - початкова кількість клітин та зв'язків між ними (1≤n≤100, 0≤m≤(n(n-1))/2). Клітини пронумеровані числами віл 1 до n, а зв'язки - числами від 1 до m. В наступних m рядках дано по два цілих числа a та b - номера клітин, що з'єднані i-м зв'язком (1 ≤ a, b ≤ n, a ≠ b). Якщо клітина a зв'язана з клітиною b, також вірно, що клітина b зв’язана з клітиною a. Гарантується, що жодні дві клітини не зв'язані більше, ніж одним зв'язком. Не існує зв'язків, що пов'язують клітину саму з собою.

   Вихідні дані:
   Виведіть єдине число - кількість кроків гри.

   Пояснення:
   На першому кроці відмирають клітини під номерами 1, 2 та 3. На другому кроці клітини 4 та 5. Після цього гра закінчується.

   Приклади

Вхідні дані   Результат роботи
5 4
1 4
4 3
4 5
5 2
2



 

SIV