Помощь с олимпиадой

[fsfS2fasS]

Задача 3: Игра
На уроке информатики учитель предложил Васе сыграть в следующую игру.

На доске записаны по порядку все целые числа от 1 до N. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.

Игра продолжается, пока на доске есть хотя бы два числа.

Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число X. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.

Входные данные
В первой строке содержится целое число N (2 ≤ N ≤ 109) — начальное количество чисел на доске.

Во второй строке содержится целое число X (1 ≤ X ≤ N) — число, которое должно остаться в конце игры.

Выходные данные
Выведите последовательность целых чисел, состоящую из чисел 1 и 2 — ходов Васи. Число 1 означает, что Вася стирает все числа на нечётных позициях, число 2 — на чётных.

Каждый ход Васи выводите на отдельной строке.

Система оценки


В этой задаче 20 тестов, не считая тестов из условия. За каждый пройденный тест будет начисляться 5 баллов.

На тесты наложены следующие ограничения:

Номера тестов	Дополнительные ограничения
1 – 2	Тесты из условия
3 – 10	N ≤ 1000
11	X = 1
12 – 14	X = N
15 – 22	без дополнительных ограничений

Примеры

Ввод	Вывод	Пояснение
10 5	2 2 1	На доске записаны числа: 1 2 3 4 5 6 7 8 9 10 Первым ходом Вася стирает все числа на чётных позициях, на доске остаются числа: 1 3 5 7 9 Затем позиции оставшихся чисел перенумеровываются — то есть оставшиеся после первого хода Васи числа получат номера от 1 до 5. Вторым ходом Вася снова удаляет все числа на чётных позициях, на доске остаются числа: 1 5 9 Третьим ходом Вася удаляет все числа на нечётных позициях, и на доске останется только число 5, которое и было нужно.
6 6	1 2 1	Во втором примере выписаны числа 1 2 3 4 5 6 Вася стирает числа на нечётных позициях, остаются 2 4 6 Вася стирает число 4, которое стоит на чётной позиции. Остаются 2 6 Вася стирает число 2, которое стоит на нечётной позиции. Осталось число 6.

Задача 2: Пирожки
Рядом с домом Пети расположена пекарня, в которой пекут вкусные пирожки с ягодами. Пете очень нравятся три вида пирожков: с брусникой, с черникой и с вишней. Пирожок с брусникой стоит A рублей, пирожок с черникой стоит B рублей, пирожок с вишней стоит C рублей.

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

• если в некоторый день он купил пирожок с брусникой, то на следующий день он купит пирожок с черникой;
• если в некоторый день он купил пирожок с черникой, то на следующий день он купит пирожок с вишней;
• если в некоторый день он купил пирожок с вишней, то на следующий день он купит пирожок с брусникой.

Например, если сегодня Петя купит пирожок с брусникой, то завтра он купит пирожок с черникой, послезавтра — пирожок с вишней, на следующий за послезавтра день — пирожок с брусникой, и так далее.

Зная, какой пирожок Петя купит сегодня, определите, сколько денег Петя потратит на пирожки в течение N дней, начиная с сегодняшнего.

Входные данные
В первой строке входных данных содержится целое число A (1 ≤ A ≤ 106) — цена пирожка с брусникой.

Во второй строке содержится целое число B (1 ≤ B ≤ 106) — цена пирожка с черникой.

В третьей строке содержится целое число C (1 ≤ C ≤ 106) — цена пирожка с вишней.

В четвёртой строке содержится целое число N (2 ≤ N ≤ 2×109) — количество дней, за которые нужно посчитать расходы Пети на пирожки.

В пятой строке содержится число 1, 2 или 3, указывающее, какой пирожок Петя купит сегодня. Число 1 соответствует пирожку с брусникой, число 2 — пирожку с черникой, число 3 — пирожку с вишней.

Выходные данные
Выведите единственное целое число — сумму, которую Петя потратит на пирожки.

Обратите внимание, что для больших значений N ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Система оценки
Решение, правильно работающее только для случаев, когда n ≤ 3, будет оцениваться в 9 баллов.

Решение, правильно работающее только для случаев, когда n ≤ 1000, будет оцениваться в 72 балла.

Примеры

Ввод	Вывод	Пояснение
14 12 11 7 1	88	Во всех примерах цены пирожков и количество дней, в течение которых нужно посчитать расходы Пети на пирожки, одни и те же. В первом примере первой покупкой Пети будет пирожок с брусникой. Значит, покупки Пети за семь дней могут быть описаны последовательностью брусника, черника, вишня, брусника, черника, вишня, брусника. Сумма, потраченная на покупки, составит 14 + 12 + 11 + 14 + 12 + 11 + 14 = 88 рублей.
14 12 11 7 2	86	Во втором примере первой покупкой Пети будет пирожок с черникой. Соответственно, покупки Пети за семь дней могут быть описаны последовательностью черника, вишня, брусника, черника, вишня, брусника, черника. Сумма, потраченная на покупки, составит 12 + 11 + 14 + 12 + 11 + 14 + 12 = 86 рублей.
14 12 11 7 3	85	В третьем примере первой покупкой Пети будет пирожок с вишней. Следовательно, покупки Пети за семь дней могут быть описаны последовательностью вишня, брусника, черника, вишня, брусника, черника, вишня. Сумма, потраченная на покупки, составит 11 + 14 + 12 + 11 + 14 + 12 + 11 = 85 рублей.

Задача 1: Путешествие поездом
Класс, в котором учится Дима, отправляется в путешествие! И, конечно же, ребята поедут поездом, в плацкартном вагоне, причём не в обычном, а в инновационном — в нём целых 11 плацкартных «купе»! Получив свой билет, Дима задумался, как можно быстро определять тех, кто едет в конкретном плацкартном «купе», а также на боковых местах, расположенных строго напротив этого «купе».

Помогие Диме определить по номеру «купе» расположенные в нём места, а также боковые места, расположенные строго напротив него (для лучшего понимания внимательно изучите рисунок).

Расположение мест в плацкартном вагоне.

Входные данные
В первой строке входных данных содержится целое число K (1 ≤ K ≤ 11) — номер «купе», интересующий Диму.

Выходные данные
Выведите шесть целых чисел в порядке возрастания — места, расположенные в соответствующем «купе» и строго напротив него.

Система оценки
В этой задаче 10 тестов, не считая теста из условия. За каждый пройденный тест будет начисляться 10 баллов.

Примеры

Ввод	Вывод
2	5 6 7 8 63 64

 

[Irval]

3. Представьте все возможные исходы в виде дерева и найдите ширину до интересующей вершины. Сложность алгоритма поиска X из исходной последовательности - O(|V|+|E|). Почитайте на сайте ИТМО, там даже доказательства есть :) -

Пожалуйста, авторизуйтесь для просмотра ссылки.

2. Я еще понимаю, когда не выходит решить более сложные задачи на олимпиадные алгоритмы, но с этой что не так?
N // 3 - количество полных циклов, когда мальчик тратит A + B + C рублей
N % 3 - количество "остаточных дней", где 1 -> A, 2 -> A + B.
1. Тут без комментариев. Казалось бы, эту задачу должны решить все, точно как и 2ю.

 

[vvasyz]

3. Представьте все возможные исходы в виде дерева и найдите ширину до интересующей вершины. Сложность алгоритма поиска X из исходной последовательности - O(|V|+|E|). Почитайте на сайте ИТМО, там даже доказательства есть :) -

Пожалуйста, авторизуйтесь для просмотра ссылки.

2. Я еще понимаю, когда не выходит решить более сложные задачи на олимпиадные алгоритмы, но с этой что не так?
N // 3 - количество полных циклов, когда мальчик тратит A + B + C рублей
N % 3 - количество "остаточных дней", где 1 -> A, 2 -> A + B.
1. Тут без комментариев. Казалось бы, эту задачу должны решить все, точно как и 2ю.

Привет, задачу решил:

n, result = int(input()), int(input())
spis = list(range(1, n + 1))
while spis != [result]:
    index = spis.index(result) + 1
    if index % 2 != 0:
        spis = list(filter(lambda x: spis.index(x) % 2 == 0, spis))
        print(2)
    else:
        spis = list(filter(lambda x: spis.index(x) % 2 != 0, spis))
        print(1)

Но она не может работать с большими числами(до 1000000000), зависает, можно это как-то поправить?

 

[hyper00944156]

3. Представьте все возможные исходы в виде дерева и найдите ширину до интересующей вершины. Сложность алгоритма поиска X из исходной последовательности - O(|V|+|E|). Почитайте на сайте ИТМО, там даже доказательства есть :) -

Пожалуйста, авторизуйтесь для просмотра ссылки.

2. Я еще понимаю, когда не выходит решить более сложные задачи на олимпиадные алгоритмы, но с этой что не так?
N // 3 - количество полных циклов, когда мальчик тратит A + B + C рублей
N % 3 - количество "остаточных дней", где 1 -> A, 2 -> A + B.
1. Тут без комментариев. Казалось бы, эту задачу должны решить все, точно как и 2ю.

Напишите просто программу и мы сверим =)

 

[fsfS2fasS]

3. Представьте все возможные исходы в виде дерева и найдите ширину до интересующей вершины. Сложность алгоритма поиска X из исходной последовательности - O(|V|+|E|). Почитайте на сайте ИТМО, там даже доказательства есть :) -

Пожалуйста, авторизуйтесь для просмотра ссылки.

2. Я еще понимаю, когда не выходит решить более сложные задачи на олимпиадные алгоритмы, но с этой что не так?
N // 3 - количество полных циклов, когда мальчик тратит A + B + C рублей
N % 3 - количество "остаточных дней", где 1 -> A, 2 -> A + B.
1. Тут без комментариев. Казалось бы, эту задачу должны решить все, точно как и 2ю.

я вообще 0

Привет, задачу решил:

n, result = int(input()), int(input())
spis = list(range(1, n + 1))
while spis != [result]:
    index = spis.index(result) + 1
    if index % 2 != 0:
        spis = list(filter(lambda x: spis.index(x) % 2 == 0, spis))
        print(2)
    else:
        spis = list(filter(lambda x: spis.index(x) % 2 != 0, spis))
        print(1)

Но она не может работать с большими числами(до 1000000000), зависает, можно это как-то поправить?

это какая?

 

[Chshi]

я вообще 0

Это 11 класс? решил что-нибудь? Если да, то напиши плиз

 

[Chshi]

Привет, задачу решил:

n, result = int(input()), int(input())
spis = list(range(1, n + 1))
while spis != [result]:
    index = spis.index(result) + 1
    if index % 2 != 0:
        spis = list(filter(lambda x: spis.index(x) % 2 == 0, spis))
        print(2)
    else:
        spis = list(filter(lambda x: spis.index(x) % 2 != 0, spis))
        print(1)

Но она не может работать с большими числами(до 1000000000), зависает, можно это как-то поправить?

Это какой номер задачи?

 

[Den094]

я вообще 0

это какая?

3

 

[Irval]

Привет, задачу решил:

n, result = int(input()), int(input())
spis = list(range(1, n + 1))
while spis != [result]:
    index = spis.index(result) + 1
    if index % 2 != 0:
        spis = list(filter(lambda x: spis.index(x) % 2 == 0, spis))
        print(2)
    else:
        spis = list(filter(lambda x: spis.index(x) % 2 != 0, spis))
        print(1)

Но она не может работать с большими числами(до 1000000000), зависает, можно это как-то поправить?

Попробуйте не менять массив и индекс при каждой итерации while, в задаче есть закономерности.

 

[fsfS2fasS]

c

3

sps

Привет, задачу решил:

n, result = int(input()), int(input())
spis = list(range(1, n + 1))
while spis != [result]:
    index = spis.index(result) + 1
    if index % 2 != 0:
        spis = list(filter(lambda x: spis.index(x) % 2 == 0, spis))
        print(2)
    else:
        spis = list(filter(lambda x: spis.index(x) % 2 != 0, spis))
        print(1)

Но она не может работать с большими числами(до 1000000000), зависает, можно это как-то поправить?

sps

 

[Chshi]

c

sps

sps

40 баллов дали за неё

 

[qqeroid]

1 и 2 не можете написать решение пожалуйста?

 

[ploor1ze]

Привет, задачу решил:

n, result = int(input()), int(input())
spis = list(range(1, n + 1))
while spis != [result]:
    index = spis.index(result) + 1
    if index % 2 != 0:
        spis = list(filter(lambda x: spis.index(x) % 2 == 0, spis))
        print(2)
    else:
        spis = list(filter(lambda x: spis.index(x) % 2 != 0, spis))
        print(1)

Но она не может работать с большими числами(до 1000000000), зависает, можно это как-то поправить?

а какая задача

 

[Chshi]

var a,b,c:integer;
begin
readln(a);
if a=1 then writeln('1 2 3 4 65 66');
if a=2 then writeln('5 6 7 8 63 64');
if a=3 then writeln('9 10 11 12 61 62');
if a=4 then writeln('13 14 15 16 59 60');
if a=5 then writeln('17 18 19 20 57 58');
if a=6 then writeln('21 22 23 24 55 56');
if a=7 then writeln('25 26 27 28 53 54');
if a=8 then writeln('29 30 31 32 51 52');
if a=9 then writeln('33 34 35 36 49 50');
if a=10 then writeln('37 38 39 40 47 48');
if a=11 then writeln('41 42 43 44 45 46');
end.
Решение 1 задачи на языке Pascal

1 и 2 не можете написать решение пожалуйста?

Написал

var a,b,c:integer;
begin
readln(a);
if a=1 then writeln('1 2 3 4 65 66');
if a=2 then writeln('5 6 7 8 63 64');
if a=3 then writeln('9 10 11 12 61 62');
if a=4 then writeln('13 14 15 16 59 60');
if a=5 then writeln('17 18 19 20 57 58');
if a=6 then writeln('21 22 23 24 55 56');
if a=7 then writeln('25 26 27 28 53 54');
if a=8 then writeln('29 30 31 32 51 52');
if a=9 then writeln('33 34 35 36 49 50');
if a=10 then writeln('37 38 39 40 47 48');
if a=11 then writeln('41 42 43 44 45 46');
end.
Решение 1 задачи на языке Pascal

Написал

100 баллов за него дают

 

[qqeroid]

с

var a,b,c:integer;
begin
readln(a);
if a=1 then writeln('1 2 3 4 65 66');
if a=2 then writeln('5 6 7 8 63 64');
if a=3 then writeln('9 10 11 12 61 62');
if a=4 then writeln('13 14 15 16 59 60');
if a=5 then writeln('17 18 19 20 57 58');
if a=6 then writeln('21 22 23 24 55 56');
if a=7 then writeln('25 26 27 28 53 54');
if a=8 then writeln('29 30 31 32 51 52');
if a=9 then writeln('33 34 35 36 49 50');
if a=10 then writeln('37 38 39 40 47 48');
if a=11 then writeln('41 42 43 44 45 46');
end.
Решение 1 задачи на языке Pascal

Написал

спасибо

 

[qqeroid]

2 никто не знает как решается?

 

[Avzms]

Можете пожалуйста решение 2 задачи выложить

 

[HORMAN]

var a,b,c:integer;
begin
readln(a);
if a=1 then writeln('1 2 3 4 65 66');
if a=2 then writeln('5 6 7 8 63 64');
if a=3 then writeln('9 10 11 12 61 62');
if a=4 then writeln('13 14 15 16 59 60');
if a=5 then writeln('17 18 19 20 57 58');
if a=6 then writeln('21 22 23 24 55 56');
if a=7 then writeln('25 26 27 28 53 54');
if a=8 then writeln('29 30 31 32 51 52');
if a=9 then writeln('33 34 35 36 49 50');
if a=10 then writeln('37 38 39 40 47 48');
if a=11 then writeln('41 42 43 44 45 46');
end.
Решение 1 задачи на языке Pascal

Написал

100 баллов за него дают

вот он - гений олимпиадной информатики.

 

[Chshi]

вот он - гений олимпиадной информатики.

А что не так? это полностью правильное решение, я в основной школе изучал только паскаль и больше ничего

 

[FTP_z0nG]

Нужны ответ на 2 задачу