خوب و خرسی

۸ مطلب در مرداد ۱۳۹۴ ثبت شده است

bool operator < (const edge &a, const edge &b){

موافقین ۰ مخالفین ۰ ۳۱ مرداد ۹۴ ، ۲۱:۱۱
kherci

چرا من اینقد سخت رو سوالا فک می کنم؟!

مال اون مدتیه که رو standby بودم!

آسون فکر کن آسون! همه ی سوالا آسونن یه راه آسون وجود داره براشون.

Take it EASY ;-)

موافقین ۰ مخالفین ۰ ۲۹ مرداد ۹۴ ، ۱۷:۱۲
kherci
  • Do dynamic programming on the maximum value that a knapsack of each size can have in it.
  • Update this array for an object of size S by traversing the array in reverse order (of capacity), and seeing if placing the current object into the knapsack of size K yields a better set than the current best knapsack of size K+S.
  • This algorithm runs in K x N time, where K is the size of the knapsack, and N is the sum of availability of objects.
  • If the knapsack is too large to allocate this array, recursive descent is the method of choice, as this problem is NP-complete. Of course, recursive descent can run for a very long time in a large knapsack being filled with small objects
موافقین ۰ مخالفین ۰ ۲۲ مرداد ۹۴ ، ۰۹:۵۹
kherci

نمی دونم چرا همیشه برا سوالای dp باید خیلی دور خودم بچرخم تا به جواب برسم! دوس دارم از این به بعد اولین چیزی که به ذهنم می رسه راه حل درست باشه ea


تجربه ی فراموش شده:

مستقل از هر چیزی(نوع سوال و ...) به محض دیدن سوال یه تابع recursive بنویس تا جواب پیش روت ظاهر بشه!! این راهیه که تو خیلی کانتستا برام مسه مشعل راهو روشن کرده!

موافقین ۰ مخالفین ۰ ۲۰ مرداد ۹۴ ، ۲۰:۳۴
kherci

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>


#define MAXBITS 12

#define MAXSEQ (1<<(MAXBITS+1))


typedef struct Seq Seq;

struct Seq {

    unsigned bits;

    int count;

};


Seq seq[MAXSEQ];


/* increment the count for the n-bit sequence "bits" */

void

addseq(unsigned bits, int n)

{

    bits &= (1<<n)-1;

    bits |= 1<<n;

    assert(seq[bits].bits == bits);

    seq[bits].count++;

}


/* print the bit sequence, decoding the 1<<n stuff */

/* recurse to print the bits most significant bit first */

void

printbits(FILE *fout, unsigned bits)

{

    assert(bits >= 1);

    if(bits == 1) /* zero-bit sequence */

        return;

    

    printbits(fout, bits>>1);

    fprintf(fout, "%d", bits&1);

}


int

seqcmp(const void *va, const void *vb)

{

    Seq *a, *b;

    

    a = (Seq*)va;

    b = (Seq*)vb;

    

    /* big counts first */

    if(a->count < b->count)

        return 1;

    if(a->count > b->count)

        return -1;

    

    /* same count: small numbers first */

    if(a->bits < b->bits)

        return -1;

    if(a->bits > b->bits)

        return 1;

    

    return 0;

}


void

main(void)

{

    FILE *fin, *fout;

    int i, a, b, n, nbit, c, j, k;

    unsigned bit;

    char *sep;

    

    fin = fopen("contact.in", "r");

    fout = fopen("contact.out", "w");

    assert(fin != NULL && fout != NULL);

    

    nbit = 0;

    bit = 0;

    

    for(i=0; i<=MAXBITS; i++)

        for(j=0; j<(1<<i); j++)

            seq[(1<<i) | j].bits = (1<<i) | j;

    

    fscanf(fin, "%d %d %d", &a, &b, &n);

    

    while((c = getc(fin)) != EOF) {

        if(c != '0' && c != '1')

            continue;

        

        bit <<= 1;

        if(c == '1')

            bit |= 1;

        

        if(nbit < b)

            nbit++;

        

        for(i=a; i<=nbit; i++)

            addseq(bit, i);

    }

    

    qsort(seq, MAXSEQ, sizeof(Seq), seqcmp);

    

    /* print top n frequencies for number of bits between a and b */

    j = 0;

    for(i=0; i<n && j < MAXSEQ; i++) {

        if(seq[j].count == 0)

            break;

        

        c = seq[j].count;

        fprintf(fout, "%d\n", c);

        

        /* print all entries with frequency c */

        sep = "";

        for(k=0; seq[j].count == c; j++, k++) {

            fprintf(fout, sep);

            printbits(fout, seq[j].bits);

            if(k%6 == 5)

                sep = "\n";

            else

                sep = " ";

        }

        fprintf(fout, "\n");

    }

    

    exit(0);

}

موافقین ۰ مخالفین ۰ ۱۷ مرداد ۹۴ ، ۲۳:۴۵
kherci

1- Look at this :

while(h>l+1) ;

موافقین ۰ مخالفین ۰ ۱۷ مرداد ۹۴ ، ۱۹:۰۰
kherci

فکرتو بچرخون!

خب اگه ساختنی نیس، حتما پیدا کردنیه

اگه مموری میشه اگه تایم میشه و اگه فک می کنی خب دیگه هیچ راهی به ذهنم نمی رسه اون وقته که سوال داره جیغ می زنه من پیدا کردنی ام!

سوالات به دو دسته ی ساختنی و پیدا کردنی تقسیم میشن چن بار بگم؟!

+ بازگشت شکوهمند من به آغوش ACM بعد از 132 روز گرامی باد! (ما شا الله و لا حول و لا قوت الا بالله العلی العظیم!)

+ با تشکر از تمامی دست اندرکاران و هل دهندگان

+ به آرامی آغاز به زنده شدن می کنی ...

از الان تا آخر عمرم اجازه نمیدم هیچ وقت هیچ چیز هیچ کس منو از ACM جدا کنه!! (ان شاالله!) تو این مدت یاد گرفتم همیشه مسیر خودمو برم و نذارم طوفان ها منو به این طرف و اون طرف ببرن ...


hooray :D

All tests OK.

Your program ('humble') produced all correct answers! This is your submission #40 for this problem. Congratulations!

موافقین ۰ مخالفین ۰ ۱۵ مرداد ۹۴ ، ۲۳:۵۴
kherci

همچنین گاهی هدف از نوشتن ترویج نظرات و دیدگاه های شخصی نویسنده یا ابراز احساسات و عواطف اوست. برخی هم انتشار نظرات خود را فرصتی برای نقد و ارزیابی آن می دانند. البته بدیهی است کسانی که دیدگاه های خود را در قالب هنر بیان می کنند، تاثیر بیشتری بر محیط پیرامون خود می گذارند.

+ من از این جمله خوشم اومد حذفش نمی کنم!

+ دیدی من به نام خدا گفته بودم ولی باز وبلاگم ابتر موند؟!

بسم الله الرحمن الرحیم ... 

ینی اگه این سری ابتر بشه ها!!

موافقین ۱ مخالفین ۰ ۱۵ مرداد ۹۴ ، ۲۳:۳۵
kherci