| ENG RUS | Timus Online Judge |
Discussion of Problem 1807. Cartridges for MaximShohruh Why my idea is wrong? [1] // Problem 1807. Cartridges for Maxim 27 Jun 2021 16:58 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! zykzhou Re: Why my idea is wrong? // Problem 1807. Cartridges for Maxim 16 Aug 2022 17:54 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. Md sabbir Rahman WA 19 [1] // Problem 1807. Cartridges for Maxim 22 Nov 2018 22:39 Can anyone please tell me what's in test 19? please? Md sabbir Rahman Re: WA 19 // Problem 1807. Cartridges for Maxim 23 Nov 2018 01:25 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. luckysundog WA7 [1] // Problem 1807. Cartridges for Maxim 21 Oct 2011 15:40 Please write answer for N = 169, 841, 674041. invokerj Re: WA7 // Problem 1807. Cartridges for Maxim 5 Dec 2013 16:40 ALSO WA7, who give more test? neko13 I got ac.But it's clearly that I'm wrong. [1] // Problem 1807. Cartridges for Maxim 9 Aug 2013 01:16 My ac program print only 500 when n=625. I think the test number is not good enough. neko13 Re: I got ac.But it's clearly that I'm wrong. // Problem 1807. Cartridges for Maxim 9 Aug 2013 01:21 I'm sorry.I use the wrong project. monyura[ONU 1 2/3] Give me a hint, I AC this using preprocessing [7] // Problem 1807. Cartridges for Maxim 12 Nov 2010 23:45 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) Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: Give me a hint, I AC this using preprocessing // Problem 1807. Cartridges for Maxim 13 Nov 2010 10:43 Optimize SkorKNURE Re: Give me a hint, I AC this using preprocessing [5] // Problem 1807. Cartridges for Maxim 30 Sep 2011 02:06 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... */ xurshid_n Re: Give me a hint, I AC this using preprocessing [4] // Problem 1807. Cartridges for Maxim 17 Jan 2012 19:59 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? luckysundog Re: Give me a hint, I AC this using preprocessing [3] // Problem 1807. Cartridges for Maxim 11 Feb 2012 17:55 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 xurshid_n Re: Give me a hint, I AC this using preprocessing // Problem 1807. Cartridges for Maxim 28 Feb 2012 20:28 Edited by author 28.02.2012 20:32 xurshid_n Re: Give me a hint, I AC this using preprocessing [1] // Problem 1807. Cartridges for Maxim 28 Feb 2012 20:29 luckysundog wrote 11 February 2012 17:55 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:19 neko13 Re: Give me a hint, I AC this using preprocessing // Problem 1807. Cartridges for Maxim 7 Aug 2013 22:25 Could you give me some hints about how to breakup a prime as m=a1+a2+a3... so that lcm(a1,a2,a3,...) is biggest? Alexandr172 197*197 [3] // Problem 1807. Cartridges for Maxim 3 May 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 Alexandr172 Re: 197*197 [2] // Problem 1807. Cartridges for Maxim 23 May 2012 18:59 All OK, I've got AC neko13 Re: 197*197 // Problem 1807. Cartridges for Maxim 7 Aug 2013 22:21 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? neko13 Re: 197*197 // Problem 1807. Cartridges for Maxim 7 Aug 2013 22:21 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? Alexandr172 WA31 [1] // Problem 1807. Cartridges for Maxim 6 May 2012 22:31 WA31 What is it? Alexandr172 Re: WA31 // Problem 1807. Cartridges for Maxim 23 May 2012 18:58 All OK, I've got AC bsu.mmf.team Need help [2] // Problem 1807. Cartridges for Maxim 1 Nov 2010 11:30 Please, write somebody full answer for N = 994009. Victor Barinov (TNU) Re: Need help [1] // Problem 1807. Cartridges for Maxim 2 Nov 2010 18:09 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 bsu.mmf.team Re: Need help // Problem 1807. Cartridges for Maxim 2 Nov 2010 19:57 Thank you Vedernikoff 'Goryinyich' Sergey (HSE: АОП) AC, but I think my solution is wrong [5] // Problem 1807. Cartridges for Maxim 2 Nov 2010 00:49 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"? =) Sandro (USU) Re: AC, but I think my solution is wrong [3] // Problem 1807. Cartridges for Maxim 2 Nov 2010 01:24 Both answers are correct. Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: AC, but I think my solution is wrong [2] // Problem 1807. Cartridges for Maxim 2 Nov 2010 13:00 How? In the first case we don't have additional multiplier 2 in LCM, but in the second case we do! Victor Barinov (TNU) Re: AC, but I think my solution is wrong [1] // Problem 1807. Cartridges for Maxim 2 Nov 2010 13:43 In first case you have even number 3841408 So both answers will have the same lcm. Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: AC, but I think my solution is wrong // Problem 1807. Cartridges for Maxim 2 Nov 2010 15:30 OMG, thank you! But now I don't understand how my code works... =) Victor Barinov (TNU) Re: AC, but I think my solution is wrong // Problem 1807. Cartridges for Maxim 2 Nov 2010 17:41 BTW, it seems that your output is wrong. LCM = 1145572696929554701079627087188585278224797526867219882418294936208691318014731501909363309122622626756133318658525035985652955558442865786706238900113218934286831376065925560824507193167414120672919107758638356289823952045129094359452304000 but it is possible to get bigger lcm.
|