Записки юного айтишника
22.01.13
Разбор задач с «Ломоносова» по информатике, ч. 1 22.01.13

Доброго времени суток, %USERNAME%. Если ты еще учишься в школе и увлечен программированием, то наверняка принимал участие в разного рода олимпиадах. Одной из них и посвящена эта записка.

Итак, олимпиада школьников «Ломоносов» ежегодно проводится МГУ совсместно с другими ВУЗами с 2005 для 11- классов и с 2006 года 9-10 классов. Проходит она, что не так уж и внезапно, в два этапа: заочный и очный. В состав входят соревнования по всем школьным и некоторым особо извращенским предметам, вроде политологии, глобалистики, журналистики и робототехники.  Участвовать в ней собираются дети от «выше среднего» до «он же гений!!11», а где- то между ними затесался и я.

Этот год- первый, когда я участвовал в «Ломоносове». Я само собою не расчитывал не особо сильные результаты. Но все сложилось даже хуже, чем я представлял..

Я взялся за олимпиады по информатике, физике и математике. Что из того вышло читайте далее.

Приступим!

Начну, пожалуй, с математики. Знаете… На этом стоит и закончить, ибо решил я только одно задание :) Стоило серьезнее отнестись к олимпиаде.. Для желающих выкладываю задания: math_task_10-11.pdf.

Перейдем к физике. Соревнования по физике проводились на отдельном ресурсе физфака МГУ. Проводились она весьма и весьма нестандартно. Было 3 заочных этапа из которых в итоге школьник должен был выбрать только один, который по их мнению написан лучше всего. Третий тур я успешно пропустил, а потому выкладываю задания только первого и второго тура: первый тур и второй тур. И тут я толком ничего не решил.

«А теперь банановый!». Олимпиада по информатике! Это единственное направление, где я решил хоть что- то, а потому постараюсь объяснить все 4( 1 — 3 — 6 — 10) моих задания в нескольких записках, так как материала для одной будет многовато. Файл со всеми заданиями.

Задание №1

Формулировка:

Квадратная таблица NxN заполняется числами от 0 до 9 следующим образом:
заполнение идет по спирали, начиная с левого верхнего угла по часовой стрелке. Ячейки
заполняются остатками от деления на 10 суммы цифр очередного числа последовательности
натуральных чисел 1, 2, 3, ….

 1  2  3  4
 3 = (1 + 2) rem 10  4 = (1 + 3) rem 10  5 = (1 + 4) rem 10  5
 2 = (1 + 1) rem 10  7 = (1 + 6) rem 10  6 = (1 + 5) rem 10  6
 1 = (1 + 0) rem 10  9  8  7

Операция rem обозначает взятие остатка от деления.
Выпишите числа, находящиеся на главной диагонали таблицы 8×8, заполненной по этим
правилам.

Что ж, классика олимпиад по программированию: заполнение матрицы по спирали. Что сложного? На самом деле- все :) Новичек в решении олимпиадных задач, вроде меня на момент начала олимпиады, сходу никогда не решит такое.

Поэтому попробуем разобраться, что нам таки нужно. Нам нужно построить матрицу, заполненную по спирали от левого верхнего угла к центру по часовой стрелке:

1 2 3 4 5 6
20 21 22 23 24 7
19 32 34 35 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11

Для этого разобьем построение целой спирали на построение квадратов на примере матрицы 6×6:

1 2 3 4 5 6
20 7
19 8
18 9
17 10
16 15 14 13 12 11

А этот квадрат, в свою очередь, на 4 цикла for: 1-6, 7-11, 12-16, 17-20. Теперь посмотрите на другие квадраты:

21 22 23 24
32 25
31 26
30 29 28 27

 

34 35
36 35

В каждом из них четыре цикла. Это значит, что они будут задавать все квадраты. Само собою, переменным параметром в них будет являться номер прохода. Запихнув все в цикл для отрисовки всех квадратов получим, что:
1) первый цикл for за все время работы алгоритма отрисует:

1 2 3 4 5 6
21 22 23 24
34 35

2) Второй цикл отрисует:

6
7
25 8
26 9
10
11

Третий и четвертый for`ы делаются абсолютно аналогично первым двум.

Подсказка: если N- нечетно, то число квадратов n = ((n-1)/2)+1, если N- четно, то n = N/2. Далее перебираем в while четыре for’а, с каждой итерацией уменьшая число квадратов( —$sn) и увеличивая номер квадрата( ++$ns).

Приступим!

Исходя из выше приведенных таблиц составим те самые 4 for цикла:

1) Заполнение матрицы слева направо

//Псевдокод
//ит=итератор
//кв= номер квадрата
//разм= размер
//яч= номер ячейки( $count)
нач цикл ( ит = кв ; ит < разм — кв ; ит++)
матр[кв][ит]=яч
яч++
кон цикл

 

21222324   3435

1 2 3 4 5 6

2) Заполнение матрицы сверху вниз

нач цикл ( ит = кв + 1; ит < разм — кв ; ит++)
матр[ит][разм — 1 — кв]=яч
яч++
кон цикл

 

7
25 8
26 9
10
11

3) Заполнение матрицы справа налево

нач цикл ( ит = разм — 2 — кв; ит >= кв ; ит++)
матр[разм — 1 — кв][ит]=яч
яч++
кон цикл

 

33 32
30 29 28 27
16 15 14 13 12

4) Заполнение матрицы снизу вверх

нач цикл ( ит = разм — 2 — кв; ит > кв ; ит++)
матр[ит][кв]=яч
яч++
кон цикл

 

1
20
19 32
18 31
17

Затем, эти 4 for‘а нужно поместить в большой while- цикл, где условием будет (ост. квадраты != 0), и каждую итерацию ост. квадраты — 1 и номер квадрата + 1

Решение на PHP, работает из консоли\браузера.

  1. <?php
  2. //Функция находения суммы чисел в ячейке матрицы и возврата остатка от деления на 10
  3. function int_to_sum($int) {
  4. $int = strval($int);
  5. $summ = 0;
  6. $len = strlen($int);
  7. for ($i = 0; $i <= $len — 1; $i++) {
  8. $summ+=$int[$i];
  9. }
  10. return $summ % 10;
  11. }
  13. //получаем N
  14. if (!empty($_GET[‘N’])) {
  15. $N = $_GET[‘N’];
  16. $c = 0;
  17. }
  18. //Так и из консоли
  19. elseif (!empty($argv[1])) {
  20. $N = $argv[1];
  21. $c = 1;
  22. }
  24. $output = array();
  25. //вычисляем число квадратов
  26. if ($N % 2 == 0)
  27. $sn = $N / 2;
  28. else
  29. $sn = (int) ($N / 2) + 1;
  30. //начальное значение
  31. $count = 1;
  32. //номер квадрата в начале алгоритма
  33. $ns = 0;
  34. $output = array();
  35. //пошло- поехало
  36. while ($sn != 0) {
  37. for ($i = $ns; $i < $N — $ns; $i++) { // step 1n
  38. $output[$ns][$i] = $count;
  39. $count++;
  40. }
  41. for ($i = $ns + 1; $i < $N — $ns; $i++) { // step 2n
  42. $output[$i][$N — 1 — $ns] = $count;
  43. $count++;
  44. }
  46. for ($i = $N — 2 — $ns; $i >= $ns; $i—) { // step 3n
  47. $output[$N — 1 — $ns][$i] = $count;
  48. $count++;
  49. }
  51. for ($i = $N — 2 — $ns; $i > $ns; $i—) { // step 4n
  52. $output[$i][$ns] = $count;
  53. $count++;
  54. }
  56. $sn—;
  57. $ns++;
  58. }
  59. if ($c == 0) {
  60. echo «<table border=1>»;
  61. for ($i = 0; $i <= $N; $i++) {
  62. echo «<tr>»;
  63. for ($ii = 0; $ii <= $N; $ii++) {
  64. if ($output[$i][$ii] != FALSE) {
  65. echo «<td width=»20» height=»20«>» . int_to_sum($output[$i][$ii]) . «</td>»;
  66. }
  67. }
  68. echo «</tr>»;
  69. }
  70. echo «</table>»;
  71. } elseif ($c == 1) {
  72. for ($i = 0; $i <= $N; $i++) {
  73. for ($ii = 0; $ii <= $N; $ii++) {
  74. if ($output[$i][$ii] != FALSE) {
  75. echo » | « . int_to_sum($output[$i][$ii])  . » | «;
  76. }
  77. }
  78. echo «n»;
  79. }
  80. }
  81. ?>

Этот код выводит требуемую матрицу. При желании, можете сделать так, что бы он выводил ответ к задаче №1 Ломоносовской олимпиады

Задание №3

Расшифруйте:

task3

Ну- с, есть догадки с первого взгляда? Это задание, пожалуй, самое просто из всей олимпиады, но не менее интересное, чем другие.

Как же расшифровать эту пикчу? Ответ прост: 1) Логика и 2) Гугл.

Как все просто, не так ли? А на самом деле за этим ответом стояли 3-4 часа непрерывного мучения гуглов. Хоть и безусловно это было невероятно интересно :)

Решения оставшихся двух заданий ждите следующей записке. 

Чистого кода и поменьше багов, друзья! До скорых встреч!

Похожие материалы:

  1. Разбор задач с “Ломоносова” по информатике, ч. 1
  2. Разбор задач с “Ломоносова” по информатике, ч. 2
Творю