|
2 Готуємось до олімпіади з інформатики 2014-2015 |
 |
 |
 |
|
Добавил(а) Administrator
|
|
06.10.14 11:53 |
|
Готуємось до олімпіади з інформатики- 2
«Класичні алгоритми для роботи з масивами та рядками, їх реалізація у вигляді програм»
1. Перевірити, чи є одномірний числовий масив упорядкованим за зростанням.
2. Дано натуральна таблиця A[10]. В таблицю B[] записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2
3. Вивести числовий ряд Фібоначі (a[i]=a[i-1]+a[i-2];)
Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від'ємними числами, а дівчаток — додатними у вигляді цілих значень α1,α2,…, αN ? Окрім того, у всіх дівчаток на голівках зав'язані бантики заввишки 10 см, а висота паркану H см.
4. . «День народження» – 30 балів.
Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.
Вхідні дані
Перший рядок містить загальну кількість учнів, натуральне число N.
В наступних рядках кількість розданих цукерок.
Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить кількість дівчат та хлопчиків через пропуск.
Приклад
|
input.txt
|
output.txt
|
|
5
3
1
2
4
3
|
3 2
|
5. Новорічна гра
Ім’я вхідного файлу: game.in
Ім’я вихідного файлу: game.out
На новорічному святі Дід Мороз вирішив провести цікаву гру для двох найвеселіших дітлахів.
У мішку Діда Мороза знаходяться не подарунки, а N карток, на кожній із яких написано деяке ціле число Ai. У гру грають двоє дітей. На початку гри обидва гравці навмання витягують по одній картці з мішка Діда Мороза. Учасник, який вийняв картку з більшим числом, отримує від Діда Мороза цукерки, до того ж кількість отриманих цукерок дорівнює різниці чисел, написаних на картках, що вийняли діти.
Наприклад, Сергій та Роман грають у цю гру. Сергій вийняв картку з числом 7, а Роман з числом 3. Після цього Сергій бере собі 4 (7 - 3 = 4) цукерки.
Дід Мороз стомився і не може визначити, скільки цукерок йому слід купити на свято. Допоможіть йому. Його цікавить максимальна кількість цукерок, яку може отримати дитина в результаті гри.
Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N(2 ≤ N ≤ 1000), яке представляє кількість карток.
Другий рядок вхідного файлу містить рівно N цілих чисел Ai(1 ≤ Ai ≤ 32767). Числа у рядку розділені одиночними пробілами. Ai – число, написане на і-й картці.
Формат вихідних даних: єдиний рядок вихідного файлу має містити одне число – максимальна кількість цукерок, яку може отримати дитина за гру.
Приклад вхідних і вихідних даних:
|
game.in
|
game.out
|
|
2
7 3
|
4
|
|
5
4 2 7 9 5
|
7
|
|
4
3 3 3 3
|
0
|
|
|
Добавил(а) Administrator
|
|
29.11.16 09:39 |
|
Готуємось до олімпіади з інформатики 20016-2017- 2
1. Фрагменти програмних кодів (С++)
|
№
|
Завдання
|
Програмний код
|
|
1.
|
Зчитування до кінця рядка
|
while (cin.peek()!='\n')
{ n++;
cin>>a[n];
}
|
|
2.
|
Зчитування до кінця файлу
|
while (!cin.eof())
{ m++;
cin>>b[m];
}
|
|
3.
|
Зчитування рядка з пропусками
|
string str;
getline(cin,str,'\n');
|
|
4.
|
Зчитування рядка з пропусками (тип string)
|
#include "fstream"
#include "string.h"
#include "string"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
int main()
{string s;
getline(cin,s);
cout<<s;
}
|
|
5.
|
Зчитування рядка з пропусками (тип char)
|
#include "fstream"
#include "string.h"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
int main()
{char str[100];
cin.getline(str,sizeof(str));
cout<<str;
}
|
|
6.
|
Кількість цифр в числі
|
#include "string"
int main()
{string s;
cin>>s;
cout<<s.length();}
#include "iostream"
#include "math.h"
using namespace std;
int main()
{
unsigned long long number;
cin>>number;
cout.precision(0);
cout<<fixed<<log10(double (number))+1;
}
|
2. Функції для роботи з рядками
Більшість функцій для роботи з рядками містяться в бібліотеці cstring .(#include <cstring>)
|
Функція
|
Дія
|
|
memset(str, c, n)
|
перші n символів рядка str заповнює значеннями c
|
|
strnset(str, c, n)
|
перші n символів рядка str заповнює значеннями c
|
|
strlen(str)
|
визначення довжини рядка
|
|
strcpy(str1, str2)
|
в рядок str1 копіює рядок str2
|
|
strncpy(str1, str2, n)
|
в рядок str1 копіює не більше, ніж n символів рядка str2
|
|
strcat(str1, str2);
|
до рядка str1 дописує рядок str2
|
|
strncat(str1, str2, n)
|
до рядка str1 дописує не більше, ніж n символів рядка str2
|
|
strchr(str, c)
|
визначає перше входження літери c в рядок str; повертає вказівник на знайдену літеру (або NULL, якщо її нема)
|
|
strrchr(str, c)
|
визначає останнє входження літери c в рядок str; повертає вказівник на знайдену літеру (або NULL, якщо її нема)
|
|
strstr(str1, str2)
|
визначає перше входження підрядка str2 в рядок str1; повертає вказівник на першу літеру знайденого підрядка (або NULL, якщо він не зустрічається)
|
|
strrev(str)
|
записує рядок str у зворотному порядку
|
|
strupr(str)
|
перетворює всі літери рядка у великі літери
|
|
strlwr(str)
|
перетворює всі літери рядка у малі літери
|
|
strcmp(str1, str2)
|
порівнює рядки str1 та str2; якщо рядки рівні, то повертає 0;
якщо відмінні – то повертає різницю між першими відмінними літерами: с1 – с2
|
|
stricmp(str1, str2)
|
аналогічна до strcmp(...), тільки ігнорує величину літер
|
|
strcspn(str1,str2)
|
повертає число – позицію першого входження в рядок str1 символу із набору str2
|
|
strdup(str1)
|
розподіляє пам’ять і копіює рядок str1 за виділеною адресою; повертає адресу початку виділеної пам’яті
|
Приклади:
strcmp("abcdefgh","abcabc") = 3;
stricmp("Abcd","abcD") = 0;
strlen("alpha") = 5;
cout<<strchr("University", 'v') –> "versity";
cout<<strstr("MicroLab Studio", "Lab") –> "Lab Studio";
cout<<strupr("My first Program") –> "MY FIRST PROGRAM".
Робота з масивами
|
Операція з масивом
|
Лінійний масив
|
Прямокутна таблиця
|
|
Опис
|
int a[100];
int i, n;//індекс, кількість елементів
|
int a[100][100];
int i,j, n,m;//індекс, кількість елементів
|
|
Введення
|
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
|
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>a[i][j];
|
|
Виведення
|
for(i=0;i<n;i++)cout<<a[i]<<” “;
|
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cout<<a[i][j]<<” “;
|
|
Сумування
|
s=0;
for(i=0;i<n;i++)s=s+a[i];
|
s=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
s=s+a[i][j];
|
|
Пошук
|
cin>>k;
for(i=0;i<n;i++) if (a[i]==k) cin<<i;
|
cin>>k;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if (a[i][j]==k)
cin<<i<<” “<<j;
|
|
Пошук максимального
|
max=a[0];nmax=0;
for(i=1;i<n;i++)if (a[i]>max) {max=a[i];nmax=i;}
|
max=a[0][0];imax=1;jmax=1;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if (a[i][j]>max) {max=a[i][j];
imax=i;jmax=j;}
|
|
Сортування
|
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++)
if (a[j]>a[j+1])
{temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;}
|
|
|
Стирання
|
n=n-1;
for(i=k-1;i<n;i++)
a[i]=a[i+1];
|
|
|
Вставка
|
n=n+1;
for(i=n-1;i>k;i--)
a[i]=a[i-1];
a[k]=x;
|
|
Готуємось до олімпіади з інформатики 20016-2017- 2
1. Фрагменти програмних кодів (С++)
|
№
|
Завдання
|
Програмний код
|
|
1.
|
Зчитування до кінця рядка
|
while (cin.peek()!='\n')
{ n++;
cin>>a[n];
}
|
|
2.
|
Зчитування до кінця файлу
|
while (!cin.eof())
{ m++;
cin>>b[m];
}
|
|
3.
|
Зчитування рядка з пропусками
|
string str;
getline(cin,str,'\n');
|
|
4.
|
Зчитування рядка з пропусками (тип string)
|
#include "fstream"
#include "string.h"
#include "string"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
int main()
{string s;
getline(cin,s);
cout<<s;
}
|
|
5.
|
Зчитування рядка з пропусками (тип char)
|
#include "fstream"
#include "string.h"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
int main()
{char str[100];
cin.getline(str,sizeof(str));
cout<<str;
}
|
|
6.
|
Кількість цифр в числі
|
#include "string"
int main()
{string s;
cin>>s;
cout<<s.length();}
#include "iostream"
#include "math.h"
using namespace std;
int main()
{
unsigned long long number;
cin>>number;
cout.precision(0);
cout<<fixed<<log10(double (number))+1;
}
|
2. Функції для роботи з рядками
Більшість функцій для роботи з рядками містяться в бібліотеці cstring .(#include <cstring>)
|
Функція
|
Дія
|
|
memset(str, c, n)
|
перші n символів рядка str заповнює значеннями c
|
|
strnset(str, c, n)
|
перші n символів рядка str заповнює значеннями c
|
|
strlen(str)
|
визначення довжини рядка
|
|
strcpy(str1, str2)
|
в рядок str1 копіює рядок str2
|
|
strncpy(str1, str2, n)
|
в рядок str1 копіює не більше, ніж n символів рядка str2
|
|
strcat(str1, str2);
|
до рядка str1 дописує рядок str2
|
|
strncat(str1, str2, n)
|
до рядка str1 дописує не більше, ніж n символів рядка str2
|
|
strchr(str, c)
|
визначає перше входження літери c в рядок str; повертає вказівник на знайдену літеру (або NULL, якщо її нема)
|
|
strrchr(str, c)
|
визначає останнє входження літери c в рядок str; повертає вказівник на знайдену літеру (або NULL, якщо її нема)
|
|
strstr(str1, str2)
|
визначає перше входження підрядка str2 в рядок str1; повертає вказівник на першу літеру знайденого підрядка (або NULL, якщо він не зустрічається)
|
|
strrev(str)
|
записує рядок str у зворотному порядку
|
|
strupr(str)
|
перетворює всі літери рядка у великі літери
|
|
strlwr(str)
|
перетворює всі літери рядка у малі літери
|
|
strcmp(str1, str2)
|
порівнює рядки str1 та str2; якщо рядки рівні, то повертає 0;
якщо відмінні – то повертає різницю між першими відмінними літерами: с1 – с2
|
|
stricmp(str1, str2)
|
аналогічна до strcmp(...), тільки ігнорує величину літер
|
|
strcspn(str1,str2)
|
повертає число – позицію першого входження в рядок str1 символу із набору str2
|
|
strdup(str1)
|
розподіляє пам’ять і копіює рядок str1 за виділеною адресою; повертає адресу початку виділеної пам’яті
|
Приклади:
strcmp("abcdefgh","abcabc") = 3;
stricmp("Abcd","abcD") = 0;
strlen("alpha") = 5;
cout<<strchr("University", 'v') –> "versity";
cout<<strstr("MicroLab Studio", "Lab") –> "Lab Studio";
cout<<strupr("My first Program") –> "MY FIRST PROGRAM".
Робота з масивами
|
Операція з масивом
|
Лінійний масив
|
Прямокутна таблиця
|
|
Опис
|
int a[100];
int i, n;//індекс, кількість елементів
|
int a[100][100];
int i,j, n,m;//індекс, кількість елементів
|
|
Введення
|
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
|
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>a[i][j];
|
|
Виведення
|
for(i=0;i<n;i++)cout<<a[i]<<” “;
|
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cout<<a[i][j]<<” “;
|
|
Сумування
|
s=0;
for(i=0;i<n;i++)s=s+a[i];
|
s=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
s=s+a[i][j];
|
|
Пошук
|
cin>>k;
for(i=0;i<n;i++) if (a[i]==k) cin<<i;
|
cin>>k;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if (a[i][j]==k)
cin<<i<<” “<<j;
|
|
Пошук максимального
|
max=a[0];nmax=0;
for(i=1;i<n;i++)if (a[i]>max) {max=a[i];nmax=i;}
|
max=a[0][0];imax=1;jmax=1;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if (a[i][j]>max) {max=a[i][j];
imax=i;jmax=j;}
|
|
Сортування
|
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++)
if (a[j]>a[j+1])
{temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;}
|
|
|
Стирання
|
n=n-1;
for(i=k-1;i<n;i++)
a[i]=a[i+1];
|
|
|
Вставка
|
n=n+1;
for(i=n-1;i>k;i--)
a[i]=a[i-1];
a[k]=x;
|
|
|
|
|
Добавил(а) Administrator
|
|
09.09.15 00:00 |
|
1. Базові структури.
Розв’язати і протестувати задачі в системі (http://134.249.159.199/cgi-bin/new-client?contest_id=23)
Логін user1-user5(пароль - 1)
2. Codeforces (http://codeforces.com/)
http://codeforces.com/problemset/problem/550/A
Два підрядка
Дано рядок s. Потрібно визначити, чи існують в цьому рядку s два підрядка, якы не пертинаються "AB" і "BA" (ланцюжків можуть йти в будь-якому порядку).
Вхідні дані
На вхід подається рядок s довжиною від 1 до 105 символів, що складається з великих літер латинського алфавіту.
Вихідні дані
Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше
3. Всеукраїнськiй олімпіадi з інформатики NetOI-2015 (http://www.olymp.vinnica.ua/
Задача DEMO_A
На площині задано координати двох відрізків AB і CD. Знайти спільну частину проекцій цих відрізків на вісь абсцис.
Вхідні дані
Ви вводите з клавіатури 8 цілих чисел - координати точок A, B, C, D. Кожне число не перевищує за абсолютною величиною 1000.
Вихідні дані
Ви виводите на екран одне число - спільну частину проекцій. Якщо спільна частина - порожня множина, вивести -1, якщо це одна точка - вивести 0.
Приклад вхідних та вихідних даних
Вхід: 2 2 7 5 3 4 8 1
Вихід: 4
Задача DEMO_B
Скільки натуральних чисел виду 2a3b5ca,b,c - невід'ємні цілі числа) належать відрізку [M;N]?
Вхідні дані
Ви вводите з клавіатури 2 цілих числа M та N. Кожне з чисел не перевищує за абсолютною величиною 10000.
Вихідні дані
Ви виводите на екран одне число - шукану кількість чисел.
Приклад вхідних та вихідних даних
Вхід: 10 20
Вихід: 6
Задача DEMO_C
Дана послідовність N цілих чисел. Знайти найменший додатній елемент цієї послідовності.
Вхідні дані
Ви вводите з клавіатури кількість чисел N та N цілих чисел - елементів цієї послідовності. Число N не перевищує 10000, кожний елемент послідовності не перевищує за абсолютною величиною 1000.
Вихідні дані
Ви виводите на екран одне число - шуканий елемент послідовності. Якщо у послідовності немає додатніх елементів - вивести 0.
Приклад вхідних та вихідних даних
Вхід: 7 -4 4 -7 3 0 8 2
Вихід: 2
Задача DEMO_D
Задано натуральне число N. Знайти найменше та найбільше число, яке складається з тих самих цифр та у такій самій кількості, що і N.
Вхідні дані
Ви вводите з клавіатури число N (1£ N £2000000000).
Вихідні дані
Ви виводите в одному рядку найменше число, а через пропуск - найбільше число.
Приклад вхідних та вихідних даних
Вхід: 7051
Вихід: 1057 7510
Задача DEMO_E
Задано текстовий рядок. Вилучити з нього всі символи, що не є цифрами. Вважається, що рядок містить хоча б одну цифру.
Вхідні дані
Ви вводите з клавіатури заданий рядок, довжина якого не перевищує 255 символів.
Вихідні дані
Ви виводите на екран шуканий рядок.
Приклад вхідних та вихідних даних
Вхід: Ф11р88н
Вихід: 1188
Задача DEMO_F
Дано K клітин шахової дошки. З'ясувати, чи всі вони одного кольору.
Вхідні дані
Ви вводите з клавіатури кількість контрольних прикладів, потім число К - кількість клітин шахової дошки,а у наступних К рядках - координати клітин (натуральні числа, не більші 8).
Вихідні дані
Ви виводите на екран для кожного приклада 1, якщо всі клітини одного кольору і 0, якщо це не так.
Приклад вхідних та вихідних даних
|
Вхід:
|
3
|
| |
|
3
|
|
|
1
|
2
|
|
8
|
1
|
|
8
|
5
|
|
2
|
|
|
1
|
1
|
|
1
|
2
|
|
2
|
|
|
1
|
1
|
|
2
|
2
|
|
Вихід: 101
Парне+парне, непарне-непарне –чорна
Парне+непарне, непарне-парне –біла
$14. Дистанційне навчання *(http://dystosvita.mdl2.com/ )
Програмування в С++
Основи програмування (Python)
|
|
РОЗВ'ЯЗОК ВСТУПНОЇ РОБОТИ 2011 |
|
|
|
|
Добавил(а) Administrator
|
|
21.09.11 10:25 |
|
3.
|
!2 л
|
8 л
|
5 л
|
|
12
|
0
|
0
|
|
4
|
8
|
0
|
|
0
|
8
|
4
|
|
8
|
4
|
0
|
|
3
|
4
|
5
|
|
3
|
8
|
1
|
|
11
|
1
|
0
|
|
6
|
1
|
5
|
|
6
|
6
|
0
|
5. Вгадати число можна за 4 спроби, використовуючи метод поділу по полам.
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
|
|
|
|
|
|
|
1
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
|
|
|
|
|
|
|
2
|
|
|
|
|
|
|
3
|
|
|
|
3
|
|
|
|
3
|
|
|
|
3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
|
4
|
|
4
|
|
4
|
|
4
|
|
4
|
|
4
|
|
4
|
|
7.
http://ega-math.narod.ru/Quant/Shestpl.htm
9.Ідея. Розв’язком задачі є числовий ряд Фібоначі.
|
Кількість сходинок
|
Варіанти
|
Кількість способів
|
|
1
|
1
|
1
|
|
2
|
11, 2
|
2
|
|
3
|
111, 12, 21
|
3
|
|
4
|
1111, 112, 121, 211, 22
|
5
|
|
5
|
|
8
|
|
6
|
|
13
|
|
7
|
|
21
|
12.Наявна матриця розміру M*N, що являє собою деякий лабіринт. Одна клітинка лабіринту є входом а інша виходом. Знайти найкоротший шлях від входу до виходу, якщо він існує.
Вхідні данні : файл Labirint.dat, де першим рядком йде два числа N та M (0<N,M<100), а далі M рядків по N чисел відокремлених пробілами. Всі числа Amn можуть приймати значення 1,2,3,4. 1 - ділянка, що можна пройти. 2 - стіна. 3 - вхід. 4 - вихід.
Вихідні данні: число T>0, яке дорівнює довженні найкоротшого шляху, або -1, якщо такого шляху не існує.
Аналіз задачі.
По-перше треба відмітити, що максимальний розмір лабіринту, не перевищує 104 елементів, тобто весь набір даних можна розмістити в статичній пам'яті.
Одним з найбільш ефективних алгоритмів пошуку найкоротшого шляху є алгоритм хвилі. Хвильовий алгоритм полягає в наступному:
1. кожної клітинок i приписується число T - тимчасова мітка.
2. заводяться два списки "фронту хвилі" NF і OF, а також перемінна T (поточний час);
3. OF:={u1}; NF:={}; T:=1;
4. для кожної з вершин i, що входять у OF, проглядаються сусідні вершини j, і якщо T[j] = -2, то T[j]=T, NF=NF + {j}.
5. якщо NF = {}, то шлях не існує, перехід до кроку 8.
6. якщо одна з вершин збігається з u2, то знайдений найкоротший шлях довжини T, перехід до кроку 8;
7. OF:=NF; NF:={}; T:=T+1; повернення до кроку 4.
8. Відновлюємо шлях проходячи масив P, шукая серед сусідів даної клітинки таку, щоб номер ітерації хвилі у неї був найменшим.
Джерела інформації
http://www.problems.ru
http://olympiads.ru
|
|