Увод в програмирането, зимен семестър 2019/2020

Задача 1 (Много лесна - 2 точки)

Асистентите си намислили редица, чийто 1-вия член е числото n, а всеки следващ член е образуван по следния начин:
- ½ от предходния, ако предходното число е четно
- 3*(предходното числото)+1, в противен случай

Да се изведе на екрана номера на 1-вия член, който е със стойност единица.

Пример:
Вход:
11
Изход:

15

Обяснение на примера:

Редицата, която имаме е: 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1…., където 1 е 15-тия член на редицата.

Ограничения:

n∈[1;1048576]

Забележка:

Гарантирано е, че всяка редица, започваща с число n∈[1,1048576], има най-много 1024 члена.

Задача 2

Дадени са две крайни редици, състоящи се от цели положителни числа, съответно с n и m на брой елементи. Ако n∈[5; 1000] и m∈[2;n], възможно ли е след премахването на краен брой елементи от 1-вата редица, да получим:

a) (Лесна - 6 точки)

Втората редица (т.е пита се дали 2-рата редица е подредица на 1-вата)

Вход:
На 1-вия ред на стандартния вход се въвеждат 2 цели положителни числа - n и m, разделени с интервал. Следват 2 реда съответно с n и m на брой елементи - съответно членовете на 1-вата и 2-рата редици.
Изход:

В случай, че от 1-вата редица, можем да образуваме 2-рата, след премахване на краен брой елементи, да се изведат елементите, които трябва да бъдат премахнати (подредени в нарастващ ред на индексите им). В противен случай да се изведе “Not a subsequence!”.

Пример:
Вход:
6 3
1 2 3 4 5 6
2 3 6
Изход:

1 4 5

Вход:
6 3
1 2 3 4 5 6
3 5 1
Изход:

Not a subsequence!

Вход:
6 3
7 2 5 1 3 6
2 5 6
Изход:

7 1 3

Обяснение на примерите:
Пример 1: След като премахнем 1, 4 и 5, получаваме директно редицата 2 3 6. (забележете, че изхода е 1 4 5, а не примерно 1 5 4 или някоя друга пермутация на 1 4 5, поради изискването да се изведат сортирани в нарастващ ред на индексите)
Пример 2: 3 5 1 е подмножество на 1 2 3 4 5 6, но не и подредица!

Пример 3: След като премахнем 7, 1 и 3, получаваме директно редицата 2 5 6. (отново, в тази последователност - сортирани в нарасващ ред на индексите!)

b) (Трудна - 2 точки)

Коя да е ротация (виж дефиницията по-надолу) на 2-рата.

Вход:
На 1-вия ред на стандартния вход се въвеждат 2 цели положителни числа - n и m, разделени с интервал. Следват 2 реда съответно с n и m на брой елементи - съответно членовете на 1-вата и 2-рата редици.
Изход:

В случай, че от 1-вата редица, можем да образуваме някоя ротация на 2-рата, след премахване на краен брой елементи, да се изведат елементите, които трябва да бъдат премахнати, разделени с интервал. В противен случай да се изведе “Not a subsequence!”.

Пример:
Вход:
6 3
1 2 3 4 5 6
2 3 6
Изход:

1 4 5

Вход:
6 3
1 2 3 4 5 6
3 5 1
Изход:

2 4 6

Вход:
6 3
1 2 3 4 5 6
1 5 3
Изход:

Not a subsequence!

Обяснение на примерите:
Пример 1: След като премахнем 1, 4 и 5, получаваме директно редицата 2 3 6.
Пример 2: След като премахнем 2, 4 и 6, получаваме 1 3 5, което е ротация на 3 5 1.

Пример 3: За разлика от Пример 2, 1 5 3 не е ротация на 1 3 5, защото rot(1 3 5, 1) = 3 5 1 и rot(1 3 5, 2) = 5 1 3

ЗАБЕЛЕЖКА: Наредбата на числата от изхода (за b) подточка) няма значение! (като бонус задачка за по-напредналите - може да ги изпечатете сортирани в нарастващ ред)

Дефиниция:

Ротация на редица A = a[0], a[1], …, a[n-1], a[n] с k позиции ще наричаме редицита rot(A,k) = a[k], a[k+1], …, a[n-1], a[n], a[0], a[1], a[2], …, a[k-1]

Пример (на ротация на редица):
A=a, b, c, d
rot(A, 0) = a, b, c, d = A
rot(A, 1) = b, c, d, a
rot(A, 2) = c, d, a, b
rot(A, 3) = d, a, b, c
rot(A, 4) = a, b, c, d = A

….

ВАЖНО:

• .cpp-файла на задача 1 да бъде именуван task1.cpp;
• Ако е решена само a) на 2-ра задача, то .cpp-файла да бъде именуван task2_easy.cpp;
• Ако е решено подусловие b) на 2-ра задача, то включва решенията на a) и по тази причина не е необходимо отделно решението на а). В такъв случай, .cpp-файла да бъде именуван task2_hard.cpp.