No. F : 케이크전문점

www.jungol.co.kr/xpert/contestproblem.php?bo_table=study&cid=1493&pid=6&al=005002&stx=6

http://www.jungol.co.kr/xpert/contestproblem.php?bo_table=study&cid=1493&pid=6&al=005002&stx=6

1. update 할 때 순서 정렬은 init TimeStamp

2. update 했는지 안했는지, 얼마나 했는지 체크하여서 넣어둠

3. update 이전에 해당 timeStampe + updateMultiple 비교해서 넣어줌

 

현재 상태 -> update 부분 수정 필요, update 들어가기 전 수정 필요

timeStamp 800 일 때, apple의 82->65 있어야 하는데...

pizza 97->82 되는 과정에서 디버깅 필요함. // 디버깅은 need to else! 부분에 추가 필요함

 

#define MAX_TABLE 101
#define MAX_CAKE 100
#define ull unsigned long long
#define NULL 0

#define DEBUG

struct NODE {
#ifdef DEBUG
    char name[20]; // for debug
#endif
    ull h;
    int timeStamp;
    int cnt;
    int period;
    NODE* prev;
    NODE* next;
}arr[40000];

// 전체 생성 될 수 있는 노드의 개수

NODE* rTable[MAX_TABLE];
char uCakeNames[MAX_CAKE][20];
char uCakeSpoilPeriods[MAX_CAKE];
int totalCakeNum;
int nodeNum;

struct BREAD {
    char cakeName[20];
    char period;
}bread[MAX_CAKE];

int arr_idx;
NODE* myalloc() {
    return &arr[arr_idx++];
}

int strcmp(char* s, char* t) {
    while (*s && *s == *t) ++s, ++t;
    return *s - *t;
}

void mstrcpy(char* dst, char* src) {
    for (int i = 0; src[i] != '\0'; i++) {
        dst[i] = src[i];
    }
    return;
}

ull str2ull(char name[]) {
    ull h = 0;
    for (int i = 0; name[i]; i++) h = (h << 5) + name[i] - 'a' + 1;
    return h;
}

// 필요한 정보를 저장 해두라는 의미인데, lookup table을 만들면 됨.
void init(int n, char cakeNames[][20], int cakeSpoilPeriods[]) {
    for (int i = 0; i < n; i++)
    {
        mstrcpy(bread[i].cakeName, cakeNames[i]);
        bread[i].period = cakeSpoilPeriods[i];
        arr[i].h = arr[i].timeStamp = arr[i].cnt = 0;
        arr[i].prev = arr[i].next = nullptr;
    }
    arr_idx = 0;
    for (int i = 1; i < MAX_TABLE; i++) {
        NODE* pHead = myalloc();
        NODE* pTail = myalloc();
        pTail->prev = pHead;
        pHead->next = pTail;
        rTable[i] = pTail;
    }
    totalCakeNum = n;
}

// 10 0 99 3 
void makeCake(int timeStamp, char cakeName[], int fresh, int cnt) {
 
    ull h = str2ull(cakeName);
    

    NODE* p = myalloc();
    for (int i = 0; i < totalCakeNum; i++) {
        if (strcmp(bread[i].cakeName, cakeName) == 0) {
            p->period = bread[i].period;
        }
    }
#ifdef DEBUG
    mstrcpy(p->name, cakeName);
#endif
    p->h = h;
    p->timeStamp = timeStamp;
    p->cnt = cnt;

    NODE* pTail = rTable[fresh];
    p->prev = pTail->prev;
    pTail->prev = p;
    p->next = p->prev->next;
    p->prev->next = p;
    nodeNum++;
}

void update(NODE* iter, int i, int timeStamp, int multiple) {
    NODE* tmp = iter;
    int newTimeStamp = iter->timeStamp + (multiple * 720);
    iter->prev->next = iter->next;
    iter->next->prev = iter->prev;

    int nowFresh = i - ((timeStamp - tmp->timeStamp) / 720 * tmp->period);
    if (nowFresh <= 0) {
        tmp = NULL;
        nodeNum--;
        return;
    }
    
    //timeStamp 순으로 찾아서 정렬해야 함.
    NODE* pTail = rTable[nowFresh];
    NODE* pHead = NULL;

    // That fresh table is nothing 
    if (pTail->prev->h == 0) {
        tmp->prev = pTail->prev;
        pTail->prev = tmp;
        tmp->next = tmp->prev->next;
        tmp->prev->next = tmp;
        tmp->timeStamp = newTimeStamp;
    }
    else {
        for (NODE* iter = pTail->prev; iter != NULL; iter = iter->prev) {
            if (iter->timeStamp < tmp->timeStamp) {
                tmp->next = iter->next;
                iter->next = tmp;
                tmp->prev = tmp->next->prev;
                tmp->next->prev = tmp;
                tmp->timeStamp = newTimeStamp;
                return;
            }
            
            // need to else !!
            else {

            }
        }
    }
    return;
}


// 720 0 1 99
int sellCake(int timeStamp, char cakeName[], int cnt) {
    ull h = str2ull(cakeName);
    int freshSum;
    int nowFresh;
    int lastTimeStamp;

    for (int i = 100; i > 0; i--) {
        for (NODE* iter = rTable[i]->prev; iter != NULL; iter = iter->prev) {
            if (iter->h == h) {
                // need update
                if (((timeStamp - iter->timeStamp) / 720) >= 1) {                   
                    update(iter, i, timeStamp, ((timeStamp - iter->timeStamp) / 720));
                }
                // count sum
                else {
                    if (iter->cnt >= cnt) {
                        iter->cnt -= cnt;
                        freshSum = i * cnt;
                        if (iter->cnt == 0) {
                            iter->prev->next = iter->next;
                            iter->next->prev = iter->prev;
                            nodeNum--;
                        }
                        return freshSum;
                    }
                    // 현재 cnt 모두 사용 하고, 삭제하고 넘어가야 함
                    else {
                        freshSum = i * iter->cnt;
                        cnt -= iter->cnt;
                        iter->prev->next = iter->next;
                        iter->next->prev = iter->prev;
                        nodeNum--;
                    }
                }
            }
        }
    }
}

void findRemainder(NODE* iter, int cnt) {
    ull h = iter->h;
    for (NODE* iter2 = iter->prev; iter2 != NULL; iter2 = iter2->prev) {

    }
}

int sumFresh, sumTime;
int maxFresh, maxTime;
int result;
int originCnt;
int cntSum;

// it masTime necessary?
int rSellBundleCake(int timeStamp, int cnt, int freshIdx, NODE* nodeP, ull findh) {
    
    for (NODE* iter = nodeP->prev; iter != NULL; iter = iter->prev) {
        if (iter->h == 0) continue;
        if (findh != 0 && iter->h != findh) continue;
        // need update
        if (((timeStamp - iter->timeStamp) / 720) >= 1) {
            NODE* iterNext = iter->next;
            update(iter, freshIdx, timeStamp, ((timeStamp - iter->timeStamp) / 720));
            iter = iterNext->prev;
        }
        else {
            // this node have cnts more than finding cnt
            if (iter->cnt >= cnt) {
                sumFresh = freshIdx * cnt;
                sumTime = iter->timeStamp * cnt;
                if (sumFresh > maxFresh) {
                    // delete node
                    iter->prev->next = iter->next;
                    iter->next->prev = iter->prev;
                    return sumFresh;
                }
                else if (sumFresh == maxFresh && sumTime > maxTime) {
                    maxFresh = sumFresh, maxTime = sumTime;
                }
            }
            // need to find more cnts
            else {
                findh = iter->h;
                sumFresh += iter->cnt * freshIdx;
                sumTime += iter->timeStamp * cnt;
                // delete node
                NODE* tmp = iter;
                NODE* tmpNext = iter->next;
                iter->prev->next = iter->next;
                iter->next->prev = iter->prev;
                rSellBundleCake(timeStamp, cnt - (iter->cnt), freshIdx, iter, findh);
                
                // restore data
                tmp->prev = tmpNext->prev;
                tmpNext->prev = tmp;
                tmp->next = tmp->prev->next;
                tmp->prev->next = tmp;
                iter = tmp;
                findh = 0;
                sumFresh -= iter->cnt * freshIdx;
                sumTime -= iter->timeStamp * cnt;

            }
        }
    }
    
    if (freshIdx == 1) {
        return 0;   // 더 이상 남은 케익이 없음
    }
    rSellBundleCake(timeStamp, cnt, freshIdx - 1, rTable[freshIdx - 1], findh);
    return sumFresh;
}


int sellBundleCake(int timeStamp, int cnt) {
    sumFresh = sumTime = maxFresh = maxTime = 0;
    originCnt = cnt;
    result = rSellBundleCake(timeStamp, cnt, 100, rTable[100], 0);
    return result;
}

/*
nodeNum 을 사용해서 for문의 조건에 추가하여 return 할 수 있고
예제를 통하여 pizz 3개를 return 하연 271을 확인 할 수 있음


03-22 time stamp 를 수정하면 안되고, 
update 부분에 update 된 숫자를 참고할 변수를 만들어서 넣어야 함

*/