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

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


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

Vasile s-a lansat în afaceri cu un produs inovativ: robotul WB, care joacă alba-neagra.
Jocul constă din K pahare identice, aşezate pe poziţii numerotate distinct de la 1 la K. WB ascunde iniţial o bilă sub paharul aflat pe poziţia S. Apoi execută foarte rapid N operaţii de interschimbare. La o interschimbare, WB selectează două poziţii şi interschimbă paharele plasate pe poziţiile selectate. Interschimbarea este făcută în aşa fel încât, dacă bila se află sub unul dintre paharele interschimbate, ea nu este vizibilă şi va fi mutată odată cu paharul sub care se află.
Fiind un robot, WB generează poziţiile paharelor implicate în interschimbări construind un şir de numere astfel: x1=c; xi=a*xi-1+b, pentru orice i>1.
La cea de a i-a interschimbare, WB alege poziţiile (xi%K+1) şi ((xi+1)%K+1), unde cu x%y se notează restul împărţirii lui x la y.
După executarea celor N interschimbări, bila se află în paharul situat pe poziţia F.

Cerinţă

Scrieţi un program care determină numerele naturale a, b, c astfel încât după executarea celor N interschimbări paharul sub care se află bila să ajungă de pe poziţia S pe poziţia F.

Date de intrare

Fişierul de intrare wb.in conţine pe prima linie numerele naturale N K S F.

Date de ieşire

Fişierul de ieşire wb.out va conţine o singură linie pe care vor fi scrise numerele naturale a b c, separate prin câte un spaţiu, având semnificaţia din enunţ.

Restricţii

• 1 ≤ N ≤ 100000
• 2 ≤ K ≤ 10
• 1 ≤ S ≤ K
• 1 ≤ F ≤ K
• Numerele naturale a, b şi c nu vor depăşi valoarea 1000.
• Dacă există mai multe soluţii, se va alege soluţia în care a este minim. Dacă există mai multe soluţii cu a minim, se alege soluţia cu b minim. Dacă există mai multe soluţii pentru a şi b minime, se alege soluţia cu c minim.
• Pentru datele de test există soluţie.

Exemple

wb.inwb.outExplicaţii
3 4 2 4 2 0 1 Se execută N=3 interschimbări. Există 4 pahare, aşezate pe poziţii numerotate de la 1 la 4. Iniţial bila este plasată sub paharul aflat pe poziţia 2, iar după 3 interschimbări va ajunge pe poziţia 4.
□ ■ □ □
Considerăm a=2 b=0 c=1
Interschimbarea 1: x1=1
Se interschimbă paharul de pe poziţia 2 cu paharul de pe poziţia 3
□ □ ■ □
Interschimbarea 2: x2=(2*x1+0)=2
Se interschimbă paharul de pe poziţia 3 cu paharul de pe poziţia 4
□ □ □ ■
Interschimbarea 3: x3=(2*x2+0)=4
Se interschimbă paharul de pe poziţia 1 cu paharul de pe poziţia 2
□ □ □ ■

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la OMI 2017: barci, expand, culori3
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, prime2, virgule, b210
Despre generare: taste, pluricex, balbe, magic3, formule, grup, zmeu, nr01, reteta2, playlist, pizza1, caramele, caini, tvshow, adevar, prime1, hexa, premii1, carti2, bile4, hof, matrx, cubinvers, arctir, guess, minmax, stele, tablou1, adunscad, sumprod, prisme, operatii1, expeval, triburi1, optim, patru, genab, dineu, cumpanit, nkd, relatii
Despre simulare: lbd, iepuras, tren2, mgo, joc2, kafka, comori, loc, bile3, cat, felinare, spioni, lift, kalah, cutii, roboti, pesti, zar1, joc16, safeu, joc20, dame, conjectura, arc, robot6
Software recomandat
surse trimise | ajutor