Файл: Составители.docx

Из таблицы видно, что ответ задачи равен сумме мах+abs(min)+1
#include

using namespace std;

int main (){

    int f1=0,f2=0,min=0,max=0,temp=0;

    string str;

    cin>>str;

    for (int i=0;i
        if (str[i]-48==1){temp++;

            if (temp>max)max=temp;   }

        else{ temp--;

            if (temp
cout<
    return 0; }
Задача 86 (№ 387) Левая рекурсия (Сложность: 20%)

В теории формальных грамматик и автоматов (ТФГиА) важную роль играют так называемые контекстно-свободные грамматики (КС-грамматики). КС-грамматикой будем называть четверку, состоящую из множества N нетерминальных символов, множества T терминальных символов, множества P правил (продукций) и начального символа S, принадлежащего множеству N.

Каждая продукция p из P имеет форму A –> a, где A нетерминальный символ (A из N), а a – строка, состоящая из терминальных и нетерминальных символов. Процесс вывода слова начинается со строки, содержащей только начальный символ S. После этого на каждом шаге один из нетерминальных символов, входящих в текущую строку, заменяется на правую часть одной из продукций, в которой он является левой частью. Если после такой операции получается строка, содержащая только терминальные символы, то процесс вывода заканчивается.

Во многих теоретических задачах удобно рассматривать так называемые нормальные формы грамматик. Процесс приведения грамматики к нормальной форме часто начинается с устранения левой рекурсии. В этой задаче мы будем рассматривать только ее частный случай, называемый непосредственной левой рекурсией. Говорят, что правило вывода A –> R содержит непосредственную левую рекурсию, если первым символом строки R является A.

Задана КС-грамматика. Требуется Найти количество правил, содержащих непосредственную левую рекурсию.

1 ... 30 31 32 33 34 35 36 37 38

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

№	INPUT.TXT	OUTPUT
1	3 S->Sabc S->A A->AA	2

Первая строка входного файла INPUT.TXT содержит количество n (1 <= n <= 1000) правил в грамматике. Каждая из последующих n строк содержит по одному правилу. Нетерминальные символы обозначаются заглавными буквами латинского алфавита, терминальные - строчными. Левая часть продукции отделяется от правой символами –>. Правая часть продукции имеет длину от 1 до 30 символов.

Выходные данные. В выходной файл OUTPUT.TXT выведите ответ на задачу.

#include

#include

using namespace std;

int main(){

char s[300];

int n,i,k;

k=0;

cin>>n;

for(i=1;i<=n;i++){

cin>>s;

if(s[0]==s[3]) k++; }

cout<
return 0; }

Для решения задачи достаточно внимательно прочитать одно предложение: Говорят, что правило вывода A –> R содержит непосредственную левую рекурсию, если первым символом строки R является A.

Т.е. должно выполняться условие s[0]=s[3]

Задача 87 (№ 633) ACM World Finals (Сложность: 20%)

Некоторые из вас, наверно, знают, что ежегодно проводится чемпионат мира по программированию среди студентов (http://acm.baylor.edu). В финал этого соревнования проходят около 80 команд со всего мира.

Каждая команда состоит из трех человек и имеет название. Напишите программу, которая по краткому названию команды и фамилиям ее участников, строит полное название команды.

Полное название команды состоит из краткого названия команды и списка фамилий ее участников. Фамилии участников в списке должны быть упорядочены по алфавиту и отделены друг от друга запятыми. Название команды от фамилий участников должно быть отделено двоеточием. После каждого знака препинания должен стоять ровно один пробел.

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

№	INPUT.TXT	OUTPUT.TXT
1	Dream Team Knuth Dijkstra Cormen	Dream Team: Cormen, Dijkstra, Knuth
2	Ivanovs Team Ivanov Ivanov Ivanov	Ivanovs Team: Ivanov, Ivanov, Ivanov
3	Team a aa aaa	Team: a, aa, aaa

Входной файл INPUT.TXT содержит ровно 4 строки. Первая из строк содержит название команды. Каждая из следующих трех строк содержит фамилию одного из членов команды. Длины строк не превышают 50 символов.

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

Выходной файл OUTPUT.TXT должен содержать ровно одну строку, содержащую полное название команды.

#include

using namespace std;

int main(){

    string s,t,f1,f2,f3,max,min,sr;

    getline(cin,t);

    cin>>f1>>f2>>f3;

    cout<
    if (f1>f2){ min=f2; max=f1;}

    else{ min=f1; max=f2;}

    if (f3>max){sr=max; max=f3;}

    else sr=f3;

    if (f3
    cout<
    return 0; }

Задача 88 (№ 675) Детали (Сложность: 20%)

№	INPUT.TXT	OUTPUT
1	4 6 AA.BBB A....B AAA..B A..BBB	1

а клеточном поле N•M расположены две жёсткие детали. Деталь A накрывает в каждой строке несколько (не ноль) первых клеток, деталь B — несколько (не ноль) последних; каждая клетка либо полностью накрыта одной из деталей, либо нет. Деталь B начинают двигать влево, не поворачивая, пока она не упрётся в A хотя бы одной клеткой. Определите, на сколько клеток будет сдвинута деталь B.

Входные данные. В первой строке входного файла INPUT.TXT записано два числа N и M —число строк и столбцов соответственно (1 ≤ N, M ≤ 100). Далее следуют N строк, задающих расположение деталей. В каждой находится ровно M символов "A" (клетка, накрытая деталью A), "B" (накрытая деталью B) или "." (свободная клетка).

Выходные данные. В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число — ответ на задачу.

#include

#include

using namespace std;

int main(){

string s;

int n,m,k;

cin>>n>>m;

int min=m;

for(int i=0;i
k=0;

cin>>s;

for(int j=0;j
if (s[j]=='.') k++;}

if (k
cout<
return 0; }

достаточно найти минимальное количество точек между А и В

1 ... 30 31 32 33 34 35 36 37 38

Задача 89 (№ 315) Наименьшая система счисления (Сл.: 26%)

Известно, что основанием позиционной системы счисления называют количество различных символов, используемых для записи чисел в данной системе счисления. Также известно, что любое число x в b-ичной системе счисления имеет вид x=a₀∙b⁰+a₁∙b¹+…+a_n∙bⁿ, где b ≥ 2 и 0 ≤ a_i < b.

Для записи чисел в b-ичной системе счисления, где b ≤ 36, могут быть использованы первые b символов из следующего списка 0,1,…, 9, A, B, …, Z. Например, для записи чисел в троичной системы используются символы 0, 1, 2, а в двенадцатеричной - 0,1,…, 9, A, B.

№	INPUT.TXT	OUTPUT
1	123	4
2	ABCDEF	16
3	AD%AF	-1

Требуется написать программу, которая по входной строке S определит, является ли данная строка записью числа в системе счисления, с основанием не большим 36, и, если является, определит минимальное основание этой системы счисления.

Входные данные. Входной файл содержит входную строку. Длина строки не превышает 255. Все символы имеют коды от 32 до 127.

Выходные данные. Выходной файл должен содержать одно число. Если строка является записью числа в некоторой системе счисления, то нужно вывести минимальное основание такой системы счисления. Иначе вывести -1.

#include

#include

using namespace std;

int main(){

string s;

getline(cin,s);

int n=s.length();

int max=0;

int w=0;

for(int i=0;i
if (s[i]=='0') w++;}

if(w==n) {cout<<2; return 0;}

for(int i=0;i
int k=s[i];

if ((k<48) || ((k>57) && (k<65)) || (k>90))

{cout<<"-1"; return 0;}

if (k>max) max=k;

}

if (max<=57) cout<
else cout<
return 0; }

Задача содержит много «подводных камней»:
1) строка может содержать пробелы, поэтому для чтения используем getline(cin,s);
2) Нет единичной системы счисления, т.е. если все нули – выводим 2
Проверка: состоит ли строка только из цифр и заглавных латинских букв? Код чисел (0,1,2,3,..,9) от 48 до 57.

Код латинских заглавных букв (А,B,C,..Z) от 65 до 90.
Находим символ с мах кодом.

Если это число, то отнимаем 47, если буква -57 и получаем основание СС.

Задача 90 (№ 277) Школьная алгебра (Сложность: 27%)

Трёхчлен a + bx + сy от двух переменных x и y однозначно определяется коэффициентами a, b и c. Написать программу, которая по заданным a, b и c выводит соответствующий трёхчлен, записанный с использованием алгебраических соглашений:

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

№	INPUT.TXT	OUTPUT.TXT
1	0 2 -1	2x-y
2	3 0 -2	3-2y

При этом запрещено менять местами члены.

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

Во входном файле через пробел записаны целые коэффициенты a, b и с, каждое из которых не превосходит 30000 по абсолютной величине.

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

Выходной файл OUTPUT.TXT должен содержать трехчлен, записанный с использованием алгебраических соглашений.

#include

using namespace std;

int main() {

int a,b,c;

cin>>a>>b>>c;

if(a!=0) cout<
if(b>1 && a!=0)cout<<"+"<
if(b>1 && a==0)cout<
if(b==1 && a!=0)cout<<"+x";

if(b==1 && a==0)cout<<"x";

if(b<-1)cout<
if(b==-1)cout<<"-x";
if(c>1) {

if(b==0 && a==0)cout<
if(b!=0 || a!=0)cout<<"+"<if(c==1){

if(b==0 && a==0)cout<<"y";

if(b!=0 || a!=0)cout<<"+y";

}

if(c<-1)cout<
if(c==-1)cout<<"-y";

if(a==0 && b==0 && c==0)cout<<0; }

Шахматы

Задача 91 (№ 935) Шахматное поле (Сложность: 16%)

На стандартной шахматной доске 8х8 заданы координаты двух клеток. Требуется определить: имеют ли данные клетки одинаковый цвет?

№	INPUT.TXT	OUTPUT.TXT
1	1 1 4 4	YES
2	1 2 7 5	NO

Входные данные. Входной файл INPUT.TXT содержит целые числа x1, y1, x2, y2, описывающие координаты двух клеток (x1,y1) и (x2,y2). Ограничения: 1 ≤ x1,y1,x2,y2 ≤ 8.

Выходные данные. В выходной файл OUTPUT.TXT выведите YES, если поля одного цвета, или слово NO в противном случае.

#include

using namespace std;

int main(){

    int x1,y1,x2,y2;

    cin>>x1>>y1>>x2>>y2;

     if((x1+y1+x2+y2)%2==0) cout<<"YES";  else cout<<"NO";

return 0; }

Задача 92 (№ 798) Шахматная доска – 2. (Сложность: 18%)

Аня разделила доску размера m × n на клетки размера 1×1 и раскрасила их в черный и белый цвет в шахматном порядке. Васю заинтересовал вопрос: клеток какого ц

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

Для того чтобы выяснить это, он спросил у Ани, в какой цвет она раскрасила j-ю клетку в i-м ряду доски. По этой информации Вася попытался определить, клеток какого цвета на доске больше. Требуется написать программу, которая по размерам доски и цвету j-й клетки в i-м ряду определит, клеток какого цвета на доске больше — черного или белого.

№	INPUT.TXT	OUTPUT.TXT
1	3 5 1 1 0	black
2	3 5 2 1 0	white
3	4 4 1 1 1	equal

Входные данные. Входной файл INPUT.TXT содержит пять целых чисел: m, n, i, j и c (1 ≤ m, n ≤ 109, 1 ≤ i ≤ m, 1 ≤ j ≤ n, с = 0 или с = 1). Значение c = 0 означает, что j-я клетка в i-м ряду доски раскрашена в черный цвет, а значение c = 1 – в белый цвет.

Выходные данные. В выходной файл OUTPUT.TXT выведите одно из трех слов:

black, если черных клеток на доске больше,

white, если белых клеток на доске больше,

equal, если черных и белых клеток на доске поровну.
#include

using namespace std;

int main(){

int m,n,j,i,c;

cin>>m>>n>>j>>i>>c;

if (m%2==0||n%2==0){cout<<"equal"; return 0; }

if (c==0){if ((j+i)%2==0) cout<<"black"; else cout<<"white"; }

if (c==1){if ((j+i)%2!=0) cout<<"black"; else cout<<"white"; }

return 0; }

Задача 93 (№ 763) Игра с ладьей (Сложность: 19%)

На бесконечной вправо и вверх шахматной доске находится ладья. Два игрока передвигают ее по очереди. За один ход разрешено сдвинуть ладью вниз или влево на произвольное (ненулевое) количество клеток так, чтобы ладья не покинула доску. Цель игры – переместить ладью в левый нижний угол, то есть клетку с координатами (1,1). Известно, что оба игрока придерживаются оптимальной стратегии. Игрок №1 ходит первым, при этом он обязан совершить хотя бы один ход. Если первый ход сделать нельзя, то определить победителя также невозможно. Требуется написать программу, которая найдет номер победившего игрока, либо определит, что этого сделать нельзя.

№	INPUT.TXT	OUTPUT.TXT
1	1 1	0
2	1 6	1

Входные данные. Входной файл INPUT.TXT содержит два натуральных числа, разделенных пробелами: X и Y – координаты ладьи перед первым ходом (X,Y ≤ 109).

Выходные данные. В выходной файл OUTPUT.TXT выведите одно число – номер победившего игрока. Если победителя определить невозможно, то следует вывести 0.
#include

using namespace std;

int main(){

    int x,y;

    cin>>x>>y;

    if(x==1 && y==1){cout<<"0"; return 0;}

     if (x==1 || y==1) cout<<"1";

        else if(x!=y) cout<<"1"; else cout<<"2";

    return 0;}

Задача 94 (№791) Соседние клетки. (Сложность: 22%)

№	INPUT	OUTPUT
1	2	1 3 10
2	64	56 63

Клетки шахматной доски пронумерованы числами от 1 до 64 по строкам слева направо и снизу вверх. Напишите программу, которая по заданному номеру клетки определяет номера всех клеток, имеющих с ней общую сторону.

Входные данные. Входной файл INPUT.TXT содержит одно целое число от 1 до 64.

Выходные данные. В выходной файл выведите через пробел в порядке возрастания номера всех клеток, имеющих с заданной общую сторону.

#include

using namespace std;

int main(){

    int cell,a;

    cin>>cell;



    a=cell-8;

    if(a>0) cout<


    a=cell-1;

    if(a>0 && a%8!=0) cout<


    a=cell+1;

    if(a<65 && cell%8!=0) cout<


    a=cell+8;

    if(a<65) cout<
    return 0; }
Задача 95 (№ 416) Шахматный конь (Сложность: 25%)

Вася решил научиться играть в шахматы. Он нашел книгу с записями партий и внимательно их изучает. Может быть, когда-нибудь Вася станет великим шахматистом, но пока он еще учится в начальной школе, и ему нелегко дается шахматная нотация. Больше всего трудностей у Васи вызывают ходы шахматного коня. Он попросил вас написать программу, которая сможет сообщить Васе, на какие клетки можно пойти конем с заданной клетки.

№	INPUT	OUTPUT
1	e2	c1 c3 d4 f4 g1 g3
2	a1	b3 c2

Вы, наверное, тоже знаете, что конь в шахматах всегда перемещается либо на две клетки по горизонтали и на одну по вертикали, либо на одну по горизонтали и на две по вертикали. Вертикали обозначаются маленькими латинскими буквами от a до h, а горизонтали - цифрами от 1 до 8. Любая клетка на шахматной доске обозначается буквой соответствующей вертикали и цифрой соответствующей горизонтали, например, c6 или e2.

Входные данные. Во входном файле записано 2 символа – координаты клетки, где стоит конь.

Выходные данные. В выходной файл в произвольном порядке выведите все координаты клеток, на которые за один ход может попасть конь, находящийся на заданной клетке.

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

У коня 8 возможных ходов:
	i-1, х+2		i+1, х+2
i-2, х+1				i+2, х+1
		i,х
i-2, х-1				i+2, х-1
	i-1, х+2		i+1, х-2

#include

# include

using namespace std;

int main (){

char n, x; string d;

cin>>n>>x;

x=x-48; // переводим символ в число

d="_abcdefgh";
for (int i = 1; i <= 8; i++ ) {

if (n==d[i]) {

i - номер буквы в строке d:='_abcdefgh'

В строке нумерация идет с 0, поэтому для удобства дописываем любой знак в начале строки
if (i!=8 && x>2) cout<
if (i<7 && x>1) cout<
if (i<7 && x!=8) cout<
if (i!=8 && x<7) cout<
if (i!=1 && x<7) cout<
if (i>2 && x!=8) cout<
if (i>2 && x!=1) cout<
if (i!=1 && x>2) cout<
}

}

return 0;}7>7>65>

1 ... 30 31 32 33 34 35 36 37 38

Смотрите также файлы

Межгосударственный совет по стандартизации, метрологии и сертификации.pdf

Из представленного ниже графика можно сделать вывод о том, что излишки покупателей составляют тысяч денежных единиц.docx

Методические рекомендации по составлению презентаций. Подготовьте презентацию на тему Войска воздушнокосмической обороны рф.doc

Содержание Основная часть 2 Список литературы 4 Основная часть.docx

Тк 18. В задании два вопроса.docx

Файл: Составители.docx

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

Выходные данные. В выходной файл OUTPUT.TXT выведите ответ на задачу.

Задача 87 (№ 633) ACM World Finals (Сложность: 20%)

Задача 88 (№ 675) Детали (Сложность: 20%)

Задача 89 (№ 315) Наименьшая система счисления (Сл.: 26%)

Задача 90 (№ 277) Школьная алгебра (Сложность: 27%)

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

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

Шахматы

Задача 91 (№ 935) Шахматное поле (Сложность: 16%)

Задача 92 (№ 798) Шахматная доска – 2. (Сложность: 18%)

Задача 93 (№ 763) Игра с ладьей (Сложность: 19%)

Задача 94 (№791) Соседние клетки. (Сложность: 22%)

№

INPUT

OUTPUT

1

2

1 3 10

2

64

56 63

Входные данные. Входной файл INPUT.TXT содержит одно целое число от 1 до 64.

Выходные данные. В выходной файл выведите через пробел в порядке возрастания номера всех клеток, имеющих с заданной общую сторону.

Входные данные. Во входном файле записано 2 символа – координаты клетки, где стоит конь.

Выходные данные. В выходной файл в произвольном порядке выведите все координаты клеток, на которые за один ход может попасть конь, находящийся на заданной клетке.

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

Смотрите также файлы

Информация

Списки файлов

Дополнительно