Лучшее - детям. Знак качества
Краевое государственное общеобразовательное автономное учреждение
Центр образования "Эврика"
  • :
  • :
Турнир по программированию «Осенний LIST».

Турнир по программированию «Осенний LIST».

Дата проведения:
31 октября 2020 года
Место проведения:
В домашних условиях.

Окончательные результаты:

7-9 класс

Участник

ОУ

Класс

A

B

C

D

E

Итого

Диплом

1

Татаринов Евгений

МАОУ Гимназия № 39

8

100

100

4

98

6

308

победитель

2

Тожиев Роман

КГОБУ Мильковская СШ № 2

9

24

100

8

92

.

224

призер

10 класс

Участник

ОУ

Класс

A

B

C

D

E

Итого

Диплом

1

Пирогов Василий

МБОУ Лицей № 21

10

100

.

.

.

.

100

призер

11 класс

Участник

ОУ

Класс

A

B

C

D

E

Итого

Диплом

1

Пудлаева Злата

МБОУ СШ № 40

10

100

.

90

100

2

292

победитель


Краткий разбор задач:

Задача A. Настольный теннис. Простая задача на условия.

Решение Татаринова Евгения:

n = int(input())

if n < 21:

print('Petya' if n % 4 == 1 or n % 4 == 2 else 'Vasya')

else:

print('Petya' if n % 2 == 1 else 'Vasya')

Задача B. Задача из старого ЕГЭ.

Задача на идею. Понятно, что искомое число можно получить если из двоичной записи данного нам числа удалить последние два разряда (это эквивалентно делению данного числа на 4 с округлением вниз) и применить к нему описанный алгоритм. Если получилось число не превышающее данное – нужное число получится из увеличенного на единицу.

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

Решение Тожиева Романа

def A(n):

b = bin(n)

if b.count('1') % 2:

b += '10'

else:

b += '00'

return int(b, 2)


k = int(input())

n = k // 4

R = A(n)

if R <= k:

R = A(n + 1)

print®

Задача C. Вещий сон. Двумерные массивы.

Нужное значение однозначно определяется количеством квадратов меньшего размера, которое можно расположить в большом по горизонтали и по вертикали (эти значения следует перемножить).

Решение Дмитрия (других данных нет)

n, m, k = map(int, input().split())

i = (k — 1) // n + 1

j = k % n;

if j == 0:

j=n

l = max(0, j — m)

r = min(j — 1, n — m)

t = max(0, i — m)

b = min(i — 1, n — m)

a = (r — l + 1) * (b — t + 1)

print(a)

Задача D. Другая задача из старого ЕГЭ. Задача на однопроходный алгоритм на строки.

Аккуратно пройдем по строке от начала до конца, проверяя, является ли текущий символ цифрой. Если да – увеличиваем счетчик цифр на 1, если нет – проверяем, чему равен счетчик цифр. Если его значение равно одному из двух данных, то фрагмент этого размера нужно либо вырезать из текущей строки, либо просто не переносить в новую строку-ответ. После этого сбрасываем счетчик цифр на ноль. Не забудьте сделать эту же проверку в самом конце строки.

Решение Пудлаевой Златы

#include <iostream>

#include <string>

using namespace std;

int main()

{

string s;

int k1 = 0, k2 = 0;

int a = 0;

cin>>k1>>k2;

cin>>s;

s+=".";

for (unsigned int i = 0; i < s.size(); i++)

{

if (s[i]=='0'||s[i]=='1'||s[i]=='2'||s[i]=='3'||s[i]=='4'||s[i]=='5'||s[i]=='6'||s[i]=='7'||s[i]=='8'||s[i]=='9')

{

a++;

}

else

{

if (a == k1 || a == k2)

{

s.erase(i-a, a);

i=i-a;

}

a = 0;

}

}

s.erase(s.size()-1,1);

cout<<s;

return 0;

}

Задача E. Чередующиеся цифры. Динамическое программирование.

Двумерной динамикой можно найти количество способов разбиения данной строки длиной n на k частей. В данной таблице по горизонтали n, по вертикали – k. На пересечении – количество способов разбиения. Например, найдем количество способов разбить строку длиной 9 на три части. Для этого вычислим все предыдущие значения:

1

2

3

4

5

6

7

8

9

1

1

1

1

1

1

1

1

1

1

2

0

0

1

1

2

2

3

3

4

3

0

0

0

0

1

1

3

3

Первый способ: отделим таким образом 10 – 1010101. Сколько есть способов разбить вторую часть строки еще на две части? Ответ в таблице на пересечении n = 7 и k = 2, и он равен 3. Действительно, 10 – 10-10101, 10 – 1010-101 и 10 – 101010-1.

Второй способ: отделим таким образом 1010 – 10101. Сколько есть способов разбить вторую часть строки еще на две части? Ответ в таблице на пересечении n = 5 и k = 2, и он равен 2. Действительно, 1010 – 10-101 и 1010 – 1010-1.

Третий способ: отделим таким образом 101010 – 101. Сколько есть способов разбить вторую часть строки еще на две части? Ответ в таблице на пересечении n = 3 и k = 2, и он равен 1. Действительно, 1010 – 1010-1.

Других способов нет. Итого 6.

Мы свели вычисление новых значений таблицы к суммированию уже вычисленных. Ответом для данного значения n будет сумма всех чисел таблицы в столбце n. Например, для n = 9, это 1 + 4 + 6 + 4 + 1 = 16.

Вот такое решение вполне можно сдать на полный балл.

Интересные числа получаются! Для n = 1 ответом будет 1, для n = 3 ответом будет 1 + 1, для n = 5 ответом будет 1 + 2 + 1, для n = 7 ответом будет 1 + 3 + 3 +1, для n = 9 ответом будет 1 + 4 + 6 + 4 + 1, и так далее. Можно пойти еще дальше, заметить закономерность и свести задачу к одномерной динамике. Оставляю эту задачу Вам на доработку.

Авторское решение ниже (выделите текст).

n = int(input())

L = [0, 1, 2, 3]

for i in range(4, n + 1):

if i % 2:

L.append(L[-1] + L[-3])

else:

L.append(L[-1] + L[-2])

print(L[n])



Уважаемые коллеги!

Краевое государственное общеобразовательное учреждение «Центр образования «Эврика» проводит в 2020 году в Камчатском крае турнир по программированию «Осенний LIST».

Турнир по программированию «Осенний LIST» — очно-заочная командная олимпиада по информатике. В связи с эпидемиологической обстановкой, в 2020 году турнир пройдет в дистанционном режиме. Вместо отборочного тура состоится пробный.

Продолжительность основного тура — 3 часа. Во время олимпиады участнику предлагается решить 5 задач. Написанные участниками решения (исходный текст программы — файл с расширением .pas, .dpr, .c, .cpp и т.п.) сдаются в автоматизированную тестирующую систему.

Участникам турнира запрещено использовать любые письменные материалы (книги, тетради с записями, …), также они не могут пользоваться никакими электронными устройствами (мобильными телефонами, калькуляторами, плеерами, флешками и т.п.), а также не имеют право использовать интернет, кроме страницы сдачи решений в тестирующей системе.

Во всех задачах требуется написать консольное приложение. Входные данные считываются с клавиатуры, а выходные данные выводятся на экран. Программа должна при всех допустимых входных данных работать не более указанного времени (как правило, 1 сек) и использовать память в размере, не большем 64М (включая память на хранение данных и бинарного кода программы).

Сложность заданий средняя, примерно соответствует муниципальному этапу ВсОШ.

Порядок проведения турнира. (старая версия, будет изменен)

Задачи прошлых лет (с 2012 года, модуль 34).

Задачи 2019 года на сайте CATS ДВФУ.

C 2019 года турнир проходит на базе тестирующей системы ДВФУ https://imcs.dvfu.ru/cats (в прошлые годы турнир проходил на сайте informatics), желательно, чтобы участники владели основами работы с тестирующей системой (умели отправлять решения, понимать вердикты ТС). Всем интересующимся олимпиадной информатикой рекомендуется зарегистрироваться (инструкция) на этом сайте и прорешать задачи пробного тура. Доступ к пробному туру будет открыт 27 сентября. Задачи пробного тура низкой и средней сложности, направлены на знакомство с тестирующей системой. Результаты пробного тура тура не влияют на итоги основного турнира.

Задачи основного тура.


В Камчатском крае турнир пройдет 31 октября 2020 года (суббота).

График турнира в 2020 году:

С 27 сентября по 30 октября 2020 – пробный тур, самостоятельное решение задач.

31 октября 2020 года с 10.00 до 13.00 – проведение турнира.

31 октября 2020 года с 13.00 – подведение итогов, определение победителей, разбор задач.

с 01 ноября 2020 – изготовление дипломов (в электронном виде).

Участие в турнире – бесплатное.

Методист по информационным технологиям КГОАУ ЦО «Эврика» Карабанов Антон Викторович.

По всем вопросам можно обращаться по почте akar_@mail.ru

Спортивное программирование в Камчатском крае.

14:00
2425

Нет комментариев. Ваш будет первым!