OR — task - Codeforces

Блог пользователя lovro-sinda

OR — task

Автор lovro-sinda, 12 лет назад, По-английски

The given is N non-negative numbers, select exactly K who provide minimal result of OR operation (binary OR operation).

Input The first line contains an integer N (1 ≤ K ≤ N ≤ 50). The next line contains N integers not exceeding 1000 000 000

Output

Print result of OR operation selected K numbers.

Examples:

entrance

2 2
1 3

output

entrance

6 3
5 2 4 1 7 5

output

Any ideas how to solve it?

bit, croatian - task, math

lovro-sinda
12 лет назад
9

Комментарии (9)

Написать комментарий?

HASP

12 лет назад, скрыть # |

Where I can submit it?

→ Ответить

lovro-sinda

12 лет назад, скрыть # ^ |

It is the task form Croatian contest, but if you want to submit you can use this link https://zatemas.zrs.hr/?app=evaluator&evlshw=solver&cd=Bo%C5%BEo%2F2013%2FDrugi+ogled%2F&evlsolve=Ili That link provide you on task at the evaluator. And you must be register to submit solution.

→ Ответить

HASP

12 лет назад, скрыть # ^ |

← Rev. 2 →

Can you submit this code?

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

long long ans = 1e18, Min, sum = 1e18, mas[60];
bool used[60];

int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++)
		scanf("%d", &mas[i]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			used[j] = 0;
		used[i] = 1;
		ans = mas[i];
		for (int j = 0; j < K; j++) {
			Min = -1;
			for (int k = 0; k < N; k++) {
				if (!used[k] && Min == -1)
					Min = k;
				else if (!used[k] && (mas[i] | mas[k]) < (mas[i] | mas[Min]))
					Min = k;
			}
			ans |= mas[Min];
			used[Min] = 1;
		}
		if (ans < sum)
			sum = ans;
	}
	printf("%I64d\n", sum);
	return 0;
}

→ Ответить

lovro-sinda

12 лет назад, скрыть # ^ |

← Rev. 2 →

16 0.00 OK! Good solution.
0 0.00 Your program printed "383", but it should be "100".
0 0.00 Your program printed "10111", but it should be "10000".
0 0.00 Your program printed "1015805", but it should be "785407".
0 0.00 Your program printed "1245079", but it should be "1234567".
0 0.00 Your program printed "13612917", but it should be "12878913".
0 0.00 Your program printed "62781311", but it should be "12345678".
0 0.00 Your program printed "1004535807", but it should be "999111222".
0 0.00 Your program printed "123723101", but it should be "123456789".
0 0.00 Your program printed "939524095", but it should be "536870911".

16/160 points

→ Ответить

k790alex

12 лет назад, скрыть # |

backtracking should be enough if you prune the search when possible.

→ Ответить

Bekmyrat.A

12 лет назад, скрыть # |

← Rev. 2 →

Could you please submit my solution

→ Ответить

lovro-sinda

12 лет назад, скрыть # ^ |

16 0.00 OK! Good solution.
16 0.00 OK! Good solution.
16 0.00 OK! Good solution.
16 0.00 OK! Good solution.
16 0.00 OK! Good solution.
16 0.00 OK! Good solution.
16 0.00 OK! Good solution.
0 0.00 Your program printed "1004535807", but it should be "999111222".
16 0.00 OK! Good solution.
16 0.00 OK! Good solution.

→ Ответить

Bekmyrat.A

12 лет назад, скрыть # ^ |

Thanks.

→ Ответить

ffao

12 лет назад, скрыть # |

← Rev. 2 →

+24

You can do this using a greedy algorithm. Let 2^x be the highest power of two smaller than or equal to the biggest of the integers in the input.

If there are less than k numbers with bit x not set (easy case): you will be forced to pick at least one number with bit x set, so answer will have bit x set no matter what you do.
If there are k or more numbers with bit x not set: it's always better to ignore all numbers in the input that have bit x set, because by not picking it you always get a smaller answer.

I submitted this solution and it was accepted, but I'll leave the implementation to you.

→ Ответить