#2150. Šeširi
Šeširi
Šeširi
题目描述
Izborne pripreme – prvi izborni ispit Zadatak Šeširi 18. lipnja 2022. 3 sekunde / 512 MiB / 100 bodova Zadatak Šeširi Srednjoeuropska informatička olimpijada (CEOI) ove se godine održava u Lijepoj Našoj. Natjecatelji su dodatno uzbuđeni zbog najpoznatije hrvatske tradicije na informatičkim olimpijadama. Naravno, radi se o darivanju šeširića s prepoznatljivim “kockastim” uzorkom. Ipak, gospodin Malnar odlučio je stati na kraj još jednoj tradiciji. Ove će se godine dijeliti jednobojni šeširići, obojeni u crvenu ili bijelu boju. Gospodin Malnar nije donio ovu odluku tek tako, već je to dio pomno promišljenog plana. Naime, Malnar zna da će se u nekom trenutku na istom mjestu naći N mladih informatičara te da će svaki od njih na glavi nositi crveni ili bijeli šeširić. Naravno, svaki će informatičar vidjeti sve šeširiće osim svojeg te će, po običaju, svi istovremeno viknuti koje boje misle da je njhov šeširić. Svi informatičari koji pogode boju svojeg šeširića za nagradu će otići na večeru s gospodinom Malnarom. No, gospodinu Malnaru jako je stalo do toga da na večeri obje boje šeširića budu dovoljno zastupljene. Rekao im je da od svih b informatičara s bijelim šeširićem barem ⌊b/2⌋njih mora pogoditi svoju boju, te od svih c informatičara s crvenim šeširićem barem ⌊c/2⌋njih mora pogoditi svoju boju, jer inače neće nikoga voditi na večeru. Pomozite mladim informatičarima pronaći strategiju koja će osigurati da uvjet gospodina Malnara bude ispunjen za svaki mogući raspored šešira. Ulazni podaci U prvom i jedinom retku je prirodan broj N, broj informatičara. Izlazni podaci Informatičari su označeni prirodnim brojevima od 1 do N. Neka je si znak koji predstavlja boju šeširića i-tog informatičara, B za bijelu odnosno C za crvenu boju. U i-tom retku treba ispisati niz od 2N−1 znakova B i C koji opisuju strategiju i-tog informatičara. Označimo taj niz znakova s xi. Informatičar će pogledati šešire ostalih, i situaciju koju vidi opisati nizom znakova yi = s1 . . . si−1si+1sN. Zatim će odrediti redni broj ki tog niza znakova među abecedno poredanim svim nizovima znakova B i C duljine N −1. Ako je ki-to slovo u njegovoj strategiji xi jednako B, reći će “bijela!”, odnosno ako je C onda će reći “crvena!”. Za dodatno pojašnjenje pogledajte probne primjere. Bodovanje Testni primjer Broj bodova Testni primjer Broj bodova Testni primjer Broj bodova N = 4 7 N = 9 7 N = 14 6 N = 5 7 N = 10 7 N = 15 6 N = 6 7 N = 11 7 N = 16 6 N = 7 7 N = 12 7 N = 17 6 N = 8 7 N = 13 7 N = 18 6 5 od 6 Izborne pripreme – prvi izborni ispit Zadatak Šeširi 18. lipnja 2022. 3 sekunde / 512 MiB / 100 bodova Probni primjeri ulaz ulaz 2 3 izlaz izlaz BC BBCC CC BCBC BBCC Pojašnjenje probnih primjera: Prvi redak slike prikazuje sva četiri moguća slučaja u prvom primjeru. Drugi redak slike prikazuje dva moguća slučaja u drugom primjeru. Prvi slučaj: s1 = C x1 = CC k1 = 4 1 C =⇒ =⇒ =⇒ 2 s2 = C x2 = CC k2 = 4 C 3 s3 = C x3 = CC k3 = 4 C Drugi slučaj: 1 s1 = C x1 = BB k1 = 1 B =⇒ =⇒ =⇒ s2 = B x2 = CB k2 = 3 2 B 3 s3 = B x3 = CB k3 = 3 C 6 od 6
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
BC
CC
样例 2
3
BBCC
BCBC
BBCC