Сайт підготовки до олімпіади з інформатики

програмування в С++

Школа олімпійського резерву з інформатики
Робота з масивом (Паскаль) 14_10_2011 PDF Печать E-mail
Добавил(а) Administrator   
14.10.11 11:59

Робота з масивами

Операція з масивом

Лінійний масив

Прямокутна таблиця

Опис

Var a:array[1..100] of integer;

i, n:integer;//індекс, кількість елементів

Var a:array[1..100,1..100] of integer;

i, n,m:integer;//індекс, кількість рядків, стовпців

Введення

readln(n);

for i:=1 to n do read(a[i]);

readln(n);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

Виведення

for i:=1 to n do write(a[i],' ');

for i:=1 to n do begin

for j:=1 to m do

write(a[i,j],' ');

writeln;

end;

Сумування

s=0;

for i:=1 to n do s:=s+a[i];

s=0;

for i:=1 to n do

for j:=1 to m do

s:=s+a[i,j];

Пошук

readln(k);

for i:=1 to n do if  a[i]=k then writeln(i);

readln(k);

for i:=1 to n do

for j:=1 to m do

if  a[i,j]=k then

writeln(i,' ',j);

Пошук максимального

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;mmax:=1;

for  i:=1 to n do

for j:=1 to m do

if  a[i,j]>max then begin max:=a[i,j];nmax:=i;mmax:=j;

end;

Сортування

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;

 

Стирання

n:=n-1;

for  i:=k to n do a[i]:=a[i+1];

 

 

Вставка

n:=n+1;

for  i:=n downto k+1 do

a[i]:=a[i-1];

 

 


 
Задача 5. Task5 PDF Печать E-mail
Добавил(а) Гісь Ігор Володимирович   
03.10.12 09:34

Задача 5. Task5

На аркуші намальовано N прямокутних трикутників. Визначили координати вершин трикутника і записали по два числа в кожному рядку але в хаотичному порядку. Визначити яку кількість прямокутних трикутників було побудовано на аркуші.

Вхідні дані. Вхідний текстовий файл Task5.in містить в першому рядку число N (3<=N<=1000) , далі слідують 3*N рядків, у кожному по 2 цілих чисел розділених пропусками – координати вершини трикутника (|x,y|<=2147483647).

Вихідні дані. Вихідний текстовий файл Task5.out містить один рядок з цілим числом k - загальну кількість трикутників , або число 0, якщо учень побудував хоча б один трикутник не прямокутний.

Приклади файлів

Task5.in

Task5.out

Task5.in

Task5.out

2

0 0

0 0

0 3

0 -3

4 0

- 4 0

2

2

0 0

0 0

0 3

0 -3

4 0

- 4 1

0

Последнее обновление 03.10.12 17:54
 
Готуємось до олімпіади (додаток 2) PDF Печать E-mail
Добавил(а) Гісь Ігор Володимирович   
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 елементів, тобто весь набір даних можна розмістити в статичній пам'яті.

Одним з найбільш ефективних алгоритмів пошуку найкоротшого шляху є алгоритм хвилі. Хвильовий алгоритм полягає в наступному:

  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, шукая серед сусідів даної клітинки таку, щоб номер ітерації хвилі у неї був найменшим.

1. Якось, пам'ятається, ще в грі "HЛО-1", проскочило побажання до тих, хто хоче стати добрим програмістом, підвищувати, підвищувати і ще раз підвищувати свій освітній рівень. На що із сторінок одного дуже поважаного видання виступив читач з наступною думкою (дослівно не пам'ятаю): "Я людина темна, але код програми - що треба. Значить, я вже добрий програміст". Дана стаття є спроба розвіяти цю глибоку помилку. В першу чергу вона адресована тим, хто займається створенням ігор і тим, кому не дає спокою думка: "А що там всередині?" Для її розуміння достатньо знання що таке двомірні масиви.

Побудова найкоротшого маршруту

Задача знаходження найкоротшого шляху між якимись точками А і В на ігровому полі з довільно розташованими перешкодами характерна, в першу чергу, для популярних сьогодні тактичних і стратегічних ігор. Як підзадача, вона може виникати практично в будь-яких іграх - RPG, квестaх, логічних (типовий приклад "Color Lines").

Чому треба шукати найкоротший маршрут? В деяких іграх, наприклад "HЛО-2", "Laser Squad", від довжини маршруту залежить кількість витрачених одиниць часу - чим оптимaльніше буде знайдений шлях, тим швидше воїн дістанеться до мети. А, наприклад, в "Color Lines" довжина маршруту не обумовлена правилами, має значення лише сам факт можливості або неможливості переміщення кулі. Але і в цій грі приємніше виглядатиме, якщо кулька відразу попрямує куди треба, а загадково не дефілюватиме по всій ігровій дошці.

Рішення цієї задачі прийшло до нас з такої далекої, здавалося б, від ігор області як електроніка. А саме - розводка друкарської плати (всі знають, що це таке? ;).

Існує велика кількість трасувальників (програм для розводки плати), заснованих на не меншій кількості різних методів, що займаються з'єднанням двох контактів єдиним провідником. Але ми розглянемо тільки один з них, найпростіший (а значить, найнадійніший і найпопулярніший) - хвильовий трасувальник.

Поставимо перед хвильовим трасувальником задачу в термінах що розробляється нами гри:
Є ігрове поле Р(MxN),де M і N, відповідно, розмір поля по вертикалі і горизонталі. Просто, це масив розмірністю MxN. Кожна клітка ігрового поля (елемент масиву) може мати багато властивостей на ваш розсуд, але для нас важливо тільки одне - її прохідність (або непрохідність). Яким чином вона визначається - це вже ваша справа. Далі: є деяка стартова точка, де знаходиться герой вашої гри, і кінцева точка, куди йому необхідно потрапити. Умовимося поки, що ходити він може тільки по чотирьох напрямах (чого вимагає від нас класичний хвильовий метод) - вправо, вліво, вперед, назад. Hеобхідно перемістити героя від місця старту до фінішу за якнайменшу кількість ходів, якщо таке переміщення взагалі можливо.

  1. Спочатку необхідно створити робочий масив R(MxN), рівний за розміром масиву ігрового поля P(MxN).
  2. Кожному елементу робочого масиву 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.
  3. Етап "Розповсюдження хвилі". Вводимо змінну Ni - лічильник ітерацій (повторів) і надаємо їй початкове значення 0.
  4. Вводимо константу Nк, котору встановлюємо рівній максимально можливому числу ітерацій (Nk<253).
  5. По рядках проглядаємо робочий масив R (оргaнізуємо два вкладених циклa: по індексу масиву i від 1 до М, по індексу масиву j від 1 до N).
  6. Якщо 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).
  7. По завершенню рядкового перегляду всього масиву збільшуємо Ni на 1.
  8. Якщо Ni>Nк,то пошук маршруту визнається невдалим. Вихід з програми.
  9. Переходимо до пункту 5.
  10. Етап побудови маршруту переміщення. Привласнюємо змінним Х і У значення координат стартової позиції.
  11. Навколо позиції R(Х,Y) шукаємо елемент з якнайменшим значенням (т.т. для цього проглядаємо R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координати цього елемента заносимо в змінні X1 і Y1.
  12. Робимо переміщення об'єкту по ігровому полю з позиції [X,Y] в позицію [X1,Y1]. (За бажанням, ви можете заздалегідь заносити координати X1,Y1 в деякий масив, і, тільки закінчивши побудову всього маршруту, зайнятися періміщення героя на екрані).
  13. Якщо R(X1,Y1)=0,то переходимо до пункту 15.
  14. Виконуємо привласнення X:=X1,Y:=Y1. Переходимо до пункту 11.
  15. Все !!!

#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;

}
 
16_01_2012 Системи числення (повторення) PDF Печать E-mail
Добавил(а) Гісь Ігор Володимирович   
16.01.13 12:45

Переведення чисел з однієї системи числення в іншу


Десяткова

Двійкова

Відмітка про виконання

0

0

2

10

5

101

10

1010

32

100000

98

1100010

1024

1000000000

6783

1101001111111

98321

11000000000010001

2000000

111101000010010000000

1073741824

1000000000000000000000000000000

5000000000

100101010000001011111001000000000

Переведення чисел в різних системах числення

На приклад, якщо потрібно перемножити числа 101 і 1001 в двійковій системі, то він спочатку ці числа переводить в десяткову систему таким чином :

(101)2=1*22+0*21+1*20=4+0+1=5

(1001)2=1*23+0*22+0*21+1*20=8+0+0+1=9

Після чого множення чисел 5 і 9 Вася з легкістю виконує в десятковій системі числення і отримує число 45. Далі виконує переведення з десяткової системи числення в двійкову. Для цього потрібно ділити число 45 на 2 ( порядок системи числення ), запам'ятовує залишки від ділення, до тих пір поки в результаті не залишиться число 0:

45

2

44

22

2

1

22

11

2

0

10

5

2

1

4

2

2

1

0

1

Відповідь складається з одержаних залишків від ділення шляхом їх запису в зворотному  порядку . Таким чином одержуємо результат : (101101)2.

1. Задача. Перевести число з  будь-якої системи числення в будь-яку іншу.

Протестувати самостійно

2. Задача  BINARY

Ім'я вхідного файлу:   BINARY.DAT

Ім'я вихідного файлу: BINARY.SOL

Максимальний час роботи на одному тесті: 3с

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число 1910 = 1×24+0×23+0×22+1×21+1×20 в двійковій  системі запишеться як 100112). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри буде число 1×24+1×23+1×22+0×21+0×20 = 28.

Оскільки придумана гра з числами все більше займає уяву учня, відволікаючи тим самим його від навчання і підготовки до олімпіади, Вас просять написати програму, яка б допомогла Дімі отримувати результат гри без важких ручних обчислень.

Вхідний файл містить одне ціле число N (0£N£32767).

Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне результату гри.

Приклад

BINARY.DAT

BINARY.SOL

19

28

3. Задача  Нулі

Ім'я вхідного файлу:   ZEROS.DAT

Ім'я вихідного файлу: ZEROS.SOL

Максимальний час роботи на одному тесті: 5с

Необхідно написати програму для знаходження кількості N-значних чисел в системі числення за основою K, таких що їхній запис не буде містити двох нулів підряд.

Формат вхідних даних.

Єдиний рядок вхідного файлу ZEROS.DAT містить два натуральних числа N та K, 2 <= K <= 10, N + K <= 18.

Формат вихідних даних.

Єдиний рядок вихідного файлу ZEROS.SOL повинен містити одне натуральне число - розв'язок задачі.

Приклад.

ZEROS.DAT:

4 2

ZEROS.SOL:

5
 
Завдання IІ етапу Всеукраїнської учнівської олімпіади з інформатики 2014-2015 н.р. PDF Печать E-mail
Добавил(а) Administrator   
04.12.14 09:17

Завдання IІ етапу Всеукраїнської учнівської олімпіади

з інформатики 2014-2015 н.р.

Задача 1. «Код» (25 балів)

Ім’я файлу програми: kod.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 1с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  4  ділянки  маршруту.  Кожну з ділянок  можна  перебороти або літаком, або потягом, або  автомобілем. Кожним видом транспорту можна скористатися двічі. За введеним чотирицифровим числом, яке задає код подолання маршруту, потрібно  вивести число, яке задає код кількості використання транспорту, яким подолали маршрут..

«Ігрове поле»  абстрактне, по вертикалі в нас види транспорту, а по горизонталі - номер прохідної ділянки маршруту Матриця тепер прямокутна 3х4 (три види транспорту і 4 ділянки  шляху) .

На малюнку представлене положення покажчиків і фішок до моменту виведення  першої і другої послідовності видів транспорту на  маршруті.

Вхідні дані. Вхідний текстовий файл містить один рядок з чотирицифровим числом.

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з кодом, яке визначає транспорт.

Приклади файлів

input.txt

output.txt

1122

220

1123

211

Задача 2. «Варіанти» (25 балів)

Ім’я файлу програми: variant.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 1с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянок  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …).  Кожним з видів транспорту можна скористуватися Kразів. Потрібно визначити кількість способів, якими можна проїхати маршрут.

Вхідні дані. Вхідний текстовий файл містить один рядок з трьома цілини числами N,M,K (1≤M,K,N≤50)).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає кількість варіантів проїзду.

Приклад файлів

input.txt

output.txt

3 3 1

6

Задача 3. «Транспорт» (25 балів)

Ім’я файлу програми: transport.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txtМаксимальний час роботи на одному тесті: 1с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянки  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …).  Кожним з видів транспорту можна скористуватися AM разів і при цьому вартість одного проїзду цим видом транспорту BM, де M номер виду транспорту. Потрібно визначити мінімальну вартість витрат на подолання шляху.

Вхідні дані. Вхідний текстовий файл містить три рядки. В першому рядку два цілих числа N,M (1≤M≤N≤1000000)). Два наступних рядки місять по M цілих чисел, які задають кількість можливих варіантів проїзду і вартість проїзду (0≤2AM,BM ≤2147483647).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду. Якщо проїзд неможливий то вивести “no”.

Приклад файлів

input.txt

output.txt

3 2

2 2

1 2

4

Задача 4. «Оптимальний маршрут» (25 балів)

Ім’я файлу програми: optimal.*

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 5с

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянки  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …). Кожним з видів транспорту можна скористатися не більше K разів.  Вартість проїзду для кожної ділянки певним видом транспорту задано в таблиці TNM, де N – номер ділянки, M - номер виду транспорту. Потрібно визначити мінімальну вартість витрат на подолання шляху.

Вхідні дані. Вхідний текстовий файл містить три рядки. В першому рядку три цілих числа N, M, K (1≤N, M, K≤1000)). В наступних M рядках містяться по N цілих чисел, які задають вартість проїзду (0≤TMN ≤2147483647).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду.

Приклад файлів

input.txt

output.txt

2 2 1

2 2

1 2

3
 
Другие статьи...


Страница 24 из 43

Главное меню

Статистика

Пользователей : 269
Статей : 225
Просмотрено статей : 127797

Вход/Регистрация

Нет