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

Ремонт кораблів (DOCKS)

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

Скласти програму, що визначає порядок постановки кораблів у док, при якій сумарний час, протягом якого кораблі чекають своєї черги, мінімальний.

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

У першому рядку файлу міститься число N – кількість кораблів, що прийшли на ремонт (1£N£10000). В наступних N рядках – пари чисел – номер судна та через пропуск – час ремонту (натуральні числа, не більші 10000).

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

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

Між числами має бути по одному проміжку. Наприкінці рядка проміжок не ставте.

Приклад вхідних та вихідних даних:

Працівники (STAFF)

(XVІІ Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)

На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.

Існують правила, за якими визначається, чи можна обробляти деталь на певному верстаті.

$11)      Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.

$12)      У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.

Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.

Напишіть програму STAFF, яка за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.

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

Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.

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

Єдиний рядок вихідного файлу STAFF.RES має містити ціле число – максимальну можливу кількість працівників заводу.

Приклад вхідних та вихідних даних:

Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий  має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станку B – деталі 2 та 4. Інших варіантів послідовності обробки немає.

Затори на дорогах (JAMMING)

Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги).

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

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

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

Вхідний файл містить єдине число S (1£S£10000) – задана відстань.

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

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

Достеменно відомо, що кількість цифр у відповіді не перевищує 700.

Приклад вхідних та вихідних даних:

Кубики (CUBES)

(XV Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)

Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.

Напишіть програму CUBES, що отримує на вхід фронтальну та праву проекції фігури та визначає мінімальну та максимальну кількість кубиків, яку можна було б використати для побудови фігури із заданими проекціями.

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

У першому рядку вхідного файлу CUBES.DAT знаходиться три числа N, M та К, що задають розміри проекцій (1≤ N, M, K ≤100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені прогалиною. Для фронтальної проекції таких чисел буде M, а для правої — K. 0 означає вільну клітинку проекції, 1 — заповнену.

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

У єдиному рядку вихідного файлу CUBES.SOL повинно знаходитися два числа: мінімальна та максимальна кількість кубиків, які можна було б використати для побудови фігури із заданими проекціями.

Приклад вхідних та вихідних даних:

1 тур - з 20.10 по 26.10.2014

точка входу для відправлення розв'язків http://176.31.28.231/cgi-bin/new-client?contest_id=15

Задача 1. Особливі числа (20 балів)

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

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

Ліміт часу: 1с.

Петрик любить створювати і досліджувати числові послідовності. Одного разу він досліджував послідовність 1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 12345678910, 1234567891011, .... і помітив, що деякі елементи цієї послідовності діляться на 3. Такі числа він назвав «особливими».

Допоможіть Петрику підрахувати, скільки елементів цієї послідовності серед перших n діляться на 3.

Вхідні дані.

Натуральне число n (1≤n≤4000000 ).

Вихідні дані.

Вивести одне знайдене число.

Приклад.

Задача 2. Суми в ромбі (100 балів)

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

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

Ліміт часу: 2с.

Вам задано таблицю N*M, у кожній клітинці якої написане деяке число. Ромбом з центром в клітинці (x₀,y₀) і розміром k будемо називати набір клітинок, координати (x,y) яких задовольняють наступну умову: |x-x₀|+|y-y₀|<k.

На малюнку в таблиці 5*6 зображено ромб з центром в клітинці (3,2) і розміром 2.

У заданій таблиці знайдіть ромб з найбільшою можливою сумою чисел.

Формат вхідного файлу.

Перший рядок вхідного файлу містить два цілих числа N і M(1≤N,M≤500). НаступніNрядків містять Mчисел. Числа в рядках розділені пробілами. Числа лежать в межах від -10⁵ до 10⁵.

Формат вихідного файлу.

Виведіть одне ціле число – суму чисел в знайденому ромбі.

Приклади

№1. ЗАДАЧА «МІЖНАРОДНА КОНФЕРЕНЦІЯ»(100 БАЛІВ)

Вас найняли для того, щоб визначити місця дипломатів за столом обговорень міжнародної конференції. На конференцію запрошено по одному дипломату з N різних країн світу. Ко­жен дипломат знає від однієї до п'яти мов. Дип­ломати, які не знають спільної мови, не можуть розмовляти один з одним. До того ж, деякі краї­ни проголосили, що не будуть підтримувати дипломатичних стосунків з деякими іншими, тобто представники цих країн не будуть роз­мовляти один з одним. Ваше завдання полягає в розробці програми DIPLOMAT.pas/.c/.cpp, що визначає місця за столом для дипломатів таким чином, щоб кожен мав можливість розмовляти з обо­ма своїми сусідами, які сидять ліворуч та пра­воруч від нього.

Стіл, що використовується, — круглий і розрахований на N персон (N£20). Дипломат може спілкуватися з дипломатом, який сидить ліво­руч, однією мовою, а з дипломатом, що сидить праворуч, — іншою.

Технічні вимоги:

Вхідний файл: DIPLOMAT. DAT.

Вихідний файл: DIPLOMAT. SOL.

    Програма: diplomat.pas/.c/.cpp

Формат вхідних даних. У першому рядку текстового файла DIPLOMAT. DAT — число N. Далі — N рядків, по одному рядку на диплома­та. Кожен рядок — послідовність слів. Сусідні слова відокремлені пробілом. Кожне слово — це послідовність великих латинських літер. Перше слово — код країни — складається з трьох літер. Друге слово має довжину від 1 до 5 літер і являє собою перелік мов, якими може спілкуватися дипломат. Кожна мова позначена однією літерою. Далі — список з не більш ніж N трилітерних слів — кодів країн, з якими уряд дипломата підтримує дипломатичні стосунки.

Формат вихідних даних. До файла DIPLOMAT. SOL треба вивести список дипломатів у порядку розміщення за столом (по одному дипломату в рядку). Кожен рядок складається з трьох слів: перше — код мови, якою дипломат може спілкуватися з сусідом ліворуч, друге — код країни дипломата, третє — код мови для спілкування з сусідом праворуч. Мож­ливе існування кількох розв'язків. Вам по­трібно знайти один. Якщо розв'язку не існує, то ваша програма має видати таке повідомлен­ня: «NO  SOLUTION EXIST»

Приклад:

Подарунок (uoi2011)

У королівстві Олімпія знаходиться N міст та M двосторонніх доріг, кожна з яких з’єднує рівно два міста. Між двома містами може бути більше однієї дороги. Усі дороги постійно грабуються розбійниками. Останнім часом розбійникам набридло витрачати сили на пограбування і вони звернулися до могутнього і справедливого короля Олімпії з комерційною пропозицією. За цією пропозицією король повинен надіслати розбійникам подарунок, що складається з золотих та срібних монет. У відповідь на люб’язність короля розбійники припинять грабувати певні дороги. Для кожної з доріг встановлена мінімальна кількість золотих і мінімальна кількість срібних монет у подарунку, щоб її пограбування скінчились. Тобто, якщо у подарунку K золотих та L срібних монет, то припиняється пограбування усіх доріг, для яких необхідна кількість золотих монет менша або рівна K, а  кількість срібних монет менша або рівна L.

В скарбниці короля немає жодної золотої або срібної монети, але є Олімпійські Тугрики. Ціна однієї золотої монети в тугриках – G, а срібної – S. Король дуже хоче, щоб після відправлення подарунку розбійникам між кожною парою міст існував хоча б один безпечний шлях, який, можливо, проходить через інші міста.

Завдання Напишіть програму gift, яка за даними про міста і дороги у королівстві та цінами монет, знайде мінімальну кількість тугриків, яку потрібно витратити королю для того, щоб отримати безпечні шляхи між кожною парою міст у королівстві.

Вхідні дані Перший рядок вхідного файлу gift.dat містить два цілих числа N і М (2≤N≤200, 1≤М≤50 000) – кількість міст і кількість доріг у королівстві Олімпія.  Другий рядок містить числа G і S (1≤G, S≤10⁹). Наступні М рядків містять інформацію про дороги та опис пропозиції розбійників. У і+2-му рядку вхідного файлу розташовано 4 натуральних числа, перші два з яких – номери міст, що з’єднані і-ою дорогою (міста нумеруються від 1 до N), наступні два – мінімальна кількість золотих і мінімальна кількість срібних монет, що треба вислати розбійникам в подарунку, щоб і-ту дорогу припинили грабувати. Обидва числа не перевищують 10⁹.

Вихідні дані Єдиний рядок вихідного файлу gift.sol має містити одне ціле число – мінімальну кількість тугриків, що потрібно витратити королю на купівлю золотих та срібних монет, щоб досягнути своєї мети, або -1, у випадку, якщо жодна кількість тугриків не допоможе.

Оцінювання Щонайменше у 30% тестів N не буде перевищувати 30 та M не буде перевищувати 150. Щонайменше у 70% тестів M не буде перевищувати 4000.

Приклад вхідних та вихідних даних

Пояснення: достатньо покласти у подарунок розбійникам 5 золотих та 20 срібних монет і вони відкриють другу та третю дороги. На купівлю цих монет король витратить 30 тугриків.

Музей (uoi2010)

У столиці країни Олімпія збудований Музей Олімпійської Слави, де виставлено нагороди школярів країни з різних предметних олімпіад. Будівля музею складається з виставкових залів, з’єднаних коридорами. Коридор сполучає рівно два зали. Відомо, що кожного залу музею можна дістатися з будь-якого іншого залу, прямуючи коридорами. Також відомо, що кількість коридорів дорівнює кількості залів.

                Вночі музей патрулюється охоронцями. Кількість охоронців дорівнює кількості залів, та у кожен момент часу охоронець доглядає за своїм залом. Кожну годину згідно плану патрулювання деякі з охоронців переходять в іншу залу, а інші залишаються на місті. План патрулювання відповідає таким вимогам:

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

2. Після переходів охоронців, у кожній залі повинен опинитися рівно один охоронець.

3. Кожну годину застосовується один і той самий план патрулювання.

Наприклад, на рисунку наведений один з можливих планів патрулювання. Згідно йому кожну годину охоронець, що знаходиться у залі 1, переходить до залу 2; охоронець з залу 2 – до залу 3; з залу 3 – до залу 1; охоронці з залів 4 та 5 міняються місцями, а охоронець з залу 6 всю ніч проводить у цьому залі.

Завдання Напишіть програму MUSEUM, яка за інформацією про кількість залів музею і їх сполучення коридорами знайде кількість різних планів патрулювання музею за модулем P.

Вхідні дані Перший рядок вхідного файлу MUSEUM.DAT містить пару цілих чисел N (3≤N≤50 000) – кількість залів у музеї, та P (2≤P≤10 000). Наступні N рядків містять пари цілих чисел від 1 до N – номери залів, що з’єднані коридором.

Вихідні дані Єдиний рядок вихідного файлу MUSEUM.SOL має містити ціле число – кількість планів патрулювання музею, за модулем P (остачу від ділення шуканої кількості на P).

Оцінювання Щонайменше в 20% тестів буде виконуватись додаткове обмеження N≤20.

Щонайменше в 60% тестів буде виконуватись додаткове обмеження N≤1000.

Приклад вхідних та вихідних даних

Існує 20 різних планів патрулювання: (1, 2, 3, 4, 5, 6), (1, 2, 3, 5, 4, 6), (1, 2, 3, 6, 5, 4), (1, 2, 4, 3, 5, 6), (1, 3, 2, 4, 5, 6), (1, 3, 2, 5, 4, 6), (1, 3, 2, 6, 5, 4), (2, 1, 3, 4, 5, 6), (2, 1, 3, 5, 4, 6), (2, 1, 3, 6, 5, 4), (2, 1, 4, 3, 5, 6), (2, 3, 1, 4, 5, 6), (2, 3, 1, 5, 4, 6), (2, 3, 1, 6, 5, 4), (3, 1, 2, 4, 5, 6), (3, 1, 2, 5, 4, 6), (3, 1, 2, 6, 5, 4), (3, 2, 1, 4, 5, 6), (3, 2, 1, 5, 4, 6), (3, 2, 1, 6, 5, 4). На рисунку з умови зображено план (2, 3, 1, 5, 4, 6).

Торговець (uoi2009)

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

В країні, де живе торговець, є N міст, які пронумеровані від 1 до N. Рідне місто торговця має номер 1, а столиця – номер N. Щоб дістатися столиці, де торговець може продати товар, йому потрібно проїхати певним маршрутом через інші міста. Між деякими парами міст існують дороги, проїзд по яким коштує певної кількості золотих. У кожному місті стягується податок за провезення кожного з видів товару, заданий у відсотках від вартості провезеного через місто товару. Відомо, що виїхавши з будь-якого міста, торговець не може до нього повернутися. Будь-які два міста з’єднані не більше ніж однією дорогою.

Задача торговця отримати найбільший прибуток – різницю отриманих у столиці коштів за проданий товар та витрат за подорож до столиці. Він не зобов’язаний брати з собою весь свій товар. Торговець завжди має достатньо золотих для виплати податків, та не може розрахуватися товаром, який він везе до столиці. Усі дороги ведуть лише в одному напрямку.

Завдання

Напишіть програму SALESMAN, що за інформацією про кількість одиниць ваги різних видів товару у торговця, ціни на ці товари у столиці, податки у містах, дороги між містами та вартість проїзду  по цих дорогах встановить максимальний прибуток, що може отримати торговець від реалізації товару.

Вхідні дані

Перший рядок вхідного файлу SALESMAN.DAT містить два цілих числа N (2≤N≤500) та M (M³1) – кількість міст та доріг між ними. Другий рядок містить три цілих невід’ємних числа, що відповідають кількостям одиниць ваги алмазів, яблук та шовку, що належать торговцю. Третій рядок містить три цілих невід’ємних числа – вартість одиниці ваги алмазів, яблук та шовку відповідно. Наступні рядки з 4-го по N+1 містять по три цілих числа від 0 до 100 включно, що відповідають відсоткам від вартості алмазів, яблук та шовку, що стягується у відповідно у містах від 2 до N-1 у якості податку. У списку міст не враховані рідне місто торговця 1 та столиця N, як такі, що не стягують податок. Наступні M рядків містять по три цілих невід’ємних числа, перші два з яких від 1 до N задають пару міст, між якими прокладено дорогу, а третє – вартість проїзду цією дорогою. Дороги ведуть в напрямку від міста, яке вказано першим, до того, яке вказано другим. Кількості одиниць ваги кожного з видів товару у торговця, вартості товарів та ціни проїзду по дорогам не перевищують 100.

Вихідні дані

Єдиний рядок вихідного файлу SALESMAN.SOL має містити одне число – точне значення знайденого максимального прибутку від поїздки до столиці. Відповідь завжди повинна містити рівно два знаки після крапки. У випадках коли торговець не може отримати прибутку чи дістатися столиці існуючими дорогами, потрібно вивести 0.00

Приклад вхідних та вихідних даних

Готуємось до олімпіади  з інформатики- 2

«Класичні алгоритми для роботи з масивами та рядками, їх реалізація у вигляді програм»

1.                   Перевірити, чи є одномірний числовий масив упорядкованим за зростанням.

2.                   Дано натуральна таблиця A[10]. В таблицю B[] записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2

3.                   Вивести числовий ряд Фібоначі (a[i]=a[i-1]+a[i-2];)

Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від'ємними числами, а дівчаток — додатними у вигляді цілих значень α1,α2,…, αN ? Окрім того, у всіх дівчаток на голівках зав'язані бантики заввишки 10 см, а висота паркану H см.

4.                   . «День народження»  – 30 балів.

Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.

Вхідні дані

Перший рядок містить загальну кількість учнів, натуральне число N.

В наступних рядках кількість розданих цукерок.

Усі числа вхідного файлу не перевищують 1 000 000 000.

Вихідні дані

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

Приклад

5.                   Новорічна гра

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

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

На новорічному святі Дід Мороз вирішив провести цікаву гру для двох найвеселіших дітлахів.

У мішку Діда Мороза знаходяться не подарунки, а N карток, на кожній із яких написано деяке ціле число Ai. У гру грають двоє дітей. На початку гри обидва гравці навмання витягують по одній картці з мішка Діда Мороза. Учасник, який вийняв картку з більшим числом, отримує від Діда Мороза цукерки, до того ж кількість отриманих цукерок дорівнює різниці чисел, написаних на картках, що вийняли діти.

Наприклад, Сергій та Роман грають у цю гру. Сергій вийняв картку з числом 7, а Роман з числом 3. Після цього Сергій бере собі 4 (7 - 3 = 4) цукерки.

Дід Мороз стомився і не може визначити, скільки цукерок йому слід купити на свято. Допоможіть йому. Його цікавить максимальна кількість цукерок, яку може отримати дитина в результаті гри.  

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N(2 ≤ N ≤ 1000), яке представляє кількість карток.

Другий рядок вхідного файлу містить рівно N цілих чисел Ai(1 ≤ Ai ≤ 32767). Числа у рядку розділені одиночними пробілами. Ai – число, написане на і-й картці.

Формат вихідних даних: єдиний рядок вихідного файлу має містити одне число – максимальна кількість цукерок, яку може отримати дитина за гру.

Приклад вхідних і вихідних даних:

Готуємось до олімпіади  з інформатики- 1

$11.       За введеним двоцифровим числом вивести суму його цифр.

$12.      Вивести трицифрове число в зворотному  порядку.

$13.       Обчислити добуток цифр чотирицифрового числа.

$14.      За введеною датою народження (три  числа) визначити кількість прожитих днів.

$15.       Задача 1. «Число» (25 балів)

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

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

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

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

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

Інструкція

1.     Попросіть загадати три цифри (обов'язково цифри, а не числа).

2.     Потім попросіть його помножити першу загадану цифру на 2 і додати до результату, що вийшов 3. Потім помножити це число на 5.

3.     Потім до вже отриманого числа додав другу загадану цифру і помножити суму на 10.

4.     До нового числа, що вийшло додайте третю задуману цифру.

5.     Попросіть його назвати число, що вийшло.

6.     Зробіть вигляд, що ви задумалися (тільки довго не думайте). Тим часом, відніміть від вимовленого вголос числа 150. Вийде, що перша, друга і третя цифри результату є задуманими цифрами гравця.

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

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

6. Задача. Годинник

Старовинний годинник б'є щопівгодини. Причому на початку кожної години він б'є стільки раз, скільки годин (по 1 разу – в час ночі і в час дня, по 2 рази – в дві години ночі та в дві години дня і так далі, опівночі і опівдні вони б'ють, відповідно, по 12 разів). І ще 1 раз вони б'ють в середині кожної години.

Даний проміжок часу (відомо, що пройшло строго менше 24 годин). Напишіть програму, що визначає, скільки ударів зробив годинник за цей час.

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

У першому рядку записаний початковий момент часу, в другому рядку — кінцевий. Моменти часу задаються двома цілими числами, що розділяються пропуском. Перше число задає години (від 0 до 23), друге - хвилини (від 1 до 59, при цьому воно не дорівнює 30).

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

У вихідний файл виведіть одне число — скільки ударів зробив годинник за цей відрізок часу.

Приклади

Числа Фібоначі

Хтось вмістив пару новонароджених кроликів в деякому місці, обгородженому з усіх боків стіною. Скільки пар кроликів народиться при цьому протягом року, якщо природа кроликів така, що кожний місяць, починаючи з третього місяця після свого народження, пара кроликів породжує іншу пару?

Input format

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

Output format

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

Examples

4

1
1
2
3

5

1
1
2
3
5

#include "fstream"
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
int main()
{
int n;
unsigned long long f1,f2,f3;
cin>>n;
if(n==1)cout<<1<<endl;else
if(n==2)cout<<1<<endl<<1<<endl;else
{f1=1;f2=1;
cout<<f1<<endl<<f2<<endl;
for (int i=3;i<=n;i++)
{f3=f1+f2;
f1=f2;
f2=f3;
cout<<f3<<endl;
}
}

return 0;}

Задача Прості числа

Вивести кількість простих чисел на проміжку натуральних чисел до N

Input format

Єдиний рядок містить число N.

Output format

Єдиний рядок файлу містить кількість простих чисел.

Examples

10

4

#include "fstream"
#include "math.h"
using namespace std;
float n,p,k;
int i,l;
int main()
{
unsigned long long a[100];

ifstream cin("input.txt");
ofstream cout("output.txt");
cin>>n;
        for (l=2;l<=n;l++)
        {
                p=0;
        for (i=2;i<=int(sqrt(float(l)));i++)
                if (l%i==0) p=1;
                if(p==0)
                {
                        k++;
                }
        }
cout<<k<<endl;
return 0;
}

24.09.2014

1. Етапи розв’язування задач

Задача 1. Перелити рідини з одного стакана в інший (Переставити змінні місцями).

2. Алгоритм: властивості, способи подання, примітиви, псевдокод.

3. Теорія розв’язку задач (Дж. Поліа, 1945)

Задача 2. Людина А хоче визначити вік трьох дітей людини В. Відомо що добуток віку рівний 36 та сума віку. А сказав, що даних недостатньо. В повідомив, що старша дитина грає на піаніно. Тоді А назвав вік дітей.

Задача 3.

 A,B,C, D зробили прогнози:

- A – сказав, що переможе В

- B – сказав, що D буде останнім;

- C - сказав, що учасник А буде третім;

- D - сказав, що збудеться передбачення А.

Один прогноз вірний і це прогноз перемржця.

Задача 4.

1. Знайдіть алгоритм розв’язку задачі і дайте відповідь на запитання.

а) Для заданого додатного числа n знайдіть таку комбінацію цілих додатніх чисел, добуток яких максимальний серед всіх можливих комбінацій цілих додатних чисел, сума яких рівна n. Наприклад, якщо n рівне 4, то шуканий список є (2,2), так як 2*2 більше, ніж 1*1*1*1, 2*1*1 і 3*1. Для n, рівного 5, шукана комбінація буде (2, 3).

б) Яка шукана комбінація для n=2001?

в) Поясніть, як вам вдалось розв’язати задачу.

4. Алгоритмічні структури.

- слідування - послідовний ;

- розгалуження – умовний;

- цикл – повторення;

- підпрограми – під задачі;

- послідовного пошук;

поки (шукане значення ≠ значення яке перевіряється і є ще не перевірені елементи)  вибрати наступний елемент, який перевіряється;

якщо шукане значення = перевіреному значенню то Шуканий елемент знайдено  інакше Шуканий елемент  не знайдено;

- рекурсивний пошук;

Вибрати сер. елемент  m=(L+R)/2;

                    якщо  шуканий елемент < за середній елемент  то  продовжити пошук(L,m-1) в лівій частині інакше  продовжити пошук(m+1, R) в правій частині

5. Ефективність і правильність алгоритму k, n^k. nⁿ, n!, log_k n.

6. Мови програмування

7. Лексеми

- алфавіт

- службові слова

- ідентифікатор

- тип даних

- синтаксис

- семантика

- присвоєння

- керуючі оператори

- процедури та функції

8. Середовище реалізації

- трансляція

- компіляція

- інтерпретація

9. Порядок роботи

1. Встановити Visual С++ Express www.microsoft.com/express/vc/.
2. Запустити середовище Головне меню\Програми\Visual C++ 9.0 Express Edition\Microsoft Visual C++ 2008 Express Edition.
3. Створити новий пустий проект «Консольний додаток Win32», який зберігати в власну папку(*.sln).
4. Створити файл вихідного коду (*.cpp)
5. Перевірити програми з додатку.

Зауваження

Для компіляції та виконання натискуйте клавішу Ctrl F5

// Під'єднання модулів

#include <iostream>//організація введення-виведення в мові програмування C++

#include <math.h>//виконання простих математичних операцій

using namespace std;// звернення до об'єктів напряму

int main()

{

int a,b; //опис цілих

float c; //опис дійсних

cin>>a>>b;//ведення даних

c=a/b;

cout<<c<<”\n”;//виведнння даних

}

11. Типи величин, вираз, операції, функції

Типи величин

int a;

float b=float(a)/3;

#include "iostream"

using namespace std;

int a,b;

int main()

{

//ifstream cin("input.txt");

//ofstream cout("output.txt");

float a;

cin>>a;

cout.precision(2);

cout<<fixed<<a<<endl; //"\n"

return 0;

}

Операції

Функції

#include "iostream"

#include "math.h"

using namespace std;

int main()

{

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

Структура програми

#include "iostream"

#include <math.h>

using namespace std;

int main()

{

cout <<"Okey";

return 0;

}

12. Слідування

1. Два  резистори  R₁  і  R₂  з'єднані паралельно. Визначити сумарний  опір за формулою .

2.     Обчислити  відстань  між двома точками з координатами X₁,Y₁ і X₂,Y₂  за формулою L=

#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 "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 серій?

13. Розгалуження

Операції порівняння

<, >. <=,>=, !=, ==

Логічні операції

&&, ||, !!

Умовний оператор

if (умова)  команда 1; else команда 2;

6. Знайти максимальне значення серед двох чисел введених з клавіатури.

#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 "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.

14. Цикл

З параметром

for (i=1;i<=n;i++) {блок операторів};

З перед умовою

while (умова){блок операторів};

Після умовою

do {блок операторів}

while (умова);

12.Скласти програму виведення на екран квадратiв всiх натуральних чисел менших за 20.

#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 "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 "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.

15. Масиви

17. Дано лінійну таблицю  із  n  цілих  чисел.  Знайти  суму  S  всіх елементів.

#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 "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. Перевірити, чи є одномірний числовий масив упорядкованим по зростанню.

16. Робота з файлами

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

}