Розбір задач
Умова задачі: Степенем симетрії натурального числа назвемо кількість пар його десяткових цифр, у яких цифри співпадають і розташовані симетрично відносно середини десяткового запису цього числа. Якщо деяка цифра стоїть посередині десяткового запису, її теж треба враховувати у парі з нею самою. Знайти степінь симетрії числа N.
Усі матеріали по задачі: https://sites.google.com/site/c4plus/olimpiadne-programuvanna/rozbir-zadac/stepin-simetriie
Задачі ХХХ Житомирської обласної олімпіади з інформатики. Перший тур.
ОЛІМПІАДА (http://www.e-olymp.com/uk/problems/7503)
Умова задачі
На олімпіаду з інформатики прибули N команд по A[i] учасників в кожній (i=1..N). Для проведення змагань приготували класи з однаковою кількістю M комп’ютерів в кожному. Яку мінімальну кількість класів потрібно задіяти, при умові, що в кожному класі будуть представники різних команд.
Вхідні дані
Числа N і M в першому рядку. В другому N чисел A[i] (i=1..N). Числові значення цілі, невід’ємні, не перевищують 100.
Вихідні дані
Одне число – необхідна кількість класів.
Приклад вхідних даних
5 3
2 3 4 1 2
Приклад вихідних даних
4
Розв'язок 1.
1. Щоб знати скільки
2. Порівнюємо
3.
4.
1. Програма,
using System;
class Program
{
static void Main()
{
// прочитаємо N
int n = System.Convert.ToInt32(str_int[0]);
// прочитаємо N чисел у масив m[]
int[] m =Convert.ToInt32 (Console.ReadLine ().Split(' '));
int N = Convert.ToInt32(Console.ReadLine());
//Знайдемо "довжину" числа
int d = 0; // "довжина" числа поки рівна 0
int a = N; // продублюємо число аби не втратити його початкове значення
do // початок циклу з післяумовою
{
a = a / 10; // укорочуємо число відкинувши останню цифру
d = d + 1; // збільшуємо "довжину" числа на 1
}
while (a >= 1); // умова циклу з післяумовою
Console.Write(d); // шукана "довжина" числа виводиться на екран
Console.ReadLine();
}
}
ТРИ ПРЯМОКУТНИКА (http://www.e-olymp.com/uk/problems/
Умова задачі
На білому аркуші паперу в клітинку намалювали три зафарбованих прямокутника, так що їх сторони лежать на лініях сітки, а вершини мають відомі цілі координати. Знайти загальну кількість зафарбованих клітинок.
Вхідні дані:
В трьох рядках по чотири цілих числа – координати двох протилежних вершин кожного прямокутника (значення по модулю не перевищують 100).
Вихідні дані:
Одне число – кількість зафарбованих клітинок.
Розв'язок 1.
1. Щоб знати скільки
2. Порівнюємо
3.
4.
1. Програма,
using System;
class ProgramOlimp
{
static void Main()
{
int N = Convert.ToInt32(Console.ReadLine());
//
Послідовність кратних (http://www.e-olymp.com/uk/problems/
Умова задачі
В послідовності натуральних чисел A1, A2, A3,... будь-яке з чисел Ak – найменше натуральне, яке ділиться без остачі на кожне з перших k натуральних чисел 1,2,3,..k. Для заданого N вказати найменше K таке, що всі N чисел послідовності, починаючи з AK – однакові.
Вхідні дані: Натуральне число N (N<100).
Вихідні дані: Відповідь до задачі.
Пояснення: Початок ряду 1 2 6 12 60 60 420 840 2520 ...
Розв'язок 1.
1. Щоб знати скільки
2. Порівнюємо
3.
4.
1. Програма,
using System;
class ProgramOlimp
{
static void Main()
{
int N = Convert.ToInt32(Console.ReadLine());
//
Подорож в місті (http://www.e-olymp.com/uk/problems/
Умова задачі
В деякому місті будинки, що знаходяться по одну сторону єдиної вулиці пронумеровані послідовними числами від 1 до N. Відстань між сусідніми будинками достатньо велика, тому мешканці звикли пересуватись по місту на маршрутних таксі, яких всього M. Поїздка по одним маршрутом на будь-яку відстань коштує лише один долар, але кожне таксі має зупинятись тільки біля строго визначених (але не менше двох) будинків. На зупинки вказує номер маршруту - A B ( A – найменший номер будинку, де зупиняється таксі, B – період зупинок).
Наприклад, маршрутне таксі з номером 2 3 при N=11 зупиняється так: 2 5 8 11 8 5 2 …, тому деякі будинки можуть бути незадіяними.
Знаючи значення N і M та номери всіх маршрутів знайти:
* кількість K будинків, де не зупиняється жодне таксі;
* скільки найменше доларів потрібно витрати, щоб дістатися з першого до N-го будинку або вивести 0, якщо це неможливо.
Числові значення N, M, A і B - натуральні, 1£ N £200, 1£A,B,M£20.
Пояснення: На таксі 1 4 рухаємось до будинку 5, потім на таксі 2 3 дістаємося до будинку 11.
Приклад введення 2 Приклад виведення 5
Приклад введення 5 3 2 3 4 1 2 Приклад виведення 4
Приклад введення 2 2 5 6 3 3 7 1 6 4 4 7
Приклад виведення
22
Приклад введення 11 2 2 3 1 4
Розв'язок 1.
1. Щоб знати скільки
2. Порівнюємо
3.
4.
1. Програма,
using System;
class ProgramOlimp
{
static void Main()
{
int N = Convert.ToInt32(Console.ReadLine());
//
Задачі ХХХ Житомирської обласної олімпіади з інформатики. Другий тур.
Добуток (http://www.e-olymp.com/uk/problems/)
Умова задачі
Маємо N цілих чисел. Який найбільший добуток можна отримати, використавши тільки три з цих чисел?
Вхідні дані
В першому рядку ціле невід'ємне N. 3<=N<=105. У другому рядку N цілих чисел, кожне по модулю не перевищує 105.
Вихідні дані
Значення найбільшого добутку трьох з них.
Приклад вхідних даних
9
3 5 -9 7 4 0 9 - 3 5
Приклад вихідних даних 315
Розв'язок 1.
Добуток тим більший чим більші у ньому множники. Отже слід знайти три найбільших числа та перемножити
1. Сортуємо масив
2. Виводимо на екран добуток трьох найбільших.
1. Програма, що не враховує від'ємні числа
class Olimp_
{
static void Main()
{
// прочитаємо N
int n = System.Convert.ToInt32(str_int[0]);
// прочитаємо N чисел у масив m[]
int[] m =Convert.ToInt32 (Console.ReadLine ().Split(' '));
// Відсортуємо масив m[]
bool f = true;
int i, r;
do
{
f = true;
for (i = 0; i<n; i++)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
f = false;
}
}
}
while f
// Знайдемо d - добуток трьох найбільших елементів масиву і виведемо на екран
System.Console.WriteLine(m[0]*m[1]*m[2]);
}
}
Розв'язок 2.
Очевидним недоліком програми є не врахування від'ємних значень масиву. Здавалося множення одне від'ємне число зробить добуток від'ємним тобто далеко не найбільшим. Але якщо перемножити два від'ємних числа результат буде додатнім. Отже слід порівняти у масиві добуток трьох найбільших чисел та двох найменших і одного найбільшого числа. Який добуток виявиться найбільшим - той і буде шуканим результатом.
1. Сортуємо масив
2. Виводимо на екран результат порівняння добутку трьох найбільших і двох найменших та одного найбільшого.
1. Програма, що не враховує від'ємні числа
class Olimp_
{
static void Main()
{
// прочитаємо N
int n = System.Convert.ToInt32(str_int[0]);
// прочитаємо N чисел у масив m[]
int[] m =Convert.ToInt32 (Console.ReadLine ().Split(' '));
// Відсортуємо масив m[]
bool f = true;
int i, r;
do
{
f = true;
for (i = 0; i<n; i++)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
f = false;
}
}
}
while f
// Порівняємо добуток трьох найбільших і двох найменших та одного найбільшого елементів масиву і більше значення виведемо на екран
if ((m[0]*m[1]*m[2])>(m[0]*m[n-1]*m[n-2])) System.Console.WriteLine(m[0]*m[1]*m[2]) else System.Console.WriteLine(m[0]*m[n-1]*m[n-2]);
}
}
Розв'язок 3.
Алгоритм можна значно оптимізувати не проводивши повне сортування масиву а визначивши лише потрібні нам три найбільших і два найменших. Для цього дещо модернізуємо нашу "будьбашку".
1. Тричі проходимо масив в напрямку більших членів обмінючи сусідні елементи.
2. Двічі проходимо у зворотньому напрямку.
3. Виводимо на екран результат порівняння добутку трьох найбільших і двох найменших та одного найбільшого.
1. Програма, що не враховує від'ємні числа
class Olimp_
{
static void Main()
{
// прочитаємо N
int n = System.Convert.ToInt32(str_int[0]);
// прочитаємо N чисел у масив m[]
int[] m =Convert.ToInt32 (Console.ReadLine ().Split(' '));
// Тричі пройдемо масив m[] вивівши "до низу" найбільші елементи
for (i = n; i<=0; i--)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
}
}
for (i = n; i<=0; i--)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
}
}
for (i = n; i<=0; i--)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
}
}
// Двічі пройдемо масив m[] вивівши "до верху" найменші елементи
int i, r;
for (i = 0; i<n; i++)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
}
}
for (i = 0; i<n; i++)
{
if (m[i]<m[i+1])
{
r = m[i];
m[i] = m[i+1];
m[i+1] = r;
}
}
// Порівняємо добуток трьох найбільших і двох найменших та одного найбільшого елементів масиву і більше значення виведемо на екран
if ((m[0]*m[1]*m[2])>(m[0]*m[n-1]*m[n-2])) System.Console.WriteLine(m[0]*m[1]*m[2]) else System.Console.WriteLine(m[0]*m[n-1]*m[n-2]);
}
}