Problema Barca

Voi propune o problema destul de usoara, pentru cei din clasele mici. Cred ca o sa va prindeti repede la ea, e adaugata pentru diversitate. E mai mult ceva de genul matematica distractiva. Pe malul unui rau se gaseste un pluton format din n soldati, numerotati de la 1 la n. Ei trebuie sa traverseze raul, dar nu au la dispozitie nici un mijloc de transport. Din fericire, chiar in dreptul lor, pe rau erau doi copii, Gigel si Ionel, intr-o mica barca de cauciuc. Copiii au fost de acord sa-i ajute pe soldati sa traverseze raul, insa a aparut un mic inconvenient: in barca, fiind mica, nu incape decat fie un singur soldat, fie cel mult cei doi copii. Ajutati-i pe Ionel si Gigel sa transporte intreg plutonul pe malul celalalt, iar ei sa revina pe malul de pe care au plecat. Cerinta Scrieti un program care sa afiseze o modalitate de utilizare a barcii de cauciuc astfel incat la final toti soldatii sa traverseze raul, realizand un numar minim de traversari. Date de intrare Fisierul de intrare barca.in are o singura linie pe care se gaseste numarul natural nenul n, reprezentand numarul de soldati din pluton. Date de iesire Fisierul de iesire barca.out va contine pe prima linie numarul minim de traversari pe care le face barca pentru ca intreg plutonul sa ajunga pe malul celalalt, iar ambii copii sa revina pe maul de pe care au plecat. Urmeaza in fisier atatea linii cate traversari va efectua barca. Linia i+1 va contine codificat continutul barcii la traversarea i, si anume: – caracterul ′I′, daca in barca se gaseste doar Ionel – caracterul ′G′, daca in barca se gaseste doar Gigel – caracterele ′IG′ daca in barca se gasesc amandoi copiii – un numar natural k, care reprezinta numarul de ordine al soldatului care este in barca si care traverseaza raul in acel moment. Restrictii

• 1 ≤ n ≤ 35000

• Initial barca si cei doi copii se gasesc pe acelasi mal cu soldatii;

• Cand copiii se gasesc impreuna pe acelasi mal, Ionel are prioritate la folosirea barcii;

• Soldatii vor traversa raul in ordinea numerotarii lor;

• Dupa terminarea operatiunii Ionel si Gigel trebuie sa ramana impreuna pe acelasi mal de unde au inceput traversarea.

• Punctaj: Daca numarul minim de traversari afisat este corect se obtine 20% din punctajul pe test. Punctajul integral se acorda daca atat numarul minim de traversari, cat si traversarile sunt corecte.

Exemplu barca.in 1 barca.out 4 IG I 1 G Explicatie: I si G traverseaza raul impreuna I se intoarce pe malul cu soldati si ramane aici soldatul 1 traverseaza raul si ramane acolo G revine pe malul initial Descrierea solutiei Pe baza informatiilor furnizate de enunt, putem deduce urmatoarele: * Ionel si Gigiel se afla la inceput in barca. * Ionel se deplaseaza inaintea soldatilor. * Gigel este ultimul care travereseaza cu barca. * Nu ne ramane decat sa afisam soldatii in ordine crescatoare. Solutie

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("barca.in");
ofstream g("barca.out");
long long n,i;
int main()
{
 f>>n;
 g<<4*n<<endl;

 for (i=1;i<=n;++i)
   g<<"IG"<<endl<<"I"<<endl<<i<<endl<<"G"<<endl;
return 0;
}