Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Гречишников Владислав Михайлович, 21 декабря 2021 г. 14:49:47
     :>
  2  Арсланбек Зулунов Фарходович, 15 апреля 2021 г. 18:07:47
     я один на чётность проверял?
  3  Алибаев Ельнур Сакенулы, 01 ноября 2020 г. 16:55:51
     Почему у меня Time limit exceeded? Хотя все ответы правильные
  4  Вязовцев Андрей Викторович, 22 февраля 2019 г. 21:39:09
     О да..... Пытался решить где-то час, хотя до алгоритма додумался сразу же. Сделал обход по диагоналям, используя свойство, что для каждой точки одной диагонали сумма координат одинакова. Может и не самое рациональное решение, но оно интересно и стоит того.
  5  Зубашев Степан, 21 мая 2017 г. 0:17:07
     ...
2. легко вычисляется количество чисел на заданной диагонали
3. легко вычисляется номер диагонали
4. берём формулу поиска N-го числа ариф. прогресссии, и учитывая, что их тут 2 разных, вычисляем максимальное число на заданной диагонали
5. определяем позицию заданной клетки в рамках своей диагонали и, зная направление диагонали и предельное значение этой диагонали - получаем результат

Как-то так. Интересно, сколько бы % было у задачи, если бы её нужно было решать с O(1) для указанной ячейки и жёсткими ограничениями по памяти и времени?
  6  Зубашев Степан, 21 мая 2017 г. 0:16:52
     Долго изучал таблицу для примера и никак не мог понять принцип движения змейки. Придумал самые разные бредовые схемы. Потом решил зайти с другого конца и осенило. Я думая о змее думал о её голове, что мол она принимает решение куда бы её повернуть исходя из какой-нибудь логики. И пытаясь понять эту логику сильно себя запутал. Так вот... К чёрту змею: таблица состоит из перекрёстных диагоналей. В одних возрастающая арифметическая прогрессия, в других убывающая. И никаких поворотов, никаких, как тут пишут "северо-западных" направлений. Просто диагонали и направление цикла.

Сдал... А в голове всё вертится, а что если N = 9999999 и нужно посчитать значение в ячейке 77243:12354? Никакие двумерные массивы тут не спасут. Должен быть простой способ определить значение в любой ячейке таблицы без циклов. Моментальное вычисление O(1). Сдал. Но задача выросла в сложности этак раза в два. Суть решения:

1. поделите таблицу на 2 части. до главной диагонали кол-во чисел на диагональ растёт, после же падает
2. легко в
  7  Луффи, 21 ноября 2014 г. 11:26:27
     сприраль сложнее
  8  Москаленко Андрей Владимирович, 11 июля 2014 г. 15:05:27
     Раньше я этой задачи боялся страшно. Вот сейчас решил написать, с первого раза прошло. Достаточно просто идти по диагоналям матрицы. Ну и не забывать про тесты, где n=1,n=2.
  9  Кияко Вячеслав Вячеславович, 24 августа 2012 г. 1:05:53
     Мне кажется здесь проще всего завести переменную хранящую направление движения змейки(северо-восток или юго-запад), дальше тупо "рисуем" диагонали по заданному направлению, а когда врезаемся в стенку матрицы, то передвигаемся на одну клетку вправо или вниз и меняем направление на противоположное, если мы не можем сдвинуться ни вправо ни вниз, значит массив заполнен как следует и его можно выводить в файл. У меня при таком подходе accepted с первого раза
  10  Кудаков Вадим Сергеевич, 29 июля 2011 г. 22:27:26
     Спасибо за задачу.
Самым интересным было подобрать i так, чтобы j вычислялась без всяких сравнений.
  11  Даньшин Антон Анатольевич, 30 апреля 2008 г. 17:31:44
     Прикольная задачка! А интересно, какой наиболее рациональный алгоритм ее решения?
     Да черт его знает... :) Просто берешь и пишешь.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2022, ICQ: 151483, E-mail: admin@acmp.ru



Live-ставки на формула 1