Программа келесі ережелерге еру қажет: Программа деректер құрылымына add element(x) функциясын қолданып

1 / 4

International Olympiad in Informatics 2016

12-19th August 2016

Kazan, Russia

day2_2

messy

messy

Country: KAZ

Күрделі қатені талдау

Ильшат бағдарламалық қамтамасыз ету инженері болып жұмы істейді және

қазір деректер құрылымымен жұмыс істейді. Ол жаңа деректер құрылымын

ойлап шығарды. Бұл деректер құрылымы

биттен тұратын

теріс емес

сандар

жиынын сақтай алады, мұндағы

саны 2 санының дәрежесі. Нақтырақ, кейбір

теріс емес бүтін   саны үшін

.

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

программа келесі ережелерге еру қажет:

Программа деректер құрылымына

add_element(x)

функциясын қолданып

биттен тұратын сандарды біреуден қоса алады. Егер программа деректер

құрылымында бар санды қосуға тырысса ештеңе өзгермейді, деректер

құрылымы өз қалпында қалады.

Барлық қосу керек элементтерді қосып болғаннан кейін

compile_set()

функциясын шақыру керек, программа жұмысы барысында бұл функцияны

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

Соңында, программа

check_element(x)

функциясы арқылы   санының

деректер құрылымындағы сандар жиынының құрамында бар-жоғын тексере

алады. Программа бұл функцияны бірнеше рет қолдана алады.

Ильшат осы деректер құрылымын бірінші рет іске асырғанда

compile_set()

функциясында қателік жасап қойды. Осы қате деректер құрылымына енгізілген

әр санның биттерін белгілі бір тәсілмен орындарын ауыстырады. Ильшат сізден

осы қатенің кесірінен пайда болған ауыстырудың нақты тәсілін тауып беруді

сұрайды.

Нақтырақ,  -ден

-ге дейінгі сандардың әрқайсысы дәл бір реттен ғана

кездесетін

сандар қатарын қарастырайық. Біз осы сандар қатарын

ауыстыру

деп атаймыз. Деректер құрылымындағы екілік санау жүйесіндегі

цифрлары

болатын санды қарастырайық (

ең бірінші цифры).

compile_set()

функциясы қолданылған уақытта осы сан екілік санау

жүйесіндегі цифрлары

болатын санғы ауыстырылады.

Дәл осы ауыстыру деректер құрылымындағы әрбір санға қолданылады.

Ауыстыру кез келген болуы мүмкін, олардың құрамына әрбір

үшін

болатын ауыстыру да кіреді.

Мысалы,

,

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

0000

,

1100

және

0111

сандарын еңгіздіңіз делік.

compile_set

функциясы осы

сандарды сәйкесінше

0000

,

0101

және

1110

сандарына ауыстырады.

n

n

b

n = 2

b

n

x

0

n − 1

, … ,

p

0

p

n−1

, … ,

a

0

a

n−1

a

0

, , … ,

a

p

0

a

p

1

a

p

n−1

0 ≤ i ≤ n − 1

= i

p

i

n = 4 p = [2, 1, 3, 0]

2 / 4

Сіздің тапсырмаңыз деректер құрылымымен әрекеттер жасай отырып

ауыстыруын табатын программа жазу. Сіздің программаңыз (берілген ретпен):

1.

биттен тұратын бүтін сандар жиынын ойлап табу,

2.  ойлаған сандар жиынын деректер құрылымына енгізу,

3.  қате орындалған функция іске асу үшін

compile_set

функциясын шақыру,

4.  кей сандардың жаңартылған деректер құрылымының жиынында бар-жоғын

check_element

функциясы арқылы тексеру,

5.  пайда болған ақпараттарды пайдаланып   ауыстыруын тауып, қайтару

керек.

Сіздің программаңыз

compile_set

функциясын тек бір рет қолдана алатынын

байқаңыз.

Оған қоса, сіздің программаңыз берілген әрбір функция үшін қолдану санына

шектеу бар. Нақтырақ,

программа

add_element

функциясын көбінде

рет қолдана алады (

"writes" сөзінен),

программа

check_element

функциясын көбінде   рет қолдана алады (

"reads" сөзінен).

Қосымша ақпарат

Сіз келесі функцияны іске асыру қажетсіз:

int[] restore_permutation(int n, int w, int r)

n

: сандар жиынының әрбір санының екілік санау жүйесіндегі цифрлар

саны (және   ауыстыруының ұзындығы).

w

: программаның

add_element

функциясының қолдану санына шектеу.

r

: программаның

check_element

функциясының қолдану санына

шектеу.

функция   ауыстыруын қайтару керек.

C программалау тілінде функция прототипі кішкене өзгеше:

void restore_permutation(int n, int w, int r, int* result)

n

,

w

және

r

мағыналары өзгертілмеген.

функция   ауыстыруын ұсынылған

result

массивіне жазып қайтару

керек: әр   үшін

мәні

result[i]

айнымалысына жазылуы қажет.

Берілген функциялар

Программа деректер құрылымымен әрекет жасауы үшін келесі үш функцияны

қолдануы қажет:

void add_element(string x)

Бұл функция деректер құрылымының сандар жиынына

x

санын қосады.

x

:

'0'

және

'1'

символдарынан тұратын жол, жиыныға қосылатын

санның екілік санау жүйесінде жазылуы. Жолдың ұзындығы

болуы

тиіс.

void compile_set()

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

функцияны қолданғаннан кейін

add_element()

функциясын қолдана

p

n

p

w

w

r

r

p

p

p

i

p

i

n

3 / 4

алмайды және бұл функцияға дейін

check_element()

функциясын қолдана

алмайды.

boolean check_element(string x)

Бұл функция

x

элементінің жаңартылған деректер құрылымының сандар

жиынында бар-жоғын тексереді.

x

:

'0'

және

'1'

символдарынан тұратын жол, тексерілетін санның

екілік санау жүйесінде жазылуы. Жолдың ұзындығы

болуы тиіс.

егер

x

элементі жаңартылған жиын құрамында бар болса

true

қайтарады, басқа жағдайларда

false

қайтарады.

Егер сіздің программаңыз жоғарыдағы шектеулердің кез келгенін бұзатын болса

сіз "Wrong Answer" жауабын аласыз.

Барлық жолдар үшін ең бірінші символы санның екілік санау жүйесіндегі ең

бірінші цифрын көрсетеді.

Анығырақ ақпарат үшін сіздің қолданатын программалау тілі үшін үлгі файлын

қолдануыңызды ұсынамыз.

Мысал

Бағалаушы келесі функцияны шақырады:

restore_permutation(4, 16, 16)

. Бізде

және программа көп

дегенде

сан енгізіп,

сан тексере алады.

Программа келесі функцияларды шақырады

add_element("0001")

add_element("0011")

add_element("0100")

compile_set()

check_element("0001")

false

қайтарады

check_element("0010")

true

қайтарады

check_element("0100")

true

қайтарады

check_element("1000")

false

қайтарады

check_element("0011")

false

қайтарады

check_element("0101")

false

қайтарады

check_element("1001")

false

қайтарады

check_element("0110")

false

қайтарады

check_element("1010")

true

қайтарады

check_element("1100")

false

қайтарады

check_element()

функциясымен қайтарылған мәндер үшін тек қана бір

ауыстыру сәйкес келеді:

. Сондықтан,

restore_permutation

функциясы

[2, 1, 3, 0]

массивін қайтару қажет.

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

1.  (20 ұпай)

,

,

, (

) болатын көп дегенде

2   индексі үшін

,

2.  (18 ұпай)

,

,

,

n

n = 4

16

16

p = [2, 1, 3, 0]

n = 8 w = 256 r = 256 0 ≤ i ≤ n − 1

i

≠ i

p

i

n = 32 w = 320 r = 1024

n = 32 w = 1024 r = 320

4 / 4

3.  (11 ұпай)

,

,

,

4.  (21 ұпай)

,

,

,

5.  (30 ұпай)

,

,

.

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

Мысал бағалаушы енгізу элементтері ретінде мәндерді келесі форматта оқиды:

1 жол:

,

,   бүтін сандары,

2 жол:   ауыстыруын құрайтын

бүтін сандар.

n = 32 w = 1024 r = 320

n = 128 w = 1792 r = 1792

n = 128 w = 896 r = 896

n w r

p

n