Форум Всеукраїнської інтернет-олімпіади NetOI

redman17 написав:

NEWCALC
Возможно я и провтыкал оптимальное решение, но нормально организованый перебор с некоторыми усечениями дает вполне приемлемый результат. Итак:
- будем искать кол-во отдельных цифр в искомом числе, сортировать и выдавать ответ
- легко заметить что тут например цифры 2,3,5,... - это одно и то же кол-во полосок так что их не следует рассматривать отдельно
- если не выполняется 2n<=k<=7n то ответ NO SOLUTION
- аккуратно прописываем минимум - там ноль не может быть в начале
....

2n<=k<=7n - неправильно, если система счисления бьудет меньше 9 то будет не 7n, а меньше)) ну для 8ричной - 6 например)

Cris, +1
Мало того - если система счисления будет меньше 7, то не удастся представить это просто двойным неравенством.
Лично я делал так (проверки "возможности" суммы k из n цифр):
1) Если p>8, 2n<=k<=7n является условием возможности. Иначе:
2) Если p>7, 2n<=k<=6n является условием возможности. Иначе:
3) Если p>4, в нашем разпоряжении есть только 2,4,6,5. Заметим, что любую пару пятерок можно заменить парой 4 и 6, в итоге n и k останутся те же. Отсюда вывод:
если сумма четна и 2n<=k<=6n, то она возможна;
если сумма нечетна, и k>=5, и 2(n-1)<=k-5<=6(n-1), то она возможна;
в противном случае получить невозможно. Иначе:
4) Если p>2, в нашем распоряжении есть только 2,6,5. Каждые четрыре пятерки можно заменить так:
5-5-5-5 = 6-6-6-2
Таким образом сумма возможна, если одну из таких сумм можно составить только с помощью 2 и 6 (см. след. шаг): k, k-5, k-10, k-15. Иначе:
5) Если p=2, в нашем распоряжении только 2 и 6. Очевидно, что сумма возможна если (k-2n) modulo 4 = 0, и 2n<=k<=6n

ух ты какая дискуссия
на самом деле такое неравенство:
- лишь один из критериев отсечения заведомо тупиковых вариантов
- если обратить внимание на сам код, то можно заметить - массивы amin, amax хранят цифры, которые будут использоваться для построения искомого числа, а minlr, maxlr - границы в столь обсуждаемом неравенстве (например minlr[i] хранит границы для цифр amin[i,2]; amin[i+1,2] ... ; amin[minq;2] /minq - кол-во цифр/)
- эти массивы строятся для каждого конкретного примера самой программой

Ну, що? хтось вже тестував на он-лайні свої проги???

Мене більше цікавить treasure  в кого як зараз?

Я б сказав, шо вона вже 1,5-2год працює )))

Что-то у меня ощущение что тесты на Treasure не верные. В моем решении теоретически могли возникнуть проблемы с точностью и из-за этого мог неверно строиться граф. Я отправил на онлайн проверку решение, которое работает медленнее, но зато там все операции производятся над обычными дробями и погрешности быть не может. Тем не менее, есть 4 теста, где WA.

ZuTa
Ну шо, ти вже протестив свої розвязки?

fdg
ага....2 задачі підвели трохи....не очікував шо буде ВА
В тебе скільки балів?

Я назбирав 50 + 42 + 60 + 57 + 42 = 251
В перших 2 задачах по часу не попроходило (це я очікував)
Тетріс пройшла...
Стреамер хз 1 тест не пройшов ВА
Треасуре 6 ВА

Та ні, нічого не добавилось....в мене такий же резалт

Я б не сказав що вона одна з самих простих....

Darkslide написав:

А мне обидно.... За тетрис у меня 39 баллов.... Я написал решение, сделал онлайн проверку, прогнав на ней вхолостую на макстесте - получил время 0.01... И успокоился. Мог, мог же отправить константами! Одна из самых простых задач, тем более что можно забить константы.... А кто виноват - разве что сам.... Обидно!

Гірше коли, виходить як http://forum.olymp.vinnica.ua/viewtopic.php?id=227, і всього на всього тому, що форум не читаю.... втратив на 4й задачі 15, а на 5й ще більше - десь балів 15-25, здається. При тому, що при іншому виводі працює правильно на всі 60....

ZuTa написав:

Я б не сказав що вона одна з самих простих....

Ну, а, що там її писати? Проста динаміка по краю з довгою арифметикою)) На с++ пищеться за 15 хвилин)

десь 7го числа.