Jump to content
Sign in to follow this  
skiller10

[RESOLVIDO] USACO - Barn Repair

Recommended Posts

skiller10

Hey,

Hoje já resolvi os último dois problemas do capítulo 1.2 sem dificuldade (Palindromic Squares, Dual Palindromes), e já fiz o Mixing Milk, que achei muito fácil, mas agora no barn repair:

http://ace.delos.com/usacoprob2?a=KoP9blnfmFd&S=barn1

não estou a ver como resolver este problema, pelo que percebi dado o numero máximo de tábuas, temos que calcular o numero de estabulos cobertos, com o tamanho mínimo das tábuas, deixando obrigatoriamente todos os estábulos com vacas cobertos.

Acho que já sei como fazer, mas deixo para amanhã :)

Alguma dica? :S

Edit: Problema resolvido com sucesso!


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
xtrm0

Nesse problema tens por exemplo a seguinte representaçao

|1|2|3|4|5|6|7|8|9|10| <-- POSIÇAO(só para explicar)

|  |v|  |  |  |  |  |v|  |v  | <-- Estábulos

v-estabulo com vaca

Se te dissessem que tinhas 2  tabuas de madeira, tinhas que escolher um comprimento para essas duas tábuas, que ocupasse o minimo numero de estabulo vazios possiveis, mas que tapasse todos os estabulos com vacas.

Para o exemplo terias:

|  |v|  |  |  |  |  |v|  |v  |

    1                  22222

O um seria a primeira tabua com comprimentos 1,

e o dois seria a segunda tabua com comprimento 3.

E a resposta seria 3+1 (4).

Fica para ti descobrires como chegar à resposta. Dou-te uma pista.

(10-8)+1 < (8-2)+1


<Signature goes here>

Share this post


Link to post
Share on other sites
skiller10

Deixo aqui o código, para alguém que tenha dúvidas, acho que está bem organizado e é eficiente:

/*
ID: joao_m-1
PROG: barn1
LANG: C++
*/
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <assert.h>
using namespace std;
//Estrutura para guardar estado do estabulo:************************************
struct Stall{
    bool ocup;       
};
//******************************************************************************
int main(void)
{
    /**/ifstream fin("barn1.in");
    /**/ofstream fout("barn1.out");
    /**/assert(fin!=NULL && fout!=NULL);
    /**/int tabuas, total_stalls, ocup_stalls, result;
    /**/int id, prim, ult, k=0;
    /**/vector <int> gaps;
    
    //Input da quantidade de tabuas a comprar, numero total de estabulos e 
    //numero de estabulos ocupados:
    fin >> tabuas >> total_stalls >> ocup_stalls;
    
    /**/Stall stabs[total_stalls];//Array para guardar os estados dos estabulos;
    
    //Inicializar os estabulos todos como vazios:
    for(int i=0; i<total_stalls; i++)
        stabs[i].ocup = false;
            
    //Input dos estabulos que estao ocupado:
    for(int i=0; i<ocup_stalls; i++){
       fin >> id;
       stabs[id-1].ocup = true;
    }
    
    //Verificar se o numero de tabuas e maior que o numero de estabulos ocupados:
    if(tabuas>=ocup_stalls){
        fout << ocup_stalls << endl;
        return 0;
    }
     
    //Calcular diferença entre primeiro e ultimo estabulo ocupado:
    for(int i=0; i<total_stalls; i++)
        if(stabs[i].ocup==true){
            prim = i;        
            break;
        }
    for(int i=total_stalls-1; i>=0; i--)
        if(stabs[i].ocup==true){
            ult = i;  
            break;
        }
    result = ult - prim;
    
    //Ver gaps:
    for(int i=prim, gapaux=0; i<=ult; i++)
        if(stabs[i].ocup==false)
           gapaux ++;                         
        else if(gapaux>0){
                gaps.push_back(gapaux);
                k ++;
                gapaux = 0;         
              } 
    
    //Ordenar gaps:
    for(int i=0; i<k-1; i++)
        for(int j=i+1, aux; j<k; j++)
            if(gaps[i]<gaps[j]){
                aux = gaps[i];
                gaps[i] = gaps[j];
                gaps[j] = aux;             
            }
            
    //Excluir 'tabuas' maiores gaps do result:
    for(int i=0; i<tabuas-1; i++)
        result -= gaps[i];

    //Imprimir resultado:
    fout << result+1 << endl;
    
    //system("PAUSE");
    return 0;
}


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

o teu algoritmo de ordenação, bubble sort, é bastante lento. em problemas mais exigentes, convém usar algo melhor como o quicksort ou mergesort.

Vocês deveriam conhecer a classe de algoritmos da stl do c++ de ponta a ponta. Têm lá um algoritmo de ordenação muito eficiente que não dá trabalho nenhum em usar.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Localhost

Quando eu ainda não utilizava C++.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX 210

void input();
void output(int);
int solve();
int comp(const void *, const void *);

int farm[MAX], dif[MAX], boards, stalls, cows;

void input() {
int aux;
FILE *fin = fopen("barn1.in","r");
fscanf(fin,"%i %i %i", &boards, &stalls, &cows);
for(aux = 0; aux < cows; aux++) {
	fscanf(fin,"%i", &farm[aux]);
	farm[aux + 1] = INT_MAX;
}
qsort(farm,cows,sizeof(int),comp);
}

int comp(const void *a, const void *b) {
return (*(int *)a - (*(int *)b));
}

int solve() {
int aux;
int used = 1;
int less = (farm[cows - 1] - farm[0] + 1);
for(aux = 1; aux < cows; aux++) {
	dif[aux - 1] = (farm[aux] - farm[aux - 1] - 1);
}
qsort(dif,cows,sizeof(int),comp);
aux = cows - 1;
while(used < boards && aux > 0) {
	less -= dif[aux];
	aux--;
	used++;
}
return less;
}

void output(int solved) {
FILE *fout = fopen("barn1.out","w");
fprintf(fout,"%i\n", solved);
fclose(fout);
}

int main(void) {
int solved = 0;
input();
solved = solve();
output(solved);
exit(0);
}


here since 2009

Share this post


Link to post
Share on other sites
skiller10

Neste problema acabei por usar o bubble sort (sinceramente nem sabia que se chamava assim, fiz porque sempre utilizei este algoritmo para ordenar. Ontem à noite já estive a começar a implementar o qsort, vou tentar ir estudando o STL B)

Obrigado pelas dicas ;)


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
skiller10

Nao tenho a certeza mas acho que podes usar em C e C++, porque faz parte da biblioteca stdlib.h


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

mogers: O Quicksort pode ser usado em qualquer linguagem ?

Desde que implementes um algoritmo, podes usa-lo em praticamente todas as linguagens.

O qsort da <stdlib> do C implementa o quicksort. O sort da <algorithm> do c++ implementa uma versão melhorada e para além disso, é mais simples de usar.

Tu tás a programar em C ou pascal? Em pascal terias de implementá-lo "à mão". Numa pesquisa rápida no google seria algo como

procedure quicksort(l, r: integer);
var 
  i, j, pivot, pom: integer;
begin
  i := l; j := r;
  pivot := akt[(l + r) div 2];
  repeat
    while (i < r) and (akt[i] < pivot) do i := i + 1;
    while (j > l) and (pivot < akt[j]) do j := j - 1;
    if i <= j then 
    begin
      if i < j then
      begin
        pom := akt[i];
        akt[i] := akt[j];
        akt[j] := pom;
      end;
      i := i + 1;
      j := j - 1
    end
  until i > j;
  if j > l then quicksort(l, j);
  if i < r then quicksort(i, r)
end;

PS: não adianta decorar o código de um algoritmo. Se perceberem verdadeiramente como um algoritmo funciona, implementam-no de cabeça sem problema nenhum. Se apenas decorarem o código, há uma probabilidade grande de não o saberem usar numa competição.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
JoaoSantos95

Eu costumo resolver problemas idênticos com métodos diferentes, na hora crio método novo (claro que a base usada é igual às outras bases de fazer aquilo mas meto sempre algo de novo). A única coisa que já uso sempre que me aparece um determinado problema que o peça (neste caso, problemas de ordenação) é o bubblesort mas o meu nível de programação ainda é de principiante e o estão a testar é se sei fazer o problema e não tanto o tempo que o problema demora a processar (claro que se for um concurso do nível da ONI ai, obviamente, que já têm um maior "rigor" no que toca ao tempo de resposta).

Sim, este ano ainda estou a programar em Pascal, devo mudar no Verão visto que só para o ano começo com C

btw o que é o akt no teu código, Miguel ?

Share this post


Link to post
Share on other sites
mogers

O akt é o array de inteiros, o código n é meu, como disse, procurei no google. já nao uso pascal ha mt mt tempo  ;)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
JoaoSantos95

Como ele não declarou o array decidi perguntar visto que podia ser alguma instrução que ainda não aprendi

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.