.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » patrate7

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
patrate7


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Bia şi Ştefan joacă un nou joc. Bia i-a cerut lui Ştefan să se gândească la un număr natural nenul mai mic strict decât VMAX=2n. Apoi, ea a luat un pix şi o foaie şi a desenat n matrice pătratice (denumite pe scurt pătrate), pe care le-a numerotat de la 1 la n. Apoi a completat pătratele în modul următor: în pătratul cu numărul i au fost scrise în ordine crescătoare toate numerele naturale nenule mai mici decât VMAX, care, scrise în baza 2, au cifra corespunzătoare lui 2i-1, egală cu 1; plasarea numerelor s-a făcut parcurgând coloanele de la stânga la dreapta şi completând fiecare coloană de sus în jos.
Fiecare pătrat are latura minimă necesară pentru ca numerele pe care trebuie să le conţină să încapă.
Este posibil ca pătratele să nu se umple integral (în acest caz pătratul se va completa cu valoarea 0).
După ce a desenat pătratele, Bia îl întreabă pe Ştefan în care dintre pătrate se află numărul la care s-a gândit el. Apoi face o magie şi ghiceşte numărul la care s-a gândit Ştefan.
În plus, ca să-l impresioneze şi mai tare pe Ştefan, Bia i-a spus linia şi coloana pe care este plasat acest număr în primul pătrat spus de Ştefan.

Cerinţă

Fiindcă voi nu credeţi în magie, scrieţi un program care să determine numărul la care s-a gândit Ştefan, precum şi poziţia acestui număr în primul pătrat spus de Ştefan.

Date de intrare

Fişierul de intrare patrate7.in conţine pe prima linie numerele naturale n şi m, separate prin spaţiu, reprezentând numărul de pătrate pe care le va desena Bia, respectiv în câte dintre pătratele desenate se află numărul la care s-a gândit Ştefan. Pe al doilea rând se află, separate prin câte un spaţiu, m numere naturale cuprinse între 1 şi n, reprezentând cele m pătrate în care se află numărul la care s-a gândit Ştefan.

Date de ieşire

Fişierul de ieşire patrate7.out va conţine pe prima linie numărul la care s-a gândit Ştefan. Pe a doua linie vor fi scrise două numere naturale separate prin spaţiu L C, reprezentând, linia, respectiv coloana pe care se află numărul respectiv în primul pătrat menţionat de Ştefan.

Restricţii

1 < m ≤ n ≤ 28
• În fiecare matrice pătratică liniile sunt numerotate de sus în jos începând cu 1, iar coloanele de la stânga la dreapta începând cu 1.
• Pentru teste valorând 50% din punctaj, n este ≤14.
• Pentru determinarea corectă a numărului la care s-a gândit Ştefan se acordă 40% din punctajul pe test. Punctajul integral se obţine pentru rezolvarea ambelor cerinţe.

Exemple

patrate7.inpatrate7.outExplicaţii
4 3 1 4 3 13 1 3 Numărul 13 este cel la care s-a gândit Ştefan pentru că acesta, scris în baza 2, este 1101. Numărul 13 este singurul care se găseşte numai în pătratele indicate de Ştefan (1, 4 şi 3), pentru că are cifrele corespunzătoare lui 20, 23 şi 22 egale cu 1. Primul pătrat menţionat de Ştefan este 1. Numărul 13 se află în acest pătrat pe linia 1 şi coloana 3.
Pătratul 1 este indicat mai jos:
1 7 13
3 9 15
5 11 0

autor: Prof. Dana Marcu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor