Problema

Trebuie sa cumparam 100 de oua cu fix 100 de lei.
Un ou de gaina costa 0.5 lei, unul de rata 2.5 si unul de gasca 10 lei.
Cate oua din fiecare fel o sa luam?

9 comentarii

  1. 90 de oua de gaina + 6 oua de rata + 4 oua de gasca

  2. Minunat! Felicitari!😀

  3. #include <cstdio>
    #include <map>
    #include <hash_map.h>
    #define N 101
    using namespace std;
    
    
    map<double, int> dp[N][N][N];
    
    int n = 100;
    
    int main()
    {
        
        dp[1][0][0][0.5] = 1;
        dp[0][1][0][2.5] = 1;
        dp[0][0][1][10] = 1;
    
        int i,  j, t;
        double k;
    
        for(i = 2; i <= n; ++i)
    	for(j = 0; j + i <= n; ++j)
    	    for(t = 0; i + j + t <= n; ++t)
    		for(k = 0.0; k <= 100; k += 0.5)
    		    dp[i][j][t][k] = dp[i-1][j][t][k - 0.5] | dp[i][j-1][t][k - 2.5] | dp[i][j][t-1][k - 10.0];
    
    
        for(i = 1; i <= n; ++i)
    	for(j = 1; j <= n; ++j)
    	    for(t = 1; t <= n; ++t)
    		if(i + j + t == n)
    		    if(dp[i][j][t][n] == 1) 
    		{
    		    printf("%d %d %d\n", i, j, t);
    		    return 0;
    		}
    
        return 0;
    }
    

    // sta vreo 20 secunde… dar macar isi face treaba😛

  4. in 20 de secunde? nu e cam mult?😛
    ia sa te vad: optimizeaza-l pentru 1 secunda.

  5. #include <cstdio>
    #include <cmath>
    #include <map>
    #include <hash_map.h>
    #define N 102
    #include <bitset>
    using namespace std;
    
    
    bool dp[N][N][N][4*N];
    
    
    const double D = 2;
    int n = 100;
    
    int main()
    {
        
        dp[1][0][0][int(0.5 * D)] = 1;
        dp[0][1][0][int(2.5 * D)] = 1;
        dp[0][0][1][int(10 * D)] = 1;
    
        
        int i,  j, t;
        double k;
    
        for(i = 2; i <= n; ++i)
    	for(j = 0; j + i <= n; ++j)
    	    for(t = 0; i + j + t <= n; ++t)
    		for(k = 0.0; k <= 100; k += 0.5)
    		    dp[i][j][t][int(k * D)] = dp[i-1][j][t][int((k - 0.5) * D) ] | dp[i][j-1][t][int((k - 2.5) * D)] | dp[i][j][t-1][int((k - 10.0) * D)];
    		
    
    	
        for(i = 1; i <= n; ++i)
    	for(j = 1; j <= n; ++j)
    	    for(t = 1; t <= n; ++t)
    		if(i + j + t == n)
    		    if(dp[i][j][t][int(n * D)] == 1) 
    		{
    		    printf("%d %d %d\n", i, j, t);
    		    return 0;
    		}
    
        return 0;
    }
    

    Asta la mine intra in 1.2 secunde

  6. poti si in Java? :))

  7. evident😛 uite cel mai rapid de pana acum: O(n^2), intra instant

    import java.util.*;
    
    public class Oua
    {
        public static void main(String[] args)
        {
    	new Oua().go();
        }
        
        void go()
        {
    	int n = 100;
    	double S = 100;
    
    	int i, j, k;
    	boolean ok = true;
    
    	for(i = 1; i <= n && ok; ++i)
    	    for(j = 1; i + j < n && ok; ++j)
    	    {
    		k = n - i - j;
    		double s = i * 0.5 + j * 2.5 + k * 10.0;
    		if(Math.abs(s - S) < 1e-10) // s == S
    		{
    		    System.out.println(i + " "  + j + " " + k);
    		    ok = false;
    		}
    	    }
    
        }
    
    }
    
  8. si in ruby😀

    
    n = 100;
    s = 100.0;
    
    ok = true;
    
    i = 1;
    
    while i < n && ok
        j = 1;
        while i + j < n && ok
    	k = n - i - j;
    	ss = i * 0.5 + j * 2.5 + k * 10.0;
    	if (s - ss).abs < 1e-10
    	    print "" + i.to_s + " " + j.to_s + " " + k.to_s + "\n";
    	    ok = false;
    	end	
    	j += 1;
    	
        end 
    
        i += 1;    
    end
    
  9. imi place cum arata ruby😀


Comments RSS TrackBack Identifier URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s