• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Warrior

[R1] De autocarro ou bicicleta?

8 mensagens neste tópico

Título:

Autocarro ou bicicleta?

Objectivo:

O João gosta muito de andar de bicicleta, e faz tudo para que as suas viagens sejam o mais agradável possível.

Contudo, a sua cidade está um pouco degradada, de modo que há zonas da cidade que ele prefere evitar, e como tal desloca-se de autocarro. Como tem uma bicicleta toda XPTO, pode transportá-la no autocarro, e é muito frequente vê-lo, no mesmo percurso, a fazer partes de bicicleta e outras de autocarro. Num dado percurso, ele pode até fazê-lo todo de bicicleta ou todo de autocarro.

O João elaborou uma lista dos segmentos do seu percurso, e atribuiu a cada um uma classificação: positiva caso goste de o percorrer, negativa em caso contrário (não existem valores a 0).

Arranjou também um mapa dos autocarros da cidade, de modo a poder utilizá-los quando pretende evitar uma parte do percurso.

O João pretende que o ajudemos a saber, num dado percurso, qual o valor máximo que pode obter da soma das classificações das partes que vai percorrer.

Explicação de Input

Linha 1 - um inteiro N (2 <= N <= 100000), representando o número de partes do percurso.

Linhas 2 a N+1 - N inteiros (positivos ou negativos), a classificação de cada um dos segmentos.

Linha N+2 - Um inteiro, K (0 <= K <= 1000) representando o número de rotas de autocarro naquele percurso.

Linhas N+3 a N+3+K - K pares de inteiros, a e b (1 <= a < b <= N+1), representando os percursos dos autocarros. Caso b=N+1, representa o destino do João.

Exemplo de input/output

Input:

5

6

-10

-2

4

1

1

2 3

Output:

9

5 segmentos, 6 -10 -2 4 1, e uma viagem de autocarro, entre 2 e 3 (portanto, saltando o segmento -10).

O Caminho máximo é percorrendo o percurso 6, apanhando o autocarro para -2, e percorrer até ao final, logo fazendo 6-2+4+1 = 9

Input

3

-5

-3

-4

1

1 4

Output:

0

O João não anda de bicicleta neste percurso.

Input:

5

6

10

-2

4

1

1

2 3

Output:

19

O João não anda de autocarro neste percurso.

Material de apoio:

Não aplicável.

Restrições:

Não aplicável.


Discussão do problema em:

http://www.portugal-a-programar.pt/index.php?showtopic=16897

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Here it goes in C++ :P

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100010

struct Segmento {
int pontos;
vector<int> buses;
} seg[MAX];

int dp[MAX];

int main()
{
int N , K , i , a , b;
scanf("%d",&N);
for (i = 1 ; i <= N ; i++) {
	scanf("%d" , & seg[i].pontos );
	seg[i].buses.clear();
}
scanf("%d", & K );
for (i = 0 ; i < K ; i++) {
	scanf("%d %d" , & a , & b );
	seg[a].buses.push_back(b);
}
dp[N+1] = 0;
for (i = N ; i >= 1 ; i--)
{
	dp[i] = seg[i].pontos + dp[i+1];
	for (size_t j = 0 ; j < seg[i].buses.size() ; j++)
		dp[i] = max( dp[i] , dp[ seg[i].buses[j] ] );
}
printf("%d\n", dp[1] );
return 0;
}

Solução com programação dinâmica em O( N+K ). Penso que funciona bem...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui fica em Haskell :P

import Data.Array

main = getContents >>= print . proc . lines

proc (n:resto) = calc n' $ zip [1..] $ reverse $ zip segs' buses'
  where n' = read n
        (segs, (_:buses)) = splitAt n' resto
        segs' = map read segs
        buses' = elems $ accumArray aggr [] (1,n') $ map (f.words) buses
        aggr = flip (
        f [a,b] = (read a, n' + 1 - read b)

calc n ll = r!n
  where r = listArray (0,n) ( 0 : map f ll)
        f (i,(v,b)) = maximum $ ((r!(i-1))+v) : map (r!) b

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui fica em Scheme: :P

(let* ((n-de-percursos (read))
      (percursos 
       (letrec ((inputs
            (lambda (acum acum-lista)
            (cond 
              ((= acum n-de-percursos) acum-lista)
              (else (inputs (add1 acum) (append acum-lista (list (read)))))))))
      (inputs 0 '())))
      
      (n-autocarros (read)) 
      (autocarros 
        (letrec ((inputs
            (lambda (acum acum-lista)
            (cond 
              ((= acum n-autocarros) acum-lista)
              (else (inputs (add1 acum) (append acum-lista (list (cons (read) (read)))))))))) 
      (inputs 0 '()))))

  (letrec ((soma 
            (lambda (acum acum-final)
            (cond 
              ((= acum n-de-percursos) (+ acum-final (list-ref percursos (sub1 acum)))) 
              ((> acum n-de-percursos) 0)
              (else
               (if (< (list-ref percursos (sub1 acum)) 0)
                   (if (assoc acum autocarros)
                       (soma (cdr (assoc acum autocarros)) acum-final)
                       (soma (add1 acum) (+ acum-final (list-ref percursos (sub1 acum)))))
                   (soma (add1 acum) (+ acum-final (list-ref percursos (sub1 acum))))))))))
           
    (soma 1 0))) 

Provavelmente, com mais algum trabalho, podia ser encurtada.. Mas pronto. :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui vai em Python:

N=input()
classificacoes=[]
for i in range(0,N): classificacoes.append(input())

K=input()
rotas=[]
for i in range(0,K):
    x=raw_input().split(' ')
    rotas.append(int(x[0]))
    rotas.append(int(x[1]))

final=classificacoes

a=0
while a<2*K:
    total=0
    for i in range(rotas[a]-1,rotas[a+1]-1): total+=classificacoes[i]
    if total<0:
for i in range(rotas[a]-1,rotas[a+1]-1): final[i]=0
    a+=2

t=0
for z in final: t+=z
print t

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui esta a minha solução em java! Acho que esta correcta! Demorou porque andei pela net a ver se aprendia programação dinâmica! Ja agora poderiam me dizer se esta  de acordo com a programação dinâmica?? E se passa nos testes claro ;)

public class Main {
    
    private static int[] segmentos;
    private static int[][] percursosA;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
      
        int n = sc.nextInt();
        segmentos = new int[n];
        for(int i = 0; i < n ; i++)
            segmentos[i] = sc.nextInt();
        
        int k =  sc.nextInt();
        percursosA = new int[k][2];
        for(int i = 0; i < k ; i++){
            percursosA[i][0] = sc.nextInt();
            percursosA[i][1] = sc.nextInt();
        }
        
        System.out.println(classificacao());
        
    }

    private static int classificacao() {
        int[] cost = new int[segmentos.length + 1];
        cost[0] = 0;
        for(int i = 1; i < cost.length; i++)
            cost[i] = cost[i-1] + segmentos[i -1];
       
        for(int j = 0; j < percursosA.length; j++){
            
            for(int i = 1; i < segmentos.length + 1; i++){
                
                if( cost[i] < segmentos[i - 1] + cost[i - 1])
                    cost[i] =  segmentos[i - 1] + cost[i - 1];
                
                if( percursosA[j][1] == i  ){
                    
                   if(cost[i] < cost[percursosA[j][0] - 1  ]  + segmentos[i -1])
                       cost[i] = cost[percursosA[j][0] - 1 ] + segmentos[i -1];
                
                }
                        
            }
            
            if( percursosA[j][1] == cost.length  ){
                int i = cost.length - 1;
                if(cost[i] < cost[percursosA[j][0] -1] )
                       cost[i] = cost[percursosA[j][0] -1 ] ;
                
            }
        }
   
        return cost[cost.length - 1];
    }

}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mais uma solução em Java, esta baseada no algoritmo de caminhos mais longos para DAGs (Directed Acyclic Graphs).

import java.util.LinkedList;
import java.util.Scanner;

public class BicicletaOuAutocarro {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] val = new int[n];
    for (int i = 0; i < val.length; i++) {
      val[i] = sc.nextInt();
    }
    LinkedList<Integer>[] origs = (LinkedList<Integer>[])new LinkedList[n+1];
    for (int i = 0; i < origs.length; i++) {
      origs[i] = new LinkedList<Integer>();
    }
    int m = sc.nextInt();
    for (int i = 0; i < m; i++) {
      int orig = sc.nextInt() - 1;
      int dest = sc.nextInt() - 1;
      origs[dest].add(orig);
    }
    int[] maxs = new int[n+1];
    for (int i = 1; i < maxs.length; i++) {
      maxs[i] = maxs[i-1] + val[i-1];
      for (int j : origs[i]) {
        maxs[i] = Math.max(maxs[i], maxs[j]);
      }
    }
    System.out.println(maxs[n]);
  }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Memoization em C++. É suficientemente rápido?

#include <cstdio>
#include <vector>
#include <climits>

#define MAXSEGS 100000
#define MAXBUSES 1000

using namespace std;

typedef struct
{
vector<int> dests;
} Buses;

int segments[MAXSEGS], memo[MAXSEGS], N, K;
bool buses[MAXBUSES];
Buses bus[MAXBUSES];

void input ()
{
int from = 0, to = 0;

for (int k = 0; k < MAXSEGS; k++)
	memo[k] = -1;

for (int k = 0; k < MAXBUSES; k++)
	buses[k] = false;

scanf ("%d", &N);
for (int i = 0; i < N; i++)
	scanf ("%d", &segments[i]);

scanf ("%d", &K);
for (int i = 0; i < K; i++)
{
	scanf ("%d", &from);
	buses[from - 1] = true;
	scanf ("%d", &to);
	bus[from - 1].dests.push_back (to - 1);
}
}

int recur (int i)
{
int b = 0, w = 0;
vector<int>::iterator it;

if (i > N - 1)
	return 0;

if (memo[i] > - 1)
	return memo[i];

if (buses[i])
	for (it = bus[i].dests.begin (); it < bus[i].dests.end (); it++)
		b = max (b, recur (*it));
else
	b = INT_MIN;

w = recur (i + 1) + segments[i];
memo[i] = max (b, w);

return memo[i];
}

int main ()
{
input ();
printf ("%d\n", recur (0));

return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora