Olimpiada
Naţională de Informatică pentru Gimnaziu
Clasa a VII-a
Problema 1 – Panglica
Gigel are o panglică alcătuită din benzi de 1 cm lăţime, colorate în diverse culori. Panglica are N benzi colorate cu C culori, culori pe care le vom numerota de la 1 la C. Gigel vrea ca la ambele capete ale panglicii să aibă aceeaşi culoare, dar cum nu poate schimba culorile benzilor, singura posibilitate rămâne tăierea unor bucăţi de la capete.
Scrieţi un program care să determine modul de tăiere a panglicii astfel încât la cele două capete să fie benzi de aceeaşi culoare, iar lungimea panglicii obţinute să fie maximă.
Fişierul de intrare PANGLICA.IN conţine:
– pe prima linie numerele naturale N şi C separate printr-un spaţiu;
– pe următoarele N linii descrierea panglicii: pe fiecare linie un număr natural de la 1 la C, reprezentând în ordine culorile fâşiilor ce alcătuiesc panglica.
Fişierul de ieşire PANGLICA.OUT va conţine următoarele 4 numere:
– pe prima linie numărul de fâşii rămase;
– pe linia a doua numărul culorii care se află la capete;
– pe linia a treia câte fâşii trebuie tăiate de la începutul panglicii iniţiale;
– pe linia a patra câte fâşii trebuie tăiate de la sfârşitul panglicii iniţiale.
§
2<=N<=10000
§ 1<=C<=200
§ Dacă există mai multe soluţii alegeţi pe cea în care se taie cât mai puţin din partea de început a panglicii.
Exemplul 1 Exemplul 2
PANGLICA.IN PANGLICA.OUT PANGLICA.IN
PANGLICA.OUT
6 3 4 5 2 4
1 2 1 2
2 1 2 1
1 1 1 0
3 2
2
2
3
Timp maxim de execuţie: o secundă / test.
Problema 2 – Jocul pietricelelor
Doi prieteni au inventat un nou joc – « jocul pietricelelor ». Ei
au la dispoziţie N
grămezi, fiecare dintre ele conţinând un număr distinct de
pietricele.
Jocul constă în alegerea unui număr oarecare de grămezi din
cele N
date, pentru a obţine în total (adunând numărul de pietricele din
grămezile selectate) un număr de pietricele cu 1 mai mare decât
ultimul număr obţinut de partenerul de joc. Primul jucător
trebuie să obţină la prima sa mutare un total de 1
pietricică. Deci, obligatoriu al doilea jucător trebuie să
obţină la prima sa mutare un total de 2 pietricele. La a doua mutare,
primul jucator este obligat sa obţină un total de 3 pietricele,
ş.a.m.d.
Câştigă cel care a obţinut totalul maxim, sau, altfel spus,
pierde cel care nu reuşeşte să obţină la rândul
său un total cu exact o pietricica mai mare decât ultimul total
obţinut de partenerul de joc.
Scrieţi un program care determină numărul de pietricele obţinut la ultima sa mutare de jucătorul câştigător.
Date de intrare
Fişierul de intrare JOC.IN conţine:
–
pe prima
linie numărul N
de grămezi;
–
pe a doua
linie N
numere ordonate crescător, reprezentând numărul de pietricele din
fiecare grămadă.
Date de iesire
Fişierul de ieşire JOC.OUT va conţine pe prima linie numărul determinat. Dacă jocul nu
poate începe, fiindcă lipseşte grămada care conţine o
pietricică, în fişier se va afişa valoarea 0.
Restricţii
Toate numerele care intervin în problemă sunt mai mici decât 60000.
Exemplu
|
JOC.IN |
JOC.OUT |
|
7 1 2 4 9 10 11 12 |
7 |
Explicatie:
Notam PJ primul jucător
şi DJ al doilea jucător.
PJ are la dispoziţie o grămadă cu o pietricică: 1
DJ are la dispoziţie o grămadă ce conţine două
pietricele: 2
PJ alege primele două grămezi: 1+2=3
DJ are la dispoziţie o grămadă ce conţine 4 pietricele:
4
PJ alege prima şi a trei grămadă: 1+4=5
DJ alege a doua şi a treia grămadă: 2+4=6
PJ alege primele trei grămezi: 1+2+4=7
Jocul ia sfârşit deoarece al doilea jucător nu poate obţine
o grămadă ce conţine 8 pietricele.
Timp maxim de execuţie: 1 secundă/test
Notă:
Timp de lucru: 3 ore. Fiecare problemă se punctează cu 100 puncte.