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[redigera]
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:
- Läs in antalet soldater
- Läs in varje enskild soldat och konvertera riktningen från 'V' och 'H' till -1 respektive 1
- Utför ett steg där varje soldats nya läge beräknas och spara den nya ställningen
- Räkna antalet steg som skett
- Avsluta ifall ingen vändning ägt rum, annars gå tillbaks till punkt 3 och gör ett nytt steg
- 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);
}
}