B. Простое Ленточное Программирование
Primary tabs
а вот теперь мне серьезно не помешает посторонняя помощь
есть задача, условие тут:
http://codeforces.ru/problemset/problem/...
в принципе, дабы по ссылкам не ходить:
/* ввод standard input вывод standard output Существует язык программирования, в котором каждая программа представлена непустой последовательностью символов «<» и «>» и цифр. Объясним, как работает интерпретатор этого языка программирования.Программа интерпретируется посредством движения указателя команды (IP), который состоит из двух частей. Указатель текущего символа (CP); Указатель направления (DP), который может указывать налево или направо; Изначально CP указывает на крайний левый символ в последовательности, а DP указывает направо. Мы повторяем следующие шаги до тех пор, пока CP впервые укажет куда-то за пределы последовательности. Если CP указывает на цифру, то интерпретатор выводит эту цифру. Затем CP перемещается на один шаг согласно направлению DP. После этого значение написанной в последовательности цифры уменьшается на один. Если выведенная цифра была 0, значит, ее нельзя уменьшить. Поэтому она удаляется из последовательности, и длина последовательности уменьшается на один. Если CP указывает на «<» или «>», то направление DP меняется на «влево» или «вправо», соответственно. Затем CP двигается на один шаг согласно DP. Если новый символ, на который указывает CP — это «<» или «>», то предыдущий символ будет удален из последовательности. Если в какой-то момент выполнения программы CP выходит за пределы последовательности, то выполнение программы завершается. У Вас есть последовательность s1,?s2,?...,?sn, состоящая из символов «<», «>» и чисел. Вы должны ответить на q запросов. Каждый запрос характеризуется двумя целыми числами l и r и спрашивает, сколько раз будет выведена каждая цифра, если мы запустим последовательность sl,?sl?+?1,?...,?sr как независимую программу на описанном языке. В первой строке входных данных содержатся два целых числа n и q (1???n,?q???100) — длина последовательности s и количество запросов. Вторая строка содержит s, последовательность из «<», «>» и цифр (0..9), записанных слева направо. Заметьте, что символы s не разделяются пробелами. Каждая из следующих q строк содержит по два целых числа li и ri (1???li???ri???n) — i-ый запрос. Для каждого запроса выведите 10 целых чисел, записанных через пробел: x0,?x1,?...,?x9, где xi равняется количеству выведенных цифр i при выполнении соответствующей программы из запроса. Выводите ответы на запросы в том порядке, в каком запросы даны во входных данных. */
- Log in to post comments
- 9700 reads
vedro-compota
Fri, 02/22/2013 - 10:31
Permalink
это задача из текущего
это задача из текущего семестра? (условие ещё не читал - вечером посмотрю)
_____________
матфак вгу и остальная классика =)
vedro-compota
Sat, 02/23/2013 - 10:07
Permalink
так какие у вас есть
так какие у вас есть соображения по поводу решения? предлагаю удалить ужасно процитированное условие и написать что вы думаете по поводу способа решения задачи.
_____________
матфак вгу и остальная классика =)
baton
Sat, 02/23/2013 - 22:01
Permalink
так. мысли.
насколько я понял условие задачи,
изначально последовательность представляет строку символов (чаров) (точнее даже не строку, а список - про списки читаем в книге "C++. Освой на примерах, Динман М.И." ( http://padabum.com/d.php?id=9670), пятая глава книги), заполненной всевозможной кашей - это следует из "....Если CP указывает на цифру..."
пытаюсь научиться адекватно конвертировать чар в инт.
таким способом вроде должно получиться - http://www.gamedev.ru/code/forum/?id=398...
потом.... есть структура IP, чей элемент CP есть указатель на (n)ный член последовательности, а DP есть char, принимающий два значения ( "") указывающие (n+1)ный или (n-1)ный член последовательности будет обработан после (n)ного
два вложеных цикла (один в другой) с несколькими условиями обрабатывают каждый член, если он - цифра, при этом - строго больше нуля - то, выводится на экран и уменьшается на один; если встречается "", то значение DP меняется. если член последовательности не цифра или ноль (меньше нуля), он удаляется из последовательности.
кроме того, количество повторений цикла ("запросов") задается пользователем.
но все равно в голове немного каша..
кстати есть костяк программы, но я никак не могу до конца его осознать (т.к. нахожусь в процессе познания теории) и пытаюсь писать свой костяк....
данный мне:
baton
Sun, 02/24/2013 - 13:04
Permalink
тест программы.
особо меня смущают примеры тестов программы, приведенные в условии для самопроверки:
Примеры тестов
Входные данные
7 4
1>3>22 1 3
4 7
7 7
1 7
Выходные данные
0 1 0 1 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
2 3 2 1 0 0 0 0 0 0
очевидно, вся фишка заключена в этих строках:
"..У Вас есть последовательность s1,?s2,?...,?sn, состоящая из символов «» и чисел. Вы должны ответить на q запросов. Каждый запрос характеризуется двумя целыми числами l и r и спрашивает, сколько раз будет выведена каждая цифра, если мы запустим последовательность sl,?sl?+?1,?...,?sr как независимую программу на описанном языке..."
но я все еще не догоняю, что и как надо написать.
baton
Sun, 06/09/2013 - 02:24
Permalink
после значительного перерыва продолжаю
задача построена на идее преобразования типа char в int и наоборот.
инт в чар переводится без особых проблем (по определению чар это числовое значение, номер символа)
а для преобразования чар в инт нужны специальные средства. как правило можно обойтись функцией atoi();
пример кода:
как мы можем видеть, тут значению эн типа инт присваивается значение а типа чар. все весьма просто.
едем дальше.
baton
Sun, 06/09/2013 - 02:54
Permalink
обращаю ваше внимание
мы должны будем так же сравнивать отвечает ли символ определенному условию, или нет - делается это следующим образом