|
24.09.2014 Сортування - Перебір |
 |
 |
 |
|
Добавил(а) Administrator
|
|
06.10.14 11:23 |
|
повний архів
Сортування елементів масиву
(методи сортування, сортування перестановкою, вибором, швидке сортування, задача кількість різних чисел в масиві)
Розглянемо способи сортування. Сама тема сортування є однією з найбільш досліджених задач.
Є три способи сортування масивів:
$1- сортування вибором;
$1- сортування обміном;
$1- сортування вставкою.
Для кожного способу є багато алгоритмів, які відрізняються часом сортування, який злежить від числа операцій порівняння і операцій обміну.
Традиційно розрізняють внутрішнє сортування, яке обробляє дані оперативної пам’яті, і зовнішнє сортування, яке оперує з даними розміщеними на дисках.
Розглянемо сортування числового одномірного масиву.
Відсортувати числовий масив: 7, 3, 8, 4,8, 5, 9, 1.
Звичайне сортування : 1, 3, 4, 5, 7, 8, 8, 9,.
Адресне сортування: 7, 3, 8, 4, 8, 5, 9, 1.
5, 2, 6, 3, 7, 4, 8, 1 (адреса).
Є багато різноманітних алгоритмів сортування (сортування бульбашкою, сортування за допомогою дерева, пірамідальне сортування, швидке сортування (половинного поділу).
Розглянемо деякі з них в дещо видозміненому вигляді.
Сортування вектором
#include "fstream"
#include<algorithm>
#include<vector>
using namespace std;
int main()
{ifstream cin("E.dat");
ofstream cout("E.sol");
long long n,k,l,i,j,c;
cin>>n>>k;
vector<long long int> a(n);
for(i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
l=0;
for(i=k;i<n;i++)
{l=l+a[i];
}
cout<<l;
return 0;
}
Перебір вектором
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> a;
ifstream f;
ofstream g;
void printper(int n);
int main()
{
f.open("input.dat");
g.open("output.ans");
int n;
f >> n;
for (int i=1;i<=n;i++){
a.push_back(i);
}
printper(n);
while (next_permutation(a.begin(),a.end())){
printper(n);
};
//printper(n);
f.close();
g.close();
return 0;
}
void printper(int n)
{
for (int i=0;i<n-1;i++){
g << a[i] << " ";
}
g << a[n-1] << endl;
} |
|
Последнее обновление 06.10.14 11:38 |
|
|
17.09.2014 Розв'язки задачі "Відрізок" |
|
|
|
|
Добавил(а) Administrator
|
|
06.10.14 10:39 |
|
Розв’язання
Розглянемо найпростіший алгоритм розв’язання задачі. Перебиратимемо всі трійки відрізків.
Для кожної трійки треба перевірити можливість існування відповідного трикутника. Якщо трикутник існує, підрахуємо сумарну вартість трьох відрізків, а з усіх знайдених вартостей виберемо найменшу. Складність алгоритму — N(N3).
А от швидше розв’язання. Розглядатимемо всі відрізки в порядку від найкоротших до найдовших і підтримуватимемо таку структуру даних: масив F, у комірці F[C] якого зберігається найбільша сумарна довжина двох відрізків (з числа перших N відрізків) із загальною вартістю c. Оскільки ціни відрізків не перевищують N, сумарна вартість двох відрізків не буде більшою за 2N. Переходячи до чергового ((k + 1)-го) відрізка — нехай цей відрізок має довжину L та вартість C — ми шукаємо найменше таке значення c, для якого F[c] >L. Це можна зробити простим лінійним пошуком. Для знайденого значення c сума C + c буде найменшою можливою вартістю трикутника, найбільшою стороною якого є розглядуваний відрізок. Якщо ця сума менша за поточний мінімум знайдених вартостей, відповідним чином цей мінімум оновлюємо. Крім того, оновлюємо і сам масив F[c]. Для цього пробуємо взяти в пару з (k + 1)-м відрізком почергово всі відрізки від першого до k-го і оновлюємо, якщо потрібно, відповідну комірку масиву F. Таким чином, на кожному з N кроків ми виконуємо з N кроків ми виконуємо O(N) операцій, тож загальна складність алгоритму — O(N2).
Тепер розглянемо оптимальне розв’язання. Воно базується на такій нескладній властивості:
Властивість. Якщо серед натуральних чисел L1, L2, ..., Lk немає трьох таких, що утворюють сторони трикутника, то найбільше з цих чисел не може бути меншим за K-й член послідовності Фібоначчі. Послідовність Фібоначчі задається таким чином: F1 = F2 = 1, Fk = Fk−1 + Fk−2, K>= 3.
Це твердження можна довести методом математичної індукції, попередньо впорядкувавши числа L1, L2, ..., Lk за неспаданням. Оскільки F45 > 109 (у чому можна переконатися, написавши спеціальну «дослідницьку» програму), серед будь-яких 45 натуральних чисел, які не перевищують 109, обов’язково знайдуться три, що є сторонами трикутника. Отже, зокрема і серед 45 найдешевших відрізків знайдуться три, що утворюють трикутник. Але ціни відрізків — перестановка чисел від 1 до N, тому сумарна ціна цих трьох відрізків не може перевищувати 45 + 44 + 43 = 132. Таким чином, усі відрізки вартістю більше за 132 можна відкинути й шукати потрібну трійку лише серед тих, що залишилися. Маємо фактично лінійне від N розв’язання з додатком, що складає порядку 1323 операцій.
|
Варіант 1
|
Варіант 2
|
|
#include "fstream"
using namespace std;
long int l[1000000],c[1000000],s,n,i,j,k;
ifstream cin("segments.dat");
ofstream cout("segments.sol");
int main()
{cin>>n;
for(i=0;i<n;i++)cin>>l[i]>>c[i];
s=2000000000;
for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++)
for(k=j+1;k<n;k++)
if (l[i]<l[j]+l[k] && l[j]<l[i]+l[k] && l[k]<l[j]+l[i] && c[i]+c[j]+c[k]<s)
s=c[i]+c[j]+c[k];
if (s<2000000000)cout<<s<<endl;else cout<<-1<<endl;
return 0;
}
|
#include "fstream"
using namespace std;
long int a[1000000],ans,n,i,j,u,l,c,k;
ifstream cin("segments.dat");
ofstream cout("segments.sol");
int main()
{cin>>n;
k=3000;
for(i=0;i<n;i++){cin>>l>>c;
a[c]=l;}
ans=2000000000;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)
for (u = j + 1; u <= n; u++)
if (i + j + u < ans && a[i] < a[j] + a[u] && a[j] < a[i] + a[u] & a[u] < a[i] + a[j]) ans = i + j + u;
if (ans==2000000000)ans=-1;
cout<<ans<<endl;
return 0;
}
|
|
|
Последнее обновление 06.10.14 11:38 |
|
10.09.2014 Завдання XXVII Всеукраїнської учнівської олімпіади з інформатики 2013/14 н. р. |
|
|
|
|
Добавил(а) Administrator
|
|
06.10.14 10:33 |
|
Відрізки (Роман Рубаненко, Роман Фурко)
Умова
Петрик дуже любить іграшки у формі геометричних фігур. Нещодавно він помітив, що серед його іграшок немає жодного трикутника. Це дуже засмутило Петрика, тому він пішов до найближчого магазину, щоб придбати новісінький трикутник. В магазині Петрику сказали, що всі трикутники вже давно розкупили, але в наявності є N прямих відрізків.
Відрізки пронумеровані послідовними натуральними числами, починаючи з одиниці. Відрізок номер i характеризується двома числами — довжиною Li та ціною Ci. Петрик дуже розумний, тому знає, що бажаний трикутник він може скласти з трьох відрізків. Більше того, наш герой знає, що трикутник можливо скласти лише з таких відрізків, що довжина будь-якого з них має бути строго меншою за сумарну довжину інших двох. Отже, хлопчик вирішив придбати рівно три таких відрізки. Звичайно, він хоче заощадити якомога більше коштів на морозиво, тому хоче витратити якнайменше на покупку відрізків для свого трикутника.
Завдання. Напишіть програму segments, яка за інформацією про відрізки визначить мінімальну вартість трьох відрізків, з яких хлопчик зможе скласти трикутник, або визначить, що це зробити неможливо.
Вхідні дані. В першому рядку вхідного файла segments.dat записано єдине число N — кількість відрізків. Далі в N рядках записана інформація про самі відрізки. Кожен такий рядок містить відповідні Li (1<=Li<= 109) та Сi.Ціни утворюють перестановку чисел від 1 до N, тобто є попарно різними натуральними числами, не більшими за N.
Вихідні дані. Вихідний файл segments.sol має містити єдине число — мінімальну вартість трьох відрізків, з яких можна скласти трикутник, або «−1» (лапки для наочності) в тому
випадку, якщо вибрати рівно три такі відрізки неможливо.
Оцінювання. Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:
o 20 балів: 1 <=N<= 100.
o 20 балів: 100 <=N<= 3000.
o 30 балів: 3000 <=N<= 104.
o 30 балів: 104 <=N<=105.
Приклади вхідних та вихідних даних.
segments.dat
4
1 1
2 2
3 3
4 4
segments.sol
9
segments.dat
3
3 1
5 3
10 2
segments.sol
-1 |
|
Последнее обновление 06.10.14 11:38 |
|
03.09.2014 Повторення "Мова програмування С++" |
|
|
|
|
Добавил(а) Administrator
|
|
04.09.14 22:19 |
«Мова програмування С, С++ »
Єдиний спосіб вивчати нову мову програмування –писати на ній програми. (Брайен Керніган)
|
Visual C++
|
C++
|
|
|
Порядок роботи
$11. Запустити середовище Головне меню\Програми\Visual C++ 9.0 Express Edition\Microsoft Visual C++ 2008 Express Edition.
$12. Створити новий проект «Консольний додаток Win32», який зберігати в власну папку.
$13. Перевірити програми з додатку.
Зауваження
Для компіляції та виконання натискуйте клавішу Ctrl F5
// Під'єднання модулів
#include "stdafx.h" //генерація файлу предкомпільованих заголовків
#include <iostream>//організація введення-виведення в мові програмування C++
#include <math.h>//виконання простих математичних операцій
using namespace std;// звернення до об'єктів напряму
int _tmain()
{
int a,b; //опис цілих
float c; //опис дійсних
cin>>a>>b;//ведення даних
c=a/b;
cout<<c<<”\n”;//виведнння даних
}
|
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
ifstream inp;inp.open("input.dat");
int a,b,c;
inp>>a>>b;
inp.close();
c=a+b;
ofstream out;out.open("output.sol");
out<<c;
out.close();
}
|
|
|
Функції
|
|
|
Ім'я
|
Опис
|
|
abs(i)
|
модуль числа
|
|
ceil(f)
|
округлення до найближчого більшого цілого числа
|
|
fabs(f)
|
абсолютне значення
|
|
floor(f)
|
округлення до найближчого меншого цілого цілого
|
|
fmod(a,b)
|
повертає залишок від ділення двох чисел
|
|
modf(x,p)
|
повертає цілу та дробову частину аргументу х зі знаком
|
|
pow(x,y)
|
вираховує значення xy
|
|
sqrt(f)
|
квадратний корінь
|
#include "stdafx.h"
#include "iostream"
#include "math.h"
using namespace std;
int _tmain()
{
double f;
f=-5.5; cout<<abs(f)<<endl;//5.5
f=-5.5; cout<<fabs(f)<<endl;//5.5
f=5.8; cout<<floor(f)<<endl;//5
f=5.8; cout<<ceil(f)<<endl;//6
f=9.0; cout<<sqrt(f)<<endl;//3
f=5; cout<<pow(f,2)<<endl;//25
f=5.5; cout<<fmod(f,2)<<endl;//1.5
f=17.25;double p,y;y=modf(f,&p); f=5.2; cout<<y<<" "<<p<<endl;//0.25 17
return 0;}
|
|
|
Операції
|
|
|
Ім'я
|
Опис
|
|
+
|
с=a+b; k=k+1; k++; s+=k;
|
|
-
|
c=a-b; k=k-1; k--; s-=k;
|
|
*
|
c=a*b;
|
|
/
|
a=5.0/2;//2.5 a=5/2;//2
|
|
%
|
a=5%2;//1
|
#include "stdafx.h"
#include "iostream"
using namespace std;
int _tmain()
{
int n,a,b;
cin>>n;/* 12 */
a=n/10;
b=n%10;
cout<<a<<endl;/* 1 */
cout<<b<<endl;/* 2 */
return 0;
}
|
|
|
Розгалуження
|
Цикл
|
|
Операції порівняння
|
З параметром
|
|
<, >. <=,>=, !=, ==
|
for (i=1;i<=n;i++) {блок операторів};
|
|
Логічні операції
|
З перед умовою
|
|
&&, ||, !
|
while (умова){блок операторів};
|
|
Умовний оператор
|
Після умовою
|
|
if (умова) команда 1; else команда 2;
|
do {блок операторів}
while (умова);
|
Масиви
|
С++
|
|
Операція
|
Лінійний масив
|
Прямоктна таблиця
|
|
Опис
|
Int a[100];
int i, n;//індекс, кількість елементів
|
Int a[100][100];
int i,j, n,m;//індекс, кількість елементів
|
|
Введення
|
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
|
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) cin>>a[i][j];
|
|
Виведення
|
for(i=1;i<=n;i++)cout<<a[i<<>" ";
|
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)cout<<a[i][j]<<" ";
|
|
Сумування
|
s=0;
for(i=1;i<=n;i++)s=s+a[i];
|
s=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)s=s+a[i][j];
|
|
Пошук
|
cin>>k;
for(i=1;i<=n;i++) if (a[i]==k) cout<<i;
|
cin>>k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)if (a[i][j]==k)cout<<i<<" "<<j;
|
|
Пошук максимального
|
max=a[1];nmax=1;
for(i=2;i<=n;i++)if (a[i]>max) {max=a[i];nmax=i;}
|
max=a[1];imax=1;jmax=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)if (a[i][j]>max) {max=a[i][j];
imax=i;jmax=j;}
|
|
Сортування
|
for(i=1;i<n;i++)
for(j=1;j<n;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;i<=n;i++)a[i]=a[i+1];
|
|
|
Вставка
|
n=n+1;
for(i=n;i>=1;i--)a[i]=a[i-1];
|
|
|
ЗАДАЧІ
|
Структура програми
#include "stdafx.h"
#include "iostream"
#include <math.h>
using namespace std;
int main()
{
cout <<"Okey";
return 0;
}
Слідування
1. Два резистори R1 і R2 з'єднані паралельно. Визначити сумарний опір за формулою .
2. Обчислити відстань між двома точками з координатами X1,Y1 і X2,Y2 за формулою L=
#include "stdafx.h"
#include "iostream"
#include <math.h>
using namespace std;
int main()
{
float x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
float l=sqrt(pow((x1-x2),2)+pow(y1-y2,2));
cout<<("L="<<l<<endl;
}
3. В рядку S символів, на сторінці R рядків. Скільки символів в книжці, у якої N сторінок?
За скільки хвилин учень прочитає книгу, якщо він одну сторінку читає за T хвилин?
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
int s,r,n,t;
cin>>s>>r>>n>> t;
int a=s*r*n;
cout<<"A=”<<a<<”\n;
int b=a/t;
cout<<"B=”<<b<<”\n;
int g,h;
g=b/60; h=b%60;
cout<<g<<”:”<<h;
}
4. Скільки лампочок потрібно, щоб освітити вулицю довжиною D км, як що стовпи з ліхтарями стоять на відстані V м?
5. Одна серія фільму по телевізору триває F хв. Скільки часу в годинах необхідно, щоб переглянути N серій?
|
Розгалуження
6. Знайти максимальне значення серед двох чисел введених з клавіатури.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
int a,b,max;
cin>>a>>b;
if (a>b) max=a; else max=b;
court<<max<<endl;
}
7. Знайти максимальне значення серед трьох чисел введених з клавіатури.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
int a,b,c,max;
cin>>a>>b>>c;
if (a>=b && a>=c) max=a;
if (b>=a && b>=c) max=b;
if (c>=a && c>=b) max=c;
cout<<max<<endl;
}
8. Введене число перевірити: додатне, від'ємне чи дорівнює нулю.
9. Напишіть програму перевірки знання додавання трьох введених чисел.
10.Введене число перевірити: менше, більше чи дорівнює воно 100.
11. Перевірити, чи існує трикутник із сторонами A, B, C.
|
Цикл
12.Скласти програму виведення на екран квадратiв всiх натуральних чисел менших за 20.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{for (int i=1;i<20;i++) cout<<i<<”*”<<i<<”=”<<,i*i;
}
13. Скласти програму знаходження суми всiх чисел кратних трьом з вiдрiзка [n,50].
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{int n; cin>>n;
int i=48;int s=0;
while (i>=n)
{s+=i;i-=3;}
cout<<s<<endl;
}
14. Протабулювати функцію f(x)=cos(2x) на проміжку [a,b] розбитого на n проміжків.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
const a=0, b=10, n=10;
float h=(b-a)/n;
float x=a;
float y;
while (x<=b)
{
y=cos(2*x);
cin<<x<< “ “<<y;
x=x+h;}
}
15. Написати таблицю переведення температури з градусів по шкалі Цельсія (С) в градуси шкали Фаренгейта (F) за формулою F=1.8*C+32 для значень від 10 до 20 градусів з кроком 2 градуси.
16. Написати таблицю переведення радіуса в площу круга для значень радіуса від 1 до 18 В кроком 2.
|
Масив
17. Дано лінійну таблицю із n цілих чисел. Знайти суму S всіх елементів.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
int a[100];
int i,n,s;
cin>>n;
for (i=1;i<=n;i++){cin>> a[i];}
s=0;
for (i=1;i<=n;i++) s=s+a[i];
cout<<s;
}
18. З масиву стерти K-тий елемент.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{
int a[100];
int i,n,k,s;
cin>>n;
for (i=1;i<=n;i++) cin>>a[i];
cin>>k;
for (i=k;i<=n;i++) a[i]=a[i+1];
n--;
for (i=1;i<=n;i++) cout<<a[i]<<” “;
}
19. В масив вставити елемент на К-те місце
20. В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.
21. Скласти програму підрахунку суми елементів з непарними номерами масиву A[1..25].
22. Задано таблиця A[1..N]. Побудувати таблицю B[1..N], в якій першими розміщені всі від`ємні елементи таблиці A, а потім всі додатні.
23. Дано натуральна таблиця A[1..10]. В таблицю М записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2.
24. Заданий одномірний числовий масив. Визначити суму добутків всіх пар сусідніх чисел.
25. Дано масив A[1..M]. Скласти програму перестановки місцями елементів з парними та непарними номерами.
26. Скласти програму запису в таблицю квадратів чисел від 1 до 100.
27. Скласти програму підрахунку кількості мінімальних елементів в масиві A[1..N].
28.В одномірному числовому масиві всі від`ємні елементи замініть нуля ми.
29. Перевірити, чи є одномірний числовий масив упорядкованим по зростанню.
|
|
|
Последнее обновление 06.10.14 11:37 |
|
Практикум з розв'язування задач |
|
|
|
|
Добавил(а) Administrator
|
|
14.05.14 10:21 |
|
Практикум з розв’язування задач
1. Задача 1 (ІІІ етап Всеукраїнської олімпіади з інформатики 2013-2014 н.р.)
A. "Все, Степан! Ти мене дістав!"
|
Input file name:
|
bubble.in
|
|
Output file name:
|
bubble.out
|
|
Time limit:
|
100 ms
|
|
Memory limit:
|
256 M
|
Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок "три - чотири" хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час t1, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робе те ж саме за час t2.
Весь цей час викладач настільки захоплений доведенням теореми, що взагалі нічого не чує. І тільки коли обидві бульбашки лопнуть одночасно, викладач почує шум і обернеться. І тоді вже точно студентам попаде на горіхи, а більше усього тому, хто приніс на пару жувальні гумки.
Визначте, скільки часу хлопці можуть насолоджуватись надуванням бульбашок, не замічені викладачем.
Наприклад, якщо t1 = 2, t2 = 3, то буде відбуватись наступне:
Степан надуває бульбашку з моменту часу t = 0 до моменту часу t = 2, потім бульбашка лопається, і він надуває бульбашку заново - з моменту часу t = 2 до моменту часу t = 4, а потім ще раз - з моменту часу t = 4 до t = 6.
Товариш Степана надуває бульбашку з t = 0 до t = 3 і ще раз з t = 3 до t = 6.
В момент часу t = 6 бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: "Все, Степан! Ти мене дістав!".
Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа t1, t2 (1 ≤ t1, t2 ≤ 109).
Формат вихідних даних: Вихідний файл повинен містити одне ціле число - час, протягом якого Степан з товаришем можуть насолоджуватись надуванням бульбашок.
Приклад вхідних та вихідних даних:
|
bubble.in
|
bubble.out
|
|
2 3
|
6
|
|
1 16
|
16
|
|
Підхід
|
Програмний код
|
Тести
|
|
Підбір в циклі з перевіркою остачі від ділення
|
nsk=a;
while (nsk%a!=0||nsk%b!=0)nsk++;
|
Зараховано 63.6%
|
|
Підбір в циклі з перевіркою остачі від ділення
|
for (int i=1;i<=a;i++)
if(a%i==0&&b%i==0)nsd=i;
nsk=a*b/nsd;
|
Зараховано 63.6%
|
|
Алгоритм Евклідіа
|
while (b!=0)
{t=a%b;
a=b;
b=t;
}
|
Зараховано 100%
|
|
Алгоритм Евклідіа
|
while (b!=0)
{a=a%b;
swap(a,b);
}
|
Зараховано 100%
|
http://www.e-olimp.com.ua/problems/7239
2. Задача 2 (ІV етап Всеукраїнської олімпіади з інформатики 2013-2014 н.р.)
Відрізки (Роман Рубаненко, Роман Фурко)
Умова. Петрик дуже любить іграшки у формі геометричних фігур. Нещодавно він помітив, що серед його іграшок немає жодного трикутника. Це дуже засмутило Петрика, тому він пішов до найближчого магазину, щоб придбати новісінький трикутник. В магазині Петрику сказали, що всі трикутники вже давно розкупили, але в наявності є N прямих відрізків.
Відрізки пронумеровані послідовними натуральними числами, починаючи з одиниці. Відрізок номер i характеризується двома числами — довжиною Li та ціною Ci . Петрик дуже розумний, тому знає, що бажаний трикутник він може скласти з трьох відрізків. Більше того, наш герой знає, що трикутник можливо скласти лише з таких відрізків, що довжина будь-якого з них має бути строго меншою за сумарну довжину інших двох. Отже, хлопчик вирішив придбати рівно три таких відрізки. Звичайно, він хоче заощадити якомога більше коштів на морозиво, тому хоче витратити якнайменше на покупку відрізків для свого трикутника.
Завдання. Напишіть програму segments , яка за інформацією про відрізки визначить мінімальну вартість трьох відрізків, з яких хлопчик зможе скласти трикутник, або визначить, що це зробити неможливо.
Вхідні дані. В першому рядку вхідного файла segments.dat записано єдине число N — кількість відрізків. Далі в N рядках записана інформація про самі відрізки. Кожен такий рядок містить відповідні Li (1 ⩽ Li ⩽ 109 ) та Сi . Ціни утворюють перестановку чисел від 1 до N, тобто є попарно різними натуральними числами, не більшими за N.
Вихідні дані. Вихідний файл segments.sol має містити єдине число — мінімальну вартість трьох відрізків, з яких можна скласти трикутник, або «−1» (лапки для наочності) в тому випадку, якщо вибрати рівно три такі відрізки неможливо.
Оцінювання. Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:
1 ⩽ N ⩽ 100.
210 < N ⩽ 3000.
3000 < N ⩽ 104 .
o 30 балів: 104 < N ⩽ 105 .
Приклади вхідних та вихідних даних.
|
segments.dat
|
segments.sol
|
|
4
1 1
2 2
3 3
4 4
|
9
|
|
3
3 1
5 3
10 2
|
-1
|
|
Підхід
|
Програмний код
|
Тести
|
|
Розглянемо найпростіший алгоритм розв’язання задачі. Перебиратимемо всі трійки відрізків.
Для кожної трійки треба перевірити можливість існування відповідного трикутника. Якщо три-
кутник існує, підрахуємо сумарну вартість трьох відрізків, а з усіх знайдених вартостей вибе-
ремо найменшу. Складність алгоритму — O(N 3 ).
|
for(int i=0;i<n-2;i++)
for(int j=i+1;j<n-1;j++)
for(int k=j+1;k<n;k++)
if(l[i]<l[j]+l[k] && l[j]<l[i]+l[k] && l[k]<l[i]+l[j])
if (c[i]+c[j]+c[k]<m)m=c[i]+c[j]+c[k];
|
|
|
А от швидше розв’язання. Розглядатимемо всі відрізки в порядку від найкоротших до найдовших і підтримуватимемо таку структуру даних: масив F, у комірці F[c] якого зберігається
найбільша сумарна довжина двох відрізків (з числа перших k відрізків) із загальною вартістю c.
|
|
|
|
Тепер розглянемо оптимальне розв’язання. Воно базується на такій нескладній властивості:
Властивість. Якщо серед натуральних чисел L1 , L2 , ..., Lk немає трьох таких, що утворюють сторони трикутника, то найбільше з цих чисел не може бути меншим за k-й член послідовності Фібоначі.
|
#pragma comment(linker, "/STACK:64000000")
#include <algorithm>
#include <memory.h>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <queue>
using namespace std;
#define prev privet1
#define next privet2
#define y1 privet3
#define rank privet4
#define left privet5
#define right privet6
#define y0 privet7
const double pi = 3.141592653589793238;
const int INF = 1 << 30, ENOUGH_VALUE_OF_N = 300;
long long a[ENOUGH_VALUE_OF_N + 2];
int main()
{
freopen("segments.dat", "r", stdin);
freopen("segments.sol", "w", stdout);
int n, i, j, u;
scanf("%d", &n);
long long len;
int cost;
for (i = 1; i <= n; i++)
{
scanf("%lld%d", &len, &cost);
if (cost <= ENOUGH_VALUE_OF_N) a[cost] = len;
}
n = min(n, ENOUGH_VALUE_OF_N);
int ans = INF;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)
for (u = j + 1; u <= n; u++)
if (i + j + u < ans && a[i] < a[j] + a[u] && a[j] < a[i] + a[u] & a[u] < a[i] + a[j]) ans = i + j + u;
if (ans == INF) ans = -1;
printf("%d\n", ans);
}
|
|
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=3 – ІІ етап (районний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11 – ІІІ етап (обласний) Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user430; пароль 400-430).
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=12 – тренувальний тур по підготовці до ІV етапу Всеукраїнської олімпіади з інформатики 2012-2013 н.р. (логін user400-user414; пароль 400-414).
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=15 – Підготовка до олімпіади 2013 (логін user400-user430; пароль 400-430).
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=22 - Тренувальний турнір до міської олімпіади з інформатики (програмування) 2013 (м.Луцьк)
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=25 - ІІ етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2013-2014н.р.
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=26 - Волинська обласна Інтернет-олімпіада 2013
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=27 - Тренувальний турнір до обласної олімпіади 2014
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=28 - ІІI етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2013-2014 н.р.
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=29 - Підготовка до IV етапу олімпіади з інформатики (м.Луцьк) 2013-2014н.р. |
|
Матеріали XXVII Всеукраїнської учнівської олімпіади з інформатики 2013/14 н. р. |
|
|
|
|
Добавил(а) Administrator
|
|
14.05.14 10:12 |
Матеріали XXVII Всеукраїнської учнівської олімпіади з інформатики 2013/14 н. р.
Умови та розв'язки
Авторські розв'язки
Результати
Розбаловка по тестах
|
|
Матеріали ІІІ етапу Всеукраїнської олімпіалди 2013-2014 н.р. |
|
|
|
|
Добавил(а) Administrator
|
|
09.02.14 20:19 |
|
Матеріали IІІ етапу Всеукраїнської учнівської олімпіади з інформатики 2013-2014
Завдання І туру
Завдання ІІ туру
Результати ІІІ етапу олімпіади з інформатики
Тести (1 тур, 2 тур)
Розбір задач |
|
Турнір з задач обласної олімпіади 2014 |
|
|
|
|
Добавил(а) Administrator
|
|
08.02.14 15:32 |
|
Турнір з задач обласної олімпіади:
http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=28
реєстрація вільна |
|
|