Казахстанские олимпиады → KBO-1 9th grades (2011-2012)
01 ноя
Это наверное мой первый пост.) Так что не ругайте! xD Мне КБО очень понравился задачи интересные и условие было очень хорошим. Поскольку еще никто не опубликовал разбор КБО для 9, я решился сделать это!)))))
Так задача А:
Ну, здесь надо считать массив и просто сделать полный обход по массиву... Если a[i][j] == 1 то проверяем x-axis и y-axis если не одна из них не содержит целого ряда однерок, то -1! Иначе, мы просто пушим в массив ответа координаты! Надеюсь правильно объяснил.) Если возникли проблемы, то можете написать в личку!
Б:
Б - интересная задачка... Ну делаем цикл от 1 ... К и считываем а, б, с. Дальше все это можно очень легко понять!))) Мы должны узнать сумму чисел от а до б кратных с!) И в этом то и вся загвоздка! Например: а = 5, б = 19, с = 5! Получается так: 5, 10, 15; 5 / 5 = 1, 10 / 5 = 2, 15 / 5 = 3; то есть, чтобы найти сумму просто 5 * (1 + 2 + 3) или (формула ГАУСА) 5 * (3 * (3 + 1) / 2)... На первый взгляд работает, НО! есть проблема, а что если а = 6, б = 19, с = 5???? Делаем следущее: чтобы найти с чего нужно начинать, надо integer v = b / c double v1 = (a * 1.00) / (c * 1.00); if (v1 > round (v1)) v1 = round (v1) + 1; else v1 = round (v1); и дальше по описанию выше.
С:
К большому сожалению я не успел ее написать.(( Но идею решения я знаю... Просто надо записать все планеты как вершины графа, а также сделать его полным, указывая длину. Затем пройтись по нему алгоритмом Дейкстры. И все! Если кому то нужна дополнительная помощь, спрашивайте!)
C сделал с помощью алгоритма Форда-Беллмана, вроде бы все правильно. А в Б вроде нужно длинку юзать...
Дата: 2011-11-02 08:37
krosss!!!)))
Дата: 2011-11-02 16:51
С - можно и Дейкстрой, можно и Беллманом, разницы особой нет. В Б длинку можно было не писать.
Дата: 2011-11-02 18:00
Я "С" написал без графа, вроде нормально. Когда отправлял выводило "Wrong answer", но когда смотришь на другие задачи в "tele2" горело зеленый цвет вместо красного. Почему?
Дата: 2011-11-02 18:28
Мне интересно, как ты ее без построения графа решал? :)
Небольшие глюки системы. Возможно зеленый цвет обозначал что ты уже сабмитил задачу.
Дата: 2011-11-02 21:23
Хорошая новость, что в Б не нужна длинка. А то последние полчаса писал длинку, закончил за 10 секунд до конца контеста и не успел сдать) С лон лон интом должно пройти? P.S. Почему когда я нажимаю 'ответить' ничего не происходит?
Дата: 2011-11-02 19:24
У меня кнопка "ответить" работает. Каким браузером пользуешься?
Для некоторых это была плохая новость. Вообще, это ошибка составителя задачи, в ней ограничения указаны неверно. Если бы (a, b) были до 10^17 то действительно нужна была длинная арифметика. Тем более при том количестве запросов, я себе не представляю как ее надо было бы реализовывать.. Так что приношу извинения от имени организаторов :)
Дата: 2011-11-02 21:24
Mozilla Firefox. Главное, что бы на следующем кбо такого не было)
Дата: 2011-11-03 09:11