Zadanie z reszta podołasz?

Question

Od pewnego czasu podejmuje się różnorakich zadań zwiazanych z programowaniem aby rozwinąć swoje umiejętności trafiłem na zadanko które wymaga trochę główkowania :)

Dziś trochę nad nim posiedziałem lecz nic z tego nie wyszło jutro oczywiście podejmę się go jeszcze raz a mimo co zostawiam was z nim.(Jeżeli komuś się nudzi w nocy :P)

Kodami pochwalcie się w komentarzach :)

http://zapodaj.net/dc304d26873e5.png.html

Answer 1

#include <iostream>

using namespace std;

int main()
{
    int n,a,b,x,w;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        x=b-a;
        w=0;
        if(x>=5){
            w=x/5;
            x%=5;
        }
        if(x>=4){
            w+=x/4;
            x%=4;
        }
        if(x>=1){
            w+=x/1;
            x%=1;
        }
        cout<<w<<endl;
    }

    return 0;
}

 

Comments

Zachlan tu nie dziala, 8 Twoj program wyda monetami 5 1 1 1 a powinien 4 i 4. Oprocz tego a i b powinny byc przechowywane w long longach, wiec w i x pewnie tez powinny byc long longami :)

---

Fakt, powiem szczerze, że program wykonałem na szybko i nie pokusiłem się o sprawdzenie jego poprawności dla innych testów ;) Dzięki za zwrócenie uwagi, poprawię ;)

Answer 2

Tak na szybko, juz mi sie nie chce tego kodowac.

obliczamy reszte: czyli reszta=kwota_jasia - cena_roweru

liczba_monet=0;

oczywiscie minimalna ilosc monet bedzie przy monetach 5-zlotowych, wiec liczymy ile jestesmy w stanie wyplacic w 5zl:

liczba_monet += (reszta-(reszta%5) )/5;

reszta = reszta%5; //pozostala reszta do wydania

Teraz to samo robimy dla monet 2-zlotowych:

liczba_monet += (reszta-(reszta%2) )/2;

reszta = reszta%2;

liczba_monet += reszta; //bo zostaly monety 1-zlotowe, wiec mnozymy razy jeden pozostala reszte (czyli nie zmieniamy nic : D )

Jutro jeszcze zobacze czy dobrze mysle...

Comments

Twoje rozwiazanie jest zle o tyle, ze zakladasz nominaly 1, 2, 5, dla ktorych strategia zachlanna dziala. Dla liczb 1,4,5 strategia zachlanna nie dziala. Jesli chcemy wydac 8 zlotych, to zachlannie wydamy 5 1 1 1 a optymalnie jest 4 i 4.

---

Faktycznie, pomyliłem 2 z 4. No w takim wypadku wszystko leży :c

Answer 3

#include <cstdio>
using namespace std;
int main(){
	int tab[10000];//, pop[10000];
	for(int i = 1; i < 10000; i++){
		// pop[i] = -1;
		tab[i] = 100000;
	}
	tab[0] = 0;
	// pop[0] = 0;
	for(int i = 0; i < 200; i++){
		if(tab[i+1] > tab[i]+1){
			tab[i+1] = tab[i] + 1;
			// pop[i+1] = 1;
		}
		if(tab[i+4] > tab[i]+1){
			tab[i+4] = tab[i] + 1;
			// pop[i+4] = 4;
		}
		if(tab[i+5] > tab[i]+1){
			tab[i+5] = tab[i] + 1;
			// pop[i+5] = 5;
		}
	}
	
	// for(int j = 0; j < 20; j++){
	// 	for(int i = 0; i < 200; i+= 20){
	// 		printf("tab[%d] = %d\n", i+j, tab[i+j]);
	// 	}
	// }
	int T;
	scanf("%d", &T);
	while(T--){
		long long a, b;
		scanf("%lld%lld", &a, &b);
		a = b - a;
		if(a <= 20) printf("%d\n", tab[a]);
		else{
			printf("%lld\n", (a/20 - 1)*4 + tab[a%40]);
		}
	}
	return 0;
}

To jest jakas tam moja bzdura, ktora sklecilem przed spaniem. Przykladowe z tresci przechodzi, wiecej zbytnio nie testowalem, ale wydawalo mi sie to nie byc totalnie zle. Napisane strasznie niechlujnie, ale to idzie poprawic :)

Comments

Błędne :) Działa dla podstawowych lecz na 100 różnych juz nie :)

Na wejsciu musze być wszystkie liczby a potem dopiero wyjscie

czyli

3

100 99 (wprowadzamy wszystkie?

a potem pokazuje się wynik dopiero wszystkich 3.

---

Nigdzie nie ma napisanego, że najpierw wejścia wszystkie podać, a dopiero później wyjścia. Jeśli program dobrze zlicza to bez różnicy czy najpierw dane będą wszystkie wpisane, a dopiero później wyświetlane czy na przemian, gdyż wejście i wyjście jest takie same w obu przypadkach, ale jeśli chcesz mieć tak jak mówisz to nie widzę problemu by przechować wyniki w zmiennych, a później je wypisać - to sam możesz zrobić.

---

Tylko mówie:D

---

To tak samo jak ja :)

Answer 4

To co wczoraj w nocy napisalem rzeczywiscie mialo blad. Tutaj poprawiona wersja. Mam nadzieje, ze tym razem uda sie i nie bedzie bledna :)

#include <cstdio>
#define MAX 100
using namespace std;
int main(){
	long long tab[MAX+10];
	for(int i = 1; i < MAX; i++){
		tab[i] = MAX;
	}
	tab[0] = 0;
	for(int i = 0; i < MAX; i++){
		if(tab[i+1] > tab[i]+1){
			tab[i+1] = tab[i] + 1;
		}
		if(tab[i+4] > tab[i]+1){
			tab[i+4] = tab[i] + 1;
		}
		if(tab[i+5] > tab[i]+1){
			tab[i+5] = tab[i] + 1;
		}
	}
	int T;
	scanf("%d", &T);
	while(T--){
		long long a, b;
		scanf("%lld%lld", &a, &b);
		a = b - a;
		if(a <= 20){;
			printf("%d\n", tab[a]);
		}
		else{
			printf("%lld\n", (a/20 - 1)*4 + tab[a%20+20]);
		}
	}
	return 0;
}