Tävlingsprogrammering/Uppgifter/Soldaterna

Soldaterna - Uppgift 1 - Onlinekvalet till PO 2007

Ett antal soldater står på ett led alla vända mot furiren, när han ger ordern "höger om". Eftersom många av soldaterna har svårt att skilja på höger och vänster blir det mest slumpen som avgör åt vilket håll de vänder sig. Ett exempel visas på första raden i figuren ovan. De soldater som på så sätt hamnar "öga mot öga" med en granne förstår båda två att de vänt sig åt fel håll och gör därför helt om (180 grader), för att kanske hamna öga mot öga med den andra grannen. Denna procedur fortsätter (steg 1 och 2 i figuren) och upphör då inga soldater längre är vända mot varandra (steg 3).

Indata

Den första raden består av heltalet n, där 2 ≤ n ≤ 100, som anger antalet soldater. Den andra raden består av en sträng med n tecken, dår varje tecken är antingen V eller H. Dessa anger åt vilket håll soldatens näsa pekar i utgångsläget.

Utdata

Programmet ska skriva ut hur många steg som behövs från utgångsläget tills lugnet infinner sig.

Exempel: Indata

6

VHVVHV

Exempel: Utdata

3

Lösning

Detta problem kan lösas som en vanlig simuleringsuppgift. Vi simulerar helt enkelt hur soldaterna vänder sig steg för steg och kontrollerar samtidigt om någon vändning överhuvudtaget skett. Om ingen vändning skett har lugnet infinnet sig och vi är klara.

Exempellösningen fungerar så här:

1. Läs in antalet soldater
2. Läs in varje enskild soldat och konvertera riktningen från 'V' och 'H' till -1 respektive 1
3. Utför ett steg där varje soldats nya läge beräknas och spara den nya ställningen
4. Räkna antalet steg som skett
5. Avsluta ifall ingen vändning ägt rum, annars gå tillbaks till punkt 3 och gör ett nytt steg
6. Skriv ut antalet steg som krävdes

Exempellösning i C++:

//Onlinekvalet till PO 2007
//Uppgift 1 - Soldaterna

#include <iostream>
using namespace std;

int  nSold;                        //antalet soldater
int  currSold[102];                //nuvarande konfiguration av soldaterna
char newSold[102];                 //nästa konfiguration av soldaterna

int main(void){
  int i, j, nStep;
  char temp;
  bool running;

  cin >> nSold;                    //läs in antalet soldater

  //---------------- läs in soldaternas lägen -------------------
  for(i = 1; i <= nSold; i++){
    cin >> temp;                   //läs in soldat nr i
    if(temp == 'V'){               //tittar åt vänster...
      currSold[i] = -1;            //...vänster i indexet
    }else{                         //tittar åt höger...
      currSold[i] = 1;             //...höger i indexet
    }
  }
  currSold[0]         = -1;        //placera vänsterstopp
  currSold[nSold + 1] =  1;        //placera högerstopp
  //-----------------------------------------------------------------------

  //---------- loopa tills alla soldater står still -------------------
  nStep = -1;                      //startvärde för antalet steg
  do{
    running = false;               //blir sant om minst en soldat rör sig

    for(i = 1; i <= nSold; i++){   //loopa igenom alla soldater
      j = i + currSold[i];         //soldat nr i tittar på soldat nr j
      if(j + currSold[j] == i){    //om soldat nr j tittar på soldat nr i...
        newSold[i] = -currSold[i]; //...så tittar de på varandra; byt håll!
        running = true;            //...soldater rör sig fortfarande
      }else{                       //annars...
        newSold[i] = currSold[i];  //...stå kvar!
      }
    }
		
    //kopiera in det nya läget till det nuvarande:
    for(i = 1; i <= nSold; i++) currSold[i] = newSold[i]; 

    nStep++;                       //räkna antalet steg
  }while(running);                 //kör tills vi når statiskt läge
  //------------------------------------------------------------------------------

  cout << nStep << "\n";           //printa antalet steg som krävdes
  return 0;
}

En lösning som använder standardbiblioteket.

#include <iostream>
#include <vector>
#include <string>
int main()
{
       const int left = 0, right = 1;
       int movement, count = 0;
       std::vector<int> soldat;
       std::vector<int>::iterator vec_itr;
       std::string::iterator str_itr;
       //Att läsa in antalet soldater behövs ej.
       std::string pos;
       std::cin >> pos;
       //Titta igenom strängen och ge integer-värden, 0 för V och, 1 för H.
       for(str_itr = pos.begin(); str_itr != pos.end(); ++str_itr)
       {
               if (*str_itr == 'V')
                       soldat.push_back(left);
               else
                       soldat.push_back(right);
       }
       //Movement ökar om soldater rör sig. Om movement är lika med 0, rör sig inga soldater.
       do{
               movement = 0;
               //Soldaterna tittar på varandra då soldaten som kommer efter den som                      
               //tittar åt höger tittar åt vänster.
               for(vec_itr = soldat.begin(); vec_itr < (soldat.end()-1); ++vec_itr)
               {
                       if (*vec_itr == 1 && *(vec_itr+1) == 0)
                       {
                               *vec_itr = 0;
                               *(vec_itr+1) = 1;
                               ++vec_itr;
                               ++movement;
                       }
                       
               }
               ++count;
       }while(movement != 0);
       //Eftersom att den gången då inga soldater rör sig räknas som en "count" 
       //minskar vi count med ett vid utskriften,
       std::cout << count-1;
       return 0;
}

En mycket enklare lösning i Java, som baseras på att så länge som minst två soldater tittar på varandra (strängen innehåller "HV") kommer dessa vända sig (byt ut "HV" mot "VH"):

public class Soldaterna {

    public static void main(String[] args) {
        Scanner io = new Scanner(System.in);
        io.nextInt(); //vi bryr oss inte om hur många soldater som finns
        String persons = io.next();
        int count = 0; //antalet vändningar
        while (persons.contains("HV")) { //så länge minst två soldater står bredvid varandra
            persons = persons.replace("HV", "VH"); //vänd soldaterna
            count++;
        }
        System.out.println(count);
    }
}