Fișierul intrare/ieșire iepuras1.in, iepuras1.out Sursă ONI 2015 clasa a 5-a
Autor Sanda Junea Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Iepuraș 1 (clasa a 5-a)

Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N căsuțe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță. Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:

  • numărul înscris în căsuța în care se află iepurașul reprezintă numărul de căsuțe peste care el va sări;
  • dacă numărul înscris în căsuța în care se află iepurașul este număr prim, atunci energia lui se dublează și va sări peste un număr dublu de căsuțe;
  • numărarea căsuțelor peste care va sări se face de la stânga la dreapta și începe cu căsuța imediat următoare.
    Astfel, dacă iepurașul se află în căsuța a treia și numărul înscris în această căsuță este 5, iepurașul va ajunge în căsuța cu numărul de ordine 13 (13=3+2*5).
  • dacă iepurașul ajunge într-o căsuță care conține numărul 0, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus;
  • iepurașul ajunge la grădina cu morcovi dacă ultimul salt pe care îl face depășește căsuța N.

Cerință

Scrieți un program care citește trei numere naturale P, N și K iar apoi N numere naturale și determină:

  1. dacă iepurașul poate ajunge sau nu, la grădina cu morcovi pornind din căsuța K și numărul de salturi pe care le face iepurașul pornind din căsuța K
  2. căsuța de pornire a iepurașului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuțe. Pentru a determina numărul de căsuțe se vor lua în calcul: căsuța de pornire, toate căsuțele peste care iepurașul a sărit și toate căsuțele în care a ajuns în urma salturilor. Iepurașul poate porni din oricare căsuță. În cazul în care există două sau mai multe căsuțe de pornire care conduc la același număr maxim de căsuțe traversate se va lua în considerare căsuța cu numărul de ordine cel mai mic.

Date de intrare

Fișierul de intrare iepuras1.in conține pe prima linie un număr natural P. Pentru toate testele de intrare, numărul P poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie a fișierului iepuras1.in se găsesc, în această ordine, numerele naturale N și K, separate prin câte un spațiu. Pe a treia linie se găsesc N numere naturale separate prin câte un spațiu, reprezentând valorile din fiecare căsuță în ordine de la 1 la N.

Date de ieșire

Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire iepuras1.out va conține pe prima linie cuvântul DA în cazul în care iepurașul a ajuns în grădina cu morcovi , respectiv cuvântul NU în caz contrar, iar pe a doua linie va conține un număr natural reprezentând numărul de salturi pe care le face iepurașul pornind din căsuța K. Dacă valoarea lui P este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire iepuras1.out va conține pe prima linie două numere naturale separate printr-un spațiu reprezentând, în ordine, căsuța de pornire și numărul maxim de căsuțe determinat, iar pe a doua linie, un șir de numere naturale separate prin câte un spațiu reprezentând numerele din căsuțele în care iepurașul nu s-a aflat sau nu a sărit pe parcursul drumului, de la stânga la dreapta, începând cu căsuța 1. Dacă numărul maxim de căsuțe traversate este chiar N linia a doua nu va conține niciun număr.

Restricții

  • 1 ≤ N ≤ 7000
  • 1 ≤ K ≤ N
  • 0 ≤ numerele conținute în căsuțe ≤ 100
  • Pentru rezolvarea corectă a primei cerințe se acordă 30 de puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă 70 de puncte.

Exemplu

iepuras1.in iepuras1.out Explicații
1
14 3
2 3 4 0 1 1 2 1 4 0 0 2 1 1
NU
2
P = 1, pentru acest test, se rezolva cerința 1). Iepurașul pleacă din căsuța 3,
sare în căsuța cu numărul de ordine 7 și mai departe, în căsuța cu numărul de
ordine 11, unde găsind numărul 0 se oprește.
2
14 3
2 3 6 0 1 1 2 1 4 0 0 2 3 1
2 13
2 6 0 1 1 2 0 0 2 1
P = 2, pentru acest test, se rezolvă cerința 2). Pentru a traversa un număr
maxim de căsuțe, iepurașul pleacă din căsuța cu numărul de ordine 2 și sare, pe rând,
în căsuțele cu numerele de ordine 8, 9, 13, și apoi în grădină, traversând astfel
13 căsuțe (de la căsuța 2 la căsuța 14). Iepurașul nu s-a aflat sau nu a sărit
în căsuțele de pe pozițiile 1, 3, 4, 5, 6, 7, 10, 11, 12 și 14.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii