Обсуждение @ 1091. Тмутараканские экзамены @ Timus Online Judge

__Andrewy__ AC,but have question [1] // Задача 1091. Тмутараканские экзамены 12 мар 2016 18:04

springWaltz Simple DP // Задача 1091. Тмутараканские экзамены 16 июл 2021 18:47

boocoo One solution // Задача 1091. Тмутараканские экзамены 25 фев 2021 19:02

KostyaRychkov`~ This problem is simpler than the rating he has )) // Задача 1091. Тмутараканские экзамены 31 июл 2020 21:31

ura Is it true or not // Задача 1091. Тмутараканские экзамены 10 фев 2020 12:13

scythe This problem is harder than the rating he has [1] // Задача 1091. Тмутараканские экзамены 24 ноя 2011 01:52

Mukhametika I got AC with time 0.875s // Задача 1091. Тмутараканские экзамены 23 авг 2013 17:16

Radi Muhammad Reza where is the problem in my code??? // Задача 1091. Тмутараканские экзамены 22 янв 2013 19:59

IgorKoval [PskovSU] Sample example. What we must find? [3] // Задача 1091. Тмутараканские экзамены 11 дек 2011 19:35

BOBUR_OG'O!!! why my logic is wrong! help please!!! i've got WA#4. [3] // Задача 1091. Тмутараканские экзамены 27 апр 2008 22:22

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.

BOBUR_OG'O!!! Re: why my logic is wrong! help please!!! i've got WA#4. [2] // Задача 1091. Тмутараканские экзамены 28 апр 2008 19:31

don't worry, i found my bug

Harhro94 [Hrayr Harutyunyan] Re: why my logic is wrong! help please!!! i've got WA#4. [1] // Задача 1091. Тмутараканские экзамены 21 июн 2011 14:02

Hi,I use the same logic but wa#4 too,can you help me?

Edited by author 21.06.2011 14:02

strange Re: why my logic is wrong! help please!!! i've got WA#4. // Задача 1091. Тмутараканские экзамены 18 ноя 2011 23:01

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

magzhan Accepted Java [1] // Задача 1091. Тмутараканские экзамены 22 июн 2011 22:14

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());
        }
    }
}

Juliet Re: Accepted Java // Задача 1091. Тмутараканские экзамены 27 июн 2011 14:50

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

Loky_Yuri [USTU Frogs] Give me some tests please! [7] // Задача 1091. Тмутараканские экзамены 8 фев 2007 12:34

And what answer for this test
2 50
--
Is it 462 or not?

Kurpilyansky Eugene (USU) Re: Give me some tests please! [6] // Задача 1091. Тмутараканские экзамены 8 фев 2007 17:33

My AC program print 452.

Loky_Yuri [USTU Frogs] Re: Give me some tests please! [5] // Задача 1091. Тмутараканские экзамены 8 фев 2007 20:32

OK! I changed my code. It give the same answer, but I have WA#4 again. Can you give some tests?

Alex Fetisov Re: Give me some tests please! [2] // Задача 1091. Тмутараканские экзамены 8 фев 2007 22:51

Try this:
26 12
0
---------
2 2
0
---------
6 24
952
Good Luck)

Loky_Yuri [USTU Frogs] Re: Give me some tests please! [1] // Задача 1091. Тмутараканские экзамены 9 фев 2007 11:42

Thank you! AC Now! Just stupid mistake! I wrote incorrect procedure to find is the number prime or not.

Alex Fetisov Re: Give me some tests please! // Задача 1091. Тмутараканские экзамены 9 фев 2007 12:51

Congradulations my friend)

elmariachi1414 (TNU) Re: Give me some tests please! [1] // Задача 1091. Тмутараканские экзамены 11 июл 2007 12:43

If you have WA4
try test
2 12

Edited by author 11.07.2007 12:43

Varun Sharma Re: Give me some tests please! // Задача 1091. Тмутараканские экзамены 3 янв 2011 07:03

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.

N0D1R No subject [2] // Задача 1091. Тмутараканские экзамены 4 ноя 2010 15:59

pisyn sad // Задача 1091. Тмутараканские экзамены 26 авг 2008 00:23

Register This is my program.... // Задача 1091. Тмутараканские экзамены 2 авг 2008 15:08

lian lian why? // Задача 1091. Тмутараканские экзамены 22 июл 2008 00:42

Neptun A small quention [1] // Задача 1091. Тмутараканские экзамены 24 окт 2007 06:11

Fuad Hajiyev Please give me direction! What's the 4th test??? [1] // Задача 1091. Тмутараканские экзамены 31 мар 2008 13:32

chinacn why my code always be "Compilation error" [1] // Задача 1091. Тмутараканские экзамены 30 ноя 2007 16:51

NBH - HBR - Hùng Phạm (Hanoi University of Science) I got AC (0.015 s) [2] // Задача 1091. Тмутараканские экзамены 18 сен 2004 09:28

Обсуждение задачи 1091. Тмутараканские экзамены