|
|
|
|
|
|
|
| 1 Федорук Семён Романович СибГУ, 12 октября 2023 г. 17:44:44 |
| Админ, у меня тут неверное решение прокатывает. 20082161. Фишка в выводе - не делается перевод строки, все значения выведены тупо через пробел одной строкой. Мне чёт не кажется, что это норма
|
|
|
| 2 Вохмянина Дария Павловна, 17 июля 2023 г. 1:02:11 |
| сдала задачу, решив в 13 строк. заполняла по диагоналям в убывающей и возрастающей арифметической прогрессии, проверяя на чётность
|
|
|
| 3 Вязовцев Андрей Викторович, 22 февраля 2019 г. 21:39:09 |
| О да..... Пытался решить где-то час, хотя до алгоритма додумался сразу же. Сделал обход по диагоналям, используя свойство, что для каждой точки одной диагонали сумма координат одинакова. Может и не самое рациональное решение, но оно интересно и стоит того.
|
|
|
| 4 Зубашев Степан, 21 мая 2017 г. 0:17:07 |
...
2. легко вычисляется количество чисел на заданной диагонали
3. легко вычисляется номер диагонали
4. берём формулу поиска N-го числа ариф. прогресссии, и учитывая, что их тут 2 разных, вычисляем максимальное число на заданной диагонали
5. определяем позицию заданной клетки в рамках своей диагонали и, зная направление диагонали и предельное значение этой диагонали - получаем результат
Как-то так. Интересно, сколько бы % было у задачи, если бы её нужно было решать с O(1) для указанной ячейки и жёсткими ограничениями по памяти и времени?
|
|
|
| 5 Зубашев Степан, 21 мая 2017 г. 0:16:52 |
Долго изучал таблицу для примера и никак не мог понять принцип движения змейки. Придумал самые разные бредовые схемы. Потом решил зайти с другого конца и осенило. Я думая о змее думал о её голове, что мол она принимает решение куда бы её повернуть исходя из какой-нибудь логики. И пытаясь понять эту логику сильно себя запутал. Так вот... К чёрту змею: таблица состоит из перекрёстных диагоналей. В одних возрастающая арифметическая прогрессия, в других убывающая. И никаких поворотов, никаких, как тут пишут "северо-западных" направлений. Просто диагонали и направление цикла.
Сдал... А в голове всё вертится, а что если N = 9999999 и нужно посчитать значение в ячейке 77243:12354? Никакие двумерные массивы тут не спасут. Должен быть простой способ определить значение в любой ячейке таблицы без циклов. Моментальное вычисление O(1). Сдал. Но задача выросла в сложности этак раза в два. Суть решения:
1. поделите таблицу на 2 части. до главной диагонали кол-во чисел на диагональ растёт, после же падает
2. легко в
|
|
|
| 6 Луффи, 21 ноября 2014 г. 11:26:27 |
| сприраль сложнее
|
|
|
| 7 Москаленко Андрей Владимирович, 11 июля 2014 г. 15:05:27 |
| Раньше я этой задачи боялся страшно. Вот сейчас решил написать, с первого раза прошло. Достаточно просто идти по диагоналям матрицы. Ну и не забывать про тесты, где n=1,n=2.
|
|
|
| 8 Кияко Вячеслав Вячеславович, 24 августа 2012 г. 1:05:53 |
| Мне кажется здесь проще всего завести переменную хранящую направление движения змейки(северо-восток или юго-запад), дальше тупо "рисуем" диагонали по заданному направлению, а когда врезаемся в стенку матрицы, то передвигаемся на одну клетку вправо или вниз и меняем направление на противоположное, если мы не можем сдвинуться ни вправо ни вниз, значит массив заполнен как следует и его можно выводить в файл. У меня при таком подходе accepted с первого раза
|
|
|
| 9 Кудаков Вадим Сергеевич, 29 июля 2011 г. 22:27:26 |
Спасибо за задачу.
Самым интересным было подобрать i так, чтобы j вычислялась без всяких сравнений.
|
|
|
| 10 Даньшин Антон Анатольевич, 30 апреля 2008 г. 17:31:44 |
Прикольная задачка! А интересно, какой наиболее рациональный алгоритм ее решения?
Да черт его знает... :) Просто берешь и пишешь.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
