Сандарды бояу қисын ойындарының ең жақсысы. Біз осы ойынның бір өлшемді нұсқасын қарастырамыз

1 / 2

International Olympiad in Informatics 2016

12-19th August 2016

Kazan, Russia

day2_1

paint

paint

Country: KAZ

Сандарды бояу

Сандарды бояу қисын ойындарының ең жақсысы. Біз осы ойынның бір өлшемді

нұсқасын қарастырамыз. Бұл ойында сізге

тордан тұратын бір қатар беріледі.

Торлар 0 ден

ге дейін нөмірленген. Ойыншы әр торды қара немесе ақ

түске бояй алады. Біз ‘

X

’ таңбасын қара торлар үшін және ‘

_

’ таңбасын ақ

торларға пайдаланамыз.

Ойыншығы

сандарынан тұратын   оң бүтін сан беріледі: бұл

кілттер

. Оның мақсаты қатарда   қатар орналасқан торлардан тұратын кесектер

болу керек. Онымен қоса cол жақтан санағандағы   нөмірлі кесектің (  ден

басталатын нөмірлеу) ұзындығы

ге тең. Мысалы, егер кілттер

болса, шешілген қисап екі кесегі болуы керек: біреуінің ұзындығы үшке және

екіншісі төртке. Сәйкесінше, егер

және

болса, дұрыс

жауаптардың бірі “

_XXX__XXXX

” болады. Бірақ мысалы “

XXXX_XXX__

” дұрыс

шешім емес: кесектердің кезегі дұрыс емес. Онымен қоса, “

__XXXXXXX_

” шешімі

де дұрыс емес: бұл жерде тек қана бір қара торлардан тұратын кесек бар, ал

бізге екі кесек керек.

Сізге жартылай шешімі бар Сандарды бояу ойыны берілген. Анығырақ айтсақ,

сізге

және   қатарлары беріледі, және кейбір торлар ақ немесе қара

болатыны берілген. Сіздің тапсырмаңыз торлар туралы қосымша ақпарат жинау.

Яғни, сіз барлық дұрыс шешімдердегі тек қара болатын торларды, және әрбір

дұрыс шешімдегі тек ақ болатын торларды табуыңыз керек. Сіз есептегі берілген

бойынша кем дегенде бір дұрыс шешім бар деп есептей аласыз.

Іске асыру бойынша қосымша ақпарат

Сіз келесі функцияны іске асыру керек(метод):

string solve_puzzle(string s, int[] c)

.

s

:

таңбасы бар сөз. Әр   үшін (

)   нөмірлі таңба:

‘

X

’ ке тең, егер   қара болса,

‘

_

’ ке тең, егер   ақ болса,

‘

.

’, егер   нөмірлі тор туралы ақпарат болмаса.

c

: жоғарыда айтылғандай   элементі бар қатар,

функция

таңбалы сөз қайтаруы керек. Әр   (

) үшін

нөмірлі таңба келесі мәндерге тең бола алады:

‘

X

’ ке тең, егер   барлық дұрыс шешімдерде қара түсті болса,

‘

_

’, ке тең, егер   барлық дұрыс шешімдерде ақ түсті болса,

‘

?

’, басқа жағдайда (яғни кейбір дұрыс шешімдерде ақ ал кейде

қара бола алса).

n

n − 1

c = [ , … ,

]

c

0

c

k−1

k

k

i

0

c

i

c = [3, 4]

n = 10

c = [3, 4]

n

c

n

i

0 ≤ i ≤ n − 1 i

i

i

i

k

n

i 0 ≤ i ≤ n − 1

i

i

i

2 / 2

Мысалдар

1 мысал

solve_puzzle("..........", [3, 4])

Бұл жерде төрт түрлі шешім бар:

“

XXX_XXXX__

”,

“

XXX__XXXX_

”,

“

XXX___XXXX

”,

“

_XXX_XXXX_

”,

“

_XXX__XXXX

”,

“

__XXX_XXXX

”.

Байқағаныңыздай 2, 6, және 7 нөмірлі торлар барлық жағдайда ақ болады.

Қалған торлар туралы ақпарат жеткіліксіз. Сонымен, жауап “

??X???XX??

” қа

тең.

2 мысал

solve_puzzle("........", [3, 4])

Бұл жердегі шешім: “

XXX_XXXX

”.

Есем бөлімдері

Барлық есеп бөлімдерінде

, және

барлық

.

1.  (7 points)

,

,   тек қана ‘

.

’ таңбасымен (бос қисап),

2.  (3 points)

,   тек қана ‘

.

’ таңбасымен,

3.  (22 points)

,   тек қана ‘

.

’ таңбасымен,

4.  (27 points)

,   тек қана ‘

.

’ және ‘

_

’ таңбаларымен (тек ақ түсті

торлар туралы ақпарат),

5.  (21 points)

,

6.  (10 points)

,

,

7.  (10 points)

,

.

Мысал бағалаушы

Мысал бағалаушы есеп берілгенін келесі түрде қабылдайда:

қатар 1:   сөзі,

қатар 2:   бүтін саны және   бүтін сандар

.

1 ≤ k ≤ n

1 ≤ ≤ n

c

i

0 ≤ i ≤ k − 1

n ≤ 20 k = 1 s

n ≤ 20 s

n ≤ 100 s

n ≤ 100 s

n ≤ 100

n ≤ 5 000 k ≤ 100

n ≤ 200 000 k ≤ 100

s

k

k

, … ,

c

0

c

k−1