Всероссийская олимпиада школьников по информатике
Потому что есть еще и реализация. Забудешь какой-нибудь тривиальный случай - и задача уже не решена, а узнаешь ты это только при объявлении результатов, когда исправлять что-то уже будет поздно. Плюс время на решение задач весьма ограничено.
Если тебе задачки с всероса кажутся примитивными - попробуй себя на www.topcoder.com/tc.
Если тебе задачки с всероса кажутся примитивными - попробуй себя на www.topcoder.com/tc.
Плюс время на решение задач весьма ограничено.Я в курсе.
На идеи для трёх задач понадобилось около часа.
Забудешь какой-нибудь тривиальный случай - и задача уже не решена, а узнаешь ты это только при объявлении результатов, когда исправлять что-то уже будет поздноНе путай традиционные школьные олимпиады в россии с ACM.
На ACM - да, если провалишь хотя бы один тест, не получишь ничего. На школьных олимпиадах - каждый тест оценивается в какое-то количество баллов (в сумме получается количество баллов за задачу за каждый пройденный тест получаешь соответствующее количество баллов.
Потому что есть еще и реализацияКогда я раньше (в школе) участвовал в олимпиадах по информатике, основнойф сложностью была как раз идея - как решить эту задачу, да ещё и уложиться в заданное время и в заданную память. А реализовать любой говнокодер может. Ну не любой, конечно, но это была довольно маленькая часть от всей нагрузки.
выложи сюда что-ли задачки. заценю твои способности. что-то я сомневаюсь, что ты за час все три заделаешь
Да они просто реально примитивные 
http://info.rusolymp.ru/default.asp?trID=4635 (я решал задачи первого дня, на второй потом посмотрю).
Только я насчёт третьей не совсем уверен. Там про ограничение ничего не сказано; в моём решении требуется порядка n*n*k времени и порядка n*k памяти. И ещё, непонятно, влезет ли итоговое число в стандартное целое - иначе придётся париться с длинной арифметикой и время+память ещё сильнее увеличатся.
http://info.rusolymp.ru/default.asp?trID=4635 (я решал задачи первого дня, на второй потом посмотрю).
Только я насчёт третьей не совсем уверен. Там про ограничение ничего не сказано; в моём решении требуется порядка n*n*k времени и порядка n*k памяти. И ещё, непонятно, влезет ли итоговое число в стандартное целое - иначе придётся париться с длинной арифметикой и время+память ещё сильнее увеличатся.
что-то я сомневаюсь, что ты за час все три заделаешьМатематические решения за час были готовы для всех трёх; осталось только это заговнокодить (но это уже влом).
ну-ка ну-ка давай сюда свои решения =)
скорее всего ты даже не пытался оценить ограничения по памяти и времени вкупе с ограничениями на входные данные.
скорее всего ты даже не пытался оценить ограничения по памяти и времени вкупе с ограничениями на входные данные.
И ещё, непонятно, влезет ли входное число в стандартное целое - иначе придётся париться с длинной арифметикой и время+память ещё сильнее увеличатся.=)
скорее всего ты даже не пытался оценить ограничения по памяти и времени вкупе с ограничениями на входные данные.Прикинь себе, пытался.
В первой задаче время линейное, память линейная.
Во второй - надо довести идею до ума, но там порядка n*n, а может быть, даже и порядка n.
=)Ещё раз, для тех, кто в танке - в условии не сказано об ограничениях.
Если бы я был на реальной олимпиаде - задал бы вопрос жюри.
anyway, время порядка n*n*k - этого хватит даже для длины в десять тысяч. Думаю, это подойдёт.
По крайней мере, 200 + сколько-то за третью задачу в один только первый день я бы получил.
писать правильный код изначально не многе умеют
вот это и оценивается на олимпиаде
решить задачку в уме - более менее легко, ве задачки более менее однотипные, нужно токо грамотно применить чтонить типа динамического программирования
написать код - тоже легко
но вот написать код без ошибок как чисто прогерских (напр. не вылазить за границы массива) так и алгоритмических (не забыть рассмотреть все случаи) да еще и с ограничением по времени - это далеко не каждый может
вот это и оценивается на олимпиаде
решить задачку в уме - более менее легко, ве задачки более менее однотипные, нужно токо грамотно применить чтонить типа динамического программирования
написать код - тоже легко
но вот написать код без ошибок как чисто прогерских (напр. не вылазить за границы массива) так и алгоритмических (не забыть рассмотреть все случаи) да еще и с ограничением по времени - это далеко не каждый может
По крайней мере, 200 + сколько-то за третью задачу в один только первый день я бы получил.Получи медаль на складе.
Олимпиады по информатике — херня, они бестолковые и бесполезные, ничему не учат. Начать нужно с азов, чтобы в школу учителя пришли, а не географичка из соседней школы часы добирала.
писать правильный код изначально не многе умеютЗначит, за последние годы в олимпиадах что-то поменялось. В моё время всё было не так.
вот это и оценивается на олимпиаде
Получи медаль на складе.Да нет, просто весело смотреть - уж диплом первой степени (который давали за 395+ баллов) я бы наверняка получил. А вместо этого я с математикой в школе ковырялся, и информатика в моей жизни была только в виде ACM, в котором я участвовал только в 11 классе.
я уж думала, ты по человечески выделил время — столько же сколько дается на олимпиаду, сел и все решил от и до
хотела сказать что-то вроде "все-таки выпускник универа от школьника не только знаниями отличается, но и навыки развиваются, и способности..."
а ты оказывается "подумал над идеями"
в ландавшице тоже обычно пишут "легко понять что", а на деле — пойди разберись
хотела сказать что-то вроде "все-таки выпускник универа от школьника не только знаниями отличается, но и навыки развиваются, и способности..."
а ты оказывается "подумал над идеями"
в ландавшице тоже обычно пишут "легко понять что", а на деле — пойди разберись
Да нет, просто весело смотреть - уж диплом первой степени (который давали за 395+ баллов) я бы наверняка получил.примерно то же думают все остальные участники олимпиады перед их началом.
я уж думала, ты по человечески выделил время — столько же сколько дается на олимпиаду, сел и все решил от и доНу как бы я тапк и сделал.
а ты оказывается "подумал над идеями"Нет.
У меня прямо сейчас есть готовые решения для первой и третьей задач - осталось только сесть и заговнокодить, но делать это мне влом.
И наброски решения (да, только идеи) для второй задачи - которые наверняка можно было бы за оставшееся время превратить в собственно решение.
Просто заниматься этим уже неинтересно.
примерно то же думают все остальные участники олимпиады перед их началом.Почему они так думают?
Я почему-то обычно на олимпиадах по математике получал примерно столько баллов, сколько у меня выходило при прорешивании задач за предыдущие годы. Отличия - возможно, на одну задачу в большую или меньшую сторону + за некоторые задачи только 5-6 баллов из 7.
осталось только сесть и заговнокодить, но делать это мне влом.
это типичный случай "легко понять что" плюс симптомы наполеонизма
сядь, да закодь
ты по алгебре задачи тоже решаешь только до составления уравнения?
сядь, да закодьЯ же говорю, неинтересно уже.
Опыт участия в подобных мероприятиях у меня есть, так что я, наверное, представляю, сколько времени на что уходит?
Так вот, за оставшиеся три (или для информатики - четыре?) часа можно спокойно и заговнокодить уже имеющиеся решения, и, возможно, сделать точное решение оставшейся задачи.
ЗЫ: Под "есть полное решение" я имею в виду, что уже есть точный алгоритм, как должна работать программа, только кода ещё нет.
и информатика в моей жизни была только в виде ACM, в котором я участвовал только в 11 классе.ээээ, acm и школа в пересечении дают пустое множество =)
ээээ, acm и школа в пересечении дают пустое множество =)Во-первых, есть школьный аналог acm, а во-вторых, наша команда поучаствовала и в четвертьфинале простого ACM (именно из-за этого я не участвовал в нём на первом курсе - потому что четвертьфинал на урале проходит весной предыдущего учебного года; ну а ко второму курсу это уже меня не интересовало).
Возможно, он систему проведения имеет ввиду. Были же школьные командные по ACM-правилам.
Олимпиады по информатике — херня, они бестолковые и бесполезные, ничему не учат. Начать нужно с азов, чтобы в школу учителя пришли, а не географичка из соседней школы часы добирала.извини, но ты не в теме.
они не очень учат программировать в идустриальном смысле но думать и решать задачи очень даже.
настолько суров, что участвовал в ACM еще школьником.
Что тебе не нравится?
в acm задачи в среднем проще, а 1/4 они проще школьной всеросийcкой.
но специфика системы оценки и наборы тестов требуют безупречного решения и реализации, так что в acm упор на кодерские навыки значительно больше, а в школьных олимпиадах больше упор на идею и эвристики.
но специфика системы оценки и наборы тестов требуют безупречного решения и реализации, так что в acm упор на кодерские навыки значительно больше, а в школьных олимпиадах больше упор на идею и эвристики.
Я, если чо, ваще не в претензии. Просто вдруг улыбнулся и написал чо попало.
в acm задачи в среднем проще, а 1/4 они проще школьной всеросийсокой.Я не говорил, что не участвовал в школьных олимпиадах по информатике.
но система специфика оценки и наборы тестов требуют безупречного решения и реализации, так что в acm упор на кодерские навыки значительно больше, а в школьных олимпиадах больше упор на идею и эвристикиДа, я уже об этом говорил.
Правда, с другой стороны, если ты на ACM неправильно решил задачу, ты можешь её исправить, в отличие от обычных олимпиад.
ЗЫ: Была на том четвертьфинале задача, которую решила только одна команда (она, кстати, получила первое место, с существенным отрывом от остальных и только четыре пытались (7, 4, 2 и 1 неудачные попытки).
Блять, мы 17 раз её отправляли, вылизывали, как только могли - хрен там, валится на самом первом тесте. Наверное, половину всего дня на эти 17 отправок потратили.
Я уже после объявления результатов взял тесты... и что же? В тестах в файлах выхода для сравнения содержалось только число. А мы писали writeln...
Правда, с другой стороны, если ты на ACM неправильно решил задачу, ты можешь её исправить, в отличие от обычных олимпиад.как правило это уже по-любому слив.
в acm нужно быть на голову умнее чтоб позволять себе лажать в реализации, а лажа в идее всегда непростительна.
как правило это уже по-любому слив.Нифига подобного.
в acm нужно быть на голову умнее чтоб позволять себе лажать в реализации, а лажа в идее всегда непростительна.Можно накосячить в идее - забыть рассмотреть какие-то нехорошие случаи. Можно опечататься в реализации, перепутать плюс с минусом - так, что это будет вскрываться только на определённых входных данных.
Нифига подобного.сколько раз ты выигрывал?
Можно накосячить в идее - забыть рассмотреть какие-то нехорошие случаи. Можно опечататься в реализации, перепутать плюс с минусом - так, что это будет вскрываться только на определённых входных данных.ну и? ты что-то не очевидное сказал?
у задач с acm покрытие тестами максимально полное, они так специально придумываются.
сколько раз ты выигрывал?Ты, кажется, говорил не про слив в дипломах, а про слив в конкретной задаче?
Так вот, если твоя программа с первого раза не прошла, это ещё ничего не значит.
у задач с acm покрытие тестами максимально полное, они так специально придумываются.Разве это что-то специфическое для acm?
ну и? ты что-то не очевидное сказал?Я тебе отвечал на то, что якобы неудача при первой попытке сдать задачу - слив.
Кстати, к вопросу о дипломах, у первого места на том четвертьфинале:
+9Довольно много задач, сданных не с первой попытки, тебе не кажется?
+8
+
+
+6
+
.
-9
+
+
-3
+1
+2
+1
+6
.
+
+1
+
+
Довольно много задач, сданных не с первой попытки, тебе не кажется?ну они решили задач больше чем вторые?
Да.
Но какое это отношение имеет к
Но какое это отношение имеет к
?Правда, с другой стороны, если ты на ACM неправильно решил задачу, ты можешь её исправить, в отличие от обычных олимпиад.как правило это уже по-любому слив.
о какое это отношение имеет кцитируй уж до конца
как правило это уже по-любому слив.
в acm нужно быть на голову умнее чтоб позволять себе лажать в реализации, а лажа в идее всегда непростительна.
Тем не менее, практически _у_всех_ команд довольно много задач решены не с первой попытки.
Как же твоё правило применяется на практике?
Как же твоё правило применяется на практике?
Ты учти, что задачи нужно решать где-то за 20-30 минут. И времени на дебаг плюса, замененного на минус (и это хорошо еще, если есть тест, на котором прога валится) - нет. А по распечаткам такое найти бывает весьма и весьма не просто.
Весь день пролежал на диване,
Много дел в голове переделал.
Заслуженно выпью сто грамм.
Причём примитивные с точки зрения школьника, а не студента - ничего, полученного за последние четыре года, я при решении не использовал.
поэтому ты мехмат и не закончил
Ты учти, что задачи нужно решать где-то за 20-30 минут. И времени на дебаг плюса, замененного на минус (и это хорошо еще, если есть тест, на котором прога валится) - нет. А по распечаткам такое найти бывает весьма и весьма не просто.Ты это к чему говоришь? Что сказать-то хочешь?
Практически у всех команд - и у первых, и у последних, и у тех, кто посередине - довольно большое количество задач решено не с первой попытки.
Где тут "если не сдал задачу с первой попытки - гарантированный слив"?
ЗЫ: Мой опыт подсказывает мне, что найти ошибку обычно можно довольно легко.
В частности, наши результаты на одном из школьных соревнований уровня области:
. -4 +1 +1 + + +1 + 6 654
Ты ещё скажи, что на олимпиадах по математике главное - умение человека держать ручку в руках и написать пять страниц текста и формул; а решение самих задач и доведение этого решения до ума - так, дело десятое.
Ты ещё скажи, что на олимпиадах по математике главное - умение человека держать ручку в руках и написать пять страниц текста и формул; а решение самих задач и доведение этого решения до ума - так, дело десятое.Ты зачем тему-то начал? Пока что ты только пиздел о том, как ты крут. Ни детального алгоритма решения задач, ни кода мы здесь не увидели. И так: у тебя есть самомнение, что мог бы с лёгкостью решить эти задачи. Дальше-то что?
Ни детального алгоритма решения задач, ни кода мы здесь не увиделиДетальные алгоритмы решения:
Задача 1
Создадим (в уме) массив размера n+1. Первый элемент - 0, второй элемент - 1, если на первом месте девочка, или -1, если на первом месте мальчик; i+1 элемент = (i элемент + 1 если на i месте девочка, и (i элемент - 1 если на i месте мальчик.
Если какая-то последовательность мальчиков и девочек от i до j включительно содержит одинаковое количество мальчиков и девочек, то на i месте в нашем придуманном массиве будет стоять то же самое число, что и на j+1; и наоборот, если на i и j местах в массиве (j > i) находятся одинаковые числа, то группа школьников от i до j-1 включительно состоит из одинакового количества мальчиков и девочек.
Реальный массив устроим таким образом: индексы от -n до n включительно, значения - целые положительные (по умолчанию 0 чтобы в них влезло n (т.е. достаточно int32 на это уйдёт (1+2*n)*4 байт, то есть, мы более чем укладываемся в ограничения по памяти.
При прохождении по мальчикам-девочкам (потребуется один проход, т.е. этим можно заниматься даже во время чтения последовательности мальчиков-девочек, не затрачивая дополнительную память) храним в уме текущее состояние нашего виртуального массива и для очередного значения x увеличиваем в реальном массиве значение по индексу x на единицу (к самому первому элементу виртуального массива, который с индексом и значением 0, это, конечно, тоже относится).
На это уйдёт линейное время.
Затем (тут уже понадобится одно число int64) идём по получившемуся массиву, для каждого его элемента, если он больше единицы, добавляем к результату (который исходно был нулём) x*(x-1)/2, где x - этот элемент. Выводим результат.
Остаётся всё это заговнокодить и прогнать на тех двух тестах, которые есть в условии задачи - чтобы отловить глупые опечатки.
Например, для первого теста получаем массив:
0 0 0 1 0 0 0 (до чтения расстановки мальчиков-девочек)
0 0 0 1 1 0 0 (прочитали первого)
0 0 0 2 1 0 0 (прочитали второго)
0 0 0 2 2 0 0 (прочитали третьего)
Результат: 2*1/2 (для нуля) + 2*1/2 (для единицы) = 2, что совпадает с правильным ответом.
Второй тест:
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0, состояние 0 (до чтения расстановки)
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0, состояние -1
0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0, 0
0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0, 1
0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 0 0, 0
0 0 0 0 0 0 0 1 3 2 0 0 0 0 0 0 0, 1
0 0 0 0 0 0 0 1 4 2 0 0 0 0 0 0 0, 0
0 0 0 0 0 0 0 1 4 3 0 0 0 0 0 0 0, 1
0 0 0 0 0 0 0 1 5 3 0 0 0 0 0 0 0, 0
Результат: 5*4/2 (для нуля) + 3*2/2 (для единицы) = 13, что совпадает с правильным ответом.
Если надо, могу написать то же для третьей задачи, но попозже - сейчас я ребутаюсь бэкапить системный раздел.
Как, как. За лишнию попытку начисляют штрафное время.
Поэтому приходиться выбирать, дополнительно протестировать программу или отправить на проверку.
И вы должны быть действительно круты, чтобы рисковать и отправить раньше.
Поэтому приходиться выбирать, дополнительно протестировать программу или отправить на проверку.
И вы должны быть действительно круты, чтобы рисковать и отправить раньше.
надо создать альт
Penurtur's best posts
блять радуешь
Penurtur's best posts
блять радуешь
Ну и чтобы совсем расслабиться надо быть уверенным, что решишь на задачу больше чем все остальные. 
Как, как. За лишнию попытку начисляют штрафное время.За лишнюю возню тоже начисляется время.
Поэтому приходиться выбирать, дополнительно протестировать программу или отправить на проверку.
И будет очень весело, если ты будешь весь чемпионат сидеть, проверять свои задачи, потом за десять минут до конца их отправишь - а половина свалится, потому что ты всё-таки не заметил опечатку.
Кроме того, много что может сказать номер теста, на котором свалилась программа.
Или ты написал программу, вроде бы, порядок времени, за который она считает - правильный, но она всё-таки свалилась по превышению времени на 20 тесте - всё понятно, надо срочно её оптимизировать (ты же исходно не знал, пройдёт она или нет; так ты потеряешь с какой-то вероятностью 20 штрафных минут, а если бы вылизывал её - то точно потерял бы время.
Задача 3
Кроме понятия "счастливых номеров", введём понятие "x-номеров" (x>=0 где номер (произвольной длины) является x-номером, если его цифры можно разделить на две (возможно, одна из них будет пустой) кучи таким образом, что их суммы будут отличаться на x.
x - целое и для номеров длиной в n не может быть больше, чем n*k.
Как легко понять, количество x-номеров длины n, начинающихся на цифру d, равно сумме количества (x-d)-номеров и (x+d)-номеров длины n-1 (или только (x+d)-номеров, если x<d)
Значит, количество x-номеров длины n равно (для простоты - в десятичной системе счисления)
s(x-9, n-1) + s(x-8, n-1) + ... + s(x+9, n-1 где s(a, b) - количество a-номеров длины b, если a>=0, и 0, если a<0 (будем для любой длины номеров хранить статистику по x-номерам для всех x, которые меньше n*k, независимо от этой длины; n - та длина, которую дали на входе)
Будем идти от 0 до того n, которое на входе, и поддерживать два массива (целых чисел или длинных целых чисел, зависит от ограничения) длины n*k.
На первом шаге (0) заполним массив нулями, только в нулевой элемент запишем единицу.
На каждом следующем шаге по массиву, который остался от предыдущего шага, будем считать новый массив (для этого нам их и понадобилось два, в каждый момент нам нужен текущий и предыдущий массивы) по описанной выше формуле. Для этого понадобится i*k*k времени (нужно заполнить i*k элементов, для каждого из них нужно проделать 2k операций).
В результате, за время порядка n*k*k мы получим массив размера n*k, в котором в нулевом элементе и лежит то, что нам нужно - количество 0-номеров длины n. Теперь достаточно всего лишь вычесть его из k^n и вывести ответ на экран.
Кроме понятия "счастливых номеров", введём понятие "x-номеров" (x>=0 где номер (произвольной длины) является x-номером, если его цифры можно разделить на две (возможно, одна из них будет пустой) кучи таким образом, что их суммы будут отличаться на x.
x - целое и для номеров длиной в n не может быть больше, чем n*k.
Как легко понять, количество x-номеров длины n, начинающихся на цифру d, равно сумме количества (x-d)-номеров и (x+d)-номеров длины n-1 (или только (x+d)-номеров, если x<d)
Значит, количество x-номеров длины n равно (для простоты - в десятичной системе счисления)
s(x-9, n-1) + s(x-8, n-1) + ... + s(x+9, n-1 где s(a, b) - количество a-номеров длины b, если a>=0, и 0, если a<0 (будем для любой длины номеров хранить статистику по x-номерам для всех x, которые меньше n*k, независимо от этой длины; n - та длина, которую дали на входе)
Будем идти от 0 до того n, которое на входе, и поддерживать два массива (целых чисел или длинных целых чисел, зависит от ограничения) длины n*k.
На первом шаге (0) заполним массив нулями, только в нулевой элемент запишем единицу.
На каждом следующем шаге по массиву, который остался от предыдущего шага, будем считать новый массив (для этого нам их и понадобилось два, в каждый момент нам нужен текущий и предыдущий массивы) по описанной выше формуле. Для этого понадобится i*k*k времени (нужно заполнить i*k элементов, для каждого из них нужно проделать 2k операций).
В результате, за время порядка n*k*k мы получим массив размера n*k, в котором в нулевом элементе и лежит то, что нам нужно - количество 0-номеров длины n. Теперь достаточно всего лишь вычесть его из k^n и вывести ответ на экран.
Я чуть прокомментирую.
Задача 3
Кроме понятия "счастливых номеров", введём понятие "x-номеров" (x>=0 где номер (произвольной длины) является x-номером, если его цифры можно разделить на две (возможно, одна из них будет пустой) кучи таким образом, что их суммы будут отличаться на x.
x - целое и для номеров длиной в n не может быть больше, чем n*k.
Как легко понять, количество x-номеров длины n, начинающихся на цифру d, равно сумме количества (x-d)-номеров и (x+d)-номеров длины n-1 (или только (x+d)-номеров, если x<d)
Значит, количество x-номеров длины n равно (для простоты - в десятичной системе счисления)
s(x-9, n-1) + s(x-8, n-1) + ... + s(x+9, n-1 где s(a, b) - количество a-номеров длины b, если a>=0, и 0, если a<0 (будем для любой длины номеров хранить статистику по x-номерам для всех x, которые меньше n*k, независимо от этой длины; n - та длина, которую дали на входе)
Будем идти от 0 до того n, которое на входе, и поддерживать два массива (целых чисел или длинных целых чисел, зависит от ограничения) длины n*k.
На первом шаге (0) заполним массив нулями, только в нулевой элемент запишем единицу.
На каждом следующем шаге по массиву, который остался от предыдущего шага, будем считать новый массив (для этого нам их и понадобилось два, в каждый момент нам нужен текущий и предыдущий массивы) по описанной выше формуле. Для этого понадобится i*k*k времени (нужно заполнить i*k элементов, для каждого из них нужно проделать 2k операций).
В результате, за время порядка n*k*k мы получим массив размера n*k, в котором в нулевом элементе и лежит то, что нам нужно - количество 0-номеров длины n. Теперь достаточно всего лишь вычесть его из k^n и вывести ответ на экран.
1. В примерах, оторые даны школьнику, был пример, где n = 50. В случае k = 9 всего 50 значных числе больше, чем 2^166. То есть в твоем алгоритме ты без длинной арифметики уже не сможешь обойтись.
2. У тебя просто будет около 5-10 баллов за эту задачу, если я не путаю. Возьмем второй тест. n = 4, k = 3. Первый твой массив (инициализация, соответствует n= 0) s(0, 0) = 1, остальные нули. На следующем шаге (по твоему алгоритму) s(0, 1) = s(1, 2) = s(2, 1) = s(3, 1) = 1, остальные 0. Очередной шаг дает s(0, 2) = s(1, 2) = s(2, 2) = s(3, 2) = 4, s(4, 2) = 3, s(5, 2) = 2, s(6, 2) = 1; остальные 0. Третий шаг (чуть чуть осталось) s(0, 3) = 16, s(1, 3) = 19, s(2, 3) = 21, s(3, 3) = 22; остальные не важно уже. Четвертый шаг s(0, 4) = s(0, 3) + s(1, 3) + s(2, 3) + s(3, 3) = 78. Итоговый твой ответ есть (k+1)^n (а не k^n, здесь у тебя тоже ошибка) - s(0, 4) = 4^4 - 78 = 256 - 78 = 168. Правильный ответ (в тестах есть) 164. Не сходится.
PS
Если серьезно, то, думаю, шансы на третий диплом (если бы ты не ленился писать, что придумал) у тебя есть
PSS
Если интересно, то можем и во второй ошибку поискать, если запостишь.
Кстати, пока у тебя описание алгоритма, а не его реализация - здесь тяжело достоверно говорить, есть ошибка или нет. К тому же это первая задача, которые решают почти все школьники с олимпиады, она очень простая и ошибиться почти негде. Но я бы предпочел, чтобы ы написал реализацию своего алгоритма, если не трудно. На одном из языков, которые разрегены на этой олимпиаде. Зачем? Если реализовать ровно то, что написано, часть тестов не пройдет. Возможно ты просто не до конца точно описал что хочешь, но, пока, приведенное описание не проходит часть тестов (не знаю сколько). При этом проходит те два, что даны для тестирования.
Детальные алгоритмы решения:
Задача 1
...
PS
Ты еще порешай задачки второго дня, обычно он интереснее, чем первый.
Вот тут http://neerc.ifmo.ru/regional/standings.html результаты не любительских соревнований, а полуфинал (и, заодно, финал чемпионата России). Все лидеры имеют по 3-4 "чистых" задачи (с первой попытки). Причем, у 3 места 6 чистых задач и одна со второй попытки. Первое место выиграло чисто по количество задач, они смогли пропихнуть задачу Е за 10 минут до конца с 13 попытки. Если быть чуть не успели бы, были бы из-за своих лишних попыток на 8(!) строчке. Причем, можно посмотреть по сколько неверных попыток (на сданных задачах) было у мест 2-7 - 4, 1, 3, 3, 1, 3. После этого тоже будешь говорить, что правильная стратегия - это много слать, просто те, кто выстуают, этого не понимают?
Тем не менее, практически _у_всех_ команд довольно много задач решены не с первой попытки.
Как же твоё правило применяется на практике?
В примерах, оторые даны школьнику, был пример, где n = 50. В случае k = 9 всего 50 значных числе больше, чем 2^166.В условии задачи, насколько я помню, никаких примеров не было... Как раз это и удивило - что ничего не сказано про порядок n.
И что, там все эти 2^166 выводились?
В любом случае, это не настолько сильно увеличивает потребляемые ресурсы (хотя да, надо погеморроиться с написанием всего этого 2^166 - это всего лишь три int64.
Итоговый твой ответ есть (k+1)^n (а не k^n, здесь у тебя тоже ошибка)Это не ошибка, это издержки написания решения на бумаге/в форуме
Идея-то понятна.Я знал об этой ошибке ещё тогда, когда писал; просто я уже сам запутался, что означает k - систему счисления или самую большую цифру, а условия под рукой не было.
s(0, 1) = s(1, 2) = s(2, 1) = s(3, 1) = 1У тебя опечатка, не s(1, 2 а s(1, 1).
Очередной шаг дает s(0, 2) = s(1, 2) = s(2, 2) = s(3, 2) = 4, s(4, 2) = 3, s(5, 2) = 2, s(6, 2) = 1; остальные 0.А тут у тебя реальная ошибка в подсчётах - впрочем, это из-за моей ошибки в написанном решении, я там впервые стал рассматривать, какой результат без вспомогательных массивов, и криво к нему перешёл.
Вот здесь вот:
Как легко понять, количество x-номеров длины n, начинающихся на цифру d, равно сумме количества (x-d)-номеров и (x+d)-номеров длины n-1 (или только (x+d)-номеров, если x<d)ошибка в переходе (upd: в решении).
Значит, количество x-номеров длины n равно (для простоты - в десятичной системе счисления)
s(x-9, n-1) + s(x-8, n-1) + ... + s(x+9, n-1 где s(a, b) - количество a-номеров длины b, если a>=0, и 0, если a<0
А если считать правильно, по первой фразе - выйдет s(1,2) = 6 (1 номер, начинающийся на 0, 2 номера, начинающиеся на 1, 2 на 2 и 1 на 3).
На самом деле, выходит, s(x, n) = s(x, n-1) + (s(x-1, n-1) + s(x+1, n-1) + s(1-x, n-1 если x != 1) + (s(x+2, n-1) + s(x-2, n-1) + s(2-x, n-1 если x!=2) итд. Вроде бы, так.
Этим и лучше олимпиады по информатике, чем по математике - там тебе дают примеры, и, если твоя программа на них свалится, сразу станет ясно, что в решении критическая ошибка.
Сейчас, к сожалению, не могу посмотреть - так были в условии задачи какие-нибудь примеры, или нет?
На одном из языков, которые разрегены на этой олимпиаде.Там разрешены (по крайней мере, раньше были) паскаль и с++; с++ для меня выглядит очень страшно, а паскаль я забыл давным-давно, и мне его ни писать, ни компилировать нечем.
Могу попробовать на c# написать...
Возможно ты просто не до конца точно описал что хочешь, но, пока, приведенное описание не проходит часть тестов (не знаю сколько)Ммм... можешь дать пример теста? (ок, будем считать, что за неё у меня часть баллов - если не обнаружится, что я действительно тут что-то криво написал)
Ты еще порешай задачки второго дня, обычно он интереснее, чем первый.Порешаю - когда захочется
Все лидеры имеют по 3-4 "чистых" задачи (с первой попытки).Но имеют и грязные задачи; а мне тут говорят, что задача, не сданная с первой попытки - несданная задача.
Первое место выиграло чисто по количество задач, они смогли пропихнуть задачу Е за 10 минут до конца с 13 попыткиКстати, F они пропихнули за 22 минуты до конца, и тоже не с первой попытки
Если быть чуть не успели бы, были бы из-за своих лишних попыток на 8(!) строчке.Если бы они до посинения эту задачу вылизывали, они бы могли тоже её не сдать; причём, потратить на вылизывание времени больше, чем на эти проверки (не штрафного, а реального, физического) и не успеть сделать остальные задачи.
Новая формула выходит такая:
s(x, n) = s(x-k, n-1) + s(x-k+1, n-1) + ... + s(x+k, n-1) если x != 0, то + сумма по всем j: j<=k и x<j s(j-x, n-1)
Тогда для четырёхзначных номеров в системе счисления с основанием 4 (k=3) получаем:
—
s(0, 1) = s(1, 1) = s(2, 1) = s(3, 1) = 1
—
s(0, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) = 4 (это соответствует истине, как легко убедиться)
s(1, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) + s(1, 1) + s(2, 1) = 6 (это тоже верно)
s(2, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) + s(3, 1) = 5 (верно: номера 02, 11, 13, 20, 31).
s(3, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) = 4 (верно, номера 03, 12, 21, 30)
s(4, 2) = s(1, 1) + s(2, 1) + s(3, 1) = 3 (верно, номера 13, 22 и 31)
s(5, 2) = s(2, 1) + s(3, 1) = 2 (верно, номера 23 и 32)
s(6, 2) = s(3, 1) = 1 (верно, номер 33)
—
s(0, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) = 4 + 6 + 5 + 4 = 19
s(1, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) + s(4, 2) + s(1, 2) + s(2, 2) = 19 + 3 + 6 + 5 = 33
s(2, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) + s(4, 2) + s(5, 2) + s(1, 2) = 33 - 5 + 2 = 30
s(3, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) + s(4, 2) + s(5, 2) + s(6, 2) = 30 - 6 + 1 = 25
остальные нас не интересуют, они уже не повлияют на результат
—
s(0, 4) = s(0, 3) + s(1, 3) + s(2, 3) + s(3, 3) = 19 + 33 + 30 + 25 = 107
результат = 256-107 = 149.
Чорд, опять где-то ошибся (или обсчитался надо думать.
s(x, n) = s(x-k, n-1) + s(x-k+1, n-1) + ... + s(x+k, n-1) если x != 0, то + сумма по всем j: j<=k и x<j s(j-x, n-1)
Тогда для четырёхзначных номеров в системе счисления с основанием 4 (k=3) получаем:
—
s(0, 1) = s(1, 1) = s(2, 1) = s(3, 1) = 1
—
s(0, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) = 4 (это соответствует истине, как легко убедиться)
s(1, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) + s(1, 1) + s(2, 1) = 6 (это тоже верно)
s(2, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) + s(3, 1) = 5 (верно: номера 02, 11, 13, 20, 31).
s(3, 2) = s(0, 1) + s(1, 1) + s(2, 1) + s(3, 1) = 4 (верно, номера 03, 12, 21, 30)
s(4, 2) = s(1, 1) + s(2, 1) + s(3, 1) = 3 (верно, номера 13, 22 и 31)
s(5, 2) = s(2, 1) + s(3, 1) = 2 (верно, номера 23 и 32)
s(6, 2) = s(3, 1) = 1 (верно, номер 33)
—
s(0, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) = 4 + 6 + 5 + 4 = 19
s(1, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) + s(4, 2) + s(1, 2) + s(2, 2) = 19 + 3 + 6 + 5 = 33
s(2, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) + s(4, 2) + s(5, 2) + s(1, 2) = 33 - 5 + 2 = 30
s(3, 3) = s(0, 2) + s(1, 2) + s(2, 2) + s(3, 2) + s(4, 2) + s(5, 2) + s(6, 2) = 30 - 6 + 1 = 25
остальные нас не интересуют, они уже не повлияют на результат
—
s(0, 4) = s(0, 3) + s(1, 3) + s(2, 3) + s(3, 3) = 19 + 33 + 30 + 25 = 107
результат = 256-107 = 149.
Чорд, опять где-то ошибся (или обсчитался надо думать.
Чорд, опять где-то ошибся (или обсчитался надо думать.
Да забей, чо, ты ж уже всё понял как решать, задачи простые и неинтересные, зачем напрягаться?
Если бы там принимали не программы, а туманные текстовые описания алгоритмов, не обращая внимания на мелкие недочёты и неточности, то ты наверняка занял бы первое место! Поздравляю!
Нашёл ошибку - например, в s(1, 3) я посчитал 111 дважды - в рамках s(0, 2) и в рамках s(2, 2)
Это полностью разрушает всё моё решение, чтобы избавиться от подобных дублей (например, 112 для s(2, 3) тоже будет посчитано дважды придётся всё усложнять, до квадратичной, наверное, сложности (по крайней мере, это первое, что пришло мне в голову).
Или каким-то образом с этим бороться. Пока что идея такая - похоже, сейчас мы считаем в s(x, n) номер d**** столько раз, сколько в этот d**** входит счастливых номеров с участием d. Значит, возможно, если вычесть из получившегося s(x, n) s(0, n-1) (и будем учитывать в s(x, n) некоторые те слагаемые, которые сейчас отбрасываем то выйдет правильный ответ.
Это полностью разрушает всё моё решение, чтобы избавиться от подобных дублей (например, 112 для s(2, 3) тоже будет посчитано дважды придётся всё усложнять, до квадратичной, наверное, сложности (по крайней мере, это первое, что пришло мне в голову).
Или каким-то образом с этим бороться. Пока что идея такая - похоже, сейчас мы считаем в s(x, n) номер d**** столько раз, сколько в этот d**** входит счастливых номеров с участием d. Значит, возможно, если вычесть из получившегося s(x, n) s(0, n-1) (и будем учитывать в s(x, n) некоторые те слагаемые, которые сейчас отбрасываем то выйдет правильный ответ.
Нифига, третья задача оказалась хитрее, чем я думал.
Там разрешены (по крайней мере, раньше были) паскаль и с++; с++ для меня выглядит очень страшно, а паскаль я забыл давным-давно, и мне его ни писать, ни компилировать нечем.слив засчитан
думаю, шансы на третий диплом (если бы ты не ленился писать, что придумал) у тебя естьНет, диплом третьей степени - это неинтересно
Короче, хуй знает, как её решать, ещё за полчаса вообще ничего приемлемого придумать не удалось. Беру свои слова про три задачи назад, пока что у меня готово только полторы задачи (первая - пока мне тут не дадут тесты, на которых она валится, очень интересно, это у меня баг в решении или в его записи; и вторая - до конца не додумана).
итого: у тебя есть полторы задачи за 2 (!) дня
У него была бы одна задача, если бы он ее реализовал и показал, что она работает на тестах. А пока 0 задач за два дня.
итого: у тебя есть полторы задачи за 2 (!) дняЗа два часа.
Я не на олимпиаде, и я почти все эти два дня занимался совершенно другими делами, а об этих задачах и не думал
Час был потрачен в пятницу на то, чтобы найти решения для трёх задач (для первой и третьей - полные, для второй - только идеи). И ещё час был потрачен сегодня на то, чтобы ещё подумать над третьей задачей, когда появились примеры (сейчас посмотрел - они действительно есть в условии, странно, что я их не заметил - потому что меня как раз удивило, что ни ограничений, ни примеров там не было) и понять, что моё решение не подходит.
Ммм... можешь дать пример теста? (ок, будем считать, что за неё у меня часть баллов - если не обнаружится, что я действительно тут что-то криво написал)
В этом предложении ты подразумевал следующее?
Затем (тут уже понадобится одно число int64) идём по получившемуся массиву, для каждого его элемента, если он больше единицы, добавляем к результату (который исходно был нулём) x*(x-1)/2, где x - этот элемент. Выводим результат.
int64 sum = 0;
for (int i = -n; i <= n; ++i) {
sum += cnt[i]*(cnt[i]-1)/2;
}
int64 sum = 0;Вроде бы, да. Правда, я бы добавил там ещё и условие if(cnt[i]>1 но это значения не имеет.
for (int i = -n; i <= n; ++i) {
sum += cnt[i]*(cnt[i]-1)/2;
}
Вот здесь бы и нашлась ошибка, но не сразу, а только после сдачи. У тебя переполнение int наступит в момент
а не вовремся суммирования в sum. Правильно это умножение уже в int64 делать. Об этом у тебя не было ни слова, да и с кодом ты согласился.
cnt[i]*(cnt[i]-1)/2
а не вовремся суммирования в sum. Правильно это умножение уже в int64 делать. Об этом у тебя не было ни слова, да и с кодом ты согласился.
Да, ты прав.
Я не настолько хорошо разбираюсь в низкоуровневых вещах, чтобы понять, что умножение тоже будет производиться в int32.
То есть, я завалил бы все тесты, в которых в массиве cnt где-нибудь встречаются элементы больше ~45к. Чорд.
Хотя существует ненулевая вероятность того, что во время проверки своей задачи я бы её проверял не только на тех тестах, которые в условии, но и на самописных - вроде полумиллиона мальчиков + полумиллиона девочек, идущих подряд, полумиллиона мальчиков+полумиллиона девочек, стоящих ababab...
Я не настолько хорошо разбираюсь в низкоуровневых вещах, чтобы понять, что умножение тоже будет производиться в int32.
То есть, я завалил бы все тесты, в которых в массиве cnt где-нибудь встречаются элементы больше ~45к. Чорд.
Хотя существует ненулевая вероятность того, что во время проверки своей задачи я бы её проверял не только на тех тестах, которые в условии, но и на самописных - вроде полумиллиона мальчиков + полумиллиона девочек, идущих подряд, полумиллиона мальчиков+полумиллиона девочек, стоящих ababab...
Оставить комментарий
kruzer25
Меня тут отец допинал до того, что я всё-таки выделил время и подумал над этими задачками (пока что - только над теми, которые были в первый день)1) Почему все задачи - настолько примитивные?
2) Почему, несмотря на это, их так плохо решают? (Диплом 3 степени даётся за 200 баллов; всего в каждый из двух дней по три задачи, за каждую дают до 100 баллов, то есть, потолок - 600)
Эх, был бы я сейчас в 11 классе, не поехал бы на математику, поехал бы на информатику