e-olymp 165. Симметрия

21/12/2017 by Даниил Крутоголов

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

Входные данные

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

Выходные данные

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

Код программы

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n, m;
    double k;
    cin >> n;
    m = log2(n);
    k = log2(n);
    while (m != k){
        n = n - (pow(2,m));
        m = log2(n);
        k = log2(n);
    }
    cout << m + 1;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

double k;

cin >> n;

m = log2(n);

k = log2(n);

while (m != k){

n = n - (pow(2,m));

m = log2(n);

k = log2(n);

}

cout << m + 1;

return 0;

}

Решение задачи

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

AL13

31/03/2016 by Молоканов Юрий

Условие

Имеется [latex]n[/latex] черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.?

Тестирование

№	Входные данные	Выходные данные
1	1	1
2	2	01
3	5	10011
4	12	101100010011
5	20	00111001101100010011

Здесь нули — черные карточки, единицы — белые, а первый символ строки обозначает карточку, лежащую внизу стопки.

Код

#include <iostream>
using namespace std;

// Узел. Используется в очереди
struct node {
    bool val;   // Значение узла
    node *next; // Указатель на следующий узел
    node(int v, node *n = NULL) {
        val = v;
        next = n;
    }
};

// Очередь. Используется как представление стопки
struct Queue {
    node *head;
    Queue(node *h = NULL) {
        head = h;
    }
    void push(bool v) { // Добавить элемент в очередь
        head = new node(v, head);
    }
    bool pop() {    // Изъять элемент из очереди
        if(head != NULL && (head -> next) != NULL) {
            node *i = head;
            node *p = i;
            while(i -> next != NULL) {
                p = i;
                i = i -> next;
            }
            bool v = i -> val;
            p -> next = NULL;
            delete i;
            return v;
        } else {
            node *n = head;
            bool v = head -> val;
            head = head -> next;
            delete n;
            return v;
        }
    }
};

int main() {
    int n;  // Количество карточек в стопке
    cin >> n;
    Queue cards;
    bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки
    for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку
        cards.push(t);  // Добавляем текущую карточку
        cards.push(cards.pop());    // Перекладываем карточку из-под стопки наверх
        t = !t; // Меняем цвет текущей карточки
    }
    cards.push(1);  // Добавляем белую карточку наверх
    for(int i = 0; i < n; i++)   // Выводим полученную стопку
        cout << cards.pop();
    return 0;
}

#include <iostream>

using namespace std;

// Узел. Используется в очереди

struct node {

bool val; // Значение узла

node *next; // Указатель на следующий узел

node(int v, node *n = NULL) {

val = v;

next = n;

}

};

// Очередь. Используется как представление стопки

struct Queue {

node *head;

Queue(node *h = NULL) {

head = h;

}

void push(bool v) { // Добавить элемент в очередь

head = new node(v, head);

}

bool pop() { // Изъять элемент из очереди

if(head != NULL && (head -> next) != NULL) {

node *i = head;

node *p = i;

while(i -> next != NULL) {

p = i;

i = i -> next;

}

bool v = i -> val;

p -> next = NULL;

delete i;

return v;

} else {

node *n = head;

bool v = head -> val;

head = head -> next;

delete n;

return v;

}

};

int main() {

int n; // Количество карточек в стопке

cin >> n;

Queue cards;

bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки

for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку

cards.push(t); // Добавляем текущую карточку

cards.push(cards.pop()); // Перекладываем карточку из-под стопки наверх

t = !t; // Меняем цвет текущей карточки

}

cards.push(1); // Добавляем белую карточку наверх

for(int i = 0; i < n; i++) // Выводим полученную стопку

cout << cards.pop();

return 0;

}

Решение

Алгоритм разбора стопки можно описать следующим образом:

Выкладываем на стол верхнюю карточку.
Пока в стопке есть карты, выполняем действия:
1. перекладываем под низ стопки верхнюю карточку;
2. выкладываем на стол верхнюю карточку.

Поэтому для построения стопки нам достаточно обратить эти действия (выкладывание на стол заменить добавлением в стопку, а перекладывание верхней карточки под низ стопки — перекладыванием нижней на ее верх) и выполнять их в обратном порядке. Тогда алгоритм построения будет следующим:

Пока на столе не останется одна карточка, выполняем действия:
1. добавляем карточку, выложенную на стол последней из имеющихся, на верх стопки;
2. перекладываем карточку из-под стопки наверх.
Добавляем карточку наверх.

Так как карточки на столе считаем разложенными в нужном по условию порядке, то есть чередующимися по цвету начиная с белой карточки, то при сборе стопки очередная добавляемая карточка будет менять цвет относительно предыдущей, причем последняя добавляемая будет белой.

Для решения задачи удобнее всего будет воспользоваться очередью, поскольку при построении стопки мы добавляем карточки только в один ее конец, а изымаем при перекладывании всегда из противоположного. Более того, в данном случае структуру можно значительно облегчить, оставив из методов только push() и pop(), причем из последнего можно за ненадобностью удалить проверку исключительной ситуации при попытке изъять карточку из пустой стопки, так как по алгоритму прямо перед изъятием всегда выполняется добавление карточки. Карточки могут быть только двух цветов, поэтому узлы очереди будут хранить значения типа bool.

Перейдем к практическому решению. Прежде всего получим количество карточек в требуемой стопке и объявим очередь:

int n;
cin >> n;
Queue cards;

int n;

cin >> n;

Queue cards;

Затем объявим переменную для цвета текущей карточки и инициализируем ее таким образом, чтобы последняя добавляемая карточка была белой. Так как при четном числе карточек в стопке последняя выкладываемая (она же — первая добавляемая) будет черной, а при нечетном — белой, то при кодировании черных и белых цветов как [latex]0[/latex] и [latex]1[/latex] соответственно инициализируется она следующим значением:

bool t = n % 2;

1	bool t = n % 2;

Теперь перейдем к сбору стопки. Действуем согласно описанному выше алгоритму: пока в стопке не окажутся все карточки, кроме одной, добавляем карточку на условный верх стопки, перекладываем карточку из-под низа наверх и меняем цвет следующей карточки. После этого добавляем на верх стопки белую карточку:

for(int i = 0; i < n - 1; i++) {
    cards.push(t);
    cards.push(cards.pop());
    t = !t;
}
cards.push(1);

for(int i = 0; i < n - 1; i++) {

cards.push(t);

cards.push(cards.pop());

t = !t;

}

cards.push(1);

Наконец, разбираем стопку, начиная с условного низа, и выводим ее как ответ на поставленную задачу:

for(int i = 0; i < n; i++)
    cout << cards.pop();

1 2	for(int i = 0; i < n; i++) cout << cards.pop();

Ссылки

Код программы на Ideone.com;

Список задач по структурам данных на Algolist.manual.ru.

Related Images:

MLoops 16

01/12/2015 by Кондратюк Настя

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).

123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231

Тесты

[latex]m[/latex] [latex]n[/latex]
4 3	123 231 132 123
8 8	12312312 23123123 13213213 12312312 23123123 13213213 12312312 23123123
10 27	123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123

Код программы

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> m >> n;
	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++){
			if((i+j)%3==0) cout << 2;
			else{
				if(j%3==0){
					if((i+j+1)%3==0) cout << 1;
					else cout << 3;
				}
				else if((j-1)%3==0) cout << 1;
				     else cout << 3;
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

for(int i=1; i<=m; i++){

for(int j=1; j<=n; j++){

if((i+j)%3==0) cout << 2;

else{

if(j%3==0){

if((i+j+1)%3==0) cout << 1;

else cout << 3;

}

else if((j-1)%3==0) cout << 1;

else cout << 3;

}

cout << endl;

}

return 0;

}

ideone.com

Решение

Пронумеруем строки от [latex]1[/latex] до [latex]m[/latex] , столбцы — от [latex]1[/latex] до [latex]n[/latex].

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

Положение символа [latex]2[/latex] определяется однозначно для всей таблицы [latex]\left (n+m \right )\vdots 3[/latex]. В столбцах, где [latex]n\vdots 3[/latex], положение символа [latex]1[/latex] — [latex]\left ( n+m+1 \right )\vdots 3[/latex] , на оставшихся свободных местах — символ [latex]3[/latex] . В столбцах, где [latex]\left ( n-1\right )\vdots 3[/latex], на свободных местах стоит символ [latex]1[/latex]. В оставшихся столбцах на свободных местах стоит символ [latex]3[/latex].

Related Images:

MLoops 17

16/11/2015 by Павел Загинайло

Задача

+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

Тесты

Входные данные

Выходные данные

+++++++++++++++++++++++++++++++
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+++++++++++++++++++++++++++++++
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+.........+.........+.........+

+++++++++++++++++++++++++++++++

+.........+.........+.........+

+++++++++++++++++++++++++++++++

++++++++
+....+..
+....+..
+....+..
+....+..

++++++++

+....+..

++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’. Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +. Далее проверяем, делится ли номер столбца, уменьшенный на 1, на число [latex]k+1[/latex], где [latex]k[/latex] — вводимый параметр. Во всех остальных случаях пишем ‘.’.

Код программы

#include <iostream>
using namespace std;

int main() {
	int m, n, k; //m-строки, n - столбцы
	cin >> m >> n >> k;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			if (i%6 == 0) cout << '+';
			else if (j%(k+1) == 0) cout << '+';
			else cout << '.';
		}
	cout << endl;	
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n, k; //m-строки, n - столбцы

cin >> m >> n >> k;

for (int i = 0; i < m; i++){

for (int j = 0; j < n; j++){

if (i%6 == 0) cout << '+';

else if (j%(k+1) == 0) cout << '+';

else cout << '.';

}

cout << endl;

}

return 0;

}

Код программы на ideone.com

Related Images:

MLoops8

07/11/2015 by Настя Филипчук

Задача

Входные данные

Два числа:количество столбцов и строк.

Выходные данные

Таблица размером n*m со следующей закономерностью:

+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21

Код

#include <iostream>
using namespace std;
int main(){
	int m,n; 
	cin>>n>>m;
	for(int i=1;i<m+1;i++){ 
		for(int j=1;j<n+1;j++){  
			if(i%2==0){
				if ((j+3)%4==0) 
					cout<< "1"; 
				else 
					cout<<(j%4==0?"2":"+");
			}
			else{
				if ((j+1)%4==0)
					cout<<"1";
				else 
					cout<<((j+2)%4==0?"2":"+");
			}
		}
	cout<<endl;
	}	
	return 0;
}

#include <iostream>

using namespace std;

int main(){

int m,n;

cin>>n>>m;

for(int i=1;i<m+1;i++){

for(int j=1;j<n+1;j++){

if(i%2==0){

if ((j+3)%4==0)

cout<< "1";

else

cout<<(j%4==0?"2":"+");

}

else{

if ((j+1)%4==0)

cout<<"1";

else

cout<<((j+2)%4==0?"2":"+");

}

cout<<endl;

}

return 0;

}

Упрощенный вариант

#include <iostream>
using namespace std;
int main()
{
	int m,n; 
	cin>>n>>m;
	for(int i=1;i<m+1;i++)
	{ 
		for(int j=1;j<n+1;j++)
		{  
			if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))
			{
				cout<< "1"; 
			}
			if ((j+3-2*(i%2))%4!=0)
			{
				cout<<((j+2*(i%2))%4==0?"2":"+");
			}
		}
		cout<<endl;
	}	
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int m,n;

cin>>n>>m;

for(int i=1;i<m+1;i++)

{

for(int j=1;j<n+1;j++)

{

if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))

{

cout<< "1";

}

if ((j+3-2*(i%2))%4!=0)

{

cout<<((j+2*(i%2))%4==0?"2":"+");

}

cout<<endl;

}

return 0;

}

Тесты

[latex]n[/latex]	[latex]m[/latex]	Выходные данные
1	1	+
7	7	+21++21 1++21++ +21++21 1++21++ +21++21 1++21++ +21++21
15	6	+21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++
25	8	+21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21

Решение

Для решения сначала нужно найти закономерность чередования символов в таблице. Пусть нумерация столбцов и строк будет начинаться с единицы, тогда, если строка [latex]i \vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 1 кратен 4 ([latex] (j+1)\vdots 4 [/latex]), то в данной строке и столбце находится «1», если же результат от прибавления номера столбца к 2 кратен 4([latex] (j+2)\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Если же строка [latex]i\vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 3 кратен 4 ([latex] (j+3)\vdots 4[/latex]), то в данной строке и столбце находится «1», а если номер столбца кратен 4([latex] j\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Ссылки

Код программы

Упрощенный код

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…