Show all threads Hide all threads Show all messages Hide all messages | AC,but have question | Felix_Mate | 1091. Tmutarakan Exams | 30 Dec 2021 12:57 | 2 | Я решил с помощью ДП: f[i,k,d]-число способов выбрать k чисел от i до s, нод которых d. Работает 0.031 sec. Вопрос: как решить эту задачу именно с помощью теории чисел( я использовал в динамике только один факт: gcd(a1,a2,...,ak)=gcd(a1,gcd(a2,...,ak)))? Актуально ли это) но здесь можно решать еще с помощью формулуы включений-исключений. Предподсчитаем простые числа. Признаки в формуле - делимость на i. сочетаниями подсчитаем кол-во способов выбрать наборы. сочетания посчитаем динамикой | Simple DP | guilty spark | 1091. Tmutarakan Exams | 16 Jul 2021 18:47 | 1 | DP[i][j][k] = count of sets of length i ending at number j with total gcd of k initialize with dp[1][n][n] = 1 for every n >= 2 && n <= s ans is summation of all dp[K][num][g] where g > 1 and num between 2 and s Edited by author 16.07.2021 18:48 Edited by author 16.07.2021 18:48 Edited by author 16.07.2021 18:48 | One solution | boocoo | 1091. Tmutarakan Exams | 25 Feb 2021 19:02 | 1 | A solution that doesn't make use of the max number being 10,000 is using inclusion-exclusion principle. Because when we take the sets of K that have a gcd divisible by 2 and the sets of K that have a gcd divisible by 3, you count twice the ones with a gcd divisible by 6, so you have to subtract those. It's similar to a solution to this problem: https://open.kattis.com/problems/coprimeintegers | This problem is simpler than the rating he has )) | KostyaRychkov | 1091. Tmutarakan Exams | 31 Jul 2020 21:31 | 1 | The most important thing is that you shouldn't keep finding sets when you've already found 10,000. Then you can optimize a little simple search and you get ACC. Good luck! | Is it true or not | ura | 1091. Tmutarakan Exams | 10 Feb 2020 12:13 | 1 | K= 11 S= 125 OTVET= 511435086865 K= 11 S= 126 OTVET= 620074954696 K= 11 S= 127 OTVET= 620074954696 K= 11 S= 128 OTVET= 747880479697 K= 11 S= 129 OTVET= 749351922670 K= 11 S= 130 OTVET= 900828406180 K= 11 S= 131 OTVET= 900828406180 K= 11 S= 132 OTVET= 1081759187586 K= 11 S= 133 OTVET= 1081759231344 K= 11 S= 134 OTVET= 1292739780552 K= 11 S= 135 OTVET= 1295226349065 | This problem is harder than the rating he has | scythe | 1091. Tmutarakan Exams | 18 May 2015 00:47 | 2 | some hints: use pascal triangle to generate c(n,k) if you use 63 bits data type all will fit. prime factorize each number for each prime count the number of number where he is a factor calculate number of posibilites remove duplicates ( this is what makes this problem a little bit harder ). Good luck. remove duplicates ( this is what makes this problem a little bit harder ). If you don't know how to do this part take a look at derivation of Euler's totient function. | I got AC with time 0.875s | degree | 1091. Tmutarakan Exams | 23 Aug 2013 17:16 | 1 | just dfs and pre calculate gcd. | where is the problem in my code??? | Radi Muhammad Reza | 1091. Tmutarakan Exams | 22 Jan 2013 19:59 | 1 | | Sample example. What we must find? | IgorKoval(from Pskov) | 1091. Tmutarakan Exams | 13 Dec 2011 21:28 | 4 | How get answer 11 for K==3 and S==10 I understand it so: a b gcd(a,b) 2 4 2 2 6 2 2 8 2 2 10 2 3 6 3 3 9 3 4 2 2 4 6 2 4 8 4 4 10 2 5 10 5 6 2 2 6 3 3 6 4 2 6 8 2 6 9 3 6 10 2 8 2 2 8 4 4 8 6 2 8 10 2 9 3 3 9 6 3 10 2 2 10 4 2 10 5 5 10 6 2 10 8 2 So, cnt = 28 //count of pair a, b And my answer is 28. Why am wrong? And how use 'K'? =)
Edited by author 11.12.2011 19:36 "You should find the number of sets of K different numbers" sets of K different numbers Please, give some example of "sets of K different numbers"( there are 11 sets(from Sample example) ) for K==3 and S==10. Thank you. Edited by author 13.12.2011 21:07 Edited by author 13.12.2011 21:07 a b c fgcd(c,fgcd(a,b)) 2 4 6 2 2 4 8 2 2 4 10 2 2 6 8 2 2 6 10 2 2 8 10 2 3 6 9 3 4 6 8 2 4 6 10 2 4 8 10 2 6 8 10 2 cnt = 11 fgcd - function which return greatest common divisor Edited by Trolol 13.12.2011 21:30 Edited by author 13.12.2011 21:50 | why my logic is wrong! help please!!! i've got WA#4. | Bobur | 1091. Tmutarakan Exams | 18 Nov 2011 23:01 | 4 | here is code const a : array [1..9] of integer=(2, 3, 5, 7, 11, 13, 17, 19, 23); var k, s, ans, x, k1 : integer; i, j : integer; p, q : int64; begin read(k, s); ans := 0; for i := 1 to 9 do if (s div a[i]) >= k then begin k1 := k; x := s div a[i]; if k1 > x-k1 then k1 := x-k1; q := 1; p := 1; for j := 1 to k1 do p := p * j; for j := x-k1+1 to x do q := q * j; ans := ans + q div p; end; if ans > 10000 then ans := 10000; writeLn(ans); end. where is wrong! this code give wrong answers for example: 2 26 3 45 3 29 2 25 .... thanks. don't worry, i found my bug Hi,I use the same logic but wa#4 too,can you help me? Edited by author 21.06.2011 14:02 If there is s = 50 and a[i] = 2 then the program tries to calculate 25! into integer type (var p) and may occur error. And this idea is wrong, for example: Let k=3 and s=25 you count the set 6 18 24 for prime 2 in cnk(25/2, 3) and also for 3 in cnk(25/3, 3). That is why your answer always exceeds the right one. you must subtract these set in each iteration. This will be: for (int i=2; res<10000; i++){ if (prime(i)){ n = s/i; if (n<k) break; else res += cnk(n,k); for (int j = 0; j<p_cnt; j++) if (n/prime[j]<k) break; else res -= cnk(n/prime[j],k); prime[p_cnt++] = i; } } I get AC with it. Edited by author 18.11.2011 23:37 | Accepted Java | magzhan | 1091. Tmutarakan Exams | 27 Jun 2011 14:50 | 2 | import java.math.BigInteger; import java.util.*; public class Problem { public static BigInteger c(int n, int k){ BigInteger r=BigInteger.ONE; for(int i=0;i<k;i++){ r=r.multiply(BigInteger.valueOf(n-i)); } for(int i=0;i<k;i++){ r=r.divide(BigInteger.valueOf(i+1)); } return r; } public static boolean inP(int x, int[] p){ for(int i=0;i<p.length;i++){ if(p[i]==x) return true; } return false; } public static void main (String[] args) { try { Scanner in = new Scanner(System.in); int k=in.nextInt(); int s=in.nextInt(); int[] p = new int[9]; boolean[] b = new boolean[s+1]; BigInteger q = BigInteger.ZERO; p[0]=2;p[1]=3;p[2]=5; p[3]=7;p[4]=11;p[5]=13; p[6]=17;p[7]=19;p[8]=23; int x=0,y=0; int[] w = new int[s+1]; for(int i=0;i<9;i++){ x=0;y=s/p[i]; for(int j=2;j<=s;j++){ if(j%p[i]==0){ if(b[j]){ for(int o=2;o<=j;o++){ if(j%o==0 && o<p[i] && inP(o,p)){ w[o]++; } } } b[j]=true; } } if(y>=k){ q=q.add(c(y,k)); } for(int j=0;j<s+1;j++){ if(w[j]>=k){ q=q.subtract(c(w[j],k)); } } w=new int[s+1]; } if(Integer.parseInt(q.toString())<=10000){ System.out.println(q); }else{ System.out.println(10000); } } catch (Exception ex) { System.out.println(ex.toString()); } } } Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com | Give me some tests please! | Loky_Yuri [USTU] | 1091. Tmutarakan Exams | 3 Jan 2011 07:03 | 8 | And what answer for this test 2 50 -- Is it 462 or not? OK! I changed my code. It give the same answer, but I have WA#4 again. Can you give some tests? Try this: 26 12 0 --------- 2 2 0 --------- 6 24 952 Good Luck) Thank you! AC Now! Just stupid mistake! I wrote incorrect procedure to find is the number prime or not. Congradulations my friend) If you have WA4 try test 2 12 Edited by author 11.07.2007 12:43 Hi, Few test cases here: k = 2 s = 2 answer = 0 k = 2 s = 3 answer = 0 k = 2 s = 4 answer = 1 k = 2 s = 5 answer = 1 k = 2 s = 6 answer = 4 k = 2 s = 7 answer = 4 k = 2 s = 8 answer = 7 k = 2 s = 9 answer = 9 k = 2 s = 10 answer = 14 k = 2 s = 11 answer = 14 k = 2 s = 12 answer = 21 k = 2 s = 13 answer = 21 k = 2 s = 14 answer = 28 k = 2 s = 15 answer = 34 k = 2 s = 16 answer = 41 k = 2 s = 17 answer = 41 k = 2 s = 18 answer = 52 k = 2 s = 19 answer = 52 k = 2 s = 20 answer = 63 k = 2 s = 21 answer = 71 k = 2 s = 22 answer = 82 k = 2 s = 23 answer = 82 k = 2 s = 24 answer = 97 k = 2 s = 25 answer = 101 k = 2 s = 26 answer = 114 k = 2 s = 27 answer = 122 k = 2 s = 28 answer = 137 k = 2 s = 29 answer = 137 k = 2 s = 30 answer = 158 k = 2 s = 31 answer = 158 k = 2 s = 32 answer = 173 k = 2 s = 33 answer = 185 k = 2 s = 34 answer = 202 k = 2 s = 35 answer = 212 k = 2 s = 36 answer = 235 k = 2 s = 37 answer = 235 k = 2 s = 38 answer = 254 k = 2 s = 39 answer = 268 k = 2 s = 40 answer = 291 k = 2 s = 41 answer = 291 k = 2 s = 42 answer = 320 k = 2 s = 43 answer = 320 k = 2 s = 44 answer = 343 k = 2 s = 45 answer = 363 k = 2 s = 46 answer = 386 k = 2 s = 47 answer = 386 k = 2 s = 48 answer = 417 k = 2 s = 49 answer = 423 k = 2 s = 50 answer = 452 k = 3 s = 2 answer = 0 k = 3 s = 3 answer = 0 k = 3 s = 4 answer = 0 k = 3 s = 5 answer = 0 k = 3 s = 6 answer = 1 k = 3 s = 7 answer = 1 k = 3 s = 8 answer = 4 k = 3 s = 9 answer = 5 k = 3 s = 10 answer = 11 k = 3 s = 11 answer = 11 k = 3 s = 12 answer = 24 k = 3 s = 13 answer = 24 k = 3 s = 14 answer = 39 k = 3 s = 15 answer = 46 k = 3 s = 16 answer = 67 k = 3 s = 17 answer = 67 k = 3 s = 18 answer = 104 k = 3 s = 19 answer = 104 k = 3 s = 20 answer = 143 k = 3 s = 21 answer = 159 k = 3 s = 22 answer = 204 k = 3 s = 23 answer = 204 k = 3 s = 24 answer = 277 k = 3 s = 25 answer = 283 k = 3 s = 26 answer = 349 k = 3 s = 27 answer = 377 k = 3 s = 28 answer = 458 k = 3 s = 29 answer = 458 k = 3 s = 30 answer = 588 k = 3 s = 31 answer = 588 k = 3 s = 32 answer = 693 k = 3 s = 33 answer = 739 k = 3 s = 34 answer = 859 k = 3 s = 35 answer = 880 k = 3 s = 36 answer = 1061 k = 3 s = 37 answer = 1061 k = 3 s = 38 answer = 1214 k = 3 s = 39 answer = 1281 k = 3 s = 40 answer = 1470 k = 3 s = 41 answer = 1470 k = 3 s = 42 answer = 1732 k = 3 s = 43 answer = 1732 k = 3 s = 44 answer = 1945 k = 3 s = 45 answer = 2063 k = 3 s = 46 answer = 2294 k = 3 s = 47 answer = 2294 k = 3 s = 48 answer = 2631 k = 3 s = 49 answer = 2646 k = 3 s = 50 answer = 2952 Make sure that if your answer is greater than 10000 then only print 10000. | No subject | Enigma | 1091. Tmutarakan Exams | 4 Nov 2010 16:11 | 3 | Edited by author 04.11.2010 16:04 MyCode in Java : int k = sc.nextInt(); int n = sc.nextInt(); int z = 0; s = new BigInteger("0"); int[] a = new int[] {1,2,3,5,7,11,13,17,19,23}; int[] b = new int[]{1,6,10,14,15,21,22}; sn = new BigInteger("0"); for (int j = 1; j <=9; j++) { z = n/a[j]; if (z>=k) { almashtirishlar(z,k); s = s.add(sn); }else break; } for (int i = 1; i <=6; i++) { z = n/b[i]; if (z>=k){ almashtirishlar(z, k); s = s.subtract(sn); }else break; } if(s.compareTo(new BigInteger("10000"))<0)System.out.println(s); else System.out.println(10000); } public static void almashtirishlar(int q,int kk) { BigInteger s1 = new BigInteger("1"); for (int i = 2; i <=q; i++) { s1 = s1.multiply(new BigInteger(i+"")); } BigInteger s2 = new BigInteger("1"); for (int i = 2; i <=kk; i++) { s2 = s2.multiply(new BigInteger(i+"")); } BigInteger s3 = new BigInteger("1"); for (int i = 2; i <=q-kk; i++) { s3 = s3.multiply(new BigInteger(i+"")); } sn = s1.divide(s2.multiply(s3)); } } Hello Enigma 4 Nov 2010 16:11 | sad | pisyn | 1091. Tmutarakan Exams | 26 Aug 2008 00:23 | 1 | sad pisyn 26 Aug 2008 00:23 svd Edited by author 26.08.2008 17:51 | This is my program.... | Register | 1091. Tmutarakan Exams | 2 Aug 2008 15:08 | 1 | program bt_gr_1091; const d:array[2..50,2..50]of word=((0,0,1,1,4,4,7,9,14,14,21,21,28,...), ...... ...... (0,...,0,0,0,0,0,0,0,0,0,0,0,0,0)); var a,b:byte; begin read(a,b); write(d[a,b]); end. and it got Accepted 0.015s,200K I just want do die... | why? | 连连 | 1091. Tmutarakan Exams | 22 Jul 2008 00:42 | 1 | why? 连连 22 Jul 2008 00:42 Edited by author 22.07.2008 02:17 | A small quention | Neptun | 1091. Tmutarakan Exams | 5 Apr 2008 23:52 | 2 | "it was proved later by the best minds of the Department that there do not exist sets of numbers with the required properties" Is it becasue that when k=25,the minimal set of numbers is {2,4,6,8,...50}???So we can't find a solution with every number within 49? If I'm right,why does the problem says "it was proved by the best minds of the Department "?It's so obvious... | Please give me direction! What's the 4th test??? | QAFQAZ FUAD.H | 1091. Tmutarakan Exams | 31 Mar 2008 17:01 | 2 | I have WAQ#4! I am sending you my program's some outputs : i:2 26 o:114 i:3 45 o:2064 i:5 43 o:10000 i:23 49 o:24
my AC ans is: 2 26 -> 114 3 45 -> 2063* 5 43 -> 10000 23 49 -> 24 *for 3 45 your ans is 2064 Edited by author 31.03.2008 17:03 | why my code always be "Compilation error" | chinacn | 1091. Tmutarakan Exams | 30 Nov 2007 19:24 | 2 | please help me!thank you very much. program p1091; var s,i,k,j:longint; yy:longint; yinzi:array[1..1000] of longint; first:boolean; lyy,total:int64; function c(y,x:longint):int64; var i:longint; i1,x1:int64; begin c:=1; x1:=x; for i:=(x+1) to y do begin i1:=i; c:=c*i1; c:=c div (i1-x1); end; end; begin readln(k,s); i:=2; while (s div i>=k) do begin fillword(yinzi,sizeof(yinzi) shr 1,0); first:=false; yy:=i; for j:=2 to i do while ((yy mod j)=0) and (yy>0) do begin inc(yinzi[j]); if yinzi[j]>1 then first:=true; yy:=yy div j; end; if not(first) then begin yy:=0; for j:=2 to 30 do inc(yy,yinzi[j]); if odd(yy) then begin lyy:=c(s div i,k); inc(total,lyy); end else begin lyy:=c(s div i,k); dec(total,lyy); end; end; inc(i); end; if total>10000 then writeln('10000') else writeln(total); end. use result:=result*i1 instead of c:=c*i1; and fillchar() instead of fillword() | I got AC (0.015 s) | NBH - HBR | 1091. Tmutarakan Exams | 16 May 2005 22:35 | 3 | 18 сен 2004 NBH - HBR 1091 Pascal Accepted 0.015 381 КБ 845118 17:02:24 9 May 2005 Fu Dong 1091 Pascal Accepted 0.001 149 KB 0.001s 49KB! Sergey Baskakov, Raphail and Denis 16 May 2005 22:35 849320 21:50:25 16 May 2005 Sergey Baskakov, Raphail and Denis 1091 Pascal Accepted 0.001 49 KB I've tried my best. I cann't make it better... Can you? BTW, to those who write efficient algos: may be you can post your results (time and memory complexity of your solutions) so that less experienced solvers could see 'ideal' results. |
|
|