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

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⁵.

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

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

Приклади