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