1 тур Волинська учнівська Інтернет-олімпіада з програмування Печать
Добавил(а) Administrator   
06.11.13 11:11

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

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

1тур - з 04.11 по 10.11.2013

точка входу для відправлення розв'язківhttp://93.171.173.139/cgi-bin/new-client?contest_id=16

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

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

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

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

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

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

Вхідні дані

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

M і N цілі; 1MN106.

Вихідні дані

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

Приклад вхідних даних

Приклад 1

200 300

Приклад 2

200 250

Приклад вихідних даних

Приклад 1

220 284

Приклад 2

Absent

Задача 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.

Приклад вхідних даних

Приклад вихідних даних

Приклад 1

2 2

1 0

1 0

Приклад 1

2

Приклад 2

4 4

0 0 1 0

0 1 0 1

1 1 1 0

0 0 1 0

Приклад 2

9

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

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

1тур - з 04.11 по 10.11.2013

точка входу для відправлення розв'язківhttp://93.171.173.139/cgi-bin/new-client?contest_id=16

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

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

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

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

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

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

Вхідні дані

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

M і N цілі; 1MN106.

Вихідні дані

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

Приклад вхідних даних

Приклад 1

200 300

Приклад 2

200 250

Приклад вихідних даних

Приклад 1

220 284

Приклад 2

Absent

Задача 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.

Приклад вхідних даних

Приклад вихідних даних

Приклад 1

2 2

1 0

1 0

Приклад 1

2

Приклад 2

4 4

0 0 1 0

0 1 0 1

1 1 1 0

0 0 1 0

Приклад 2

9


Задача 1

Спосіб 1

Спосіб 2

Алгоритм:

1.Перебираємо всі числа з діапазону [M,N]

2. Шукаємо для поточного числа суму дільників

d1=0;

for (int i=1;i<k;i++)

if (k%i==0)d1=d1+i;

cout<<d1<<endl;

3. Якщо сума дільників лежить на проміжку [k+1, N], то шукаємо суму дільників для знайденої суми

4. Якщо знайдена сума рівна поточному числу k, то виводимо результат і фіксуємо що знайшли хоча б одну пару

5. Якщо жодної пари не знайшли, то виводимо «Absent»

  1. 220 284
  2. 1184 1210
  3. 2620 2924
  4. 5020 5564
  5. 6232 6368
  6. 10744 10856
  7. 12285 14595
  8. 17296 18416
  9. 63020 76084
  10. 66928 66992
  11. 67095 71145
  12. 69615 87633
  13. 79750 88730
  14. 100485 124155
  15. 122265 139815
  16. 122368 123152
  17. 141664 153176
  18. 142310 168730
  19. 171856 176336
  20. 176272 180848
  21. 185368 203432
  22. 196724 202444
  23. 280540 365084
  24. 308620 389924
  25. 319550 430402
  26. 356408 399592
  27. 437456 455344
  28. 469028 486178
  29. 503056 514736
  30. 522405 525915
  31. 600392 669688
  32. 609928 686072
  33. 624184 691256
  34. 635624 712216
  35. 643336 652664
  36. 667964 783556
  37. 726104 796696
  38. 802725 863835
  39. 879712 901424
  1. 898216 980984

Задача 2

0 0 0 0 (0 кроків)

0 1 1 1  

0 0 0 0 (1 крок)

0 0 1 1

1 1 1 0

0 0 0 0 (2 кроки)

0 0 0 1

0 1 1 0

0 0 0 1

0 0 0 0 (3 кроки)

1 1 1 1

1 0 0 0

0 0 1 1

1 1 1 0

0 0 0 0 (4 кроки)