NewCircle

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=106)

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

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

Приклади.

Введення 3 -2 -1 0
Виведення 3 3 0

Введення 5 1 2 -3 3 0
Виведення 1 2 3

Розв'язання.*

З послідовності (P[N]) будемо послідовно виділяти відрізки починаючи з 1-го елемента та знаходитемо їх суму (Vs), яку будемо порівнювати з максимальною (Ms) та зберігатимемо початок (Mb) і кінець (Me) відрізка з максимальною сумою.

Запишемо алгоритми мовами програмування.

Free Pascal:
Var Mb, Me,
   N, I, J : 1..50;
    Ms, Vs : Integer;
         P : Array [1..50] Of Integer;
Begin
 Read (N);
 For I := 1 To N Do
  Read(P[I]);
 Mb := 1;
 Me := 1;
 Ms := P[1];
 For I :=1 To N Do Begin
  Vs := P[I];
  For J := I+1 To N+1 Do Begin
   If Vs > Ms
    Then Begin
     Mb := I;
     Me := J-1;
     Ms := Vs;
    End;
   If (P[J] > P[J-1]) And (J <= N)
    Then Vs += P[J]
    Else Break;
  End;
 End;
 Write(Mb, ' ', Me, ' ', Ms);
End.

C++:
#include <iostream>
using namespace std;
int main(){
 int n;
 cin >> n;
 int p[n];
 for (int i=0; i<n; i++)
  cin >> p[i];
 int mb=0, me=0, ms=p[0];
 for (int i=0; i<n; i++){
  int vs=p[i];
  for (int j=i+1; j<n+1; j++){
   if (vs>ms){
    mb=i;
    me=j-1;
    ms=vs;
   };
   if ((p[j]>p[j-1])&&(j<n))
    vs+=p[j];
    else break;
  }
 }
 cout << mb+1 << ' ' << me+1 << ' ' << ms;
}

* Розв'язання, на мою думку вірне, але проходить 9 з 10 тестів.

Brackets

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=105)

Задача. Дано алгебраїчний вираз з дужками, записаний одним рядком. Вірно чи не вірно в ньому розставлено дужки?

Технічні умови. Програма читає  з клавіатури рядок з виразом (не довший за 255 символів). Програма виводить на екран відповідь у вигляді текстового рядка. Якщо дужки розставлено вірно - друкує слово True, якщо не вірно - False.

Приклад.
Введення:
(a+b)
Виведення:
True

Розв'язання.

У виразі вірно розставлено дужки, якщо кількість відкритих дорівнює кількості закритих і закрита не зустрічається раніше за відкриту. Отже, резервуємо змінну К, яку будемо збільшувати на 1 при зустрічі '('  і відповідно зменшуватимемо при зустрічі ')', та слідкуватимемо щоб К не стало від'ємним (K<0 - ')' зустрічається раніше за '(').

Запишемо алгоритми мовами програмування.

Free Pascal:

Var R : String[255];

    K, I : Integer;

Begin

 Read (R);

 K := 0;

 For I :=1 To Length (R) Do Begin

  Case R[I] Of

   '(' : Inc (K);

   ')' : Dec (K);

  End;

  If K < 0

   Then Break;

 End;

 Write (K = 0);

End.

C++:*
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
 char r[256];
 cin >> r;
 int k=0;
 for (int i=0; i<strlen(r); i++) {
  switch (r[i]) {
   case '(' : k++; break;
   case ')' : k--; break;
  }
  if (k<0) break;
 }
 std::cout << std::boolalpha;
 std::cout << (bool)!k;
}

* Розв'язання, на мою думку вірне, але не проходить жодного тесту....

Clock

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=104)

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

Технічні умови. Програма читає два цілих числа  h  та  m  з клавіатури. Програма виводить.  ціле число  хвилин  на екран.

Приклади.

Введення: 0 0
Виведення: 0

Введення: 1 1
Виведення: 4

Розв'язання*.

Для розв'язування задачі скористаємося годинником ОС. Будемо по черзі від 0:00 до 12:00 співставляти стрілки годинника і записувати час. Отримаємо 11 співпадань, які розділять 12 годин на 12 проміжків. Так як нам потрібно знайти число повних хвилин, а також для зручності, переведемо ввведений час та часи співпадань у хвилини. Хвилини співпадань будемо зберігати в масиві, в який для замкнення кільця додамо 13-й елемент - 720 хвилин = 0:00. Отже, якщо введений час потраплятиме в один із проміжків, то різниця між кінцем інтервалу і введеним часом буде шуканою, інакше стрілки вже співпадають.

Запишемо алгоритми мовами програмування.

Free Pascal:

Const X : Array [0..11] Of 0..720 =

(0, 65, 130, 196, 261, 327, 392, 458, 523, 589, 654, 720); 

Var H, M, I : Integer;

Begin

 Read (H, M);

 M := (H mod 12)*60 + M;

 H := 0;

 For I := 1 To 11 Do

  If (X[I-1] < M) And (M < X[I])

    Then H := X[I] - M;

 Write (H);   

End.

C++:

#include <iostream>
using namespace std;
int main()
{
 const int x[] =
 {0, 65, 130, 196, 261, 327, 392, 458, 523, 589, 654, 720};
 int h, m;
 cin >> h >> m;
 m=(h%12)*60+m, h=0;
 for (int i=1; i<=11; i++)
  if ((x[i-1]<m)&&(m<x[i]))
   h=x[i]-m;
 cout << h;
}

* Розв'язання, хоча воно вірне, не дуже мені подобається...

Hex

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=103)

Задача. Дано число Ch  в десятковій системі числення.  Написати програму що переводить дане число в систему числення з основою m.

Технічні умови. Програма читає  з клавіатури в першому рядку число m (2≤m≤16), в другому - число Ch (0≤Ch≤2+10⁹)  в десятковій системі.  Програма виводить на екран відповідь в вигляді текстового рядка.

Приклад.
Введення:
16
1024
Виведення:
400

Розв'язання

Задача обернена до попередньої (Nhex).

Щоб перевести число 1024 з 10-вої системи числення в 16-ву потрібно послідовно ділити 1024 та отримані частки на 16 доти, поки частка не стане меншою за 16. Остання частка і буде першою цифрою отриманого числа, залишки записані в зворотньому порядку - рештою чисел (перший залишок - остання цифра).

Переведемо:

3-тя цифра - 1024:16 = 64*16 + 0;

2-га цифра - 64:16 = 4*16 + 0;

1-ша цифра - 4<16, тому ділення завершено і 1024₁₀ = 400₁₆.

Запишемо алгоритми мовами програмування.

Free Pascal:

Var M, Z : 2..16;
         Ch : 0..2000000000;
           N : String[31];

Begin

 ReadLn (M);

 Read (Ch);

 N := '';

 Repeat

  Z := Ch mod M;

  Ch := Ch div M;

  If Z < 10

   Then N := Chr (48+Z) + N

   Else N := Chr (55+Z) + N;

 Until Ch = 0;

 Write(N);

End. 

C++:

#include <iostream>
#include <string.h>
using namespace std;

int main()

{

 int m, ch, z;

 cin >> m >> ch;

 string n="";

 do

 {

 z=ch%m, ch/=m;

 char c=(z<10) ? (z+48) : (z+55);

 n=c+n;

 }

 while (ch!=0);

 cout << n;

}

Nhex

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=102)

Задача. Дано число  в системі числення з основою  m (2≤m≤16). Написати програму що переводить дане число в систему числення з основою 10.

Технічні умови. Програма читає  з клавіатури першому рядку  число  m (основу системи числення), а в другому - текстовий рядок, в якому записано саме число Ch (0≤Ch≤2+10⁹). Програма виводить на екран відповідь у вигляді десяткового числа.

Приклад.
Введення:
16
FFFF
Виведення:
65535

Розв'язання.

Переведемо число FFFF з 16-вої системи числення в 10-ву:
FFFF₁₆ = 15*16³ + 15*16² + 15*16¹ + 15*16⁰ = 15*4096 + 15*256 + 15*16 + 15*1 = 61440 + 3840 + 240 + 15 = 65535.
Отже, потрібно знайти суму добутків цифр числа і відповідних розрядів. 
Для реалізаці алгоритму нам потрібні цифри введеного числа переведені з символьного типу в числовий:'0' - 0, ..., '9' - 9, 'A' - 10, ..., 'F' - 15.
Відповідно Ch[i], ..., Ch[3], Ch[2], Ch[1].
(Потрібно врахувати, що в Pascal символи рядкового типу нумеруються з 1, а в C++ - з 0.)
Для переведення будемо використовувати коди символів (коди є числами) врахувавши різницю між кодом і числом яке він позначає. Коди символів: '0'..'9' - 48..57, 'A'..'F' - 65..70. Переведену цифру будемо записувати в зміннну Z.
Наприклад:
Ch[i] = '8':  Z = код('8') - 48 = 56 - 48 = 8;
Ch[i] = 'D': Z = код('D') - 55 = 68 - 55 = 13.
Розряд: m^i-1, ..., m², m¹, m⁰, будемо зберігати в змінній Rd.
Відповідно: Rd = 1; Rd = Rd*m = m¹; Rd = Rd*m = m*m = m²; ...
Шукане число будемо зберігати в змінній N.

Запишемо алгоритми мовами програмування.

Free Pascal:

Var M, Z : 2..16;
         Ch : String[31];
            I : Byte;
   N, Rd : LongInt;
Begin
 ReadLn (M);
 Read (Ch);
 N := 0;
 Rd := 1;
 For I:=Length(Ch) DownTo 1 Do Begin
  If Ch[I]<='9'
   Then Z := Ord(Ch[I])-48
   Else Z := Ord(Ch[I])-55;
  N += Z*Rd;
  Rd *= M;
 End; 
 Write(N);
End.

C++:

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
 int m, z;
 char ch[32];
 cin >> m >> ch;
 int n=0, rd=1;
 for (int i=strlen(ch)-1; i>=0; i--)
 {
 z=(ch[i]<='9') ? (ch[i]-48) : (ch[i]-55);
 rd*=(n+=z*rd, m);
 }
 cout << n;
}

Worms

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=101)

Задача. Черв’ячки - цікаві тваринки. Якщо їх залишити вдвох і не турбувати, то через 10 хвилин їх стане четверо, через 20 хвилин – восьмеро, через 30 хвилин – 16 штук. Скільки їх стане через N (N>1) хвилин? Зауваження: на появу нових черв’ячків потрібно рівно 10 хвилин. Всі нові черв’ячки появляються одночасно.

Технічні умови. Програма зчитує з клавіатури ціле число N – кількість хвилин. Програма виводить на екран одне ціле число – кількість черв’ячків через вказаний час.

Приклади.

Введення> 5

Виведення>  2

Введення> 48

Виведення> 32

Розв'язання

Запишемо відповідність:

0 хвилин - 2 черв'ячки, 10 - 4, 20 - 8, 30 - 16, ...

Так як в інтервалах: [0, 10), [10, 20), [20, 30), [30, 40), ... кількість черв'якчків не змінюється то поділивши хвилини на 10 і кількість черв'ячків подавши у вигляді степенів(^) двійки отримаємо нову відповідність: 0 хв. - 2¹ черв., 1 - 2², 2 - 2³, 3 - 2⁴, ... Бачимо що: [N/10] хвилин - 2^N+1 черв'ячків, де [] - ціла частина.

Запишемо алгоритми мовами програмування.

Free Pascal:

Var N : Integer;
Begin
 Read (N);
 Write (Round(Exp((N div 10 + 1)*ln(2))));
End.

Примітка: в Pascal відсутня функція степеня, тому степінь подано через властивості логарифмів.

C++:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  int n;
  cin >> n;
  cout << pow(2.0,n/10+1);
}

Vinni

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=100)

Задача. Вінні Пух любить складати віршики говорячи речення задом наперед. Якось йому попалось довге складне речення і він забув свій віршик, пробуючи його виговорити. Складіть програму, яка б допомагала ведмедику легко складати такі віршики. Зауваження: віршик може складатись як із 1 слова, так і з декількох, розділених пропусками.

Технічні умови. Програма зчитує з клавіатури стрічку-віршик. В кінці віршика ніколи не ставиться крапка. Довжина віршика менша за 255 символів. Програма виводить на екран стрічку, яку отримано внаслідок повороту.

Приклади.

Введення>роза
Виведення>азор

Введення>Все медведи любят мед
Виведення>дем тябюл идевдем есВ

Розв'язання

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

Запишемо алгоритми мовами програмування.

Free Pascal:

Var S : String;

    I : Byte;

Begin

 Read (S);

 For I:=Length(S) DownTo 1 Do

  Write (S[I]);

End.

C++:

#include <iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

int main()

{

 char s[255];

 gets(s);

 for (int i=strlen(s)-1; i>=0; i--)

  cout << s[i];

}

Slon

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=99)

Задача. Петрик П'яточкін вишикував у рядок слоненят та рахує їх по кожному кольору окремо. Всього буває 8 кольорів слоненят. У рядок вишикувались N (10<N<999) слоненят. Скільки слоненят кожного кольору стоїть перед Петриком? Бажано їх порахувати пройшовши всього один раз перед строєм.

Технічні умови. Програма зчитує з клавіатури ціле число N - кількість слоненят, потім, через пропуск - N чисел від 1 до 8, якими ми пронумеровали кожен колір в тій послідовності, в якій вони потрапляли на очі Петрику від початку рядка. Програма виводить на екран в один рядок через пропуски пари цілих чисел, де перше число пари - колір, а друге - кількість слоненят такого кольору.

Приклад.

Введення>12 1 1 2 3 3 1 5 6 8 7 6 5 

Виведення> 1 3 2 1 3 2 4 0 5 2 6 2 7 1 8 1

Розв'язання.

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

Запишемо алгоритми мовами програмування.

Free Pascal:

Var N, K : 0..999;

      Ks : Array [1..8] Of 0..999;

Begin

 Read(N);

 For N := 1 To N Do Begin 

  Read (K);

  Inc(Ks[K]);

 End;

 For K := 1 To 8 Do

  Write (K,' ',Ks[K],' ');

End.

C++:

#include <iostream>
using namespace std;
int main()
{
  int n, k, c[]={0,0,0,0,0,0,0,0};
  cin >> n;
  for (int i=0; i<n; i++)
  {
   cin >> k;
   c[k-1]++;
  }
  for (int i=0; i<8; i++)
   cout << i+1 << ' ' << c[i] << ' ';
}

Сircle

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=97)

Задача: Василько взяв великого циркуля та зайшов до кімнати, підлога якої являє собою квадрат зі стороною рівною M (M>1м). Поставивши циркуль на перетині діагоналей цього квадрата він почав будувати кола. Перше коло мало діаметр 10 см., друге – 30, трете – 40, четверте – 60, п’яте – 70, шосте – 90 см. і т.д. Скільки повних кіл може побудувати в цій кімнаті Василько?

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

Приклади:

Введення> 240
Виведення> 16

Введення> 380
Виведення> 25

Розв'язання

Переведемо послідовність радіусів в дециметри і запишемо викресливши зайві числа: 1, 2, 3, 4, 5, 6, 7, 8, 9, ... .

Бачимо, що послідовність утворена з ряду натуральних чисел виключенням чисел, які передують числам кратним 3.

Потрібно підрахувати кількість її членів. Рахуємо:

З викресленими від 1 до M їх буде M.

Викреслених від 1 до M - (M+1)\3, де \ - ціла частина.

(1+1)\3 - 0, (2+1)\3 - 1, (3+1)\3 - 1,  (4+1)\3 - 1, (5+1)\3 - 2, ... .

Без викреслених: M - (M+1)\3.

Запишемо алгоритми мовами програмування.

Free Pascal:

Var M : Integer;

Begin

 Read(M);

 M := M div 10;

 Write(M - (M+1) div 3);

End.

C++:

#include <iostream>

using namespace std;

int main()

{

  int m;

  cin >> m;

  m = m/10;

  cout << m - (m+1)/3;

}

Leopold

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=98)

Задача. Кіт Леопольд пішов на рибалку та наловив риби. Кожну рибу він старанно зважив. Перша риба (найменша), яку він зважував важила рівно L грам. Кожна наступна рибина була на К грамів важча за попередню. Скільки заважила вся риба, яку наловив Леопольд, якщо відомо, що спіймав він N (N>0) риб?

Технічні умови. Програма зчитує з клавіатури ціле число N - кількість рибин, потім, через пропуск, L - маса першої риби в грамах та, через пропуск - К - на скільки кожна наступна рибина важча від попередньої. Програма виводить на екран одне ціле число - масу всієї упійманої риби в грамах.

Приклади.

Введення> 10 250 100
Виведення> 7000

Введення> 12 100 150
Виведення> 11100

Розв'язування.

Задача зводиться до знаходження суми n перших членів арифметичної прогресії за формулою: Sn = (2*a1+(n-1)*d)*n/2. Де: a1 = L, n = N, d = K.

Запишемо алгоритми мовами програмування.

Free Pascal:

Var N, L, K : Integer;
Begin
 Read(N, L, K);
 Write ((2*L + K*(N-1))*N div 2);
End.

C++:

#include <iostream>
using namespace std;
int main()
{
  int n, l, k;
  cin >> n >> l >> k;
  cout << (2*l + k*(n-1))*n / 2;
}