Шестая личная интернет-олимпиада

12 лет назад, # |

+10

Будут ли токены? Всем удачи.

→ Ответить

12 лет назад, # ^ |

Нет, токенов пока не будет. Веб-клиент не поддерживает эту возможность.

→ Ответить

12 лет назад, # ^ |

А почему? На втором отборочном ИОИП они вроде же были

→ Ответить

12 лет назад, # ^ |

не было

→ Ответить

Gassa

12 лет назад, # |

А можно ли где-то видеть текущие результаты? По ссылкам today мониторы месячной давности.

→ Ответить

12 лет назад, # ^ |

+11

Текущих результатов нет, поскольку баллы объявляются по окончании тура.

→ Ответить

12 лет назад, # |

+14

Кто-нибудь может пояснить 1ый сэмпл задачи В?

Письмо жюри отправил, но они так и не ответили (прошло около получаса).

→ Ответить

Sereja

12 лет назад, # ^ |

Аналогичный вопрос. Тоже отправил вопрос жюри. По идеи ответ 12 9 6 должен быть. Если следовать условию.

→ Ответить

Belonogov

12 лет назад, # ^ |

я тоже не понимаю его, и тоже отправил письмо, и тоже не получил ответа.

по идеи там должно быть 12 9 6?

→ Ответить

12 лет назад, # ^ |

Вроде да.

Либо условие написано слишком плохо, либо неправильный сэмпл.

→ Ответить

12 лет назад, # ^ |

← Rev. 3 →

-8

Я так понимаю, составляя семпл решили, что быстрее = больше времени

→ Ответить

12 лет назад, # ^ |

Это ж совсем глупо.

→ Ответить

12 лет назад, # ^ |

-10

В том и дело. Я как-то сразу не обратил внимания, больше на семпл смотрел, а не на условие. Интересно, как они это исправят, полтора часа контеста прошло.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

-9

/* Тут должна быть традиционная для CF в таких случаях шутка про unrated раунд */

→ Ответить

randrew

12 лет назад, # |

Ну что там слышно? Жюри ответа не дали?

→ Ответить

12 лет назад, # ^ |

Нет, не дали.

→ Ответить

randrew

12 лет назад, # |

17:44 В задаче B (Спутник), ответ в первом примере "12 9 6". Решения будут перетестированы.

→ Ответить

12 лет назад, # |

+14

Задача B (Спутник): Ошибка в тесте из условия была. Условия и тест в системе исправлены. Решения перетестированы. Результаты проверки присланы заново. Не забудьте, что будут проверятся только принятые на проверку решения.

Приносим извинения за задержку в исправлении ошибки и ответах на письма.

→ Ответить

12 лет назад, # |

Как решать С?

→ Ответить

12 лет назад, # ^ |

-6

я решал так: найдем последнее число, которое полностью лежит в этом отрезке и для него посчитаем динамику dp[длина числа][сколько пар нулей][чем кончается][превысил префикс числа префикс найденного нами числа]

ну еще надо учесть, что после последнего числа остается какой то небольшой хвост и его надо отдельно проверить

для 10⁷ работает

→ Ответить

pavel.savchenkov

12 лет назад, # ^ |

← Rev. 2 →

Я нашёл число, на котором последовательность обрывается, затем динамика:
d[len][k][last][gr] — сколько двоичных чисел (без 2-х единиц подряд) длины len,имеющих k парных нулей, последний символ last и меньше, больше или равно префикса граничного числа длины len.
UPD: у меня решение палёное или все просто так минусуют? :)

→ Ответить

12 лет назад, # ^ |

забей

→ Ответить

Vaness

12 лет назад, # ^ |

-6

Схематично расскажу. Заметим, что имеет смысл посчитать количество таких пар только в каждом числе отдельно.

Теперь собственно решение: 1) Находим номер последнего числа, которое целиком влезло в строку 2) Для каждой длины(в фибоначчиевой системе счисления) насчитаем динамику — сколько таких пар существует среди чисел с такой длиной(и меньших последнего). Это вроде стандартная динамика.

→ Ответить

12 лет назад, # ^ |

Для кого стандартная, а для кого — не очень :)

→ Ответить

12 лет назад, # ^ |

+17

Какая-то не очень динамика — на 8 баллов всего.

→ Ответить

Vaness

12 лет назад, # ^ |

Увы :(

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

у меня дп немного другое

pair<long long, long long> dp[len][last(0,1)][flag]

flag — это boolean, если текущее число меньше или равно последнего числа, которое полностью входит в нашу часть в динамике два значения — количество нулей и количество таких чисел

→ Ответить

12 лет назад, # ^ |

по сути своей, все вышеприведенные решения — одно и тоже

→ Ответить

12 лет назад, # ^ |

Покажи пожалуйста код

→ Ответить

pavel.savchenkov

12 лет назад, # ^ |

Вот мой код

→ Ответить

12 лет назад, # |

И D тоже неплохо рассказать было бы :)

→ Ответить

12 лет назад, # |

мне одному не понравилось, что задача С была почти такая же, как и на предыдущей тренировке?

→ Ответить

12 лет назад, # ^ |

Мне тоже не понравилось.

На предыдущей она попроще была, разве что.

→ Ответить

kostya_by

12 лет назад, # ^ |

они разные, но мне кажется неправильным на 3/5 индивидуальных контестах на задачу С ставить ДП по разрядам. есть же еще другие темы.

→ Ответить

12 лет назад, # ^ |

Какое ДП по разрядам? Десять минут посливать суммы чисел Фиббоначчи в единую формулу плюс пять минут на написание тащит! :-)

→ Ответить

Rubanenko

12 лет назад, # ^ |

А пару контестов назад была еще одна задача из цикла "написать дп по цифрам"...

→ Ответить

ioanisyan

12 лет назад, # |

A когда будут доступны результаты ?

→ Ответить

witua

12 лет назад, # ^ |

надеюсь не так как в прошлый раз

→ Ответить

12 лет назад, # ^ |

Обычно, это 2-3 часа.

Правда, один раз они были доступны через 5 минут после окончания тура.

→ Ответить

12 лет назад, # ^ |

+21

Это зависит от разных причин. На некоторых олимпиадах отключается тестирование на всех тестах во время тура, на некоторых сервера вполне справляются. Сегодня была отключена только задача D — вот она сейчас и дотестируется.

К сожалению, иногда нету физической возможности сразу выложить результаты на сайт...

→ Ответить

12 лет назад, # ^ |

можно следить за тестрирование в клиенте

→ Ответить

Aganov

12 лет назад, # |

в D проходит сначала жадно передвигать меч по прямой, а потом пересекать окружности? P.S. у меня в задаче С в одной функции был int, вместо long long, а я все понять не мог, из-за чего у меня TLится на 10^10, обнаружил это через 5 минут после окончания контеста, с исправленным багом работает на макс тестах...

→ Ответить

fdoer

12 лет назад, # ^ |

казалось бы, лучше сначала найти нужную точку на окружности вокруг конечной точки, а затем жадно двигаться уже к ней

→ Ответить

12 лет назад, # ^ |

а как ее найти?

→ Ответить

fdoer

12 лет назад, # ^ |

Ну, я делал так: мы хотим сначала сколько-то раз передвигать нашу точку по прямой — в сумме на расстояние n * segmentLength, а затем один раз передвинуть на segmentLength уже в конечную точку. Также мы знаем расстояние d между начальной и конечной точками. Отсюда n ≈ [d / segmentLength] Теперь можно по теореме косинусов найти угол между вектором (начальная-конечная) и вектором (начальная-промежуточная). Зная угол и длину вектора, находим промежуточную.

→ Ответить

12 лет назад, # ^ |

насколько я понял, вы сначала вычисляете это точку, а потом двигаете к ней, но тогда не пойму, чем это лучше того чтобы двигать точку и походу смотреть, можем мы достигнуть из нашей текущей токчи конечную точку?

→ Ответить

fdoer

12 лет назад, # ^ |

Пусть Вы, преодолев расстояние n * segmentLength, обнаруживаете, что расстояние до конечной меньше segmentLength (я ведь правильно понял, какую проверку Вы имеете в виду?). Тогда теперь Вам нужно сделать как минимум два перемещения: на окружность и с окружности в центр. Но первого из этих перемещений можно избежать, если с самого начала двигаться в удобную нам точку на окружности. Такая точка, достижимая из начальной за n шагов существует всегда, т.к. за n шагов можно оказаться даже внутри окружности.

→ Ответить

12 лет назад, # ^ |

ах да! спасибо

→ Ответить

12 лет назад, # |

На чем можно было слить А?

→ Ответить

12 лет назад, # ^ |

на лонгах, на даблах, не?

→ Ответить

12 лет назад, # ^ |

Возможно. Обидно, блин.

→ Ответить

12 лет назад, # ^ |

а можете описать, как надо было делать? Просто у меня 0, это толкает меня на мысль, что я не правильно понял условие

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

Находим $\text{[math]}$ . Теперь нам нужно найти подарок с минимально возможной стоимостью большей либо равной х. b вообще было не нужно.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

А нет, я нашел багу. Оказывается в одном месте опечатался, стоило сотни, печально

→ Ответить

12 лет назад, # ^ |

вы бы код показали

→ Ответить

12 лет назад, # ^ |

нам задана стоимость основного товара, к нему надо выбрать подарочный товар, но при этом стоимость выбранного товара не должна быть меньше a процентов основного и не больше b процентов, при этом, если таких товаров несколько, надо выбрать товар с минимальной стоимостью

то есть пусть цена основного товара x, а товара, который мы ищем y, тогда должно выполняться $\text{[math]}$ иначе говоря ax ≤ 100y ≤ bx ну тут надо не забыть про то что цены до 10⁹ и поставить long long

вот код

P.S. объясняю и чувствую себя идиотом — разжевывыю какую-то элементарность

→ Ответить

12 лет назад, # ^ |

спасибо за объяснения, все таки дело было не в понимании

→ Ответить

12 лет назад, # |

Результаты выложены на сайте.

→ Ответить

12 лет назад, # |

Как? Нет, как я умудрился набрать сорок по первой? И ведь я даже не знаю, в чём баг — нет доступа к решению.

→ Ответить

Rubanenko

12 лет назад, # ^ |

я вместо "continue" — "break" поставил, норм чё)

→ Ответить

Sereja

12 лет назад, # ^ |

← Rev. 2 →

Скорее всего лонг лонг забыл, если 40 набрал.

Кстати, я тебя понимаю. На одном недавнем нирке тоже слетел на халяве при всех остальных решенных :)

→ Ответить

12 лет назад, # ^ |

Не-а, не забыл. Блин, вот бы код ещё раз посмотреть. А вот нет доступа. Веселуха, в общем)

→ Ответить

Sereja

12 лет назад, # ^ |

Скорее всего именно на каких-нибудь переполнениях, иначе почему именно ровно 40(которые в условии указаны)?

→ Ответить

12 лет назад, # ^ |

ХЗ, так, наверное, и есть. Ладно, хрен с ним) Не такая высокая птица, чтобы париться о ней)

→ Ответить

12 лет назад, # |

Такой вопрос еще, почему у меня в С 40? вот код, на локальной машине все проходит. Код я не менял, только дебаг комменты убрал, чтобы легче читалось.

Может ли это быть из-за того, что я не правильно вывожу лонги?

→ Ответить

pavel.savchenkov

12 лет назад, # ^ |

Да) Поменял на cin и cout , прошло все тесты.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

значит фигня с

#ifdef WIN
use I64d
#else
use lld
#endif

не пашет? Вообще какая переменная точно определяет виндовс машину от других? Я видел несколько вариантов, но не пойму, какие правильные, а какие из головы: WIN, WIN32, _WIN_, __WIN__, __WIN32__, DOS...

→ Ответить

12 лет назад, # ^ |

← Rev. 3 →

В MinGW работают эти: WIN32, __WIN32__, _WIN32_ И вообще, лучше писать так, чтобы сразу получить CE:

#ifdef _WIN32_
use I64d here
#elif linux
use lld here
#else
#error Invalid OS...
#endif

У меня в шаблоне сделано так:

#ifdef _WIN32_
#define LLD "%I64d"
#elif linux
#define LLD "%d"
#else
#error Invalid OS...
#endif
// ... some code ...
printf("Hello World! Int=%d, LL=" LLD "! :)\n", 123, 123ll);

Знай и люби особенности своего языка программирования и его компиляторов.

→ Ответить

fetetriste

12 лет назад, # ^ |

я бы не стал призывать любить неудачные решения в дизайне

→ Ответить

12 лет назад, # ^ |

Ну не портить же цитату :)

→ Ответить

12 лет назад, # |

+20

Вообще, честно говоря, проблемсет не понравился. Не было ничего, где нужно хоть сколько-нибудь подумать — сиди себе и пиши боянистые задачи. Не говорю про первые две незадачи, C — 42 раза сверни формулу с числами Фиббоначчи/напиши динамику за логарифм в произвольной степени/сделай чё угодно, D — классический боянчик про кратчайшую ломаную. Беее.

→ Ответить

12 лет назад, # ^ |

Все хорошие задачи копятся на серьезные олимпиады :) А вообще, Макс, со временем около 90% школьных задач становятся боянистыми...

→ Ответить

12 лет назад, # ^ |

Вот неожиданность-то :-) Я имел в виду, в сравнении с остальными школьно-нерковыми турами этот получился слишком боянистый. От остальных как-то такого гнетущего ощущения не оставалось.

→ Ответить

12 лет назад, # ^ |

Что-то никто кроме тебя, этот "D — классический боянчик" не смог написать на 100. Может расскажешь как?

→ Ответить

12 лет назад, # ^ |

Ну, переформулируем задачу так: нам нужно найти кратчайшую ломаную из отрезков длины l, которая содержит отрезки u и v в качестве звеньев. Кратчайшую в смысле количества звеньев.
Заметим, что отрезки u и v должны быть крайними. Значит можно перебрать от какого из концов отрезка u до какого из концов отрезка v будет идти наша ломаная. Теперь осталось научиться строить кратчайшую ломаную между двумя точкам A и B.
Разберём руками два вырожденных случая — когда A и B совпадают, ломаная будет нулевой и получается два варианта — если отрезки u и v совпадали (мне кажется, все, у кого 98, посеяли именно этот случай), то итоговая ломаная будет из одного звена, если же они только имели общий конец, то получается ломаная из двух звеньев. В противном случае — |AB| ≠ 0. Утверждение. Кратчайшая ломаная будет содержать $\text{[math]}$ звена. Как это понять? Если $\text{[math]}$ , то очевидно, что кратчайшая ломаная как раз разбивает AB на k таких отрезков. Если же |AB| не кратно l, то мы либо откусываем отрезок длины l От отрезка AB, либо, если |AB| < 2l, строим два отрезка длины l, образующих равнобедренный треугольник с AB в основании. Легко доказать, что такая ломаная будет кратчайшей.
Победа.

→ Ответить

de_troit

12 лет назад, # |

Может кто-нибудь показать пример кода (на с++) как вводить с getline в цикле ?

→ Ответить

12 лет назад, # ^ |

for (int i=0;i<n;i++){ 
   getline(cin,s);
   getline(cin,s);
   cin>>x;
   // do something with s
}

Так у меня выглядела первая задача. Вводим s 2 раза, т.к. в первый раз она считает только символ перевода строки.

→ Ответить

Sultan

12 лет назад, # ^ |

← Rev. 2 →

Не плодите говнокод, чтобы этого символа не было надо очищать поток перед чтением:

fflush(stdin);

или же считывать после чисел пробелы и переводы строки через scanf("%d%*c", &n);

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

В некоторых случаях ~~Ваш код~~ код вида scanf("%d ") становится говнокодом. Например, представьте себе, что произойдёт, если строка для считывания содержит пробелы. Например:

123456
  <<spaces here and there>>

Правильно — пробелы в начале строки не считаются, что довольно трудно поймать, если об этом отдельно не подумать.

А про очистку потока я вообще не понял. scanf("%d") читает ровно одно число и еще один символ после (который, вроде как, загоняет обратно при помощи ungetc или как-то так). Поэтому перевод строки несчитанным останется, чтобы мы там с буфером не делали.

→ Ответить

Sultan

12 лет назад, # ^ |

← Rev. 2 →

1)Согласен, о пробелах я не подумал.

2) Я когда-то очень долго не понимал, что происходит после чтения строки, но после экспериментов я пришел к этим двум способам. Очистка потока уберет все лишние символы(да, не всегда хорошо), scanf("%d%*c") считает число и ТОЧНО считает еще один символ после, т.е. перевод строки, а scanf("%d") скорее всего прямолинеен и считывать только число и ничего больше.

→ Ответить