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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2009-01-21 21:10:23

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

redman17 написав:

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

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

Поза форумом

 

#27 2009-01-21 21:17:08

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

згоден з Cris

Поза форумом

 

#28 2009-01-21 21:41:36

Darkslide
Новий користувач
Звідки: м. Київ
Зареєстрований: 2007-10-26
Повідомлень: 27

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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


Everything simple is genious, everything genious is simple.

Поза форумом

 

#29 2009-01-21 21:43:03

Брэнд
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2007-09-30
Повідомлень: 44

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Кстати, это не единственный случай для NO SOLUTION. Пример 3 8 2.

Поза форумом

 

#30 2009-01-21 21:53:35

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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


WE DIE HARD!!!

Поза форумом

 

#31 2009-01-22 14:37:19

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

ZuTa написав:

лампплюс писав динаміку...але трохи погано її оптимізував...не думаю шо набере повний бал(ТЛЕ)

Я також писав динаміку, для n=50 k=100 працює 2,5 с


Let arriving night explain,
Day fade I remain

Поза форумом

 

#32 2009-01-22 14:40:04

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

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

Поза форумом

 

#33 2009-01-22 14:45:04

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Вже працює on-line перевірка


Let arriving night explain,
Day fade I remain

Поза форумом

 

#34 2009-01-22 14:46:05

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

#35 2009-01-22 14:47:12

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

fdg
В тебе treasure  пройшла все?

Поза форумом

 

#36 2009-01-22 16:09:51

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

#37 2009-01-22 16:32:32

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

ZuTa написав:

fdg
В тебе treasure  пройшла все?

В мене 18 балів


Let arriving night explain,
Day fade I remain

Поза форумом

 

#38 2009-01-22 17:16:41

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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


Let arriving night explain,
Day fade I remain

Поза форумом

 

#39 2009-01-22 17:18:20

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

kadr
Згоден...дуже підозріло....але в мене 6 тестів ВА... sad
Хоча розв"язок задачі очевидний...

Поза форумом

 

#40 2009-01-22 17:19:38

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

#41 2009-01-22 17:21:08

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

ZuTa
У мене 187, а в тебе як?


Let arriving night explain,
Day fade I remain

Поза форумом

 

#42 2009-01-22 17:27:42

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

#43 2009-01-22 17:35:07

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Я тікишо перепровірив, то
43+33+60+39+39=214
По-моєму там добавились тести.


Let arriving night explain,
Day fade I remain

Поза форумом

 

#44 2009-01-22 17:41:21

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

#45 2009-01-22 17:53:10

Uran
Новий користувач
Зареєстрований: 2008-12-04
Повідомлень: 4

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

60+60+60+57+54=291
Здається хтось інтригу береже

Поза форумом

 

#46 2009-01-22 19:06:29

ZuTa
Новий користувач
Зареєстрований: 2007-09-30
Повідомлень: 90
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

#47 2009-01-22 19:17:13

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Мені здавалось, що тетріс найскладніша задача, поки не придумав досить простий розвязок.


Let arriving night explain,
Day fade I remain

Поза форумом

 

#48 2009-01-22 19:20:38

TheEvilOfTheDay
Новий користувач
Звідки: Подалі від Київського Лідеру..
Зареєстрований: 2008-11-29
Повідомлень: 12
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Darkslide написав:

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

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

ZuTa написав:

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

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

Поза форумом

 

#49 2009-01-22 19:22:12

fdg
Новий користувач
Зареєстрований: 2006-11-16
Повідомлень: 33

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Ніхто незнає, коли приблизно буде 4 тур?


Let arriving night explain,
Day fade I remain

Поза форумом

 

#50 2009-01-22 19:25:51

TheEvilOfTheDay
Новий користувач
Звідки: Подалі від Київського Лідеру..
Зареєстрований: 2008-11-29
Повідомлень: 12
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

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

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt