понедельник, 11 апреля 2011 г.

Типы данных

Целые числа.

Задача A. Кролики
Пусть есть n клеток и m зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке (по принципу Дирихле).
В первой строке входного файла записаны два натуральных числа n и m. (1 ≤ n, m ≤ 109).

  1.   int n, m, count = 0;
  2.   cin >> n >> m;
  3.  
  4.   count = m / n;
  5.   m %= n;
  6.   if (m)
  7.     count++;
  8.   cout << count;
* This source code was highlighted with Source Code Highlighter.


Задача B. Сумма от 1 до N
Сумму всех целых чисел от 1 до 100 можно посчитать при помощи хитрого приема.
Разобьем все числа по парам 1 и 100, 2 и 99, 3 и 98 и т.д. Сумма каждой пары 101. Пар всего 100 пополам (50). Поэтому сумма равна

 форм
Дано одно целое число N. Гарантируется, что ответ "помещается" в тип long long (в Си). Найти сумму всех целых чисел от 1 до N.

  1. long long sum_modul(long long n)
  2. {
  3.   if (n&1)
  4.     return (n+1)/2*n;
  5.   else
  6.     return n/2*(n+1);
  7. }
  8. int main()
  9. {
  10.   freopen("input.txt","r",stdin);
  11.   freopen("output.txt","w",stdout);
  12.  
  13.   long long n, s;
  14.   cin >> n;
  15.   if (n > 0)
  16.     s = sum_modul(n);
  17.   else
  18.     s = -sum_modul(-n) + 1;
  19.  
  20.   cout << s;
  21.   return 0;
  22. }
* This source code was highlighted with Source Code Highlighter.

P.S.
1) Важно заметить, что в условии задачи гарантируется, что лишь ответ помещается в тип long long. А на промежутчные вычисления такой гарантии не дается, поэтому в функции sum_modul  формулу подсчета стоит модифицировать так, чтобы сначала происходило деление на 2, а только потом умножение. Таким образом мы предохраняемся от переполнения типа. Целочисленно делить на 2 без потерь, конечно, нужно четное число, поэтому заранее проверяем в строке 3, что является четным: само значение n или n+1.
2) Второй подводный камень условия – нет гарантии исключения отрицательности конечного значения N. Поэтому в строках 16 и 18 учитываем особенности знака.


Задача C. k-я секунда суток
Идёт k-я секунда суток. Определите, сколько целых часов h и целых минут m прошло с начала суток.
На вход программе подается целое число k (0 ≤ k ≤ 86399). Выведите на экран фразу:
It is ... hours ... minutes.
Вместо многоточий программа должна выводить значения h и m, отделяя их от слов ровно одним пробелом.

  1.   int s, h, m;
  2.   cin >> s;
  3.   s--;
  4.   h = s / 3600;
  5.   m = (s % 3600)/ 60;
  6.   cout << "It is " << h << " hours " << m << " minutes.";
* This source code was highlighted with Source Code Highlighter.

P.S. Нужно обратить внимание, что в условии задачи просится найти сколько прошло полных часов и минут, т.е. если идет 60-ая секунда, то это значит, что прошло полных только 59 секунд, но никак не минута. Поэтому первым делом в 3-ей строке кода избавляемся от “идущей” незавершившейся секунды:  s -- .

Задача D. Часовая стрелка
Часовая стрелка повернулась с начала суток на d градусов. Определите, сколько сейчас целых часов h и целых минут m. На вход программе подается целое число d (0 ≤ d < 360). Выведите на экран фразу:
It is ... hours ... minutes.
Вместо многоточий программа должна выводить значения h и m, отделяя их от слов ровно одним пробелом.

  1.   int d, m, h;
  2.   cin >> d;
  3.   m = d * 2;
  4.   h = m / 60;
  5.   m %= 60;
  6.   cout << "It is " << h << " hours " << m << " minutes.";
* This source code was highlighted with Source Code Highlighter.


Задача E. Без циклов
В книге на одной странице помещается k строк. Таким образом, на 1-й странице печатаются строки с 1-й по k-ю, на второй — с (k+1)-й по (2k)-ю и т. д. Напишите программу, по номеру строки в тексте определяющую номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.
На вход программе подаются число k — количество строк на странице и число n — номер строки в тексте (1 ≤ k ≤ 200, 1 ≤ n ≤ 20000).

  1.   int k, n, page, line;
  2.   cin >> k >> n;
  3.   page = (n - 1) / k + 1;
  4.   line = (n - 1) % k + 1;
  5.   cout << page << ' ' << line;
* This source code was highlighted with Source Code Highlighter.


Задача F. Два момента времени
Даны значения двух моментов времени, принадлежащих одним и тем же суткам: часы, потом минуты и секунды для каждого из моментов времени. Известно, что второй момент времени наступил не раньше первого. Определите, сколько секунд прошло между двумя моментами времени.
В первой строке входных данных находятся три целых числа — часы, минуты и секунды первого момента времени. Во второй строке — три числа, характеризующие второй момент времени. Число часов лежит в диапазоне от 0 до 23, число минут и секунд — от 0 до 59.

  1.   int h1, m1, s1;
  2.   cin >> h1 >> m1 >> s1;
  3.   int h2, m2, s2;
  4.   cin >> h2 >> m2 >> s2;
  5.  
  6.   s1 = s1 + m1*60 + h1*3600;
  7.   s2 = s2 + m2*60 + h2*3600;
  8.   cout << s2 - s1;
* This source code was highlighted with Source Code Highlighter.

2 комментария:

  1. Хорошие задачки, я совсем уже забыл олимпиадное школьное программирования. Задачки простые и тривиальные, но мозг отвык их решать, поэтому пришлось немного его поразмять.

    ОтветитьУдалить
  2. Этот комментарий был удален автором.

    ОтветитьУдалить