| Вопрос: Матрица:выбор элемента | Добавлено: 04.02.05 13:33 |
Автор вопроса:  K-00 | ICQ: 179750444 |
|
Помогите с задачей, пожалуйста.
В квадратную матрицу A порядка n записали n^2 чисел. В ячейку Aij записали число равное произведению ij для всех i, j, изменяющихся от 1 до n. Например, для n=3 матрица A после заполнения имеет вид: 1 2 3 A = 2 4 6 3 6 9. После этого все элементы матрицы выписали на доску в порядке неубывания. Ваша задача найти K-е число в этом списке. Входные данные В первой строке входного файла содержится пара натуральных чисел N, K (1<=N<=10^4; 1<=K<=N^2), разделенных пробелом. Выходные данные В выходной файл выведите единственное число - ответ на поставленную задачу. Пример Ввод 3 4 Вывод 3 |
| Ответы | Всего ответов: 3 |
|
Номер ответа: 1 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #1 | Добавлено: 04.02.05 19:54 |
|
Какие ограничения на N? Если небольшие, то можно в лоб:
#include <stdio.h> #include <stdlib.h> #define MAX_N 20 #define INPUT_FILE "input.dat" #define OUTPUT_FILE "output.dat" int cmp(const void *p1, const void *p2){ int i1 = *(int *)p1; int i2 = *(int *)p2; if(i1<i2){ return -1; } else if(i1==i2){ return 0; } else return 1; } int main(){ int a[MAX_N][MAX_N], b[MAX_N*MAX_N], n, m, k, j, cn=0, min, t; FILE *f; f = fopen(INPUT_FILE, "r"  ;
fscanf(f, "%d %d", &n, &m); fclose(f); for(k=1; k<=n; k++){ for(j=1; j<=n; j++){ b[cn++] = k*j; } } qsort(b, n*n, sizeof(int), &cmp); f = fopen(OUTPUT_FILE, "w" ;
fprintf(f, "%d", b[m-1]); fclose(f); return 0; } |
||
|
Номер ответа: 2 Автор ответа: K-00 ICQ: 179750444 Вопросов: 7 Ответов: 20 |
Профиль | | #2 | Добавлено: 07.02.05 14:30 |
|
Sharp
ограничение времени на тест: 1 сек. ограничение памяти на тест: 640 KB. 32 битный компилятор: [X] 1<=N<=10^4; 1<=K<=N^2 так что в лоб нельзя) |
||
|
Номер ответа: 3 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #3 | Добавлено: 07.02.05 20:02 |
|
Вышеуказанный алгоритм имеет сложность O(N^2), зато жрет N^2*4 байт памяти, т.е. 400 метров в максимальном случае (10^4; 10^8).
Если ставить перед собой цель минимизации памяти, тогда можно предложить такой алгоритм сложности K^(3/2) (т.е. в худшем случае N^3): #include <stdio.h> int main(){ int n, k; scanf("%d %d", &n, &k); int cn=1, res=0; for(cn=1; cn<=n*n; cn++){ for(int i=1; i<=n && i*i<=cn; i++){ if(cn%i == 0){ if(cn/i == i){ res++; } else{ res+=2; } //printf("res = %d\n", res); if(res>=k){ printf("Answer: %d\n", cn); return 0; } } } } return 0; } Этот алгоритм почти не жрет памяти, но весьма требователен к процу. И вообще я сомневаюсь в возможности существования эффективного переборного алгоритма для этой задачи при 10^4; 10^8, разве что комбинаторикой какой-нибудь... Надо еще подумать. |
||
Страница: 1 |