---
# System prepended metadata

title: 13723 - Cookie Monster
tags: [bubble sort]

---

# 13723 - Cookie Monster

>author: Utin
###### tags: `bubble sort`

---

## Brief
See the code below

## Solution 0

```c=
#include <stdio.h>
#include <string.h>

int n, m;
int arr_status[1001][2]; //0: the number of '7', 1: length
char arr[1001][1001]; //record cookies' values
int string_index = 0; //record the position when convert number into string

/*
Swapping the string is too inefficient,
so we declare an array to record each position of them.
While doing some arrangement, we just need to change this array.
*/
int ans[1001];

void convert(int k, int i);

int main() {
    scanf("%d %d", &n, &m);
    char c;
    int index = 0;
    scanf("\r");
    while((c = getchar()) != EOF) {
        if(c == '|') {
            //do nothing
        }
        else if(c == '\n') {
            index += 1;
            string_index = 0;
        }
        else {
            int temp;
            ungetc(c, stdin);
            scanf("%x", &temp);
            convert(temp, index);
        }
    }

    //initialize ans array
    for(int i = 0; i < n; i++) {
        ans[i] = i;
    }

    /*
    BubbleSort:
    Compare the numbers of '7' first and then compare the value.
    Because "Bubble Sort" will move the maximum to the last position,
    so we just need to do m times to get m maximum value.
    */
    for(int t = n; t > n-m; t--) {
        for(int i = 0; i < t-1; i++) {
            if(arr_status[ans[i]][0] > arr_status[ans[i+1]][0]) {
                int temp = ans[i];
                ans[i] = ans[i+1];
                ans[i+1] = temp;
            }
            else if(arr_status[ans[i]][0] == arr_status[ans[i+1]][0]) {
                if(arr_status[ans[i]][1] == arr_status[ans[i+1]][1]) {
                    if(strcmp(arr[ans[i]], arr[ans[i+1]]) > 0) {
                        int temp = ans[i];
                        ans[i] = ans[i+1];
                        ans[i+1] = temp;
                    }
                }
                else if(arr_status[ans[i]][1] > arr_status[ans[i+1]][1]) {
                    int temp = ans[i];
                    ans[i] = ans[i+1];
                    ans[i+1] = temp;
                }
            }
        }
    }

    /*
    BubbleSort:
    The problem ask us to print the value of the cookies
    from the minimum to the maximum whether there exist '7' or not.
    Thus we should sort the array again.
    */
    for(int t = n; t > n-m; t--) {
        for(int i = n-m; i < t-1; i++) {
            if(arr_status[ans[i]][1] == arr_status[ans[i+1]][1]) {
                if(strcmp(arr[ans[i]], arr[ans[i+1]]) > 0) {
                    int temp = ans[i];
                    ans[i] = ans[i+1];
                    ans[i+1] = temp;
                }
            }
            else if(arr_status[ans[i]][1] > arr_status[ans[i+1]][1]) {
                int temp = ans[i];
                ans[i] = ans[i+1];
                ans[i+1] = temp;
            }
        }
	}

	//output
	for(int i = n-m; i < n; i++) {
            printf("%s\n", arr[ans[i]]);
	}
}

//convert hexadecimal numbers to string
void convert(int k, int i) {
    if(k == 0) return;

    // recursion
    convert(k/10, i);

    //convert each digit of number to the string
    arr[i][string_index] = k % 10 + '0';

    //count the length of the string
    arr_status[i][1] += 1;

    //count the number of '7'
    if(arr[i][string_index] == '7') {
        arr_status[i][0] += 1;
    }
    string_index += 1;
}

// By Utin
```

## Reference