ВУЗ: Не указан

Категория: Решение задач

Дисциплина: Не указана

Добавлен: 17.03.2024

Просмотров: 306

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Составители:

Ильина Е.А,

Волынская О.С,

учителя информатики КГУ «Гимназия №9» г.Караганды

Линейные алгоритмы

Задача 1 (№ 1) A+B (Сложность: 1%)

Входные данные. В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 109.

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

Задача 3 (№ 903) Бисер (Сложность: 2%)

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

Задача 4 (№ 942) Олимпиада (Сложность: 2%)

Задача 5 (№ 195). Эния (Сложность: 3%)

Задача 7 (№ 33) Два бандита ( Сложность: 4%)

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

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

Задача 10 (№ 819) Прямоугольный параллелепипед

(Сложность: 10%)

     x=(h*(l+w)*2)/16; нужно учесть, что банка может быть неполной

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

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

Задача 14 (№ 780) Футбол (Сложность: 22%)

Выходные данные. В выходной файл OUTPUT.TXT выведите одно число – общее количество забитых мячей.

2 способ

Задача 15 (№ 900) Три грибника (Сложность: 23%)

Разветвляющиеся алгоритмы

Задача 16 (№ 25) Больше-меньше (Сложность: 3%)

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

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

Задача 19 (№ 8)Арифметика (Сложность: 5%)

Задача 21 (№ 755) Сбор земляники (Сложность: 6%)

Выходные данные. В выходной файл выведите слово YES, если информация, опубликованная в газете, может соответствовать правде, и слово NO - иначе.

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

Задача 33 (№ 948) Сроки в книге (Сложность: 13%)

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

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

Задача 37 (№ 929) Игральные кубики (Сложность: 15%)

Входные данные. Входной файл INPUT.TXT содержит одно натуральное число n — количество очков, которые получил первый игрок (n ≤ 1010).

Задача 38 (№ 263) Метро (Сложность: 16%)

Задача 39 (№ 844) Поля (Сложность: 16%)

Входные данные. Входной файл INPUT.TXT содержит целые числа a и b – длины сторон прямоугольника (1 < = a*b ≤ 1014).

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

Задача 40 (№ 294) Болты и гайки (Сложность: 17%)

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

Выходные данные. В выходной файл выведите одно целое число – размер ущерба.

Задача 41 (№ 606)Треугольник – 3 (Сложность: 17%)

Задача 42 (№ 952) В автобусе (Сложность: 18%)

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

Задача 43 (№ 952) Кастинг (Сложность: 19%)

Требуется написать программу, которая по заданным числам n, a, b и с определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

1, если в данном тесте требуется определить минимальное количество актеров;

Вторая строка входного файла содержит разделенные пробелами четыре целых числа: n, a, b, с (1 ≤ n ≤ 10 000, 0 ≤ a ≤ n, 0 ≤ b ≤ n, 0 ≤ c ≤ n).

Задача 45 (№ 68) Дом - Школа – Дом (Сложность: 21%)

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

Задача 49 (№ 692) Бинарные числа (Сложность: 8%)

Задача № 52 (№ 233). Автобусная экскурсия (Сложность: 14%)

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

Задача 55 (№ 264) Оттепель(Сложность: 17%)

Задача 56 (№ 949) Фибоначчиева последовательность. (Сл.17%)

Задача 57 (№ 778) Офис (Сложность: 18%)

Задача 60 (№ 947) Карточки – 3 (Сложность: 22%)

Входные данные. Входной файл INPUT.TXT содержит единственное положительное число X - длина нависающей части. Число X задано с двумя знаками после запятой и 0.01 ≤ x < 10.00.

Задача 62 (№ 716) Треугольник Максима (Сложность: 25%)

Задача 63 (№ 272) Сумма max и мin (Сложность: 26%)

Массивы

Задача 66 (№ 149). Разворот (Сложность: 9%)

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

Задача 69 (№ 637) NEERC (Сложность: 17%)

Задача 70 (№ 293) Налоги (Сложность: 20%)

Выходные данные. В выходной файл выведите одно число - номер фирмы, от которой государство получает наибольший налог. Если таких фирм несколько, выведите фирму с наименьшим номером.

Строки

Задача 74 (№ 324) Четырехзначный палиндром ( Сл.: 10%)

Задача 80 (№ 43) Нули (Сложность: 16%)

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

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

Задача 81 (№ 297) Кругляши (Сложность: 16%)

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

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

Задача 83 (№ 895) Крестики-нолики (Сложность: 19%)

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

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

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

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

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

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

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

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


Из таблицы видно, что ответ задачи равен сумме мах+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=a0∙b0+a1∙b1+…+an∙bn, где b ≥ 2 и 0 ≤ ai < 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>