Zadanie Losy ILOCAMP

Question

Siema, robilem sobie zadanka na pocwiczenie ogolnej algorytmiki i utknalem w pewnym zadaniu. Moje podejscie wydaje sie byc dobre, natomist dostaje tylko 10%. Pomoze ktos w znalezieniu bledu?

https://szkopul.edu.pl/problemset/problem/5BwD26NEDhLd9c6ypF5zJfUt/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

struct bin {
	int wyg, prz;
};

bool f(bin a, bin b) {
	return ((unsigned long long)a.wyg * (b.wyg + b.prz) >
			 (unsigned long long)b.wyg * (a.wyg + a.prz));
}

bin arr[10001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, g;
	cin >> n >> g;

	for (int i = 1; i <= n; i ++)
		cin >> arr[i].wyg >> arr[i].prz;

	// sortuje wzgledem najwiekszego stosunku
	// wygranych losow do wszystkich losow
	sort(arr + 1, arr + n + 1, f);

	/* for (int i = 1; i <= n; i ++)
		cout << arr[i].wyg << ' ' << arr[i].prz << '\n'; */

	unsigned long long los = 0;
	for (int i = 1; i <= n; i ++) {
		if (g == 0)
			break;

		if (arr[i].wyg > 0) {
			los += (min(g, arr[i].wyg) + arr[i].prz);
			g -= min(g, arr[i].wyg);
		}
	}

	if (g == 0)
		cout << los;
	else
		cout << "NIE";
}

 

Comments

to jest dp, gdzie dp[i] to minimalna liczba losów które trzeba kupić żeby zagwarantować wylosowanie i losów wygrywających

---

wywala te same bledy, pomimo, ze robie zupelnie inna metoda: (wynik to 30/100)

#include <bits/stdc++.h>

using namespace std;

struct bin {
	int a, b;
};

bin arr[10001];
unsigned long long dp[1001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, g;
	cin >> n >> g;

	for (int i = 1; i <= n; i ++)
		cin >> arr[i].a >> arr[i].b;

	for (int i = 1; i <= g; i ++) {
		bin mn = {INT_MAX, 0};

		for (int j = 1; j <= n; j ++) {
			if (arr[j].a > 0 and arr[j].b + 1 < mn.a)
				mn = {arr[j].b + 1, j};
		}

		if (mn.a != INT_MAX) {
			dp[i] = dp[i - 1] + mn.a;
			arr[mn.b].a --, arr[mn.b].b = 0;
		}

	}

	if (dp[g])
		cout << dp[g];
	else
		cout << "NIE";
}

 

---

Nie wygląda to za bardzo na dp bo licząc dp[i] korzystasz tylko z dp[i-1]. Rozwiązanie jest podobne do problemu plecakowego

---

@polandonion, A jak byś dodał jeszcze kolejny warunek na sortowanie. Najmniejsza liczba przegrywających a drugi warunek (mniej znaczący) to największa liczba wygranych.

Ale i to pewnie nie wystarczy.

---

masz na myśli stopień trudności wymyślenia rozwiązania, czy jego implementacji?

 

stopień trudności zadania, a za tym idzie ciekawszy, trudniejszy kod do zrealizowania.