Задача «Школа танцев» РОИ 2008 Автор задачи: Вадим Юрьевич Антонов Разбор: Сергей Игоревич Назаров.

Презентация:



Advertisements
Похожие презентации
Массивы в Паскале. Создание массива: var a:array [1..5] of integer; i:integer; begin for i:=1 to 5 do begin write ('a[',i,']='); readln(a[i]); end; end.
Advertisements

Оператор присваивания := Ввода Read(x1,x2,…) Readln(x1,x2,…) Вывода Writex(x1,x2,…) Writeln(x1,x2,…) Составной оператор begin …. End;
Program show; User CRT, Graph; const N=1000; var X, Y:array [1..N] of integer; Gd, Gm, xm, ym, i:integer; begin Gd:=0; Initgraph (Gd, Gm, ); xm:=getmaxX;
5.Дана матрица А и вектор Х соответствующих размерностей. Нечетные строки матрицы заменить элементами вектора Х. Результаты работы: n=4 m=
Одномерный массив Turbo Pascal 9 класс. Объясните каждый шаг в программе. Что делает программа? Сколько раз срабатывает цикл? Var A : array [1..10] of.
Решение задач с использованием массивов
9.Задана целочисленная матрица. Вывести N чисел - максимальные значения элементов для каждой строки, где N - количество строк матрицы
Тема: Нахождение минимального и максимального элемента в массиве.
Поиск максимального и минимального элемента линейного массива на языке Turbo Pascal. Program poisk; Const n=10; Type mass=array[1..n] of integer; Var a:mass;
Циклические алгоритмы. Циклическими называются алгоритмы, в которых повторяется определенная последовательность действий (тело цикла). Определение.
3. Дана прямоугольная матрица, элементами которой являются целые числа. Поменять местами ее строки следующим образом: первую строку с последней, вторую.
Задачи сортировки для одномерного массива ПРОСТОЙ ВЫБОР.
PROGRAM example1; const m=100; var a : ARRAY [1.. m] of INTEGER; i,k,n,q : INTEGER; BEGIN readln (n); randomize; WRITELN('Полученный массив:' ); FOR i.
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100 – баллы учащихся выпускного класса за итоговый тест.
Задача Разбить предложение по словам. В предложении могут быть знаки «.», «!», «?» и «,»
Программирование на языке Паскаль. Часть II К. Поляков, Сумма выбранных элементов 1 Задача: заполнить массив случайными числами в интервале [-10,10]
Циклические алгоритмы Обобщающий урок. Ответьте на вопросы: 1.Что такое алгоритм? 2.Какие типы алгоритмов мы изучили? 3.Какие алгоритмы называются циклическими?
const n=10; var a:array[1..n] of integer; i,j,c,b,k:integer; begin randomize; for i:=1 to n do begin a[i]:=random(11)-5;write(a[i]:5) end;writeln;
1 Программирование на языке Паскаль Тема 2. Максимальный элемент массива.
PROGRAM example1; CONST N = 8; M = 10; VAR a : ARRAY [ 1.. N, 1.. M ] of INTEGER; i, j : INTEGER; BEGIN FOR i := 1 TO N DO FOR j := 1 TO M DO a[ i, j ]
Транксрипт:

Задача «Школа танцев» РОИ 2008 Автор задачи: Вадим Юрьевич Антонов Разбор: Сергей Игоревич Назаров

Решение с асимптотикой О(N 2 ) ABBABABBAA

Решение с асимптотикой О(N) ABBABABBAA Sum[0] = 0; Sum[i] = Sum[i 1] + 1, S[i] = 'A' Sum[i] = Sum[i 1] - 1, S[i] = 'B' Sum[i]: S[i]:

Решение с асимптотикой О(N) var Count: array[-NMAX...NMAX] of integer; Ans: int64;... Sum := 0; Ans := 0; Count[0] := 1; for i := 1 to N do begin if (S[i] = 'A') then Sum := Sum + 1; else Sum := Sum 1; inc(Ans, Count[Sum]); inc(Count[Sum]); end; writeln(Ans);