naquo

OIA 2014 - Nivel 3 Problema 1 - "Trazas de cobre"

Jul 29th, 2015
243
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.82 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include "pistas.h"
  3.  
  4. /* Descripción del algoritmo
  5.  *
  6.  *   La idea es iterar buscando leds y controles para conectar que estén a N
  7.  *   distancia, N se incrementa en cada pasada y el algoritmo corta cuando no
  8.  *   quedan leds o controles
  9.  */
  10. int leds = 0;
  11. int par = 0;
  12. int controles = 0;
  13. int tamanio_cadena = 0;
  14. int* soluciones;
  15. char* placa;
  16.  
  17. void intentar_conexion(int indice_control, int indice_led) {
  18.     if(es_led(indice_led)) {
  19.         soluciones[par * 2] = indice_control + 1;
  20.         soluciones[par * 2 + 1] = indice_led + 1;
  21.         placa[indice_control] = 'U';
  22.         placa[indice_led] = 'U';
  23.         par++;
  24.         leds--;
  25.         controles--;
  26.     }
  27. }
  28.  
  29. int normalizar(int indice) {
  30.     return abs(indice) % tamanio_cadena;
  31. }
  32.  
  33. int es_led(int indice) {
  34.     return placa[indice] == 'L';
  35. }
  36.  
  37. int es_control(int indice) {
  38.     return placa[indice] == 'C';
  39. }
  40.  
  41. int contar() {
  42.     char* c;
  43.     for(c = placa; *c != '\0'; c++) {
  44.         tamanio_cadena++;
  45.         if(*c == 'C') {
  46.             controles++;
  47.         } else {
  48.             // Tiene que ser un led
  49.             leds++;
  50.         }
  51.     }
  52. }
  53.  
  54. int conecta(char cadena[], int pares[]) {
  55.     // Aqui debe programar la solucion al problema.
  56.     placa = cadena;
  57.     soluciones = pares;
  58.     contar();
  59.     {
  60.         int i;
  61.         int distancia;
  62.         for(distancia = 1;;distancia++) {
  63.             if(!controles || !leds) {
  64.                 break;
  65.             }
  66.             for(i = 0; i < tamanio_cadena; i++) {
  67.                 if(es_control(i)) {
  68.                     intentar_conexion(i, normalizar(i + distancia));
  69.                     if(es_control(i)) {
  70.                         intentar_conexion(i, normalizar(i - distancia));
  71.                     }
  72.                 }
  73.             }
  74.         }
  75.     }
  76.     return par;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment