Show all threads Hide all threads Show all messages Hide all messages | Algo | Baurzhan | 1748. The Most Complex Number | 22 Jun 2019 21:25 | 9 | Algo Baurzhan 26 Jan 2010 11:48 Can somebody tell me how solve this problem? what is test19? maybe some wrong in test19 It can be solved using backtracking :) Re: Algo Igor Mihajlovic 3 Apr 2010 15:39 can anyone tell me what algo for this problem Re: Algo Artem Khizha [DNU] 28 Jul 2010 17:25 > can anyone tell me what algo for this problem I can, though my approach wasn't so easy. I used precalculations. My way is to generate all pairs (N, P), where P = 1, 2, ... - complexity of number and N - such minimal number, that has exactly P divisors. How to do this with such large inputs? Solve another problem: recover N, if you know P. I used backtrack there, but still I'm wondering whether there is a more beautiful way. First I wrote a recursive function that tries all v=2^a * 3^b * 5^c * 7^d * 11^e * ... with a>=b>=c>=... It generates +- a million possibilities and takes around 300 ms for each case. So I got TLE with 100 cases. Then I wrote code that reads all the n values and sort them. Then I call the recursive function with 10^18. I added a binary search to it that finds the smallest n greater or equal to v and update the best result for it. When the recursive function returns, I update the results for the larger values of n with the smaller results. And then I output the results in the same order as the input. All in less that 50 lines of C++. Re: Algo Keshav Sharma 22 Jun 2019 21:25 I think u can safely assume that that there is no number with power>10 so 10>=a>=b>=c>=d... and now I think u will get AC without doing anything else. Plus small small optimisation.. like breaking at a point if current no. > query(which is obvious to do so) and other such small small optimisation will do. Other thing is to check if ur current no. doesnt exceed the long long range (u can only check by using log()...) Re: Algo Timur_Bekibaev 31 Jan 2010 21:14 Баур, эта задача решатся "в лоб" Re: Algo SamGTU7_Kareva Nadezhda Vladimirovna 12 Jun 2013 23:56 | wa 17 | index | 1748. The Most Complex Number | 14 Sep 2018 22:06 | 1 | wa 17 index 14 Sep 2018 22:06 had wa on test 17, changed long long to long double and calculated everything until 1e20 and got accepted. | Some hints and wa17 | Gleb | 1748. The Most Complex Number | 16 Aug 2018 18:45 | 1 | I precalculated this numbers by algo like bfs, the last most complex numbers have 92160, 96768, 98304, 103680 divisors. Wa17 - max test. I have wa17 because of wrong right border in binary search. Check your program, may be it hepls you. Also you can visit https://oeis.org/A002182 | Weak test cases and Time Limit too strict for Java | rishav kumar | 1748. The Most Complex Number | 25 Apr 2018 06:38 | 1 | Same code gets AC in c++ but gets TLE in test 14 in Java. Turns out, even if you dont use the condition of "powers of primes should be in non increasing order" , your c++ code gets AC, while for Java you have to use that condition. Edited by author 25.04.2018 06:42 Edited by author 25.04.2018 06:42 | For WA#9 | Prime | 1748. The Most Complex Number | 11 Jul 2015 16:09 | 2 | Use cin cout for c++ Edited by author 29.10.2013 13:59 thx for your help or I will be insane. | if WA 19 | [RISE] Levon Oganesyan [RAU] | 1748. The Most Complex Number | 24 Jun 2014 04:47 | 1 | if WA 19 [RISE] Levon Oganesyan [RAU] 24 Jun 2014 04:47 try: 1 897612484786617600 answer: 897612484786617600 103680 | I cannot detect error (WA1) Please help me :) | Mickkie | 1748. The Most Complex Number | 25 Aug 2013 20:09 | 1 | #include<stdio.h> #include<math.h> #include<map> using namespace std; map<unsigned long long,int> M;
int Prime[30]={0,2,3,5,7},Pct=5; void genprime(int); int expP[30]={70},solVal[500],ctsol; unsigned long long solKey[500]; void gensol(unsigned long long,int); void arrange(); main() { genprime(30); gensol(1,1); arrange(); //for (int i=1;i<=ctsol;i++) printf("%lld %d\n",solKey[i],solVal[i]); int Test,id; unsigned long long n; scanf("%d",&Test); for (int t=1;t<=Test;t++) { scanf("%llu",&n); id=ctsol; while (solKey[id]>n) id--; printf("%llu %d\n",solKey[id],solVal[id]); } } void genprime(int K) { int i,j; for (i=11;Pct<K;i+=2) { for (j=1;Prime[j]*Prime[j]<=i;j++) if (i%Prime[j]==0) break; if (Prime[j]*Prime[j]>i) Prime[Pct++]=i; } //for (int i=1;i<Pct;i++) printf("%d\t",Prime[i]); } void gensol(unsigned long long x,int pID) { int i,pro=1; for (i=1;i<30;i++) pro*=expP[i]+1; M[x]=pro;
if (log10(x)+log10(Prime[pID])<=18.3 && expP[pID]<expP[pID-1]) { expP[pID]++; gensol(x*Prime[pID],pID); expP[pID]--; } if (log10(x)+log10(Prime[pID+1])<=18.3 && expP[pID]!=0) { expP[pID+1]++; gensol(x*Prime[pID+1],pID+1); expP[pID+1]--; } } void arrange() { map<unsigned long long,int>::iterator it; for (it=M.begin();it!=M.end();it++) { if (it->second > solVal[ctsol]) { ctsol++; solKey[ctsol]=it->first; solVal[ctsol]=it->second; } } } | WA#10 | Ade | 1748. The Most Complex Number | 12 Jun 2013 15:48 | 2 | WA#10 Ade 30 Nov 2012 19:18 Don't know why. Maybe something tricky between 1e11 ~ 1e12? Re: WA#10 SamGTU7_Kareva Nadezhda Vladimirovna 12 Jun 2013 15:48 The same problem. Even precalculated data didn't help | 1748 | Vilchevski Konstantin | 1748. The Most Complex Number | 9 Jun 2013 04:59 | 3 | 1748 Vilchevski Konstantin 26 Jan 2010 21:36 Wrong answer 3 test. Help! Re: 1748 Ivanov Alexander (HSE Mozgless Eagles) 22 Jul 2011 17:29 In my case it was problems with test 1 12 Correct answer 12 6 Edited by author 22.07.2011 18:01 Re: 1748 SamGTU7_Kareva Nadezhda Vladimirovna 9 Jun 2013 04:59 try 2 12 2 Second test number is smaller than the first | test17 | Hanzbrow (TNU) KCC | 1748. The Most Complex Number | 7 Feb 2013 04:11 | 4 | test17 Hanzbrow (TNU) KCC 30 Jan 2010 00:59 really curious about it, do you have any idea? Am I right? 19 1 1 1 10 6 4 100 60 12 1000 840 32 10000 7560 64 100000 83160 128 1000000 720720 240 10000000 8648640 448 100000000 73513440 768 1000000000 735134400 1344 10000000000 6983776800 2304 100000000000 97772875200 4032 1000000000000 963761198400 6720 10000000000000 9316358251200 10752 100000000000000 97821761637600 17280 1000000000000000 866421317361600 26880 10000000000000000 8086598962041600 41472 100000000000000000 74801040398884800 64512 1000000000000000000 856811873911587456 491520 No, for 10^18 correct answer is 897612484786617600 103680 Try using unsigned long long and compute the numbers untill 10^19 | HELP ME!!!!!!! WA8 - I think the correct solution; WA11 - I think not the correct solution; WHY? ?? | ANDREY TRUBIN | 1748. The Most Complex Number | 27 Jul 2011 21:03 | 3 | WA 8 #include <iostream> #include <math.h> using namespace std; long long h[104680]; int main(){ int wr,a2,a3,a5,a7,a11,a13,a17,a19,a23,a29,a31,a37,i,t; long long p,u,f1,c1,e,k,n,g,c,f,b2,b3,b5,b7,b11,b13,b17,b19,b23,b29,b31,b37,j; for (i=1;i<=104000;i++)h[i]=1000000000000000011; for (a2=0;a2<=8;a2++){ b2=powf(2,a2); for (a3=0;a3<=4;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=0;a5<=3;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=0;a7<=2;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=0;a11<=1;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; b17=b13*powf(17,a17); for (a19=0;a19<=1;a19++){ if (a2<a19)break; b19=b17*powf(19,a19); for (a23=0;a23<=1;a23++){ if (a2<a23)break; b23=b19*powf(23,a23); for (a29=0;a29<=1;a29++){ if (a2<a29)break; b29=b23*powf(29,a29); for (a31=0;a31<=1;a31++){ if (a2<a31)break; b31=b29*powf(31,a31); for (a37=0;a37<=1;a37++){ k=b31*powf(37,a37); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1)*(a19+1)*(a23+1)*(a29+1)*(a31+1)*(a37+1); if (g<=103680){ if ((0<k)&&(k<h[g])){ h[g]=k; } } } } } } } } } } } } } } cin >> t; for (i=1;i<=t;i++){ cin >> n; f1=0;c1=0; for (j=1;j<=103680;j++){ if (h[j]<=n){ f1=h[j]; c1=j; } } cout << f1 << " " << c1 << endl; } cin >> i; return 0; } WA 11 #include <iostream> #include <math.h> //#include <fstream> //#include <ctime> using namespace std; int main(){ int a2,a3,a5,a7,a11,a13,a17,a19,a23,a29,a31,a37,i,t; long long k,n,g,c,f,b2,b3,b5,b7,b11,b13,b17,b19,b23,b29,b31,b37; //ifstream f1("1.txt"); cin >> t;//clock_t t0 = clock(); for (i=1;i<=t;i++){ cin >> n; c=1; f=1; if (n>1000000000000){ for (a2=4;a2<=9;a2++){ b2=powf(2,a2); for (a3=1;a3<=5;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=1;a5<=4;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=1;a7<=3;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=1;a11<=2;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; b17=b13*powf(17,a17); for (a19=0;a19<=1;a19++){ if (a2<a19)break; b19=b17*powf(19,a19); for (a23=0;a23<=1;a23++){ if (a2<a23)break; b23=b19*powf(23,a23); for (a29=0;a29<=1;a29++){ if (a2<a29)break; b29=b23*powf(29,a29); for (a31=0;a31<=1;a31++){ if (a2<a31)break; b31=b29*powf(31,a31); for (a37=0;a37<=1;a37++){ k=b31*powf(37,a37); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1)*(a19+1)*(a23+1)*(a29+1)*(a31+1)*(a37+1); if ((((k<=n) && (c<g))||((k<f) && (c==g)))&&(k>0)){ c=g; f=k; } } } } } } } } } } } //lkj3:; } } cout << f << " " << c << endl; } else { if (n>1000000){ for (a2=2;a2<=8;a2++){ b2=powf(2,a2); for (a3=1;a3<=4;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=1;a5<=3;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=0;a7<=2;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=0;a11<=1;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; b17=b13*powf(17,a17); for (a19=0;a19<=1;a19++){ if (a2<a19)break; b19=b17*powf(19,a19); for (a23=0;a23<=1;a23++){ if (a2<a23)break; b23=b19*powf(23,a23); for (a29=0;a29<=1;a29++){ if (a2<a29)break; b29=b23*powf(29,a29); for (a31=0;a31<=1;a31++){ if (a2<a31)break; k=b29*powf(31,a31); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1)*(a19+1)*(a23+1)*(a29+1)*(a31+1); if (((k<=n) && (c<g))||((k<f) && (c==g))){ c=g; f=k; } } } } } } } } } } //lkj3:; }
} cout << f << " " << c << endl; } else { for (a2=0;a2<=7;a2++){ b2=powf(2,a2); for (a3=0;a3<=4;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=0;a5<=2;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=0;a7<=2;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=0;a11<=1;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; k=b13*powf(17,a17); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1); if (((k<=n) && (c<g))||((k<f) && (c==g))){ c=g; f=k; } } } } } } //lkj3:; }
} cout << f << " " << c << endl; } }
}//clock_t t1 = clock();cout << "time: " << (double)(t1 - t0) / CLOCKS_PER_SEC << endl; cin >> i; return 0; } Solved 15 hours!!!!!!!!!!!!!!!!!!!!!!!! long long < 2^63 Received overflow On it received WA!!!!!!!!! Edited by author 10.07.2011 23:16 Edited by author 10.07.2011 23:17 Edited by author 10.07.2011 23:17 Edited by author 10.07.2011 23:17 | what is test19? | l@mho | 1748. The Most Complex Number | 24 Dec 2010 02:03 | 2 | maybe some wrong in test19 I also keep getting WA on test 19..did you arrive at anything regarding this ? |
|
|