Сайт підготовки до олімпіади з інформатики

Волинська учнівська Інтернет-олімпіада з програмування

Реєстрація http://vippoolimp.16mb.com/joomla/index.php/registr2013

1тур - з 04.11 по 10.11.2013

Задача 1. Цікаві числа (20 балів)

Ім'я вхідного файлу: number.dat

Ім'я вихідного файлу: number.ans

Програма: number.*

Обмеження часу: 2с

Два різних натуральних числа називаються цікавими, якщо перше з них дорівнює сумі дільників другого числа, за винятком самого другого числа, а друге дорівнює сумі дільників першого числа, за винятком самого першого числа. Потрібно знайти всі пари цікавих чисел, обидва з яких належать проміжку від M до N.

Вхідні дані

У першому рядку знаходяться відокремлені пропуском числа M і N.

M і N цілі; 1 ≤ M ≤ N ≤ 10⁶.

Вихідні дані

У кожному рядку вивести по парі чисел через пропуск. Перше число пари повинно бути менше другого. Рядки повинні бути відсортовані у порядку зростання першого числа пари. Якщо пар цікавих чисел на проміжку немає, вивести "Absent".

200 250

220 284

Задача 2. Таблиця (100 балів)

Ім'я вхідного файлу: table.dat

Ім'я вихідного файлу: table.ans

Програма: table.*

Обмеження часу: 2с

Маємо таблицю розміром N*M, в кожній клітинці якої записана цифра 0 або 1. На кожному кроці Ви можете вибрати одну клітинку і поміняти значення в усіх клітинках, які знаходяться в тому ж рядку або в тому ж стовпці, на протилежні. Таким чином, на кожному кроці Ви змінюєте рівно N+M-1 клітинок.

Визначити мінімальну кількість кроків необхідних для того, щоб перетворити всі клітинки даної таблиці в 0. Кількість рядків і стовпців – парні числа. Наприклад, якщо ви вибрали клітинку (2,2):

1 1 1                       1 0 1

0 1 1 ->   1 0 0

0 0 1                       0 1 1

Вхідні дані

Перший рядок містить два цілих числа M і N (2<N,M<1000).Далі N рядків по Mцілих чисел, - опис таблиці (кожне число 0 бо 1). N і M – парні.

Вихідні дані

Одне число – мінімальна кількість кроків, які необхідні, щоб перетворити всі клітинки таблиці в 0.

Волинська учнівська Інтернет-олімпіада з програмування

Реєстрація http://vippoolimp.16mb.com/joomla/index.php/registr2013

1тур - з 04.11 по 10.11.2013

Задача 1. Цікаві числа (20 балів)

Ім'я вхідного файлу: number.dat

Ім'я вихідного файлу: number.ans

Програма: number.*

Обмеження часу: 2с

Два різних натуральних числа називаються цікавими, якщо перше з них дорівнює сумі дільників другого числа, за винятком самого другого числа, а друге дорівнює сумі дільників першого числа, за винятком самого першого числа. Потрібно знайти всі пари цікавих чисел, обидва з яких належать проміжку від M до N.

Вхідні дані

У першому рядку знаходяться відокремлені пропуском числа M і N.

M і N цілі; 1 ≤ M ≤ N ≤ 10⁶.

Вихідні дані

У кожному рядку вивести по парі чисел через пропуск. Перше число пари повинно бути менше другого. Рядки повинні бути відсортовані у порядку зростання першого числа пари. Якщо пар цікавих чисел на проміжку немає, вивести "Absent".

200 250

220 284

Задача 2. Таблиця (100 балів)

Ім'я вхідного файлу: table.dat

Ім'я вихідного файлу: table.ans

Програма: table.*

Обмеження часу: 2с

Маємо таблицю розміром N*M, в кожній клітинці якої записана цифра 0 або 1. На кожному кроці Ви можете вибрати одну клітинку і поміняти значення в усіх клітинках, які знаходяться в тому ж рядку або в тому ж стовпці, на протилежні. Таким чином, на кожному кроці Ви змінюєте рівно N+M-1 клітинок.

Визначити мінімальну кількість кроків необхідних для того, щоб перетворити всі клітинки даної таблиці в 0. Кількість рядків і стовпців – парні числа. Наприклад, якщо ви вибрали клітинку (2,2):

1 1 1                       1 0 1

0 1 1 ->   1 0 0

0 0 1                       0 1 1

Вхідні дані

Перший рядок містить два цілих числа M і N (2<N,M<1000).Далі N рядків по Mцілих чисел, - опис таблиці (кожне число 0 бо 1). N і M – парні.

Вихідні дані

Одне число – мінімальна кількість кроків, які необхідні, щоб перетворити всі клітинки таблиці в 0.