Олімпіадні завдання та їх розв'язок (2015)

Олімпіада з інформатики

Корисна інформація з інформатики

Завдання для олімпіади з інформатики 2 туру (8-9 клас)

1. Скільки до Нового Року? (7366)

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

Вхідні дані

У єдиній стрічці ціле число N (0 < N≤ 31500000) – кількість секунд, що залишилось до Нового Року.

Вихідні дані

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

• Ліміт часу 1 секунда

• Ліміт використання пам'яті 64 MiB

Вхідні дані #1

21009 Вихідні дані #1

0 5 50 9

var n:longint;

d,h,m,s:integer;

begin

readln(n);

d:=n div 86400;

h:=(n mod 86400) div 3600;

m:=(n mod 3600) div 60;

s:=n mod 60;

writeln(d,' ',h,' ',m,' ',s);

end.

2. Знижки (7337)

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

Вхідні дані:

Три натуральних числа a, b, с – ціни трьох товарів (1 ≤ a,b, с ≤ 10000).

Вихідні дані:

Вартість покупки.

Вхідні дані #1

8 11 6 Вихідні дані #1

17

var a,b,c,max,min:longint;

begin

readln(a,b,c);

if (a>=b) and (a>=c) then max:=a;

if (b>=a) and (b>=c) then max:=b;

if (c>=a) and (c>=b) then max:=c;

if (a<=b) and (a<=c) then min:=a;

if (b<=a) and (b<=c) then min:=b;

if (c<=a) and (c<=b) then min:=c;

writeln(max+min);

end.

3. Кількість даних цифр в числі (1609)

Підрахувати кількість цифр a в числі n.

Вхідні дані

У першому рядку записано одне ціле 32-розрядне число N.

У другому рядку записано одну цифру а.

Вихідні дані

Одне число - розв'язок задачі.

• Ліміт часу 1 секунда

• Ліміт використання пам'яті 122.17 MiB

Вхідні дані #1

25557

5 Вихідні дані #1

3

Вхідні дані #2

100

0 Вихідні дані #2

2

var a,b : string;

k,i : integer;

BEGIN

readln(a);

readln(b);

k:=0;

for i:=1 to length(a) do

if a[i]=b then k:=k+1;

writeln(k);

end.

1609 Python

a=str(input()) a=list(a) b=input()print(a.count(b))

4. Молоко та пиріжок (7365)

Учням першого класу призначають додаткову склянку молока та пиріжок, якщо першокласник важить менше 30 кг. В перших класах школи навчається n учнів. Склянка молока має об'єм 200 мл, а замовлені упаковки молока – 0,9 л. Визначити кількість додаткових пакетів молока та пиріжків, необхідних щодня.

Вхідні дані

У першому рядку задано ціле число n (0 < n ≤ 100). У наступному рядку знаходяться n додатних дійсних чисел – маси кожного першокласника.

Вихідні дані

В одному рядку вивести два цілих числа - кількість додаткових пакетів молока та пиріжків, необхідних щодня.

• Ліміт часу 1 секунд

• Ліміт використання пам'яті 122.17 MiB

Вхідні дані

20

30 37 31 25 32 29 35 40 28 25 30 34 26 23 20 22 21 30 38 33

Вихідні дані #1

2 9

var i,n,kol,mol:integer;

w:real;

begin

kol:=0;

readln(n);

for i:=1 to n do

begin

read(w);

if w<30 then kol:=kol+1;

end;

if kol*200 mod 900=0

then mol:=kol*200 div 900

else mol:=kol*200 div 900+1;

writeln(mol,' ',kol);

end.

100% результат (если для считывания w использовать readln то получается ошибка выполнения)

5. Поле-чудес (7340)

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

Вхідні дані:

Слово записане великими англійськими буквами (не більше 100 символів).

Вихідні дані:

Відповідь до задачі.

• Ліміт часу 1 секунда

• Ліміт використання пам'яті 64 MiB

Вхідні дані

GOOGLE Вихідні дані

4

Var s:string;

i,j,k,n:integer;

Begin

Readln(s);

k:=0;

for i:=1 to Length(s) do

begin

n:=0;

for j:=i+1 to Length(s) do

if s[i]=s[j] then n:=n+1;

if n=0 then k:=k+1;

end;

Writeln(k);

End.

100% результат (нахождение количества различных символов в слове)

Завдання для олімпіади з інформатики 2 туру (10-11 клас)

1. Молодший біт (1753)

Для заданого додатнього цілого A (1 ≤ A ≤ 100), вивести молодший біт A.

Наприклад, якщо A = 26, то його ми можемо записати у двійковому вигляді, як 11010, молодший біт A є 10, і на виході повинно бути 2.

Інший приклад виглядає наступним чином: при A = 88, це число A ми можемо записати у двійковій формі 1011000, молодший біт в A є 1000, і на виході повинно бути 8.

Вхідні дані

Кожен рядок вхідних даних містить лише одне ціле число A (1 ≤ A ≤ 100). Рядок, який містить "0" позначає кінець уведення, і цей рядок не є частиною вхідних даних.

Вихідні дані

Для кожного числа A, отриманого на вході, у окремому рядку вивести значення його молодшого біта.

Рішення

#include <iostream>

using namespace std;

int main()

{

int temp,len = 0;

unsigned char res[100];

do

{

cin >> temp;

if (temp)

{

res[len] = 1;

while (!(temp % 2)) (res[len]*=2, temp/=2);

len ++;

}

}

while (temp);

for (int i = 0; i < len; i++) cout << (int)res[i] << endl;

}

2. Білі кубики (478)

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

Вхідні дані

Один рядок містить три цілих числа – розміри бруска в дм, які не перевищують 1000000.

Вихідні дані

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

· Ліміт часу 1 секунда

· Ліміт використання пам'яті 64 MiB

Рішення

using System;

namespace ConsoleApplication2

{

class Program

{

static void Main(string[] args)

{

string setir = Console.ReadLine();

var massiv = setir.Split(' ');

long a = long.Parse(massiv[0]);

long b = long.Parse(massiv[1]);

long c = long.Parse(massiv[2]);

long renglenmishUzler = 2 * (a * b + a * c + b * c);

long say = a * b * c;

Console.WriteLine("{0} {1}", say, 6 * say - renglenmishUzler);

}

}

}

Білі кубики (478) Python

a, b, c = map(int,input().split()) N=(a*b*c) N1=N*6 s1=2*(a*b+b*c+a*c) N2=N1-s1 print(N,N2)

3. Звичайна перестановка (2040)

За двома рядками a та b слід вивести такий рядок x найбільшої довжини, який одночасно є підрядком перестановки a та підрядком перестановки b.

Вхідні дані

Складається з декількох тестів, кожний з яких містить два рядки. Кожний рядок складається з символів нижнього регістру, причому першим рядком у парі є a, а другим рядком b. Максимальна довжина кожного рядка 1000 символів.

Вихідні дані

Для кожного тесту в окремому рядку вивести рядок x. Якщо таких рядків декілька, то виводити слід найменший в алфавітному порядку.

· Ліміт часу 1 секунда

· Ліміт використання пам'яті 122.17 MiB

Рішення

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

string a, b, res;

int mas[1001][1001];

pair <int, int> ij;

int main()

{

do

{

getline(cin, a);

getline(cin, b);

if (cin)

{

sort(&a[0], &a[a.length()]);

sort(&b[0], &b[b.length()]);

for (int i = 0; i < a.length() + 1; i++)

for (int j = 0; j < b.length() + 1; j++)

{

if (i*j == 0) mas[i][j] = 0;

else if (a[i - 1] == b[j - 1]) mas[i][j] = mas[i - 1][j - 1] + 1;

else mas[i][j] = max(mas[i - 1][j], mas[i][j - 1]);

}

ij.first = a.length();

ij.second = b.length();

res = "";

while (ij.first > 0 && ij.second > 0)

{

if (mas[ij.first][ij.second] > max(mas[ij.first - 1][ij.second], mas[ij.first][ij.second - 1]))

{

res += b[ij.second - 1];

ij.first--;

ij.second--;

}

else if (mas[ij.first][ij.second - 1] == mas[ij.first][ij.second]) ij.second--;

else if (mas[ij.first - 1][ij.second] == mas[ij.first][ij.second]) ij.first--;

}

if (res != "") for (int i = res.length() - 1; i >= 0; i--) cout << res[i];

cout << endl;

}

} while (cin);

}

4. n-значні числа (1288)

Скільки натуральних n-значних чисел починається з цифри a або цифри b?

Вхідні дані

Три цілих числа: n (0 < n ≤ 10⁶) , a та b. Всі дані, як і сама умова задачі, задані у десятковій системі числення.

Вихідні дані

Вивести кількість натуральних n-значних чисел, що починаються з цифри a або цифри b.

· Ліміт часу 1 секунд

· Ліміт використання пам'яті 122.17 MiB

Рішення

#include <iostream>

#include <string>

using namespace std;

int main()

{

int n, a, b; cin >> n >> a >> b;

string s;

if (a + b == 0) cout << 0 << endl;

else

{

if (a == b | !(a*b)) cout << 1;

else cout << 2;

for (int i = 0; i < n - 1; i++) s += '0';

cout << s << endl;

}

}

5. Колір (2228)

Намистинки n кольорів з'єднані між собою у циклічне намисто з n намистинок (n ≤ 10⁹). Вам потрібно підрахувати кількість різних намист, які можна отримати. У намисті не обов'язково використовувати усі n кольорів. Повтореннями, отриманими у результаті обертання намиста навколо центру, потрібно знехтувати.

Відповідь виведіть по модулю p.

Вхідні дані

Перший рядок містить кількість тестів x (x ≤ 3500). Кожен з наступних x рядків містить два числа n та p (1≤ n ≤ 10⁹, 1 ≤ p ≤ 30000).

Вихідні дані

Для кожного тесту вивести відповідь в окремому рядку.

· Ліміт часу 2 секунди

· Ліміт використання пам'яті 64 MiB

#include<cstdio>

#include<vector>

using namespace std;

const int maxn = 1 << 15;

vector<pair<int, int> >v;

int n, mod, cnt = 0, prime[maxn];

int phi(int x)

{

int a = x;

for (int i = 0; i < cnt; i++)

{

int &p = prime[i];

if (p*p > x) break;

if (x%p == 0)

{

while (x%p == 0) x /= p;

a -= a / p;

}

}

if (x > 1) a -= a / x;

return a%mod;

}

int pow(int x)

{

int ans = 1, base = n%mod;

while (x)

{

if (x & 1) ans = ans*base%mod;

base = base*base%mod; x >>= 1;

}

return ans;

}

int dfs(int pos, int cur)

{

int ans = phi(n / cur)*pow(cur - 1) % mod;

while (pos < v.size())

{

int nxt = cur;

for (int i = 0; i < v[pos].second; i++)

{

nxt *= v[pos].first;

ans = (ans + dfs(pos + 1, nxt)) % mod;

}

pos++;

}

return ans;

}

void read(int &d)

{

char ch;

while (ch = getchar(), ch < 48 || ch > 57); d = ch - 48;

while (ch = getchar(), ch > 47 && ch < 58) d = d * 10 + ch - 48;

}

void write(int d)

{

if (d == 0){ puts("0"); return; }

char str[6]; str[5] = 0; int i;

for (i = 4; d; i--) str[i] = d % 10 + 48, d /= 10;

puts(str + i + 1);

}

int main()

{

int t, vis[maxn];

for (int i = 2; i < maxn; i++)

if (!vis[i])

{

prime[cnt++] = i;

for (int j = i*i; j < maxn; j += i) vis[j] = 1;

}

read(t);

while (t--)

{

read(n), read(mod);

v.clear(); int x = n;

for (int i = 0; i < cnt; i++)

{

int num, &p = prime[i];

if (p*p > x) break;

if (x%p) continue;

for (num = 0; x%p == 0; num++) x /= p;

v.push_back(make_pair(p, num));

}

if (x > 1) v.push_back(make_pair(x, 1));

write(dfs(0, 1));

}

return 0;

}

53. Праздник Анфисы

Прямоугольный ангар розмером M на N (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг Анфиса может перемещаться с одной паркетины на другую только через общую сторону. Какое наименьшее количество шагов нужно сделать Анфисе, находясь на паркетине A, к кусочку сыру, расположенному на паркетине B?

Входные данные

В первой строке размеры ангара M на N. Во второй строке номер паркетины, в кототрой находится Анфиса A и номер паркетины с кусочком сыру B. 1 ≤ M, N ≤ 30000.

Выходные данные

Единственное число - количество шагов K, которые нужно сделать Анфисе.

Лимит времени 1 секунда

Лимит использования памяти 64 MiB

Входные данные

5 4

25 38

Выходные данные

5

var m, n, xp, yp, xk, yk, st, fin, temp, rez :longint;

begin

readln (n, m);

readln (st, fin);

if n=1 then begin

rez:=abs(st-fin);

writeln (rez); halt;

end;

if m=1 then begin

rez:=abs(st-fin);

writeln (rez); halt;

end;

if st>fin then begin temp:=st; st:=fin; fin:=temp; end;

xp:=((st-1) div (2*n))+1;

yp:=(((st-1) mod (2*n)) div 2)+1;

xk:=((fin-1) div (2*n))+1;

yk:=(((fin-1) mod (2*n)) div 2)+1;

if (xp=xk) then

begin

rez:=abs(st-fin);

writeln (rez); halt;

end;

if (yp=yk) and (st mod 2 = fin mod 2) then

begin

rez:=abs(xk-xp)*2;

writeln (rez); halt;

end;

if (yp=yk) and (st mod 2 =0) and (fin mod 2=1) then

begin

rez:=abs(xk-xp)*2-1;

writeln (rez); halt;

end;

if (yp=yk) and (st mod 2 =1) and (fin mod 2=0) then

begin

rez:=abs(xk-xp)*2+1;

writeln (rez); halt;

end;

if (xp<xk) and (yp<yk) and (st mod 2 = fin mod 2) then

begin

rez:=abs(xk-xp)*2+abs(yk-yp)*2;

writeln (rez); halt;

end;

if (xp<xk) and (yp<yk) and (st mod 2 =0) and (fin mod 2=1) then

begin

rez:=abs(xk-xp)*2+abs(yk-yp)*2-1;

writeln (rez); halt;

end;

if (xp<xk) and (yp<yk) and (st mod 2 =1) and (fin mod 2=0) then

begin

rez:=abs(xk-xp)*2+abs(yk-yp)*2+1;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp=xk+yk) and (st mod 2 = fin mod 2) then

begin

rez:=abs(yk-yp)*2;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp>xk+yk) and (st mod 2 = fin mod 2) then

begin

rez:=abs(xk-xp)*2;

yp:=yp-abs(xp-xk);

rez:=rez+abs(yp-yk)*2;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp>xk+yk) and (st mod 2=0) and (fin mod 2=1) then

begin

rez:=abs(xk-xp)*2;

yp:=yp-abs(xp-xk);

rez:=rez+abs(yp-yk)*2+1;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp>xk+yk) and (st mod 2=1) and (fin mod 2=0) then

begin

rez:=abs(xk-xp)*2;

yp:=yp-abs(xp-xk);

rez:=rez+abs(yp-yk)*2-1;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp<xk+yk) and (st mod 2 = fin mod 2) then

begin

rez:=abs(yk-yp)*2;

xp:=xp+abs(yp-yk);

rez:=rez+abs(xp-xk)*2;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp<xk+yk) and (st mod 2=0) and (fin mod 2=1) then

begin

rez:=abs(yk-yp)*2;

xp:=xp+abs(yp-yk);

rez:=rez+abs(xp-xk)*2-1;

writeln (rez); halt;

end;

if (xp<xk) and (yp>yk) and (xp+yp<xk+yk) and (st mod 2=1) and (fin mod 2=0) then

begin

rez:=abs(yk-yp)*2;

xp:=xp+abs(yp-yk);

rez:=rez+abs(xp-xk)*2+1;

writeln (rez); halt;

end;

end.

E-olimp 17. Садовник-художник

После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски N деревьев есть у него, если никаких два одинаковых цвета не могут быть рядом?

Входные данные

Количество деревьев N (1 ≤ N ≤ 50).

Выходные данные

Количество способов покраски.

var n, i:longint;

rez:int64;

begin

readln (n);

rez:=3;

for i:=2 to n do

rez:=rez*2;

writeln (rez);

end.

Tаблица 13.1. Целочисленные типы данных Free Pascal (Lazarus).

ПРИМЕЧАНИЕ

В Free Pascal типы Int64 и QWord не являются порядковыми! Это означает, что вы не можете использовать их, например, для индексных переменных в циклах.

Тип Int64 это 64 битовое целое число со знаком. Этот размер фиксирован, и не будет изменён в будущих выпусках Delphi.

Функции типа IntToStr поддерживают Int64.

Целочисленные константы приводятся к типу Int64, когда они превышают размер Integer.

Задача 124 e-olimp

Квадрат

Найдите периметр и площадь квадрата.

Входные данные

Каждая строка является отдельным тестом и содержит одно целое число - длину стороны квадрата n (1 ≤ n ≤ 1000).

Выходные данные

Для каждого теста выведите в одной строке периметр и площадь квадрата.

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

Входные данные #1

3

5

10

Выходные данные #1

12 9

20 25

40 100

var

n: integer;

f1, f2: text;

begin

assign(f1, 'input.txt');

assign(f2, 'output.txt');

reset(f1);

rewrite(f2);

repeat

begin

readln(f1, n);

writeln(f2, n * 4, ' ', n * n);

end;

until eof(f1);

close(f2);

close(f1);

end.

Задача A-Випробування автомата

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

Вартість склянки чаю та кави в автоматі передбачається встановити рівній п'яти ужикам (така в Ужляндії валюта). Автомати будуть приймати монети по 5 і 10 ужиків, а також купюри в 10, 50 і 100 ужиків. Коли програмісту потрібно видавати здачу (тобто коли програміст кинув у автомат монету в 10 ужиків, або купюру в 10, 50 або 100ужиків), автомат видає здачу монетами в п'ять ужиків; якщо ж пасажир кинув у автомат монету в п'ять ужиків, то автомат її зберігає і може використовувати для здачі наступним програмістам.

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

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

Формат вхідних даних: У першому рядку вхідного файлу знаходиться одне натуральне число N - кількість покупок в автоматі, які були здійснені в ході випробування (1 ≤ N ≤ 50 000). У другому рядку знаходяться N натуральних чисел, кожне з яких рівне номіналу монети або купюри, яку використовував черговий програміст для оплати; кожен номінал може приймати одне з чотирьох значень: 5, 10, 50 або 100.

Формат вихідних даних: У вихідний файл виведіть одне число - мінімальну кількість монет в п'ять ужиків, які треба було завантажити в автомат спочатку, щоб усім програмістам вистачило здачі.

Примітка:

У першому прикладі одна монета в п'ять ужиків буде потрібна для здачі першому програмісту і 19 монет - третьому, але під час здачі третьому можна використовувати ту монету, яку кине другий програміст, тому спочатку у автоматі досить 19 монет.

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

У третьому прикладі першоve програмісту потрібні дев'ять монет здачі, та всі вони повинні спочатку знаходиться в автоматі.

Приклад

Задача B-Кросворд

Вам дано квадратний кросворд розміру NxN. Порожні клітини позначені в ньому символом '-', зафарбовані - символом '#'. За правилами кросвордів, кожне слово має складатися мінімум з 2 букв.

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

Формат вхідних даних: У першому рядку міститься число N (1 ≤ N ≤ 2000) - розмір кросворду. Наступні N рядків містять кросворд. Кожен рядок складається з N символів '-' і '#', описаних вище.

Формат вихідних даних: Виведіть два числа - кількість слів по горизонталі і по вертикалі.

Приклад

Задача C-Цікава задача

Арифметична прогресія це послідовність чисел виду a₁, a₁ + d, a₁ + 2d, ..., a₁ + (n-1)d, ..., де a₁ - це перший член прогресії, d - це фіксована різниця між попереднім та наступним.

Степан, дізнавшись про проведення ІІІ етапу Всеукраїнської олімпіади з інформатики, вирішив запропонувати учасникам непросту, цікаву задачу, на тему "Арифметична прогресія".

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

Наприклад, перший член арифметичної прогресії 2, тоді маємо виписати на дошці послідовність 2, 4, 6, 8, ... Четвертий член цієї арифметичної прогресії є повним кубом числа 2 (8 = 23).

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

Формат вхідних даних: Єдиний рядок вхідного файлу містить одне ціле число А(1 ≤ А ≤ 10⁹).

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

Система оцінювання: Рішення, які вірно працюють для A ≤ 10 набиратимуть не менше 20 балів.

Пояснення:

Перший приклад: четвертий член цієї арифметичної прогресії (2, 4, 6, 8, ...) є повним кубом числа 2 (8 = 23).

Другий приклад: другий член цієї арифметичної прогресії (4, 8, ...) є повним кубом числа 2 (8 = 23).

Третій приклад: перший член цієї арифметичної прогресії (125, ...) є повним кубом числа 5 (125 = 53).

Приклад

Неповне рішення.

Щоб набрати більше балів, потрібно задане число розкласти на прості множники і врахувати, щоб кількість однакових простих множників була кратною трьом.

Задача D-Увімкніть лампу

Степан розробляє електронну схему на прямокутній сітці розміром N*M.

Усього N*M квадратних плиток. Два (з чотирьох) протилежних кута кожної плитки з'єднані дротом.

Джерело живлення під’єднано до лівого верхнього кута сітки, лампа - до правого нижнього. Для того щоб увімкнути лампу можна повернути будь-яку плитку на 90 градусів у обох напрямках.

На зображені лампа вимкнута. Якщо повернути будь-яку плитку у другій cправа колонці, то лампа увімкнеться.

Напишіть програму, яка знаходить мінімальну кількість плиток, що треба перевернути для того, щоб увімкнути лампу.

Формат вхідних даних: Перший рядок містить два цілих числа N та M - розміри сітки. Далі слідують N рядків по M символів - \ або /, що характеризують напрямлення дроту на даній плитці.

Формат вихідних даних: Єдиний рядок вихідного файлу має містити відповідь на задачу, або ж повідомлення "NO SOLUTION", в тому випадку, коли увімкнути лампу неможливо.

Обмеження:

1 ≤ N, M ≤ 500.

Система оцінювання:

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

40 балів можна отримати, якщо Ваша програма вірно працює при 1 ≤ N ≤ 4 та 1 ≤ M ≤ 5.

Приклад

E-Свято в Ужляндії

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

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

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

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

Формат вхідних даних: Перший рядок вхідного файлу містить ціле число N (2 ≤ N ≤ 10⁵) - кількість міст в Ужляндії. Міста пронумеровані натуральними числами від 1 до N, Ужмісто має номер 1. Далі йдуть N-1 рядок. Кожен з цих рядків містить три розділених одиночними пробілами цілих числа X, Y, Z: між містами з номерами X і Y є дорога, за яку відповідальне місто з номером X, і за проїзд по якій стягується податок рівний Z (1 ≤ Z ≤ 10⁴).

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

Система оцінювання:

N ≤ 10 – не менше 20 балів

N ≤ 20 – не менше 30 балів

N ≤ 200 – не менше 50 балів

N ≤ 2000 – не менше 70 балів

Приклад

10-11 клас

Міська олімпіада 2016

1. Несчастливый автобус(№ 247)

Витя живёт довольно далеко от школы, поэтому, чтобы не опаздывать на уроки, он ездит на автобусе. Витя - очень наблюдательный мальчик, он старается замечать все интересные совпадения, которые происходят в жизни. Однажды он заметил, что как только он садится в автобус, у которого номер в двоичном представлении второй цифрой справа имеет единичку, так его обязательно вызовут к доске отвечать заданный урок. А кто же любит ходить к доске?! Тем более, если накануне просидел за компьютером и не выучил уроки!!! Явно, что в таком случае грозит "двойка" ...

Помогите Вите составить список автобусов, которые он считает "несчастливыми" автобусами.

Входные данные

В певрой строке записано число N (0 ≤ N ≤ 100000) — количество автобусов, далее указаны номера автобусов m_i (0 ≤ m_i ≤ 2³¹-1) по одному в строке.

Выходные данные

Выведите количество "несчастливых" автобусов.

varx,k,i,n:longint; //Мое решение

begin

k:=0;

readln(n);

fori:=1to ndo

begin

readln(x);

if ((x-2) mod4=0) or ((x-3) mod4=0) thenk:=k+1;

end;

writeln(k);

end.

vari,n,t,k:longint; //Решение Устинова

begin

k:=0;

readln( n );

fori:=1to ndo

begin

readln( t );

if (t div2) mod2=1theninc( k );

end;

writeln( k );

end.

2. Компакт-диски (№107)

Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 100 дисков стоит 100 грн., из 20 дисков - 30 грн., а один диск стоит 2грн. Какую минимальную сумму нужно истратить для покупки n таких дисков?

Входные данные

Количество дисков n (n ≤ 1000).

Выходные данные

Вывести минимальную сумму в гривнах для покупки n дисков.

varn:integer;

k100,k20,k:integer;

begin

k100:=0;k20:=0;k:=0;

readln(n);

if n>=100thenbegin k100:=n div100; n:=n mod100;end;

if n>=65then k100:=k100+1

elseif n mod20<=14

thenbegin k20:=n div20;k:=n mod20;end

else k20:= n div20+1;

writeln(100*k100+30*k20+2*k);

end.

3. Лицензионное ПО (№ 255)

Как вы знаете, для удостоверения лицензионности ПО используются серийные номера и регистрационные ключи. Вами, как ведущими разработчиками систем верификации лицензионности ПО была разработана идея надежнейшей в своём роде системы. Основывается она на цифровых корнях чисел. Теперь вам требуется написать программу, определяющую цифровой корень данного числа.

Для произвольного числа цифровой корень определяется следующим образом:

1. Если сумма цифр числа меньше десяти, то цифровой корень и есть сумма цифр этого числа.

2. В противном случае цифровой корень числа равен цифровому корню суммы его цифр.

Входные данные

Единственное число n (0 ≤ n ≤ 2³¹- 1).

Выходные данные

Вывести одно число - ответ на поставленную задачу.

varsum:longint; //Мое решение

functions_chifr(x:longint):longint;

vara:integer;

begin

s_chifr:=0;

whilex>0 do

begin

a:=x mod 10;

s_chifr:=s_chifr+a;

x:=x div 10;

end;

end;

Begin

readln(sum);

whilesum>9 do

sum:=s_chifr(sum);

writeln(sum);

End.

vark,t,i:longint; //Решение Устинова

s:string;

begin

readln(s);

if length(s)>1 then

begin

k:=0;

for i:=1 to length(s) do

begin

k:=k+ord(s[i])-48;

end;

while k>9 do

begin

t:=0;

while k>0 do

begin

t:=t+(k mod 10);

k:=k div 10;

end;

k:=t;

end;

writeln(k);

end else writeln(s);

end.

4. Кубики (№202)

Витэк еще в детсадике любил играть в кубики. Так как Витэк был в старшей группе, то на всех кубиках были большие буквы, да еще и английские. А так как детсадик был специализированным и детсадиковцев готовили как будущих разведчиков, то все они должны были знать английский язык. А возможно - и не разведчиков, а дипломатов, но и для этой профессии знание английского языка было необходимым. Витэк не очень хорошо запоминал все слова, что учили на занятиях в детсадике, но всегда мог запомнить самое длинное слово, которое на кубиках, что использовались на занятиях, читалось в обеих направлениях одинаково.

Сколько кубиков было использовано в слове, которое запомнил Витэк?

Входные данные: В первой строке – количество разложенных перед Витэком кубиков N (1 ≤ N ≤ 100000), в следующей строке последовательность N букв на кубиках без пробелов.

Выходные данные: Количество букв в самом длинном слове, которое запомнил Витэк.

vars:ansistring;

mas:array['A'..'Z'] oflongint;

n,i,k:longint;

ch:char;

begin

k:=0;

readln(n);

readln(s);

fori:=1to length(s) do

inc(mas[s[i]]);

forch:='A'to'Z'do

k:=k+mas[ch] div2;

k:=K*2;

if k=n thenwriteln(k) elsewriteln(k+1);

end.

5^*. Решение задач (№ 893)

В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100000) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.

Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Входные данные

Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100000, 0 ≤ A ≤ 10⁹) - количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 10⁹, 1 ≤ bi ≤ 10⁹) - соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.

Выходные данные

Выведите одно число - максимальное количество задач, которое Вася сможет решить.

typech=record//С использованием пузырьковой сортировки 70% тестов

a,b:longint;

end;

varmas:array[1..100000] ofch;

pr:ch;

i,j,n,um,kol:longint;

Begin

readln(n,um);

kol:=0;

fori:=1to ndo

read(mas[i].a,mas[i].b);

fori := 1to n-1do

forj := 1to n-ido

if mas[j].a> mas[j+1].a thenbegin

pr := mas[j];

mas[j] := mas[j+1];

mas[j+1] := pr;

end;

fori:=1to ndo

if um>=mas[i].athenbeginkol:=kol+1;um:=um+mas[i].b;end;

writeln(kol);

End.

typez=record //с использованием быстрой сортировки 100 тестов

a,b:longint;

end;

varn,i,k:longint;

a:Int64;

m:array[1..100000] of z;

procedureqSort(l,r:longint);

vari,j:longint;

w,q:z;

begin

i := l; j := r;

q := m[(l+r) div2];

repeat

while (m[i].a<q.a) doinc(i);

while (q.a< m[j].a) dodec(j);

if (i<= j) then

begin

w:=m[i]; m[i]:=m[j]; m[j]:=w;

inc(i); dec(j);

end;

until (i> j);

if (l < j) thenqSort(l,j);

if (i< r) thenqSort(i,r);

end;

begin

readln(n,a);

i:=0; k:=0;

while n>0do

begin

Inc(i);

Readln(m[i].a,m[i].b);

if a>=m[i].athen

begin

a:=a+m[i].b;

dec(i); inc(k);

end;

Dec(n);

end;

n:=i;

qSort(1,n); i:=1;

while (i<=n) and (a>=m[i].a) do

begin

a:=a+m[i].b;

Inc(k); Inc(i);

end;

Writeln(k);

end.

8-9клас

1. Среднее число (№108)

Дано три различных числа a, b, c. Вывести среднее из них.

Входные данные

Числа a, b, c целые и по модулю не превышают 1000.

Выходные данные

Вывести среднее среди трех чисел.

vara,b,c:integer;

Begin

readln(a,b,c);

if (b<a) and (a<c) or (c<a) and (a<b)then writeln(a);

if (a<b) and (b<c) or (c<b) and (b<a)then writeln(b);

if (a<c) and (c<b) or (b<c) and (c<a)then writeln(c);

end.

2. Банкомат (№ 138)

В банкомате имеются в достаточном количестве купюры номиналом10,20,50,100,200и500гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n гривен или вывести -1, если указанную сумму выдать нельзя.

Входные данные

Одно число n (1 ≤ n ≤ 1000000).

Выходные данные

Наименьшее количество купюр, которыми можно выдать n гривен.

varn,k:longint;

begin

readln(n);

k:=0;

k:=k+n div 500; n:=n mod 500;

k:=k+n div 200; n:=n mod 200;

k:=k+n div 100; n:=n mod 100;

k:=k+n div 50; n:=n mod 50;

k:=k+n div 20; n:=n mod 20;

k:=k+n div 10; n:=n mod 10;

ifn<>0 thenwriteln(-1) elsewriteln(k);

End.

Банкомат (№ 138) Python

n=int(input())

k=0 k=k+n//500n=n%500 k=k+n//200n=n%200 k=k+n//100n=n%100; k=k+n//50n=n%50; k=k+n//20n=n%20 k=k+n//10n=n%10 if n!=0: print(-1) else: print(k)

3. Количество игрушек (№927)

Задано количество видов игрушек в магазине, количество игрушек каждого вида и стоимость игрушки каждого вида. Определить количество игрушек, стоимость которых меньше 50 грн.

Входные данные

В первой строке задано количество наличных в прейскуранте видов игрушек n (0 ≤ n ≤ 1000). В следующих n строках задано по 2 числа через пробел: сначала количество игрушек a (0 ≤ a ≤ 1000) очередного вида и их цена b (0 < b ≤ 10000) в грн.

Выходные данные

Вывести количество игрушек, стоимость которых меньше 50 грн.

vari,n,kol:integer;

otv:longint;

cena:real;

Begin

readln(n);

otv:=0;

fori:=1to n do

begin

read(kol,cena);

ifcena<50 thenotv:=otv+kol;

end;

writeln(otv);

end.

4. Сдвиньэлементы (№ 922)

Задан одномерный массив целых чисел длины n. Сдвинуть элементы массива вправо циклически на 1 шаг.

Входные данные

В первой строке задано количество элементов массива n (n ≤ 100). Во второй строке через пробел заданы сами элементы массива, значение каждого из которых по модулю не превышает 100.

Выходные данные

В одной строке вывести через пробел n чисел: новые значения элементов массива.

vara:array[1..100] oflongint;

n,i,x:longint;

Begin

readln(n);

fori:=1to ndo

read(a[i]);

x:=a[n];

fori:=n downto2do

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

a[1]:=x;

fori:=1to ndowrite(a[i],' ');

end.

5. Покупка цветов (№ 891)

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по a рублей за штуку и гладиолусы по b рублей за штуку (a < b). У Васи есть c рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже c рублей. Помогите ему вычислить стоимость такого букета.

Входные данные

Три целых числа a, b, c (1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000).

Выходные данные

Выведите одно число - стоимость самого дорогого букета из максимального количества цветов.

vari_a,i_b,a,b,c,kol,stoim:longint; //Моерешение

Begin

readln(a,b,c);

kol:=0;stoim:=0;

fori_a:=0to c div a do

fori_b:=0to c div b do

if (i_a+i_b>=kol) and (a*i_a+b*i_b<=c) thenkol:=i_a+i_b;

fori_a:=0to c div a do

fori_b:=0to c div b do

ifi_a+i_b=kolthenif (a*i_a+b*i_b>stoim) and (a*i_a+b*i_b<=c) thenstoim:=a*i_a+b*i_b;

writeln(stoim);

end.

vara,b,c,m,t,k:longint; //решение Устинова

begin

Readln(a,b,c);

k:=c div a;

m:=k*a;

t:=m;

while (k>0) and (t>=a) and (t-a+b<=c) do

begin

t:=t-a+b; dec( k );

if t>m thenm:=t;

end;

Writeln( m );

end.