|
2 тур Волинська учнівська Інтернет-олімпіада з програмування |
 |
 |
 |
|
Добавил(а) Administrator
|
|
13.11.13 11:48 |
|
2 тур - з 11.11 по 17.11.2013
точка входу для відправлення розв'язків http://93.171.173.139/cgi-bin/new-client?contest_id=17
Задача 1. За сірниками (20 балів)
Ім'я вхідного файлу: money.dat Ім'я вихідного файлу: money.ans Програма: money.*
Ліміт часу: 1 секунда
Василько записався на гурток технічної творчості «Умілі ручки». На гуртку йому показали, як будувати сірникові будиночки. Але для побудови йому необхідно придбати сірники.
Пачки сірників продаються в трьох різних видах упаковок. Упаковка зі 100 пачок коштує 1 грн., з 20 пачок – 30 коп., а одна окрема пачка коштує 2 коп.
Василько обмежений в коштах, підрахуйте яка мінімальна сума має бути у Василька, щоб купити N пачок сірників.
Технічні умови
Вхідні дані
Кількість N пачок, які потрібно купити. N ≤ 1000.
Вихідні дані.
Мінімальна сума, потрібна для покупки, в гривнях.
Приклад
|
money.dat
123
|
money.ans
1.36
|
|
Розв’язок
|
|
a=n/100;
n=n%100;
b=n/20;
n=n%20;
c=n%20;
r=(a*100+b*30+c*2)/100;
|
|
a=n/100;
n=n%100;
b=n/20;
n=n%20;
c=n%20;
if(b>3){b=0;c=0;a=a+1;}
if(c>15){c=0;b=b+1;}
r=double(a*100+b*30+c*2)/100.0;
cout.precision(2);
cout<< fixed<<r<<endl;
|
Задача 2. Сірники (100 балів)
Ім'я вхідного файлу: match.dat Ім'я вихідного файлу: match.ans Програма: match.*
Ліміт часу: 1 секунда
Василько для побудови сірникових будиночків, почав розкладати сірники на столі. Йому стало цікаво, яка мінімальна кількість сірників потрібна для того, щоб викласти на площині N квадратів зі стороною в один сірник? Сірники він не ламав та не клав один на одного, вершинами квадратів були точки, де сходились кінці сірників.
Поможіть Васильку підрахувати мінімальну кількість сірників, для побудови квадратів N.
Технічні умови
Вхідні дані
Єдиний рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 109).
Вихідні дані
Одне число, мінімальна кількість сірників.
Приклад
|
Розв’язок
|
|
a=sqrt(double(n));
r=2*a*(a+1);
|
|
a=sqrt(double(n));
b=n-(a*a);
if (b==0)r=2*a*(a+1);else
r=2*a*(a+1)+b*2+((b-1)/a+1);
|
|
|
1 тур Волинська учнівська Інтернет-олімпіада з програмування |
|
|
|
|
Добавил(а) Administrator
|
|
06.11.13 11:11 |
|
Волинська учнівська Інтернет-олімпіада з програмування
Реєстрація http://vippoolimp.16mb.com/joomla/index.php/registr2013
1тур - з 04.11 по 10.11.2013
Задача 1. Цікаві числа (20 балів)
Ім'я вхідного файлу: number.dat
Ім'я вихідного файлу: number.ans
Програма: number.*
Обмеження часу: 2с
Два різних натуральних числа називаються цікавими, якщо перше з них дорівнює сумі дільників другого числа, за винятком самого другого числа, а друге дорівнює сумі дільників першого числа, за винятком самого першого числа. Потрібно знайти всі пари цікавих чисел, обидва з яких належать проміжку від M до N.
Вхідні дані
У першому рядку знаходяться відокремлені пропуском числа M і N.
M і N цілі; 1 ≤ M ≤ N ≤ 106.
Вихідні дані
У кожному рядку вивести по парі чисел через пропуск. Перше число пари повинно бути менше другого. Рядки повинні бути відсортовані у порядку зростання першого числа пари. Якщо пар цікавих чисел на проміжку немає, вивести "Absent".
|
Приклад вхідних даних
Приклад 1
200 300
Приклад 2
200 250
|
Приклад вихідних даних
Приклад 1
220 284
Приклад 2
Absent
|
Задача 2. Таблиця (100 балів)
Ім'я вхідного файлу: table.dat
Ім'я вихідного файлу: table.ans
Програма: table.*
Обмеження часу: 2с
Маємо таблицю розміром N*M, в кожній клітинці якої записана цифра 0 або 1. На кожному кроці Ви можете вибрати одну клітинку і поміняти значення в усіх клітинках, які знаходяться в тому ж рядку або в тому ж стовпці, на протилежні. Таким чином, на кожному кроці Ви змінюєте рівно N+M-1 клітинок.
Визначити мінімальну кількість кроків необхідних для того, щоб перетворити всі клітинки даної таблиці в 0. Кількість рядків і стовпців – парні числа. Наприклад, якщо ви вибрали клітинку (2,2):
1 1 1 1 0 1
0 1 1 -> 1 0 0
0 0 1 0 1 1
Вхідні дані
Перший рядок містить два цілих числа M і N (2<N,M<1000).Далі N рядків по Mцілих чисел, - опис таблиці (кожне число 0 бо 1). N і M – парні.
Вихідні дані
Одне число – мінімальна кількість кроків, які необхідні, щоб перетворити всі клітинки таблиці в 0.
|
Приклад вхідних даних
|
Приклад вихідних даних
|
|
Приклад 1
2 2
1 0
1 0
|
Приклад 1
2
|
|
Приклад 2
4 4
0 0 1 0
0 1 0 1
1 1 1 0
0 0 1 0
|
Приклад 2
9
|
Волинська учнівська Інтернет-олімпіада з програмування
Реєстрація http://vippoolimp.16mb.com/joomla/index.php/registr2013
1тур - з 04.11 по 10.11.2013
Задача 1. Цікаві числа (20 балів)
Ім'я вхідного файлу: number.dat
Ім'я вихідного файлу: number.ans
Програма: number.*
Обмеження часу: 2с
Два різних натуральних числа називаються цікавими, якщо перше з них дорівнює сумі дільників другого числа, за винятком самого другого числа, а друге дорівнює сумі дільників першого числа, за винятком самого першого числа. Потрібно знайти всі пари цікавих чисел, обидва з яких належать проміжку від M до N.
Вхідні дані
У першому рядку знаходяться відокремлені пропуском числа M і N.
M і N цілі; 1 ≤ M ≤ N ≤ 106.
Вихідні дані
У кожному рядку вивести по парі чисел через пропуск. Перше число пари повинно бути менше другого. Рядки повинні бути відсортовані у порядку зростання першого числа пари. Якщо пар цікавих чисел на проміжку немає, вивести "Absent".
|
Приклад вхідних даних
Приклад 1
200 300
Приклад 2
200 250
|
Приклад вихідних даних
Приклад 1
220 284
Приклад 2
Absent
|
Задача 2. Таблиця (100 балів)
Ім'я вхідного файлу: table.dat
Ім'я вихідного файлу: table.ans
Програма: table.*
Обмеження часу: 2с
Маємо таблицю розміром N*M, в кожній клітинці якої записана цифра 0 або 1. На кожному кроці Ви можете вибрати одну клітинку і поміняти значення в усіх клітинках, які знаходяться в тому ж рядку або в тому ж стовпці, на протилежні. Таким чином, на кожному кроці Ви змінюєте рівно N+M-1 клітинок.
Визначити мінімальну кількість кроків необхідних для того, щоб перетворити всі клітинки даної таблиці в 0. Кількість рядків і стовпців – парні числа. Наприклад, якщо ви вибрали клітинку (2,2):
1 1 1 1 0 1
0 1 1 -> 1 0 0
0 0 1 0 1 1
Вхідні дані
Перший рядок містить два цілих числа M і N (2<N,M<1000).Далі N рядків по Mцілих чисел, - опис таблиці (кожне число 0 бо 1). N і M – парні.
Вихідні дані
Одне число – мінімальна кількість кроків, які необхідні, щоб перетворити всі клітинки таблиці в 0.
|
Приклад вхідних даних
|
Приклад вихідних даних
|
|
Приклад 1
2 2
1 0
1 0
|
Приклад 1
2
|
|
Приклад 2
4 4
0 0 1 0
0 1 0 1
1 1 1 0
0 0 1 0
|
Приклад 2
9
|
|
Задача 1
|
|
Спосіб 1
|
Спосіб 2
|
|
Алгоритм:
1.Перебираємо всі числа з діапазону [M,N]
2. Шукаємо для поточного числа суму дільників
d1=0;
for (int i=1;i<k;i++)
if (k%i==0)d1=d1+i;
cout<<d1<<endl;
3. Якщо сума дільників лежить на проміжку [k+1, N], то шукаємо суму дільників для знайденої суми
4. Якщо знайдена сума рівна поточному числу k, то виводимо результат і фіксуємо що знайшли хоча б одну пару
5. Якщо жодної пари не знайшли, то виводимо «Absent»
|
- 220 284
- 1184 1210
- 2620 2924
- 5020 5564
- 6232 6368
- 10744 10856
- 12285 14595
- 17296 18416
- 63020 76084
- 66928 66992
- 67095 71145
- 69615 87633
- 79750 88730
- 100485 124155
- 122265 139815
- 122368 123152
- 141664 153176
- 142310 168730
- 171856 176336
- 176272 180848
- 185368 203432
- 196724 202444
- 280540 365084
- 308620 389924
- 319550 430402
- 356408 399592
- 437456 455344
- 469028 486178
- 503056 514736
- 522405 525915
- 600392 669688
- 609928 686072
- 624184 691256
- 635624 712216
- 643336 652664
- 667964 783556
- 726104 796696
- 802725 863835
- 879712 901424
- 898216 980984
|
|
Задача 2
|
|
0 0 0 0 (0 кроків)
0 1 1 1
0 0 0 0 (1 крок)
0 0 1 1
1 1 1 0
0 0 0 0 (2 кроки)
0 0 0 1
0 1 1 0
0 0 0 1
0 0 0 0 (3 кроки)
1 1 1 1
1 0 0 0
0 0 1 1
1 1 1 0
0 0 0 0 (4 кроки)
|
|
|
|
Готуємось до олімпіади з інформатики (додаток 3) |
|
|
|
|
Добавил(а) Administrator
|
|
01.11.13 10:57 |
|
Додаток 3
Готуємось до олімпіади з інформатики
(додаток 3)
|
Єдиний спосіб вивчати нову мову програмування –
писати на ній програми.
Брайен Керніган
План роботи
|
- Олімпіадна інформатика. Методика організація роботи з обдарованими учнями.
- Тематика олімпіадних задач. Методика складання алгоритмів та їх аналіз.
- Правила проведення олімпіад по програмуванню. Типові помилки і налагодження програм. Система для автоматичного тестування програм ejudge.
- Практикум з розв’язування олімпіадних задач.
|
Олімпіадна інформатика
1. Що таке олімпіадна інформатика?
Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.
2. Як перевіряються розв’язки задач олімпіади
Історично склалося так, що розв’язки на олімпіадах по програмуванню перевіряються автоматично. Ваше завдання написати програму, яка за заданими вхідними даними обчислює і виводить вихідні дані.
3.Апаратне та програмне забезпечення
Учасникам олімпіади можуть вибирати мову програмування с заданого переліку: Pascal, C або C++. Система програмування Free Pascal 2.0 (чи новішої версії), GCC 4.2 (чи новішої версії), Turbo Delphi Explorer, Visual C++ 2008 Express).
4. Тематика задача олімпіади
Завдання олімпіади мають бути алгоритмічного характеру, тобто основними результатами роботи учасника має бути: алгоритм, що правильно та ефективно розв’язує поставлену задачу, та програма, що реалізує запропонований алгоритм.
Основними категоріями олімпіадних задач є:
|
Геометрія
Графічні задачі
Динамічне програмування
Довга арифметика
Жадібний алгоритм
Задачі для початківців
Комбінаторика
Масиви
Математика
Математичне моделювання
|
Обробка рядків
Послідовності
Рекурсія, перебір
Логічні задачі
Сортування
Структури даних
Теорія графів
Теорія ігор
Теорія чисел
|
| |
- Етап олімпіади
- Інформатика
- Інформаційні технології
|
|
|
|
| |
|
- Теорія чисел: розклад числа на множники
- Обчислювальна геометрія: довжина відрізка, властивості геометричних фігур
- Пошук та сортування масивів
- Повний перебір, динамічне програмування
|
- Текстовий редактор: параметри сторінки, форматування шрифту і абзацу, колонтитули, форматування графічних об’єктів, колонки
- Презентації: створення авто фігур, налаштування анімації руху по колу з налаштуванням періоду
- Електронні таблиці: формули з використанням функцій (логічних, математичних ЕСЛИ, СУММЕСЛИ, ABS), побудова діаграм
- СУБД: створення таблиць, форм, запитів на вибір та з параметром, звітів з групуванням
|
|
| |
|
- Синтаксичний аналіз: робота з рядками
- Пошук та сортування масивів
- Теорія чисел: НСД
- Динамічне програмування
- Теорія графів
|
- Текстовий редактор: параметри сторінки, форматування шрифту і абзацу, колонтитули, форматування графічних об’єктів, колонки, розділи
- Презентації: створення авто фігур, групування, налаштування анімації, кнопки, гіперпосилання
- Електронні таблиці: формули з використанням функцій (логічних, математичних, посилання і масиви, перевірка властивостей і значень ЕСЛИ, СУММЕСЛИ, ABS, СТОЛБЕЦ, СТРОКА, ЕПУСТО), побудова діаграм, елементи форми
- СУБД: створення таблиць, зв’язок між таблицями, створення декількох ключових полів, форм в ручну, запитів на вибір та з параметром, групові операції , звітів з групуванням, макроси
|
|
| |
|
- Повний перебір
- Жадібні алгоритми
- Динамічне програмування
- Граф: пошук найкоротшого шляху, пошук в ширину
- Обчислювальна геометрія: опуклі многокутники
- Структури даних: дерево
|
- Текстовий редактор: макрос в режимі автозаписуванням
|
|
| |
|
|
|
|
5. Системи тестування
Працюйте в он-лайн системах, які автоматично перевіряють та тестують Ваші розв’язки:
http://olymp.sumdu.edu.ua - Веб-ресурс підтримки та проведення шкільних та студентських олімпіад з інформатики
http://www.e-olimp.com.ua/ - Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України
http://www.olymp.vinnica.ua/ - Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet.
Список тестуючи систем
7. Логічні задачі
Задача 1.
Переможці олімпіад.
П’ятеро однокласників: Ірина, Тарас, Катя, Сергій і Микола стали переможцями олімпіад школярів з фізики, математики, інформатики, літератури та географії. Відомо, що:
- переможець олімпіади з інформатики вчить Іірину і Тараса працювати на комп’ютері;
- Катя і Сергій також зацікавились інформатикою;
- Тарас завжди побоювався фізики;
- Катя, Тарас і переможець олімпіади з літератури займаються плаванням;
- Тарас і Катя привітали переможця олімпіади з математики;
- Іра шкодує, що в неї залишається мало часу на літературу.
Переможцем якої олімпіади став кожен з учнів?
8. Базові структури алгоритмів: слідування, розгалуження, цикл.
Задача 2. «Фотокартка» (PHOTO)
Учень на новенькому кольоровому струменевому принтері учень надрукував фотографії зроблені у свій день народження. Розмір фото AxB cм. Роздільна здатність принтера R точок на дюйм (1 дюйм = 2,54 см).
Завдання
Визначити скільки пікселів містить надруковане фото?
Вхідні дані
Перший рядок містить два дійсні числа, які задають розмір фотокартки. Останній рядок містить натуральне число, яке задає роздільну здатність. Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить шукану кількість мегапікселів на фотографії, як дійсне число з двома знаками після коми.
Приклад
|
input.dat
|
output.ans
|
|
2.54
2.54
1000
|
1.00
|
Задача 3. «Клас» .
На початку навчального року класний керівник між учнями класу поділила N зошитів та M олівців. Скільки учнів в класі, якщо відомо їх не менше ніж K і кожний з учнів отримав однакову кількість зошитів та олівців.
Вхідні дані
Перший рядок містить натуральні числа N, M, K. Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить знайдену кількість учнів. Якщо результатів декілька, то вивести всі через пропуск в зростаючому порядку.
Приклад
|
input.dat
|
output.ans
|
|
92
138
25
|
46
|
Задача 4. «День народження» – 30 балів.
Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.
Вхідні дані
Перший рядок містить загальну кількість учнів, натуральне число N.
В наступних рядках кількість розданих цукерок.
Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить кількість дівчат та хлопчиків через пропуск.
Приклад
|
input.dat
|
output.ans
|
|
5
3
1
2
4
3
|
3 2
|
9. Структуровані типи величин.
Операції з масивом.
|
Операція з масивом
|
Pascal
|
C++
|
|
Опис
|
Var a:array[1..100] of integer;
i, n:integer;//індекс, кількість елементів
|
int a[100];
int i, n;//індекс, кількість елементів
|
|
Введення
|
readln(n);
for i:=1 to n do read(a[i]);
|
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
|
|
Виведення
|
for i:=1 to n do write(a[i],’ ‘);
|
for(i=1;i<=n;i++)cout<<a[i]<<” “;
|
|
Сумування
|
s=0;
for i:=1 to n do s:=s+a[i];
|
s=0;
for(i=1;i<=n;i++)s=s+a[i];
|
|
Пошук
|
readln(k);
for i:=1 to n do if a[i]=k then writeln(i);
|
cin>>k;
for(i=1;i<=n;i++) if (a[i]==k) cout<<i;
|
|
Пошук максимального
|
max:=a[1];nmax:=1;
for i:=2 to n do if a[i]>max then begin max:=a[i];nmax:=i;end;
|
max=a[1];nmax=1;
for(i=2;i<=n;i++)if (a[i]>max) {max=a[i];nmax=i;}
|
|
Сортування
|
for i:=1 to n -1do
for j:=1 to n -1do
if a[j]>a[j+1] then begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp;
end;
|
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 to n do a[i]:=a[i+1];
|
n=n-1;
for(i=k;i<=n;i++)
a[i]=a[i+1];
|
|
Вставка
|
n:=n+1;
for i:=n downto k+1 do
a[i]:=a[i-1];
|
n=n+1;
for(i=n;i>=1;i--)
a[i]=a[i-1];
|
10. Робота з файлами
|
Pascal
|
C++
|
|
var f1,f2:text;
assign(f1,’input.dat’);
reset(f1);
read(f1,...);
close(f1);
assign(f2,’output.dat’);
rewite(f2);
write(f2,...);
close(f2);
|
#include <fstream.h>
void 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();
}
|
|
assign(input,’input.dat’);
reset(input);
read(...);
close(input);
assign(output,’output.dat’);
rewite(output);
write(...);
close(output);
|
#include <fstream.h>
ifstream inp("input.dat");
ofstream out("output.sol");
void main()
{
int a,b,c;
inp>>a>>b;
c=a+b;
out<<c;
}
|
- Є велика кількість завдань, які вимагають знання з теорії чисел. Наприклад , знаходження простих чисел, розкладання на прості множники , поділ з остачею, НСД та НСК і т.д.
- Ряд
- Приклад
- Формула N елемента
- Рекурентне співвідношення
- Непарні числа
- 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21
- 2n-1
- an=an-1+2
- Арифметична прогресія
- 3, 6, 9, 12,15,18,21
- an=a1+(n-1)d
- an=an-1+d
- Прості
- 2, 3, 5, 7, 11, 13, 17, 23
- Фібоначчі
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
- 1/√5((1+√5)/2-(1-√5)/2)n
- F(n) = F(n-1) + F(n-2) для F(0) = 0 та
- F(1) = 1.
- Факторіал
- 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800
- n(n-1)(n-2)…2.1
- F(n)=F(n-1)*n
- Каталана
- 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
- (2n)!/(n!(n+1)!)
- Cn=∑CiCn-1-i
- Комбінації
- 1,3,6,3,1
- n!/(k!(n-k)!
- Cmn=Cmn-1(m-n+1)/n
- …
|
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
|
Практичний тур
|
http:://olymp.gimn14.lutsk.ua/new-register
- вибрати турнір: Опорна школа. Теорія чисел
- створити обліковий запис, зареєструватися в системі ввівши логін, адресу електронну пошту (пароль записати)
- ввійти в систему
- відредагувати дані (ввести ім’я учасника: Прізвище, ім’я, школа)
- підтвердити реєстрацію
- протестувати задачі
|
Задача 5.
XVII Всеукраїнська олімпіада з інформатики. Другий тур. Працівники (100 балів)
На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.
Існують правила, за якими визначається чи можна обробляти деталь на певному верстаті.
- Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.
- У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.
Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.
Завдання
Напишіть програму STAFF, що за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.
Вхідні дані
Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.
Вихідні дані
Єдиний рядок вихідного файлу STAFF.SOL має містити ціле число – максимальну можливу кількість працівників заводу.
Приклад вхідних та вихідних даних
Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станке B – деталі 2 та 4. Інших варіантів послідовності обробки немає.
Задача 6.
XIX Всеукраїнська олімпіада з інформатики. Перший тур. Дільники (100 балів)
За заданим натуральним числом N необхідно обчислити кількість натуральних чисел, які є дільниками N! (факторіалу числа N).
Наприклад, при N=4, N!=4·3·2·1=24. Це число має такі дільники: 1, 2, 3, 4, 6, 8, 12, 24. Таким чином шукана кількість дорівнює 8.
Завдання
Напишіть програму DIVISOR, що за натуральним N, знаходить кількість дільників його факторіалу.
Вхідні дані
Єдиний рядок вхідного файлу DIVISOR.DAT містить одне ціле число N (1≤N≤45).
Вихідні дані
Єдиний рядок вихідного файлу DIVISOR.SOL має містити одне ціле число – знайдену кількість дільників числа N!
Приклад вхідних та вихідних даних
Задача 7.
Просте число — це натуральне число, яке має рівно два натуральних дільника (лише 1 і саме число)
Послідовність простих чисел починається так:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 , 127, 131, 137, 139, 149, …
Написати програму виведення простих чисел в діапазоні до N.
|
Мова програмування
|
Варіант 1
|
Варіант 2
|
|
Pascal
|
var n,i,j:integer;
p:integer;
begin
readln(n);
for i:=2 to n do
begin
p:=0;
for j:=2 to round(sqrt(i)) do
if i mod j =0 then p:=1;
if p=0 then write(i,' ');
end;
end.
|
var a:array[1..100000000] of integer;
j,k,n,i:integer;
begin
readln(n);
for i:=1 to n do a[i]:=i;
a[1]:=0;
i:=1;
while i<=n div 2 do begin
while a[i]=0 do i:=i+1;
j:=i+a[i];
while j<=n do begin
a[j]:=0;
j:=j+a[i];
end;
i:=i+1;
end;
for k:=1 to n do
if a[k]<>0 then write(a[k],' ');
writeln;
end.
|
|
С++
|
// прості 2 3 5 7 11 13 17
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{int n,i,j,p;
cin>>n;
for (i=2;i<=n;i++)
{p=0;
for (j=2;j<i; j++)
if (i%j==0) p=1;
if ( p==0) cout<<i<<" ";}
return 0;
}
|
#include "iostream"
using namespace std;
int main()
{int n;
cin>>n;
int *a=new int[2*n];
int j,i;
for(i=1;i<=n;i++)a[i]=i;
a[1]=0;i=1;
while (i<=n/2)
{while (a[i]==0) i++;
j=i;
while (j<=n){j=j+a[i];a[j]=0;}
i++;
}
for (i=1;i<=n;i++)
if (a[i]!=0)cout<<a[i]<<" ";
}
|
Фіксація часу роботи програми
|
Pascal (Delphi)
|
C++ (Visual C++)
|
|
uses
SysUtils, windows;
var time:int64;
begin
time:=gettickcount;
//*****************************
time:=gettickcount-time;
writeln(time/1000:0:5);
end.
|
#include <time.h>
using namespace std;
int main()
{
//системний час до
clock_t start = clock();
//*********************
// час після
long double r=(clock() - start)*1. / CLOCKS_PER_SEC;
cout<<"times work = "<<r<<endl;
return 0;
}
|
Теорія графів
|
1
|
Пошук в глибину
|
void p(int k, int v)
{c[k]=v;
if (v==v2 || k>=n) {
if (v==v2)
{
//for (int i=1;i<=k;i++)cout<<c[i]<<" ";cout<<endl;
int s=0;
for (int i=1;i<k;i++)s=s+a[c[i]][c[i+1]];
//cout<<"s="<<s<<endl;
if (s<m) m=s;
}
}
else
for (int i=1;i<=n;i++)
if (a[v][i]>0) p(k+1,i);
}
|
|
2
|
Флойда
|
k= 1;
for(i= 1;i<=n;i++)x[i]=a[v1][i];
// {инвариант: x[i] = МинСт(1,i,k)}
while (k!=n)
{
for(s=1;s<=n;s++){
y[s]=x[s];
for(i=1;i<=n;i++) if (y[s]>x[i]+a[i][s]) y[s]= x[i]+a[i][s];
// {y[s] = МинСт(1,s,k+1)}
for (i=1;i<=n;i++) x[s]=y[s];
}
k++;
}
|
|
3
|
Форда
|
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
|
|
4
|
Прима
|
|
Задача 8. Дорога в гімназію.
Задача Дорога в школу
|
Имя входного файла:
|
input.dat
|
|
Имя выходного файла:
|
output.ans
|
|
Ограничение времени:
|
30 с
|
|
Ограничение памяти:
|
64 M
|
Задача 4. Дорога в гімназію
На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити хоча б довжину найкоротшої дороги від доми до школи.
Формат вхідних даних
Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії. Наступні рядків задають карту намальованих доріг початкова та кінцева точка.
Формат результату
Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги. Якщо дороги немає вивести "no".
Приклад
|
input.dat
|
output.ans
|
6
150 70
160 90
100 100
170 120
120 140
80 160
1 2
2 3
2 4
3 5
4 5
5 6
|
152.556
|
Задача 9. Дорога в гімназію 2.
На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити довжину найкоротшої дороги та сам маршрут від доми до школи.
Формат вхідних даних
Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії. Наступні рядків задають карту намальованих доріг початкова та кінцева точка.
Формат результату
Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги та рядок цілих чисел, які задають маршрут. Якщо дороги немає вивести "no".
Приклад
|
input.dat
|
output.ans
|
6
150 70
160 90
100 100
170 120
120 140
80 160
1 2
2 3
2 4
3 5
4 5
5 6
|
152.556
1 2 4 5 6
|
Задача 10.
Збирання мита (TALLAGE) -100 балів.
Король країни Аріїв завоював Nміст на території сусідніх держав.
Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.
Вхідні дані:
Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість міст у країні, а також цілі числа X та Y – координати столиці.
Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.
Значення координат по модулю менші 50000.
Вихідні дані:
Єдиний рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.
Приклади:
|
input.dat
|
output.ans
|
|
6 0 0
1 1
-1 1
0 2
1 -1
-1 -1
0 -2
|
8.485
|
6. Список ресурсів
|
|
Последнее обновление 13.11.13 11:53 |
|
Готуємось до олімпіади (додаток 2) |
|
|
|
|
Добавил(а) Гісь Ігор Володимирович
|
|
30.10.13 10:53 |
|
додаток 2
Готуємось до олімпіади
(додаток 2)
1.Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в даній послідовності.
|
1 спосіб.
Посортувати і відшукати різницю, рівну два між сусідніми елементами.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{int n,i,j,temp,r,a[1000];
cin>>n;
for (i=1;i<=n;i++)cin>>a[i];
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;}
a[n+1]=n+1;
for (i=1;i<=n;i++)
if (a[i+1]-a[i]==2) r=a[i]+1;
cout<<r<<endl;
return 0;
}
|
2 спосіб.
Перевірити, чи існує кожне з чисел від 0 до N у послідовності, використовуючи два вкладених цикли.
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{int n,i,j,s,r,a[1000];
cin>>n;
for (i=1;i<=n;i++)cin>>a[i];
for (i=0;i<=n;i++)
{s=0;
for (j=1;j<n;j++)
if (j==a[i]) s=1;
if (s==0) r=i;
}
cout<<r<<endl;
return 0;
}
|
|
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 згідно з формулою
Результат R=S2-S1=15-14=1
Отже, не існує числа 1.
|
#include "stdafx.h"
#include "iostream"
using namespace std;
int main()
{int n,i,j,s1,s2,r,a[1000];
cin>>n;
for (i=1;i<=n;i++)cin>>a[i];
s1=0;
for (i=1;i<=n;i++)s1=s1+a[i];
s2=(n+0)*(n+1)/2;
r=s2-s1;
cout<<r<<endl;
return 0;
}
|
По вигляду, структурі і кількості простих операцій видно, що найоптимальнішими способом є останній, де використовується формула знаходження суми арифметичної прогресії.
2. Проходження лабіринту.Написати алгоритм пошуку виходу в лабіринті.
Наявна матриця розміру 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 елементів, тобто весь набір даних можна розмістити в статичній пам'яті.
Одним з найбільш ефективних алгоритмів пошуку найкоротшого шляху є алгоритм хвилі. Хвильовий алгоритм полягає в наступному:
- кожної клітинок i приписується число T - тимчасова мітка.
- заводяться два списки "фронту хвилі" NF і OF, а також перемінна T (поточний час);
- OF:={u1}; NF:={}; T:=1;
- для кожної з вершин i, що входять у OF, проглядаються сусідні вершини j, і якщо T[j] = -2, то T[j]=T, NF=NF + {j}.
- якщо NF = {}, то шлях не існує, перехід до кроку 8.
- якщо одна з вершин збігається з u2, то знайдений найкоротший шлях довжини T, перехід до кроку 8;
- OF:=NF; NF:={}; T:=T+1; повернення до кроку 4.
- Відновлюємо шлях проходячи масив P, шукая серед сусідів даної клітинки таку, щоб номер ітерації хвилі у неї був найменшим.
1. Якось, пам'ятається, ще в грі "HЛО-1", проскочило побажання до тих, хто хоче стати добрим програмістом, підвищувати, підвищувати і ще раз підвищувати свій освітній рівень. На що із сторінок одного дуже поважаного видання виступив читач з наступною думкою (дослівно не пам'ятаю): "Я людина темна, але код програми - що треба. Значить, я вже добрий програміст". Дана стаття є спроба розвіяти цю глибоку помилку. В першу чергу вона адресована тим, хто займається створенням ігор і тим, кому не дає спокою думка: "А що там всередині?" Для її розуміння достатньо знання що таке двомірні масиви.
Побудова найкоротшого маршруту
Задача знаходження найкоротшого шляху між якимись точками А і В на ігровому полі з довільно розташованими перешкодами характерна, в першу чергу, для популярних сьогодні тактичних і стратегічних ігор. Як підзадача, вона може виникати практично в будь-яких іграх - RPG, квестaх, логічних (типовий приклад "Color Lines").
Чому треба шукати найкоротший маршрут? В деяких іграх, наприклад "HЛО-2", "Laser Squad", від довжини маршруту залежить кількість витрачених одиниць часу - чим оптимaльніше буде знайдений шлях, тим швидше воїн дістанеться до мети. А, наприклад, в "Color Lines" довжина маршруту не обумовлена правилами, має значення лише сам факт можливості або неможливості переміщення кулі. Але і в цій грі приємніше виглядатиме, якщо кулька відразу попрямує куди треба, а загадково не дефілюватиме по всій ігровій дошці.
Рішення цієї задачі прийшло до нас з такої далекої, здавалося б, від ігор області як електроніка. А саме - розводка друкарської плати (всі знають, що це таке? ;).
Існує велика кількість трасувальників (програм для розводки плати), заснованих на не меншій кількості різних методів, що займаються з'єднанням двох контактів єдиним провідником. Але ми розглянемо тільки один з них, найпростіший (а значить, найнадійніший і найпопулярніший) - хвильовий трасувальник.
Поставимо перед хвильовим трасувальником задачу в термінах що розробляється нами гри:
Є ігрове поле Р(MxN),де M і N, відповідно, розмір поля по вертикалі і горизонталі. Просто, це масив розмірністю MxN. Кожна клітка ігрового поля (елемент масиву) може мати багато властивостей на ваш розсуд, але для нас важливо тільки одне - її прохідність (або непрохідність). Яким чином вона визначається - це вже ваша справа. Далі: є деяка стартова точка, де знаходиться герой вашої гри, і кінцева точка, куди йому необхідно потрапити. Умовимося поки, що ходити він може тільки по чотирьох напрямах (чого вимагає від нас класичний хвильовий метод) - вправо, вліво, вперед, назад. Hеобхідно перемістити героя від місця старту до фінішу за якнайменшу кількість ходів, якщо таке переміщення взагалі можливо.
- Спочатку необхідно створити робочий масив R(MxN), рівний за розміром масиву ігрового поля P(MxN).
- Кожному елементу робочого масиву R(i,j) привласнюється деяке значення в поля P(i,j) за наступними правилами:
а) Якщо поле P(i,j) непрохідне, то R(i,j):=255;
б) Якщо поле P(i,j) прохідне, то R(i,j):=254;
в) Якщо поле P(i,j) є цільовою (фінішної) позицією, то R(i,j):=0;
г) Якщо поле P(i,j) є стартовою позицією, то R(i,j):=253.
- Етап "Розповсюдження хвилі". Вводимо змінну Ni - лічильник ітерацій (повторів) і надаємо їй початкове значення 0.
- Вводимо константу Nк, котору встановлюємо рівній максимально можливому числу ітерацій (Nk<253).
- По рядках проглядаємо робочий масив R (оргaнізуємо два вкладених циклa: по індексу масиву i від 1 до М, по індексу масиву j від 1 до N).
- Якщо R(i,j) рівний Ni, то є видимими сусідні елементи R(i+1,j), R(i-1,j),R(i,j+1), R(i,j-1) за наступним правилом (як приклад розглянемо R(i+1,j)):
а) Якщо R(i+1,j)=253, то переходимо до пункту 10;
б) Якщо R(i+1,j)=254, виконується присвоєння R(i+1,j):=Ni+1;
в) У всій інших випадках R(i+1,j) залишається без змін. Аналогічно поступаємо з елементами R(i-1,j), R(i,j+1),R(i,j-1).
- По завершенню рядкового перегляду всього масиву збільшуємо Ni на 1.
- Якщо Ni>Nк,то пошук маршруту визнається невдалим. Вихід з програми.
- Переходимо до пункту 5.
- Етап побудови маршруту переміщення. Привласнюємо змінним Х і У значення координат стартової позиції.
- Навколо позиції R(Х,Y) шукаємо елемент з якнайменшим значенням (т.т. для цього проглядаємо R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координати цього елемента заносимо в змінні X1 і Y1.
- Робимо переміщення об'єкту по ігровому полю з позиції [X,Y] в позицію [X1,Y1]. (За бажанням, ви можете заздалегідь заносити координати X1,Y1 в деякий масив, і, тільки закінчивши побудову всього маршруту, зайнятися періміщення героя на екрані).
- Якщо R(X1,Y1)=0,то переходимо до пункту 15.
- Виконуємо привласнення X:=X1,Y:=Y1. Переходимо до пункту 11.
- Все !!!
|
#include "iostream"
using namespace std;
int a[1000][1000];
int main()
{int n,m,i,j,k,f;
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)cin>>a[i][j];
k=2;
f=1;
while (f==1)
{f=0;
|
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
if (a[i][j]==k && a[i-1][j]==1) {f=1;a[i-1][j]=k+1;}
if (a[i][j]==k && a[i+1][j]==1) {f=1;a[i+1][j]=k+1;}
if (a[i][j]==k && a[i][j-1]==1) {f=1;a[i][j-1]=k+1;}
if (a[i][j]==k && a[i][j+1]==1) { f=1;a[i][j+1]=k+1;}
}
k++;
}
for (i=1;i<=n;i++){
for (j=1;j<=m;j++) cout<<a[i][j]<<" ";
cout<<endl;}
return 0;
}
|
|
|
Теорія графів Турнір «Графи» |
|
|
|
|
Добавил(а) Гісь Ігор Володимирович
|
|
23.10.13 10:52 |
|
Теорія графів
Турнір «Графи»
|
1
|
Пошук в глибину
|
void p(int k, int v)
{c[k]=v;
if (v==v2 || k>=n) {
if (v==v2)
{
//for (int i=1;i<=k;i++)cout<<c[i]<<" ";cout<<endl;
int s=0;
for (int i=1;i<k;i++)s=s+a[c[i]][c[i+1]];
//cout<<"s="<<s<<endl;
if (s<m) m=s;
}
}
else
for (int i=1;i<=n;i++)
if (a[v][i]>0) p(k+1,i);
}
|
|
2
|
Флойда
|
k= 1;
for(i= 1;i<=n;i++)x[i]=a[v1][i];
// {инвариант: x[i] = МинСт(1,i,k)}
while (k!=n)
{
for(s=1;s<=n;s++){
y[s]=x[s];
for(i=1;i<=n;i++) if (y[s]>x[i]+a[i][s]) y[s]= x[i]+a[i][s];
// {y[s] = МинСт(1,s,k+1)}
for (i=1;i<=n;i++) x[s]=y[s];
}
k++;
}
|
|
3
|
Форда
|
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
|
|
4
|
Прима
|
|
|
5
|
Дейкстри
|
Алгоритм дуже простий, його реалізація представлена нижче. Алгоритм працює з вершинами як з числами. Тобто кожній вершині зіставляється число - номер представлення в масиві. Величина p - це кількість вершин. Сам алгоритм по вхідній матриці довжин дуг і заданим точкам початку і кінця шляху зберігає його в масив H. Цей масив є співвіднесеними вершинами за наступним правилом: якщо вершина v лежить на потрібному нам найкоротшому шляху, то попередня нею точка на цьому шляху записана як H[v]. Також при цьому ж умові інший масив T в значенні T[v] міститиме довжину найкоротшого шляху від точки початку до v. Також цей алгоритм оперує наступними змінними:
C - матриця довжин дуг. Її розмір C[p, p]. C[v1, v2] - містить довжину дуги від точки v1 до точки v2. Примітка: За відсутності зв'язок між цими точками відстані між ними мають бути нескінченні, а не дорівнюють нулю. Це питання розглядалося раніше.
s - початкова точка шляху в графі. Та, звідки треба знайти шлях в точку t.
t - кінцева точка шляху в графі. Це мета пошуку.
X - цей одновимірний масив служить сховищем міток, для вершин, в яких би ми вже проходили в алгоритмі.
v - поточна вершина обходу (украй динамічна змінна)
////ініціалізація і опис початкового стану змінних
Перебір значень u від 1 до p:
{
T[u] = ∞;
X[u] = 0;
}
// // триває опис НУ, окремий випадок - початкова вершина.
H[s] = 0; // немає попередній початковій вершині
T[s] = 0; // довжина шляху до неї дорівнює нулю
X[s] = 1; // і ми тут були
v = s; // встановлюємо початкову вершину, як поточну оброблювану.
Мітка M : // мітка для стрибків в коді
// // далі перебираємо усі прилеглі до поточної вершини точки, і визначаємо для них
// // мінімальна відстань, порівнюючи записане в масив T і шлях по
// // поточній вершині.
Перебір значень u від 1 до p:
{
якщо X[u]=0 і T[u] > T[v]+C[v, u] те:
{
T[u] = T[v] + C[v, u];
H[u] = v; //обов'язково запишемо попередню вершину для цього шляху
}
}
// // далі шукаємо наступну точку для обходу, грунтуючись на її відстані від
// // почала. Для наступного циклу виберемо точки, що мають найменшою шлях,
// // і цей шлях вибирається, грунтуючись на даних масиву T, де довжина
// // шляхи враховує тільки довжину зв'язків, по яких вони йдуть. Т. о.
// // перший знайдений шлях від s до t і буде найкоротшим.
l = ∞;
v = 0;
Для змінної u значення від 1 до p:
{
якщо X[u] = 0 і T[u] < l те:
{
v = u;
l = T[u];
}
}
Якщо v = 0 те:
{
exit(); //немає шляху
} інакше
Якщо v = t те:
{
exit(); //шлях знайдений, наступна вершина і кінцева
} інакше
{
X[v] = 1;
Перейти на мітку M; // новий круг
}
Якщо залишилися якісь порожні місця, рекомендую пройтися по алгоритму наново, і усвідомити його остаточно. Крок основного циклу виконує дві дії: по-перше, розставляє/оновлює знання про мінімальні шляхи сусідніх з поточною вершин, по-друге, визначає вершину для наступного кроку, яка має найкоротший шлях від початку.
Як бачите, алгоритм не зайде в пошуку далі, ніж треба, і за умови, що вершини лежать близько один до одного, результат буде отриманий дуже скоро. Проте якщо шлях "далекий", то доведеться обійти практично увесь граф. Представлений алгоритм - один з найвідоміших, простіших і дієвіших. Його також називають хвилевим алгоритмом, оскільки обхід здійснюється як би хвилями, оновлюючи прилеглі вершини.
За допомогою алгоритму Дейкстры добре шукати конкретні одноразові шляхи. Але найчастіше на ігровому полі це завдання відбувається багаторазово. Причому з різними початковими умовами. Використовувати цей же алгоритм ніхто не забороняє, але далі я пропоную вашій увазі ще один алгоритм для пошуку найкоротшого шляху. Алгоритм Флойда має схожі початкові дані, але на виході повертає двовимірний аналог масиву H[p] -> H[p][p].
|
|
|
Готуємось до олімпіади з інформатики 2013-2014 н.р. (додаток 1) |
|
|
|
|
Добавил(а) Гісь Ігор Володимирович
|
|
16.10.13 10:48 |
|
додаток 1
Готуємось до олімпіади з інформатики
2013-2014 н.р.
|
Форма проведення
|
Представлення
|
|
Теоретичний тур
|
Описати алгоритм та написати програмний код розв’язку задач
|
|
Практичний тур
|
http:://192.168.0.199/new-register?constent_id=1
зареєструватися в системі
логін: Прізвище та ім’я (англійською мовою)
пароль записати
Ввести ім’я учасник: Прізвище, ім’я, клас
Підтвердити реєстрацію
|
Задача 1. «Фотокартка» (PHOTO) – 10 балів.
Учень на новенькому кольоровому струменевому принтері учень надрукував фотографії зроблені у свій день народження. Розмір фото AxB cм. Роздільна здатність принтера R точок на дюйм (1 дюйм = 2,54 см).
Завдання
Визначити скільки пікселів містить надруковане фото?
Вхідні дані
Перший рядок містить два дійсні числа, які задають розмір фотокартки. Останній рядок містить натуральне число, яке задає роздільну здатність. Усі числа вхідного файлу за абсолютною величиною не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить шукану кількість мегапікселів на фотографії, як дійсне число з двома знаками після коми.
Приклад
|
input.txt
|
output.txt
|
|
2.54
2.54
1000
|
1.00
|
Задача 2. «Клас» – 20 балів.
На початку навчального року класний керівник між учнями класу поділила N зошитів та M олівців. Скільки учнів в класі, якщо відомо їх не менше ніж K і кожний з учнів отримав однакову сумарну кількість зошитів та олівців.
Вхідні дані
Перший рядок містить натуральні числа N, M, K. Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить знайдену кількість шкіл. Якщо результатів декілька, то вивести всі через пропуск в зростаючому порядку.
Приклад
|
input.txt
|
output.txt
|
|
92
138
25
|
46
|
Задача 3. «День народження» – 30 балів.
Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.
Вхідні дані
Перший рядок містить загальну кількість учнів, натуральне число N.
В наступних рядках кількість розданих цукерок.
Усі числа вхідного файлу не перевищують 1 000 000 000.
Вихідні дані
Єдиний рядок файлу містить кількість дівчат та хлопчиків через пропуск.
Приклад
|
input.txt
|
output.txt
|
|
5
3
1
2
4
3
|
3 2
|
Задача 4. Дорога в гімназію -40 балів.
На вимогу класного керівника учень знайшов в Інтернеті карту міста на якій він визначив і задав в декартовій системі координат координати точок на шляху від доми до гімназії, і намалював дороги між ними (див. рис). Допоможіть учню визначити хоча б довжину найкоротшої дороги від доми до школи.
Вхідні дані:
Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість точок на карті.
Наступні N рядків містять через проміжок координати Xi , Yi точок на карті. Значення координат по модулю менші 50000. Перші координати задають – координати доми, а останні – координати гімназії,,
Наступні рядків задають карту намальованих дорігпочаткова та кінцева точка.
Вихідні дані:
Єдиний рядок має містити дійсне число з трьома знаками після коми – дожину найкоротшої дороги.Якщо дороги немає вивести "no".
Приклади:
|
input.txt
|
output.txt
|
|
6
150 70
160 90
100 100
170 120
120 140
80 160
1 2
2 3
2 4
3 5
4 5
5 6
|
152.556
|
|
|
Добавил(а) Administrator
|
|
09.10.13 22:24 |
|
#include "stdafx.h"
#include "fstream"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
long a[101][101],v1,v2,n,m;
int main()
{long i,j,t,k;
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)a[i][j]=10000000;
for (k=1;k<=m;k++)
{cin>>i>>j>>t;
a[i][j]=t;a[j][i]=t;
}
cin>>v1>>v2;
/*for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<v1<<" "<<v2<<endl;
*/
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
/*for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
*/
//cout<<v1<<" "<<v2<<endl;
if (a[v1][v2]>=10000000)cout<<-1<<endl;
else cout<<a[v1][v2]<<endl;
return 0;
}
|
program poisk_min;
{$APPTYPE CONSOLE}
var a:array[1..100,1..100] of integer;
nmin,min,i,j,k,l,n,s:integer;
c:array [1..100]of integer;
f1,f2:text;
function f(nn,vv:integer):boolean;
var pr:boolean;
i:integer;
begin
pr:=true;
for i:=1 to nn do
if vv=c[i] then pr:=false;
f:=pr;
end;
begin
assign(f1,'graph.dat');reset(f1);
assign(f2,'graph.sol');rewrite(f2);
readln(f1,n);
for i:=1 to n do
for j:=1 to n do
read(f1,a[i,j]);
close(f1);
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[k,j]<a[i,j] then
a[i,j]:=a[i,k]+a[k,j];
for i:=1 to n do begin
for j:=1 to n do write(f2,a[i,j],' ' );
writeln(f2);
end;
close(f2);
end.
|
|
|
|