| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Why my idea is wrong? | Shohruh | 1807. Патроны для Максима | 16 авг 2022 17:54 | 2 |
When n>10 is a prime, i am writing n=k*3+l*2, where l=1,2 or 3 depending whether n mod 3 = 1 2 or 0. Then I get lcm=3^k*2^l, which is the maximal with respect to all possible divisions of n. However, my program gives WA6. Am I correct?
Thanks! Clearly the lcm of k 3's and l 2's is at most 6 -- you are asked the lcm of them, not the product of them. |
| WA 19 | Md sabbir Rahman | 1807. Патроны для Максима | 23 ноя 2018 01:25 | 2 |
WA 19 Md sabbir Rahman 22 ноя 2018 22:39 Can anyone please tell me what's in test 19? please? Btw I just checked the LCMs of all numbers from 1 to 31607 using OEIS and they matched, soI have no idea where the error is. |
| WA7 | luckysundog | 1807. Патроны для Максима | 5 дек 2013 16:40 | 2 |
WA7 luckysundog 21 окт 2011 15:40 Please write answer for N = 169, 841, 674041. ALSO WA7, who give more test? |
| I got ac.But it's clearly that I'm wrong. | neko13 | 1807. Патроны для Максима | 9 авг 2013 01:21 | 2 |
My ac program print only 500 when n=625.
I think the test number is not good enough. I'm sorry.I use the wrong project. |
| Give me a hint, I AC this using preprocessing | monyura[ONU 1 2/3] | 1807. Патроны для Максима | 7 авг 2013 22:25 | 8 |
I use Dynamics that originally need 31607*3400 operation for input 31607*31607, but when I notice that only first 114 prime numbers uses, and only first 8 of them with power more than 1, I reduce operation count to 200*31607. BTW it works smth about 3 sec. So I use preprocessing to solve it. Does exist another algorithm, or I need to optimize this one? (I think people, who ac this problem, guess algorithm by it complexity) Maybe that can help someone to solve...
/*
* Firstly note that according to the problem statement N is composite.
* Then find smallest divisor M that N%M == 0 and let G = M/N.
* Now we can factorize N as N = G*M = G*(a1 + a2 + ...) and consider
* values G*a[i], gcd(G*a1, G*a2, ...) == G as the answer. Those values
* will have the largest GCD. It can be easily proved that to maximize
* LCM all a[i] must be coprime and be of the form prime^k.
* Use dp to find such partition...
*/ But when N~ 10^9 and N - is prime number, than smalles divisor M = N, and G = N/M = 1.
a[1] + a[2] + ...a[k] = M ~10^9 . how do use DP? N cannot be a prime number, it's always composite. Read the statement carefully
> each box contained at least one hundred cartridges.
> Anka noticed that there was the same number of cartridges in all boxes
maybe it will be more correct to replace "in all boxes" with "in each box"?
Edited by author 11.02.2012 17:56
Edited by author 28.02.2012 20:32 N cannot be a prime number, it's always composite. Read the statement carefully
> each box contained at least one hundred cartridges.
> Anka noticed that there was the same number of cartridges in all boxes
maybe it will be more correct to replace "in all boxes" with "in each box"?
Edited by author 11.02.2012 17:56 Thank you!!!!!!!!!! Hovewer, if M - is smalles divisor of N, than 1 < M < 31623 ! I Ac, with 0.046 s !! Edited by author 28.02.2012 22:19 Edited by author 28.02.2012 22:19Could you give me some hints about how to breakup a prime as m=a1+a2+a3... so that lcm(a1,a2,a3,...) is biggest? |
| 197*197 | Alexandr172 | 1807. Патроны для Максима | 7 авг 2013 22:21 | 4 |
197*197 Alexandr172 3 май 2012 21:27 Please, write solve for N = 197*197...
My result: 1576 1773 4925 1379 2167 2561 3349 3743 4531 5713 6107 197 197 197 197 197 Can you give me some hints about how to breakup a prime as m=a1+a2+a3... so that lcm(a1,a2,a3,...) is biggest? Can you give me some hints about how to breakup a prime as m=a1+a2+a3... so that lcm(a1,a2,a3,...) is biggest? |
| WA31 | Alexandr172 | 1807. Патроны для Максима | 23 май 2012 18:58 | 2 |
WA31 Alexandr172 6 май 2012 22:31 |
| Need help | bsu.mmf.team | 1807. Патроны для Максима | 2 ноя 2010 19:57 | 3 |
Please, write somebody full answer for N = 994009. My AC program outputs:
88733 78763 72781 70787 66799 60817 58823 52841 46859 42871 40877 36889 30907 28913 22931 18943 16949 12961 10967 48853 24925 26919 31904 997
LCM = 1438976816627817242848511727497751141600 |
| AC, but I think my solution is wrong | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1807. Патроны для Максима | 2 ноя 2010 17:41 | 6 |
This test: 900660121
My solution printed 30011 30011 30011 510187 570209 690253 870319 930341 1110407 1230451 1290473 1410517 1470539 1590583 1770649 1830671 2010737 2130781 2190803 2370869 2430891 2490913 2670979 2911067 3031111 3091133 3211177 3271199 3391243 3631331 3751375 3811397 3841408 3931441 4111507 4171529 4471639 4531661 4711727 4891793 5011837 5071859 5191903 5371969 5431991 5732101 5792123 5912167 5972189 6332321 6692453 6812497 6872519 6992563 7172629 7232651 7532761 7712827 7892893 8072959 8132981 8313047 8433091 8493113 8793223 9213377 9333421 9393443 9513487 9933641 10113707 10413817 10473839 10593883 10773949 11014037 11194103 11374169 11494213 11674279 11914367 12034411 12274499 12574609 12634631 12934741 12994763 13174829 13294873 13474939 13715027 13835071 13895093 14015137 14375269 14615357 14735401 14975489 15095533 15275599 15695753 16235951 16416017 16716127 16896193 17076259
But I think that first two 30011 is better to substitute for 60022. Or where am I "stuping"? =) Both answers are correct. How? In the first case we don't have additional multiplier 2 in LCM, but in the second case we do! In first case you have even number 3841408
So both answers will have the same lcm. OMG, thank you! But now I don't understand how my code works... =) BTW, it seems that your output is wrong.
LCM =
1145572696929554701079627087188585278224797526867219882418294936208691318014731501909363309122622626756133318658525035985652955558442865786706238900113218934286831376065925560824507193167414120672919107758638356289823952045129094359452304000
but it is possible to get bigger lcm. |
