CF: 158A (Next Round)


Problem link: http://codeforces.com/problemset/problem/158/A

ব্যাপারটা অনেকটা এরকম যে, n-সংখ্যক প্রতিযোগী আছে, এবং তাদের পয়েন্ট দেয়া আছে। আমরা এদের মধ্য থেকে k-জন প্রতিযোগী নির্বাচিত করতে চাই। প্রতিযোগীদের পয়েন্টগুলো সর্ট করেই দেয়া থাকবে। অর্থাৎ, যে সবচেয়ে বেশি পয়েন্ট পেয়েছে তার পয়েন্ট সবার আগে থাকবে। যেমন প্রথম ইনপুট স্যাম্পল দেখি।

8 5
10 9 8 7 7 7 5 5

অর্থাৎ, ৮ জনের মধ্যে প্রথম ৫ জনকে নিতে চাই। এখন কথা হল, পঞ্চম প্রতিযোগী পেয়েছে ৭ পয়েন্ট এবং আমরা তাকে নিব। তবে, ষষ্ঠ প্রতিযোগীও পেয়েছে ৭ পয়েন্ট, তাকে কিভাবে বাদ দেই? (তার তো মন খারাপ হয়ে যাবে :-(, তাই না? সুতরাং তাকেও নিতে হবে)। তাহলে আমাদের উত্তর হবে, ৬ জনকে নিতে হবে।

আরও একটা উদাহরণ

8 5
100 90 88 85 80 80 80 80

Answer:
8

আরও একটা উদাহরণ

8 5
100 90 88 0 0 0 0 0

Answer:
3

আমরা ৫ জনকে নিতে চেয়েছিলাম বটে। তবে ০ (শুন্য) পেলে তো আর নেয়া যায় না! তাই আমরা ৩ জনকে নিতে পারব।

(প্রবলেমে বলা আছে, পজিটিভ নাম্বার পেতে হবে, অর্থাৎ >= ১, মনে রাখতে হবে, ০ (শুন্য) পজিটিভ নাম্বার না)

Solution 1


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{
    int n, k;

    scanf ("%d %d", &n, &k);

    int solved [50 + 10];

    for ( int i = 0; i < n; i++ ) {
        scanf ("%d", &solved [i]);
    }

    // margin is our last limit. 
    // We can not accept contestant's point below this limit.  
    int margin = solved [k - 1];

    int cnt = 0;

    for ( int i = 0; i < n; i++ ) {
        
        // contestant's point must be greater than or equals to margin 
        // and contestant's point must be a positive number  
        if ( solved [i] >= margin && solved [i] ) cnt++;
    }

    printf ("%d\n", cnt);

    return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s