| Автор |
1071 |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 20-02-2008 18:17 |
|
|
Див.: http://acm.timus.ru/problem.aspx?space=1&num=1073
No pasaran !!! |
     
|
| Автор |
RE: 1071 |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 21-02-2008 10:41 |
|
|
Yup Тільки обмеження строгіші...
Pascal not dead! |
|
|
| Автор |
RE: 1071 |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 21-02-2008 20:21 |
|
|
ibm написав:
Yup Тільки обмеження строгіші...
Ага, як у нас на ваші "Кольорові вежі"...
No pasaran !!! |
|
|
| Автор |
RE: 1071 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 26-04-2009 20:09 |
|
|
Кому смішно з обмежень варіанту 1073 - гляньте на "1593. Квадратная страна. Версия 2" - там "В единственной строке стоит положительное число N ? 1015 — число квадриков, которое было у жителя." (10 в 15ому)  оце вже серйозніші обмеження |
|
|
| Автор |
RE: 1071 |
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09 |
| Опубліковано 08-02-2011 10:04 |
|
|
Шановні адміністратори, поясніть , будь ласка, чому мій розв*язок дає ТЛ?! Ідейно, він би мав проходити, чи не так?
http://acm.lviv.ua/fusion/viewpage.php?page_id=12&SubmitID=107119
|
|
|
| Автор |
RE: 1071 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 08-02-2011 14:53 |
|
|
CUPIDON, я аж здивувався з потужності тестувалки, проходить)
О(N), як в тебе, працює 0.187 з коренями і 0.125 без них
(сабміти 107155 і
107154). А твоя проблема в неправильному переборі)))
З.І. Оптимальний розв'язок задачі - O(N^(1/3)).
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: 1071 |
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09 |
| Опубліковано 08-02-2011 16:52 |
|
|
|
LeBron написав:
CUPIDON, я аж здивувався з потужності тестувалки, проходить)
О(N), як в тебе, працює 0.187 з коренями і 0.125 без них
(сабміти 107155 і
107154). А твоя проблема в неправильному переборі)))
З.І. Оптимальний розв'язок задачі - O(N^(1/3)).
Шо за брєд, який ще оптимальний?! По-моєму, оптимальний - це не той який працює найшвидше, а той в якого (ефективність)/(реалізація) найменша, нє?!
А шо тут дивуватись?! То ж О(10^7), воно МАЄ проходити.
Шо ти маєш на увазі під "неправильний перебір"?!
|
|
|
| Автор |
RE: 1071 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 08-02-2011 19:18 |
|
|
|
CUPIDON написав:
[quote]LeBron написав:
Шо за брєд, який ще оптимальний?! По-моєму, оптимальний - це не той який працює найшвидше, а той в якого (ефективність)/(реалізація) найменша, нє?!
А шо тут дивуватись?! То ж О(10^7), воно МАЄ проходити.
Шо ти маєш на увазі під "неправильний перебір"?!
Ну тоді за корінь назвем оптимальним))))
Він і пишеться не довше цього, так що там відношення краще точно)))
О(10^7) - цим позначенням ти мене вбив Так недалеко й до О(1). Просто в твому коді багато "зайвого" в плані обчислень, тобто кожна ітерація явно потужніша за додавання двох чисел)
Неправильний перебір - значить, неправильний перебір. Адміністрація не зобов'язана за учасників задачі розв'язувати) В тебе в переборі вискакують такі групи чисел, котрі не задовольняють умову (тобто ти пробуєш скласти число не так, як це дозволено умовою).
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
| Автор |
RE: 1071 |
cupidon4uk
Користувач
Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09 |
| Опубліковано 08-02-2011 20:00 |
|
|
здав. за корінь з N. Але не розумію чому воно так працює. Знайшов на форумі тімуса підказку, шо:
N is NOT a sum of 3 squares <=> N=(8k+7)*4^m
Так а хтось можу пояснити чому це дійсно так?
І ше я не розумію, де я робив "неправильний перебір". Може тепер поясниш, коли в мене і так АС ?
|
|
|
| Автор |
RE: 1071 |
LeBron
Головний Адміністратор
Повідомлень: 704
Звідки: ЛНУ
Зареєстрований: 10.02.09 |
| Опубліковано 08-02-2011 20:30 |
|
|
В тебе був навіть не "кривий перебір", а дещо взагалі незрозуміле
Погано поставлені межі перебору, тому у випадку трьох квадратів ти третім числом ставив корінь з від'ємного числа.
А з приводу підказки - це прямий наслідок об'єднання загальної форми теореми Лагранжа (вірніше, її доведення) та часткового випадку, який довів Лежандр ще десь так років 200 тому в своїй "Теорії чисел".
Якщо треба деталі - погугліть, я можу спробувати коротко написати тут доведення, але Лагранж з Лежандром зробили це до мене в загальних рисах, добрі люди потім об'єднали і оформили, так що не буду плагіатом займатись.
Так як даний факт провіряється за логарифм, чи є одним квадратом - обчислюється умовно за логарифм в кубі(ніколи не цікавився в деталях, як машинно... Там іще швидше; а вручну без вищої математики - за логарифм в кубі), то найвужче місце - чи є сумою 2 квадратів. Там нічого краще кубічного кореня поки не придумали.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом. |
|
|
Birthday(s):
