Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований. Если вы раньше видели эти задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве. Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве. Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
→ Теги задачи
жадные алгоритмы
математика
Нет прав на редактирование
→ Материалы соревнования
- Анонс (англ.)
Разбор задач (англ.)
Условие задачи было недавно изменено. Просмотреть изменения.
H. Максимальный AND
ограничение по времени на тест
ограничение по памяти на тест
256 мегабайт
стандартный ввод
стандартный вывод
Вам дан массив $$$a$$$ длины $$$n$$$ и неотрицательное целое число $$$k$$$. Вы можете выполнить не более чем $$$k$$$ операций над массивом следующего типа:
Assembler #1 / Ассемблер / ЛамПанель / Основы ассемблера
- Выбрать индекс $$$i$$$ ($$$1 leq i leq n$$$) и заменить $$$a_i$$$ на $$$a_i$$$ $$$mathsf$$$ $$$2^j$$$, где $$$j$$$ — любое целое число от $$$0$$$ до $$$30$$$ включительно . Другими словами, в операции можно выбрать индекс $$$i$$$ ($$$1 leq i leq n$$$) и установить $$$j$$$-й бит $$$a_i$$$ в $$$1$$$ ($$$0 leq j leq 30$$$).
Выведите максимально возможное значение $$$a_1$$$ $$$mathsf$$$ $$$a_2$$$ $$$mathsf$$$ $$$dots$$$ $$$mathsf$$$ $$$a_n$$$ после выполнения не более чем $$$k$$$ операций.
Входные данные
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 le t le 100$$$) — количество наборов входных данных в тесте. Далее следует описание наборов.
Первая строка каждого набора содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 le n le 2 cdot 10^5$$$, $$$0 le k le 10^9$$$).
Затем следует единственная строка, содержащая $$$n$$$ целых чисел, описывающих массив $$$a$$$ ($$$0 leq a_i < 2^$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 cdot 10^5$$$.
Выходные данные
Для каждого набора входных данных выведите единственную строку, содержащую максимально возможное $$$mathsf$$$ значение $$$a_1$$$ $$$mathsf$$$ $$$a_2$$$ $$$mathsf$$$ $$$dots$$$ $$$mathsf$$$ $$$a_n$$$ после выполнения не более чем $$$k$$$ операций.
Входные данные
4 3 2 2 1 1 7 0 4 6 6 28 6 6 12 1 30 0 4 4 3 1 3 1
Выходные данные
2 4 2147483646 1073741825
Примечание
Для первого набора мы можем установить бит $$$1$$$ ($$$2^1$$$) последних $$$2$$$-х элементов с помощью $$$2$$$-х операций, получив таким образом массив [$$$2$$$, $$$3$$$, $$$3$$$], значение $$$mathsf$$$ которого равно $$$2$$$.
Для второго набора мы не можем выполнить никаких операций, поэтому ответом будет только $$$mathsf$$$ всего массива, равное $$$4$$$.
Источник: codeforces.com
Assembler #11 / Ассемблер / ЛамПанель / Вывод данных / Ламповая панель
Уроки 25 — 27
Процессор. Память. Устройства ввода и вывода
§34. Процессор. §35. Память. §36. Устройства ввода. §37. Устройства вывода
Для выполнения этих работ используется учебный компьютер «ЛамПанель», который можно загрузить со страницы https://kpolyakov.spb.ru/prog/lamp.htm.
Возможности программы «ЛамПанель»
Наконец, мы подошли к самой интересной возможности программы «ЛамПанель» — управлению ламповой панелью. Ламповая панель (цифра 1 на рисунке) – это устройство вывода.
Обмен данными процессора и внешнего устройства происходит через порты – регистры контроллера внешнего устройства. У ламповой панели 8 портов, которые называются P0, P1, P2, P3, P4, P5, P6 и P7. Каждый порт «отвечает» за одну строку лампочек, например, для того, чтобы «зажечь» всю верхнюю строку нужно записать в порт P0 код FFFF16 (все 16 бит – единичные). Для этого можно использовать, например, команды
К сожалению, записать число сразу в порт нельзя – сначала нужно записать его в регистр (в данном примере – в R0), а потом – из регистра в порт.
Для того, чтобы изменить второй сверху ряд лампочек, нужно записать новое значение в P1 и т.д.; последний ряд управляется портом P7. Например, для того, чтобы все ряды лампочек горели одинаково, можно записать нужный код сначала в регистр:
а затем из этого регистра – во все порты:
Здесь многоточие обозначает аналогичные команды записи содержимого регистра R0 в порты P2…P6. Однако вместо последней серии из 8 команд можно использовать всего одну:
Эта команда вызывает системную процедуру с номером 2, находящуюся в ПЗУ компьютера. Для того, чтобы увидеть все процедуры, которые записаны в ПЗУ, нужно щелкнуть по кнопке или выбрать пункт верхнего меню Программа – Просмотр ПЗУ. После этого появляется окно, в левой части которого перечислены все системные процедуры (с их номерами), а в правой части показывается код выбранной процедуры:
В этом списке есть много полезных процедур, в том числе
0 – очистка экрана (погасить все лампочки);
1 – зажечь все лампочки на панели;
3-4 – прокрутка изображения вниз и вверх;
6-9 – логические операции;
1216 – вывод числа, записанного в регистр R0, в десятичной системе счисления;.
1316 – вывод числа, записанного в регистр R0, в шестнадцатеричной системе счисления.
Обратите внимание, что номер системной процедуры задается в шестнадцатеричной системе счисления.
Рассмотрим еще одну задачу: вывести на экран рисунок, закодированный в виде шестнадцатеричных чисел (бит, равный единице, обозначает горящую лампочку). Для этого нужно сначала записать коды рисунка в память. Поскольку наш компьютер основан на архитектуре фон Неймана, в нем программа и данные находятся в одной области памяти. Поэтому данные можно записать с помощью специальной команды DATA после команды STOP:
. ; здесь будет программа STOP M: ; метка – начало блока данных DATA AAAA ; код первой строчки DATA 5555 DATA AAAA DATA 5555 DATA AAAA DATA 5555 DATA AAAA DATA 5555 ; код последней строчки
Для того, чтобы вывести этот рисунок на экран, нужно записать его адрес в регистр R0 и вызвать системную процедуру с номером 5:
SYSTEM 5 ; вывести на экран рисунок, адрес которого в R0
DATA AAAA ; код первой строчки
Задание на практическую работу
1. Запишите в таблицу минимальное и максимальное числа, которые можно вывести на ламповую панель, если использовать шестнадцатеричную систему:
2. Составьте программу, после выполнения которой ламповая панель выглядит так:
3. Как вы думаете, что выведет приведенная выше (в теоретической части) программа, которая вызывает системную процедуру с номером 5? Проверьте ваш ответ с помощью тренажёра.
4. Закодируйте изображение домика и выведите его на экран.
5. Добавьте в предыдущую программу команды, которые сначала шифруют изображение, используя операцию «исключающее ИЛИ» с маской BCA716, а затем – восстанавливают исходное изображение. При изменении маски программа не должна изменяться. Изучите текст системной процедуры, которую вы используете.
6. Напишите программу, которая делает «бегущую строку» из рисунка-домика.
7. Напишите программу, которая организует «обратный отсчет» от 100 до 0, а затем выводит рисунок с домиком и останавливается.
Следующая страница §34. Процессор
Cкачать материалы урока
Источник: xn—-7sbbfb7a7aej.xn--p1ai
Программа ЛамПанель
Единственный в мире Музей Смайликов
Самая яркая достопримечательность Крыма
Скачать 261.5 Kb.
И
30.11.2021
нформатика, 10 класс К.Ю. Поляков, Е.А. Еремин
Устройство компьютера
Практические работы
Моделирование работы компьютера
Программа «ЛамПанель» – это модель процессора, который управляет ламповой панелью, то есть, может с помощью специальных команд зажигать и гасить определенные лампочки.
4 – оперативная память
Коды в памяти
Память (область 4) разбита на ячейки размером 1 байт = 8 бит. Значение каждой ячейки записывается в виде двух шестнадцатеричных цифр – каждая из них кодируется ровно четырьмя битами.
Каждая строчка в окне 4 содержит 8 байт памяти. Число слева, выделенное красным цветом – это адрес (номер) первой ячейки, показанной в этой строке. Справа от шестнадцатеричных кодов показана символьная строка из 8 символов – те же данные, только представленные как символы.
Данные можно записывать в память напрямую, используя команду DATA, например, можно набрать такую программу:
Если теперь нажать клавиши Ctrl+F9, происходит ассемблирование («сборка») – перевод программы в машинные коды, затем эти коды записываются в память:
Посмотрим на окно отладчика. Каждый байт памяти имеет собственный адрес, адреса соседних байтов отличаются на единицу. Однако байтовые ячейки, как правило, слишком малы для хранения чисел (как целых, так и дробных) и машинных команд. Поэтому процессор должен уметь работать с более крупными блоками данных, которые часто называют машинными словами. Программа «ЛамПанель» умеет работать с 16-битными словами, то есть может сразу читать из памяти (в регистр) и записывать в память двухбайтный блок.
Любая машинная команда состоит из целого числа 16-битных слов, то есть из четного числа байтов. По договоренности адресом двухбайтового слова считается меньший из адресов входящих в него байтов, причем адрес этот обязательно должен быть четным.
В нашем случае память записаны два 16-битных слова (4 байта), 313216 и FFFF16, причем эти слова процессор распознал как две команды:
Такой перевод из кодов команд в их символьное обозначение называется дизассемблирование (обратное ассемблирование, «разборка»).
Эту программу можно запустить, нажав на клавишу F9, и убедиться, что она действительно скопирует содержимое регистра R3 в регистр R2.
Теперь посмотрим на окно «Память»:
Видим, что байты 16-битного слова расположены «наоборот» – сначала младший байт 3216, а затем – старший 3116. Кроме того, в правой части окна видно, что эти коды соответствуют символам «21яя». Все специальные коды (не соответствующие каким-то принятым изображениям символов) обозначены точками. Таким образом, компьютер, основанный на архитектуре фон Неймана, не может самостоятельно различить, где данные, а где команды.
Выполнение программы
Теперь выполним программу в пошаговом режиме, нажав на клавишу F8. После этого в регистр PC (англ. programcounter – программный счётчик) записывается стартовый адрес 0, с которого начинается выполнение программы. В окне Отладчик зелёным цветом выделена первая команда. Она еще не выполнялась, но будет выполнена при повторном нажатии F8.
При этом регистр PC, будет указывать на начало следующей команды (которая еще не выполнялось).
- регистр PC содержит адрес команды, которая будет выполнена следующей; как только эта команда будет выбрана из памяти, регистр-счетчик автоматически будет увеличен так, чтобы снова указывать на очередную команду;
- процессор воспринимает байты, расположенные по этому адресу, как код команды (а не как данные);
- программа всегда начинает выполняться с некоторого известного (в данном случае – нулевого) адреса, который «вшит» в компьютер и автоматически заносится в регистр PC при его включении;
- программа останавливается, когда будет выполнена команда STOP с кодом FFFF16.
Работа с памятью
Для того, чтобы обрабатывать данные из оперативной памяти, процессор должен загрузить их в регистры. Поскольку программа и данные расположены в одной области памяти, размещать данные можно сразу после команды STOP:
Метка D нужна для того, чтобы удобно было загружать адрес блока данных в регистр, например, так:
Можно считать, что D – это переменная программы. После этого легко загрузить в регистр данные из памяти:
MOV (R0),R1 ; загрузить в R1 данные, адрес которых записан в R0
Аналогичной командой можно изменить содержимое ячейки памяти:
MOV R2,(R0) ; записать данные из R2 в ячейку, адрес которой
; записан в R0
Заметим, что с помощью этого метода можно сразу обратиться к любой ячейке памяти, поэтому такой вид памяти называется память с произвольным доступом (англ. RAM = random access memory).
Обработка отдельных байтов
Как вы знаете, минимальная ячейка памяти, имеющая собственный адрес, называется байтом. В современных компьютерах 1 байт составляют 8 бит. Поэтому компьютер должен иметь возможность работать не только с 16-битными словами, но и с отдельными байтами.
Во-первых, в команде DATA можно задавать не только шестнадцатеричные числа, но и символьные строки, взятые в кавычки.
DATA «ABCDEFG»
В этом случае символы заданной строки записываются в память последовательно, начиная с первого. Теперь запишем адрес строки в регистр в какой-нибудь регистр, например, в R0:
Чтобы работать с отдельными байтами, используют байтовые версии команд, которые заканчиваются на букву B. Например, байтовый вариант команды MOV называется MOVB. Команда
загружает один байт из памяти (расположенный по адресу, который записан в R0) в регистр R2. Теперь рассмотрим такую задачу – преобразовать все заглавные латинские буквы в строчные. Для этого нужно посмотреть, чем отличаются коды заглавных и строчных букв:
A: 01000001
Затем нужно записать результат обратно в память, по адресу, находящемуся в R0:
Для перехода к следующему символу просто увеличиваем R0 на единицу
и выполняем те же самые команды. Отметим, что две команды
MOVB R2,(R0) ; записать байт в память
ADD 1,R0 ; к следующему байту
можно заменить на одну, которая делает то же самое:
MOVB R2,(R0)+ ; записать байт в память и перейти
; к следующему байту
Чтобы обработать 6 символов, можно организовать цикл со счётчиком в регистре R1:
MOV 6,R1 ; счётчик шагов цикла (сделать 6 раз)
MOVB (R0),R2 ; прочитать байт из памяти
OR 20,R2 ; заглавную – в строчную
MOVB R2,(R0)+ ; записать байт в память и перейти к следующему
SUB 1,R1 ; уменьшить счетчик
JNZ M ; если не все сделали – переход на метку M
DATA «ABCDEFG»
- Запустите тренажёр «ЛамПанель». Введите программу
Используя дизассемблер программы «ЛамПанель», запишите эту программу на языке ассемблера:
Запишите код команды STOP:
- Как вы думаете, какой код будет иметь команда MOVR1,R3? Проверьте свой ответ с помощью программы.
Напишите программу, которая складывает переменные A и B и записывает результат в переменную SUM:
- Напишите программу, которая преобразует строчные буквы в заглавные, используя байтовые операции. Блок данных может выглядеть так:
DATA «abcdefgh»
- Усовершенствуйте программу так, чтобы цикл останавливался не после заданного количества букв, а тогда, когда очередной прочитанный байт равен 0. Возможно, вам понадобятся другие команды условного или безусловного перехода – изучите их по справочной системе (клавиша F1).
- Поскольку в компьютере с архитектурой фон Неймана программа и данные расположены в одной области памяти, программа может менять свой собственный код. Напишите какую-нибудь программу, которая изменяет сама себя во время работы.
Процессор и устройства вывода
Наконец, мы подошли к самой интересной возможности программы «ЛамПанель» — управлению ламповой панелью. Ламповая панель (цифра 1 на рисунке) – это устройство вывода.
Обмен данными процессора и внешнего устройства происходит через порты – регистры контроллера внешнего устройства. У ламповой панели 8 портов, которые называются P0, P1, P2, P3, P4, P5, P6 и P7. Каждый порт «отвечает» за одну строку лампочек, например, для того, чтобы «зажечь» всю верхнюю строку нужно записать в порт P0 код FFFF16 (все 16 бит – единичные). Для этого можно использовать, например, команды
MOV FFFF, R0
OUT R0, P0
К сожалению, записать число сразу в порт нельзя – сначала нужно записать его в регистр (в данном примере – в R0), а потом – из регистра в порт.
Для того, чтобы изменить второй сверху ряд лампочек, нужно записать новое значение в P1 и т.д.; последний ряд управляется портом P7. Например, для того, чтобы все ряды лампочек горели одинаково, можно записать нужный код сначала в регистр:
MOV AAAA, R0
а затем из этого регистра – во все порты:
OUT R0, P7
Здесь многоточие обозначает аналогичные команды записи содержимого регистра R0 в порты P2…P6. Однако вместо последней серии из 8 команд можно использовать всего одну:
SYSTEM 2
Эта команда вызывает системную процедуру с номером 2, находящуюся в ПЗУ компьютера. Для того, чтобы увидеть все процедуры, которые записаны в ПЗУ, нужно щелкнуть по кнопке или выбрать пункт верхнего меню Программа – Просмотр ПЗУ. После этого появляется окно, в левой части которого перечислены все системные процедуры (с их номерами), а в правой части показывается код выбранной процедуры:
В этом списке есть много полезных процедур, в том числе
0 – очистка экрана (погасить все лампочки);
1 – зажечь все лампочки на панели;
3-4 – прокрутка изображения вниз и вверх;
6-9 – логические операции;
1216 – вывод числа, записанного в регистр R0, в десятичной системе счисления;.
1316 – вывод числа, записанного в регистр R0, в шестнадцатеричной системе счисления.
Обратите внимание, что номер системной процедуры задается в шестнадцатеричной системе счисления.
Рассмотрим еще одну задачу: вывести на экран рисунок, закодированный в виде шестнадцатеричных чисел (бит, равный единице, обозначает горящую лампочку). Для этого нужно сначала записать коды рисунка в память. Поскольку наш компьютер основан на архитектуре фон Неймана, в нем программа и данные находятся в одной области памяти. Поэтому данные можно записать с помощью специальной команды DATA после команды STOP:
. ; здесь будет программа
M: ; метка – начало блока данных
DATA AAAA ; код первой строчки
DATA 5555 ; код последней строчки
Для того, чтобы вывести этот рисунок на экран, нужно записать его адрес в регистр R0 и вызвать системную процедуру с номером 5:
SYSTEM 5 ; вывести на экран рисунок, адрес которого в R0
DATA AAAA ; код первой строчки
- Как вы думаете, что выведет приведенная выше (в теоретической части) программа, которая вызывает системную процедуру с номером 5? Проверьте ваш ответ с помощью тренажёра.
- Закодируйте изображение домика и выведите его на экран.
- Добавьте в предыдущую программу команды, которые сначала шифруют изображение, используя операцию «исключающее ИЛИ» с маской BCA716, а затем – восстанавливают исходное изображение. При изменении маски программа не должна изменяться. Изучите текст системной процедуры, которую вы используете.
- Напишите программу, которая делает «бегущую строку» из рисунка-домика.
- Напишите программу, которая организует «обратный отсчет» от 100 до 0, а затем выводит рисунок с домиком и останавливается.
Источник: topuch.com