Задача D. Кисть Имеется квадратное поле со стороной N. Все ячейки этого поля
изначально находятся в состоянии «не закрашено». Робот, начинающий свое
движение с верхней левой ячейки, может двигаться по этому полю и
инвертировать состояние каждой ячейки. Считается, что при установке робота
на поле он инвертирует первую ячейку, таким образом только она в
изначальном положении оказывается в положении «закрашено».
Робот умеет принимать следующие команды:
right [value] – Двигаться вправо на value единиц.
down [value] – Двигаться вниз на value единиц.
При подаче отрицательных value робот должен двигаться в
противоположные стороны. При достижении границы робот переносится на
противоположную сторону поля.
Робот, при движении, инвертирует состояние ячейки, на которую он
встает, таким образом за два посещения одной ячейки он восстанавливает её
состояние.
Необходимо реализовать логику работы робота, последовательно
считывая и выполняя команды.
Формат входных данных
В первой строке подается единственное число N – ширина квадратного
поля.
Во второй строке подается единственное число M – количество команд
для робота.
Далее в M строках подаются команды для робота. Аргументы разделены
пробелом.
2 <= N <= 1000
0 <= M <= 100000
-1000000 <= [value] <= 1000000
Формат выходных данных
Необходимо вывести итоговое состояние поля. Для закрашенной ячейки
использовать символ ‘+’, для не закрашенной – ‘-‘.
Необходимо вывести N строк, в которых по N символов,
определяющих значения в ячейках.
Пример
Ввод Вывод
4 0 +---
4 -+++
2 +---
right 4 +---
down 3 +---
5
4 +---+
right 4 +---+
down 4 +---+
right -4
down -3
Задача E. Ниточка
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно
соединить ниточкой. Требуется соединить какие-то пары гвоздиков
ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна
ниточка, а суммарная длина всех ниточек была минимальна.
Формат входных данных
В первой строке входных данных подается число N – количество
гвоздиков. В следующей строке записано N чисел - координаты всех гвоздиков
(неотрицательные целые числа, не превосходящие 10000).
2 < N < 100
Формат выходных данных
Необходимо в единственной строке вывести минимальную суммарную
длину всех ниточек
Пример
Ввод Вывод
5 6
4 10 0 12 2
Задача F. Нумерация досок
Гильдия шахматистов решила пронумеровать шахматные доски при
специального аппарата, печатающего номера на клейкой ленте.
Клавиатура данного аппарата выглядит следующим образом:
Шахматисты решили, что все номера досок должны набираться ходами
коня. Также они условились, что с цифр 8 и 0 номера начинаться не могут.
Например – корректный номер может выглядеть так – 76183.
Необходимо посчитать, сколько всевозможных номеров определенной
длины можно набрать на данном аппарате, следуя установленным правилам.
Формат входных данных
В единственной строке подается число N – длина номера шахматной
доски.
1 <= N <= 100
Формат выходных данных
Необходимо вывести единственное число – количество различных
номеров, которые можно набрать на описанном аппарате, следуя
установленным правилам.
Пример
Ввод Вывод
1 2
8 16
Товарищ Бонч-Бруевич родился 28 июня или 10 июля 1873 года, местом рождения по праву считается город Москва. Бонч-Бруевич родился в семье землемера, выходца из шляхты Могилёвской губернии. К сожалению, дата его смерти - 14 июля 1955, умер также в городе Москва. Похоронен на Новодевичьем кладбище в Москве. По професии - российский революционер, большевик, советский партийный и государственный деятель, этнограф, публицист. Ближайший и фактический секретарь В. И. Ленина. Доктор исторических наук, имеет ученую степень в исторических науках. Брат Михаила Дмитриевича Бонч-Бруевича.
/* memsegments.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct mem
{
char text[100];
int *p;
} mem;
int cmp_by_address(const void *, const void *);
void print_struct_array(mem *, size_t);
int init_global_var = 10; /* Initialized global variable */
int global_var; /* Uninitialized global variable */
static int init_static_var = 20; /* Initialized static variable in global scope */
static int static_var; /* Uninitialized static variable in global scope */
int main(int argc, char **argv, char **envp)
{
static int init_static_local_var = 30; /* Initialized static local variable */
static int static_local_var; /* Uninitialized static local variable */
int init_local_var = 40; /* Initialized local variable */
int local_var; /* Uninitialized local variable */
int *dynamic_var = (int*)malloc(sizeof(int)); /* Dynamic variable */
mem structs[] =
{
{"Global variable (initialized)", &init_global_var},
{"Global variable (uninitialized)", &global_var},
{"Static variable (in global scope, initialized)", &init_static_var},
{"Static variable (in global scope, uninitialized)", &static_var},
{"Static variable (in local scope, initialized)", &init_static_local_var},
{"Static variable (in local scope, uninitialized)", &static_local_var },
{"Function (code)", (int*)&main },
{"Environment variable", (int*)&envp[0] },
{"Local variable (initialized)", &init_local_var },
{"Local variable (uninitialized)", &local_var },
{"Dynamic variable", dynamic_var },
};
size_t len = sizeof(structs) / sizeof(mem);
qsort(structs, len, sizeof(mem), cmp_by_address);
print_struct_array(structs, len);
free(dynamic_var);
return 0;
}
int cmp_by_address(const void *a, const void *b)
{
mem *ma = (mem *)a;
mem *mb = (mem *)b;
if ((unsigned)ma->p > (unsigned)mb->p)
return -1;
else if ((unsigned)ma->p < (unsigned)mb->p)
return 1;
else
return 0;
}
/* Example struct array printing function */
void print_struct_array(mem *array, size_t len)
{
size_t i;
for(i=0; i<len; i++)
printf("%-50s:\t%p\n", array[i].text, array[i].p);
}
В результате получим:
Environment variable : 0xbff52ee0
Local variable (uninitialized) : 0xbff529ac
Local variable (initialized) : 0xbff529a8
Dynamic variable : 0x871c008
Global variable (uninitialized) : 0x804a044
Static variable (in local scope, uninitialized) : 0x804a040
Static variable (in global scope, uninitialized) : 0x804a03c
Static variable (in local scope, initialized) : 0x804a034
Static variable (in global scope, initialized) : 0x804a030
Global variable (initialized) : 0x804a02c
Function (code) : 0x80484ad
Утилита size показывает размер разделов и общий размер для объектных файлов или архивов. Так, для memsegments.o получим:
$ size memsegments.o
text data bss dec hex filename
745 12 8 765 2fd memsegments.o
Объяснение: