|
Добавил(а) Administrator
|
|
13.10.17 10:28 |
|
Теорія графів (скачати)
Codeforces (http://codeforces.com/)
http://codeforces.com/problemset/problem/550/A
Два підрядка
Дано рядок s. Потрібно визначити, чи існують в цьому рядку s два підрядка, які не перетинаються "AB" і "BA" (ланцюжків можуть йти в будь-якому порядку).
Вхідні дані
На вхід подається рядок s довжиною від 1 до 105 символів, що складається з великих літер латинського алфавіту.
Вихідні дані
Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше
$11. Турнір http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11
Задачі А
Неуважність
Степан вдало пройшов співбесіду і ось уже як чотири місяці працює на одній із самих престижних ІТ компаній. Прийшов час здавати проект менеджеру і Степан, як істинний студент, все виконує у останню ніч перед здачею. Набирає текст Степан звичайно дуже швидко, але неуважно. От і цього разу останню частину тексту він набрав не звернувши уваги, що випадково натиснув клавішу caps lock. Таким чином великі букви були набрані маленькими, а маленькі великими. Інші символи він набрав вірно. Степан настільки стомився, що немає сил виправити помилки, і він вирішив кілька годин поспати. Допоможіть Степану, доки він спить, напишіть програму, яка виправляє неуважно набраний текст.
Input format
перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.
Output format
вихідний файл має містити виправлений текст.
Examples
|
Input in text.in
|
Output in text.out
|
|
sCHOOL
|
School
|
Задача F
Арифметика
Молодший брат Степана Мишко навчається у першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану, напишіть програму, яка визначає, кількість різних цифр у числі Мишка.
Input format
перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 101000), записане Мишком.
Output format
вихідний файл має містити одне число – кількість різних цифр у числі.
Examples
|
Input in count.in
|
Output in count.out
|
|
1233
|
3
|
Теорія графів
Основні алгоритми роботи з графами:
http://www.e-olymp.com/uk/problems/4764 - Матриця суміжності, степінь вершин
http://www.e-olymp.com/uk/problems/4763 - Від списку ребер до матриці суміжності
http://www.e-olymp.com/uk/problems/625 - Пошук в глибину на графах
http://www.e-olymp.com/uk/problems/975 - Флойд (зчитування матриці)
http://www.e-olymp.com/uk/problems/983 - Флойд (створення матриці)
http://www.e-olymp.com/uk/problems/2968 - Флойд (Форд)
http://www.e-olymp.com/uk/problems/1365 - Дейкстри
http://www.e-olymp.com/uk/problems/2965 - Дейкстра
http://www.e-olymp.com/uk/problems/981 - мінмальне остове дерево (алгоритм Прима)
http://www.e-olymp.com/uk/problems/964 - Матриця інцендентності |
|
Добавил(а) Administrator
|
|
13.10.17 10:23 |
|
Codeforces (http://codeforces.com/)
http://codeforces.com/problemset/problem/550/A
Два підрядка
Дано рядок s. Потрібно визначити, чи існують в цьому рядку s два підрядка, які не перетинаються "AB" і "BA" (ланцюжків можуть йти в будь-якому порядку).
Вхідні дані
На вхід подається рядок s довжиною від 1 до 105 символів, що складається з великих літер латинського алфавіту.
Вихідні дані
Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше
Готуємось до олімпіади з інформатики 2017-2018- 2
1. Фрагменти програмних кодів (С++)
|
№
|
Завдання
|
Програмний код
|
|
$11.
|
Зчитування до кінця рядка
|
while (cin.peek()!='\n')
{ n++;
cin>>a[n];
}
|
|
$12.
|
Зчитування до кінця файлу
|
while (!cin.eof())
{ m++;
cin>>b[m];
}
|
|
$13.
|
Зчитування рядка з пропусками
|
string str;
getline(cin,str,'\n');
|
|
$14.
|
Зчитування рядка з пропусками (тип 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;
}
|
|
$15.
|
Зчитування рядка з пропусками (тип 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;
}
|
|
$16.
|
Кількість цифр в числі
|
#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
|
|
22.09.17 07:52 |
|
1. Базові структури алгоритмів
Приклад 1
Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в даній послідовності.
1 спосіб.
Посортувати і відшукати різницю, рівну два між сусідніми елементами.
n=5
0 2 1 5 3
0 1 2 3 5
4
2 спосіб.
Перевірити, чи існує кожне з чисел від 0 до N у послідовності, використовуючи два вкладених цикли.
3 спосіб.
Скористатися формулою суми арифметичної прогресії.
Приклад:
N=5;
Послідовність А[1..N] 4 2 3 0 5
Сума елементів послідовності рівна S1=4+2+3+0+5=14
Сума арифметичної прогресії (0..N) 0 1 2 3 4 5 згідно з формулоюS=(An+A1)*n/2
S2=(5+0)*15/2
Результат R=S2-S1=15-14=1
Отже, не існує числа 1.
Приклад 2
Аналогічний приклад можна навести і на більш складніший числовий ряд чисел Фібоначі.
Спосіб 1
Кожне наступне знаходити як суму двох попередніх.
1 1 2 3 5 8 ...
k1 перше число
k2 друге число
k3:=k1+k2;
k1:=k2;
k2:=k3;
Спосіб 2
Використаємо рекурентну формулу чисел Фібоначі.
![F_n = \frac{ \left( \frac{1+\sqrt{5}}{2} \right)^[...]](http://e-maxx.ru/tex2png/cache/b905d527e4c238203b5be148f5f93a83.png)
http://e-maxx.ru/algo/fibonacci_numbers
Кожне число Фібоначі знаходять за формулою:
xy exp(y*ln(x))
Приклад 3
Перестановка значення змінної місцями
a,b 2,3 3,2
c=a;a=b;b=c;
c=2;a=3;b=2;
a=a+b; b=a-b; a=a-b;
a=5;b=5-3=2;a=5-2=3;
2. Розгалуження
Приклад 3
Скласти програму знаходження найбільшого з трьох чисел a,b,c, введених з клавіатури.
Існують різні способи розв’язку даного завдання
1 спосіб
var a,b,c,max:integer;
begin
readln(a,b,c);
if (a>=b && a>=c) max=a;
if (b>=a)and(b>=c) then max:=b;
if (c>=a)and(c>=b) then max:=c;
writeln(max);
end.
2 спосіб
Вкладені розгалуження
IF умова THEN IF умова THEN оператори ELSE оператори ELSE оператори
var a,b,c,max:integer;
begin
readln(a,b,c);
if a>b then if a>c then max:=a else max:=c else if b>c then max:=b else max:=c;
writeln(max);
end.
3 спосіб
var a,b,c,max:integer;
begin
readln(a,b,c);
max:=a;
if b>max then max:=b;
if c>max then max:=c;
writeln(max);
end.
Третій спосіб найраціональніший
C++
max(a, max(b,c);
3. Цикл
Приклад 3
Знайти найбільший спільний дільник
(HCD) a,b,
HCD(0,0)=0
HCD(a,0)=(a)
HCD(а,в)=HCD(b,r1)=HCD(r1,r2)=HCD(rn-1,rn)=|rn-1|, де rі- остача від ділення?
Знайти найменше спільне кратне (HCD) цілиx чисел аШ0,вШ0
HCK(a,b)=a*b/HCD(a,b)
HCD(а,в)=HCD(b,r1)=HCD(r1,r2)=HCD(rп-1,rn)=|rn-1|
4.Знайти досконалі числа на проміжну [1,n].
6=1+2+3 (досконале - рівне сумі всіх своїх дільників, крім останнього)
45 15 ------- 2 3 4 5 6 7 8 9 10 11 12 13 14 15
45 % 15=0
15
15 25
- b
15%25=25
25 % 15=10
15 %10 =5
10%5=0
5
0
while (b>0)
{temp=a%b;
a=b;
b=temp;
}
nsd=a
Алгоритм Евкліді
Приклад 4
Знайти дільники числа.
Знайти кількість дільників числа.
Практикум
$11. Фібоначі
Турнір «Методика складання алгоритмів – 24» Задача B
$12. НСД.
https://www.e-olymp.com/uk/problems/137
https://www.e-olymp.com/uk/problems/136
https://www.e-olymp.com/uk/problems/7239
https://www.e-olymp.com/uk/problems/4742
https://www.e-olymp.com/ru/problems/4283 |
|
Последнее обновление 22.09.17 08:01 |
|
Добавил(а) Administrator
|
|
15.09.17 09:14 |
|
Всеукраїнськiй олімпіадi з інформатики NetOI-2015 (http://www.olymp.vinnica.ua/)
|
|
Читать полностью
|
|
Добавил(а) Administrator
|
|
15.09.17 09:11 |
|
7226 День календаря
Як відомо день програміста припадає на 256 день року, у невисокосний рік це - 13 вересня, а у високосний — 12. Не забудьте привітати своїх колег і наставників.
Аналогічно пропонується розпізнати число та номер місяця, що припадає на день за номером n у невисокосному2014 році.
Вхідні дані
Натуральне число n (1 ≤ n ≤365).
Вихідні дані
Число (від 1 до 31) та номер місяця (від 1 до 12), що відповідає дню з номером n.
Вхідні дані
256
Вихідні дані
|
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int m=0;
while (n>a[m]){n=n-a[m];m++;}
cout<<n<<" "<<m<<endl;
}
|
|
193 Сума цифр
Знайти найменше і найбільше N-значні натуральні числа, які мають суму цифр M.
У вхідному файлі числа N і M (1≤N≤100, 1≤M≤9*N). До вихідного файлу потрібно записати два N-значних числа в неспадаючому порядку.
Вхідні дані
3 4
Вихідні дані
|
#include <iostream>
using namespace std;
int main()
{int n,m;
cin>>n>>m;
long long x=1;
for(int i=1;i<n;i++) x=x*10;
int s=0;
while (s!=m)
{
int t=x;
s=0;
while(t>0)
{
s=s+t%10;
t=t/10;
}
x++;
}
x--;
cout<< x << " ";
x=9;
for(int i=1;i<n;i++) x=x*10+9;
s=0;
while (s!=m)
{
int t=x;
s=0;
while(t>0)
{
s=s+t%10;
t=t/10;
}
x--;
}
x++;
cout<< x << endl;
return 0;
}
|
#include <iostream>
using namespace std;
int a[100],b[100];
int main()
{int n,m;
cin>>n>>m;
int s=1;
int i=n-1;
a[0]=1;
int temp=m-1;
while (temp>0 and i>0)
{
if(temp<=9) a[i]=temp; else a[i]=9;
temp=temp-a[i];
i--;
}
a[0]=a[0]+temp;
for(int i=0;i<n;i++) cout<<a[i];
cout<<" ";
s=0;
i=0;
temp=m;
while (temp>0)
{
if(temp<=9) b[i]=temp; else b[i]=9;
temp=temp-b[i];
i++;
}
for(int i=0;i<n;i++) cout<<b[i];
cout<<endl;
return 0;
}
|
1356 SMS голосування
У фіналі фабрики зірок було проведено SMS голосування для визначення переможців серед N конкурсантів. Телеглядачі відправляли SMS з номером (число від 1 до N) свого улюбленого виконавця і кількість відповідних SMS склали рейтинг кожного учасника. Всього на головний комп’ютер конкурсу надійшло M повідомлень SMS. Потрібно скласти програму, яка виведе номери трьох переможців у порядку спадання їх рейтингів та зростання номерів у випадку, якщо рейтинги рівні.
Вхідні дані
У першому рядку записано два числа N і M (3 ≤ N ≤ 100, 1 ≤ M ≤ 1000000).
У наступному рядку M чисел, кожне з яких не перевищує N.
Вихідні дані
Три числа - номери переможців записані в один рядок, через пропуск.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
5 10 1 2 3 4 5 2 1 2 4 2
Вихідні дані
2 1 4
|
Зчитати масив
Підрахувати кількість кожного елемента
Знайти три максимальні
Сортування
|
#include <iostream>
int a[1001],b[4];
using namespace std;
int main()
{int n,m,k,maxx,nmaxx;
cin>>m>>n;
for(int i=1;i<=n;i++) {cin>>k;a[k]++;}
for(int j=1;j<=3;j++)
{
maxx=a[1];nmaxx=1;
for(int i=1;i<=m;i++)
if(a[i]>maxx){maxx=a[i];nmaxx=i;}
a[nmaxx]=-1;
b[j]=nmaxx;
}
cout<<b[1]<<" "<<b[2]<<" "<<b[3]<<endl;
return 0;
}
|
|
|
Последнее обновление 22.09.17 08:01 |
|
Добавил(а) Гісь І.В.
|
|
15.09.17 09:09 |
|
7226 День календаря
Як відомо день програміста припадає на 256 день року, у невисокосний рік це - 13 вересня, а у високосний — 12. Не забудьте привітати своїх колег і наставників.
Аналогічно пропонується розпізнати число та номер місяця, що припадає на день за номером nу невисокосному2014 році.
Вхідні дані
Натуральне число n(1≤ n ≤365).
Вихідні дані
Число (від 1 до 31) та номер місяця (від 1 до 12), що відповідає дню з номером n.
Вхідні дані
256
Вихідні дані
193 Сума цифр
Знайти найменше і найбільше N-значні натуральні числа, які мають суму цифр M.
У вхідному файлі числа N і M (1≤N≤100, 1≤M≤9*N). До вихідного файлу потрібно записати два N-значних числа в неспадаючому порядку.
Вхідні дані
3 4
Вихідні дані
1356 SMS голосування
У фіналі фабрики зірок було проведено SMS голосування для визначення переможців серед Nконкурсантів. Телеглядачі відправляли SMS з номером (число від 1 до N) свого улюбленого виконавця і кількість відповідних SMS склали рейтинг кожного учасника. Всього на головний комп’ютер конкурсу надійшло Mповідомлень SMS. Потрібно скласти програму, яка виведе номери трьох переможців у порядку спадання їх рейтингів та зростання номерів у випадку, якщо рейтинги рівні.
Вхідні дані
У першому рядку записано два числа Nі M(3≤ N ≤100,1≤ M ≤1000000).
У наступному рядку Mчисел, кожне з яких не перевищує N.
Вихідні дані
Три числа - номери переможців записані в один рядок, через пропуск.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
5 10 1 2 3 4 5 2 1 2 4 2
Вихідні дані
2 1 4 |
|
Последнее обновление 22.09.17 08:01 |
|
|
