Решение (с длинной арифметикой)

#include<fstream>

using namespace std;

struct rec {

int size;

int number[100];

};

int n, k, startpos, endpos;

rec data[301];

void calc (int pos, int b, int e) {

int carry = 0;

for (int j=0; ;j++) {

   for (int l=b; l<e; l++) carry+=data[l].number[j];

   if (!carry) break;

   else {

       data[pos].number[j] = carry%10;

       data[pos].size++;

   }

   carry /= 10;

}

}

int main() {

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

scanf ("%d %d", &k, &n);

if (k==1) { printf ("1"); return 0; }

for (int i=0; i<=n; i++) {

   if (i<=k) {

       data[i].number[0] = 1;

       data[i].size = 1;

   } else {

       data[i].number[0] = 0;

       data[i].size = 1;

   }

}

for (int i=2; i<=n; i++) {

   if (i<=k) {startpos = 0; endpos = i;}

   else {endpos = i; startpos = endpos - k;}

   calc (i, startpos, endpos);

}

if (data[n].number[data[n].size-1]==0)

   data[n].size-=2;

for (int i=data[n].size; i>-1; i--)

   printf ("%i", data[n].number[i]);

}

 

Задача №276.  Лестница из кубиков (acm.timus.ru)

Ограничение времени: 1.0 секунды

Ограничение памяти: 64 МБ

У маленького мальчика есть набор из N кубиков (5 ≤ N ≤ 500). Из этих кубиков можно сложить различные лестницы. Лестницы имеют ступени различного размера, следующие в порядке возрастания этого размера (обратите особое внимание на то, что лестница не может иметь две одинаковые ступени). Каждая лестница должна иметь минимум две ступени, и каждая ступень должна состоять минимум из одного кубика. На рисунке приведены примеры лестниц для N=11 и N=5:

Рис. 51. Иллюстрация к задаче «Лестница из кубиков»

Найдите число Q различных лестниц, которые маленький мальчик может построить ровно из N кубиков.

Исходные данные

Число N

Результат

Число Q

Пример

исходные данные	результат
212	995645335

Источникзадачи: Ural State University Internal Contest ‘99 #2

Решение (без длинной арифметики)

#include<iostream>

using namespace std;

int main(){

short n;

cin >> n;

long long q[501] = {1,};

for (short i = 1; i <= n; i++)

   for (short j = n; j >= i; j--)

       q[j] += q[j-i];

cout << q[n]-1;

return 0;

}

Задача №277.  Без двух нулей подряд

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких, что их запись не содержит двух подряд идущих нулей.

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

Во входном файле INPUT.TXT записаны два натуральных числа N и K в десятичной системе счисления (2 ≤ K ≤ 10; 2 ≤ N; 4 ≤ N+K ≤ 18).

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

В выходной файл OUTPUT.TXT необходимо вывести целое число в десятичной записи – ответ на задачу.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	2 10	90
2	4 2	5
3	6 3	328

Решение

Для решения данной задачи используем метод динамического программирования. Пусть d[i] - количество чисел, состоящих ровно из i цифр и оканчивающихся на цифру, отличную от нуля. Аналогично, обозначим через d0[i] количество i-значных чисел, оканчивающихся на нуль. При этом будем рассматривать только те числа, которые не содержат в своей записи двух нулей подряд. Так же не будем рассматривать числа с лидирующими нулями, даже в том случае, когда i=1 (так как у нас n>1). Тогда очевидно, что d[1]=k-1 и d0[1]=0. Теперь мы можем выразить d[i] и d0[i] через d[i-1] и d0[i-1] следующим образом: d[i] = (d[i-1]+d0[i-1])*(k-1), d0[i] = d[i-1]. Используя данные рекуррентные соотношения, мы можем линейно, пробегая по i от 2 до n, вычислить d[n] и d0[n]. Ответом на задачу будет значение d[n]+d0[n]. Вышеописанный алгоритм решения представим в следующей форме:

#include <iostream>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, k, d[110], d0[110];

cin >> n >> k;

d[1] = k - 1;

d0[1] = 0;

for (int i = 2; i <= n; i++){

   d[i] = (d[i-1] + d0[i-1]) * (k - 1);

   d0[i] = d[i-1];

}

cout << d[n] + d0[n];

}

Использование массивов в данной задаче так же не обязательно, так как вычисляемые значения на i-м шаге зависят только от (i-1)-го шага.

#include <fstream>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, k, d1, d2, d3;

cin >> n >> k;

d2 = k-1;

d1 = 0;

for (int i = 2; i <= n; i++){

     d3 = (d1 + d2)*(k-1);

     d1 = d2;

     d2 = d3;

}

cout<<d2+d1;

}

Задача №278.  Волосатый бизнес (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на пиво и сигареты. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы произвольной длины стоимостью С у.е. за каждый сантиметр. Так как волосяной рынок является очень динамичным, то цена одного сантиметра волос меняется каждый день, как и курс валют. Неформал является очень хорошим бизнес-аналитиком. Он смог вычислить, какой будет цена одного сантиметра волос в каждый из ближайших N дней (для удобства пронумеруем дни в хронологическом порядке от 0 до N-1). Теперь он хочет определить, в какие из этих дней ему следует продавать волосы, чтобы по истечению всех N дней заработать максимальное количество денег. Заметим, что волосы у неформала растут только ночью и вырастают на 1 сантиметр за ночь. Следует также учесть, что до 0-го дня неформал с горя подстригся наголо, и к 0-му дню длина его волос составляла 1 сантиметр.

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

В первой строке записано целое число N (0 < N ≤ 100). Во второй строке через пробел заданы N натуральных чисел, не превосходящих 100, соответствующие стоимости C[i] 1 сантиметра волос за каждый i-й день.

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

Вывести максимальную денежную сумму, которую может заработать неформал за N дней.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	5 73  31  96  24  46	380
2	10 1  2  3  4  5  6  7  8  9  10	100
3	10 10  9  8  7  6  5  4  3  2  1	55

Решение

Cдавать волосы нужно в тот день, когда цена максимальна среди оставшихся дней. Т.е. до окончания срока каждый раз нужно находить максимальный элемент массива C[k] (k=p+1..N-1) и сдавая все волосы получать свои C[k]*(k-p) у.е. , где p - номер последнего дня cдачи волос.

#include <bits/stdc++.h> //подключение ВСЕХ стандартных библиотек

#define PRICE first

#define DAY second

using namespace std;

int main(){

int n, i, sum = 0, day = 0;

cin >> n;

vector <pair <int, int>> c(n); //пары «цена – номердня»

for(i = 0; i < n; i++) {

   cin >> c[i].PRICE;

   c[i].DAY = i + 1;

}

while(c.size()){

   sort(c.rbegin(), c.rend()); //сортировка в обратном порядке

   sum += c[0].PRICE * (c[0].DAY - day);

   day = c[0].DAY;

   for(i = 1; i < c.size(); i++)

       if(c[i].DAY < c[0].DAY)

           c.erase(c.begin() + i--);

   c.erase(c.begin());

}

cout << sum;

}

Задача №279.  Призы

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

Алиса хорошо знает Боба, и для каждого приза выяснила его ценность для Боба, которая является целым положительным числом. Алиса обижена на Боба и хочет выбрать свои призы так, чтобы суммарная ценность призов, которые достанутся Бобу, была как можно меньше. При этом Алису не волнует, какие призы достанутся ей.

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x

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

Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3).

Вторая строка содержит n целых положительных чисел: a₁, a₂, …, a_n. Для каждого приза указана его ценность для Боба (1 ≤ a_i ≤ 109)

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

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

Решение

Очевидно, «лобовой» подход в решении данной задачи состоит в том, чтобы перебрать все возможные номера призов i, начиная с которых которые Алиса может выбрать (от 1 до n-k+1) свои k призов. Затем для каждого её выбора найти, на какую сумму Боб сможет выбрать призов до i, и на какую после i. Максимальное из этих двух чисел должно быть наименьшим для всех возможных вариантов. Реализация каждой проверки будет производиться циклами, которые, в свою очередь будут содержать вложенные циклы (Алиса перебирает iот 1 до n-k+1, для каждого iперебираются варианты сумм, которые наберёт Боб, затем из этих сумм ищутся максимальные и т.д.).

Это решение на олимпиаде не позволит получить много баллов за задачу. Попытаемся улучшить его временные характеристики.

#include <iostream>

#include <cstdlib>

#define SIZE 10000

using namespace std;

int main() {

unsigned int n, k, a[SIZE];

unsigned long long s[SIZE]={0,},before[SIZE]={0,},after[SIZE],

       best = 1e12;  //просто очень большое число

cin >> n >> k;

for(int i = 1; i <= n; i++){

   cin >> a[i];

   s[i] = s[i-1] + a[i];

}

for(int i = k; i <= n; i++)         

   before[i] = max(before[i-1], s[i] - s[i-k]);

   

for(int i = n – k + 1; i; i--)

   after[i] = max(after[i+1], s[i+k-1] - s[i-1]);

   

for (int i = 1; i <= n – k + 1; i++)

   best = min(best, max(before[i-1], after[i+k]));

 

cout << best;

return 0;

}

Задача №280.  K-ичные числа.

Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число правильным, если его K-ичная запись не содержит двух подряд идущих нулей. Например:

1010230 — правильное 7-значное число;

1000198 не является правильным числом;

0001235 — не 7-значное, а 4-значное число.

Даны числа N, K и M, вычислите количество правильных K-ичных чисел, состоящих из N цифр.

Ограничения: 2 ≤ N, K ≤ 10¹⁸.

Исходные данные

Числа N, K и M в десятичной записи, разделенные переводом строки.

Результат

Искомое количество в десятичной записи.

Пример

исходные данные	результат
2 10	90

Решение

#include <iostream>

using namespace std;

int a[2000], b[2000], c[2000];

int main(){

int g, n, k, i, j, m = 1, t = 2000;

cin >> n >> k;

a[t-1] = 1; b[t-1] = k - 1;

for(i = 2; i <= n; i++){

     g = 0;

     for(j = t-1; j >= t-m; j--){

           c[j]=a[j]+b[j];

           c[j]=c[j]*(k-1)+g;

           if (c[j]>9) {g = c[j]/10; c[j] = c[j] % 10;}

           else g = 0;

     a[j] = b[j]; b[j] = c[j];

     }

     if (g){

           m++;

           b[t-m] = g; c[t-m] = g;

     }

}

for(j = t - m; j < t; j++) cout << c[j];

}

Задача №281.  Счастливые билеты (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Требуется вычислить количество N - значных счастливых билетов. Напомним, что билет называется счастливым, если сумма первой половины его цифр равна сумме другой его половины. Например, билет 564159 счастливый, т.к. 5+6+4=1+5+9.

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

В единственной строке записано натуральное четное число N (N ≤ 100) – количество цифр в билете.

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

Нужно вывести одно целое число – количество N-значных счастливых билетов.

Примеры

№	Ввод	Вывод
1	4	670
2	6	55252
3	12	39581170420

Решение

Очевидно, что полный перебор всех вариантов не позволит решить поставленную задачу. Для 100-значного билета это потребует 10¹⁰⁰ степени операций. Идея решения задачи заключается в использовании суммы цифр билета. Для простоты понимания, рассмотрим 6-значные «счастливые билеты». Разделим цифры билета на две части. Если количество способов получить для трёхзначного числа сумму цифр S обозначить за N₃(S), то количество способов получить счастливый билет с такой же суммой цифр в обеих частях составляет N₃²(S)[39]. Таким образом, общее количество шестизначных счастливых билетов можно определить по формуле:

В общем виде эта формула будет выглядеть так

Таблица значений N_n(k) [8 стр. 68-70]

k	n = 1	n = 2	n = 3	n = 4
0	1	1	1	1
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20
4	1	5	15	35
5	1	6	21	56
6	1	7	28	84
7	1	8	36	120
8	1	9	45	165
9	1	10	55	220
10		9	63	282
11		8	69	348
12		7	73	415
13		6	75	480
14		5	75	540
15		4	73	592
16		3	69	633
17		2	63	660
18		1	55	670
19			45	660
20			36	633
21			28	592
22			21	540
23			15	480
24			10	415
25			6	348
26			3	282
27			1	220
28				165
29				120
30				84
31				56
32				35
33				20
34				10
35				4
36				1

Эта таблица позволяет нам вывести рекуррентную формулу. Легко увидеть, что элемент каждого следующего столбца можно определить при помощи суммы не более чем 10 элементов из предыдущего (от текущего значения kдо k-10)

Решение методом динамического программирования

class huge {

… // описание класса сверхдлинных целых huge

     // из главы «Длинная арифметика»

};

 

int main(){

int n;

cin >> n;

n /= 2;

huge dp[n+1][n*9+1];

 

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

     dp[1][i]=1;

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

     for(int j = 0; j <= i * 9; j++)

           for(int k = 0 ; k <= min(j, 9); k++)

          dp[i][j] += dp[i-1][j-k];

 

huge answer = 0;

for (int i = 0; i <= n * 9; i++)

     answer += dp[n][i]*dp[n][i];

cout << answer;

}

Решение можно еще ускорить, если учесть, что N_n(0) = N_n(9×n), N_n(1) = N_n(9×n-1) и т.д.

Задача №282.  Покупка билетов

(Лимит времени 1 секунда.Лимит использования памяти 16 Мб)

За билетами на премьеру нового мюзикла выстроилась очередь из n человек, каждый из которых хочет купить один билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким стоящим подряд людям отдавать деньги первому из них, чтобы он купил билеты на всех.

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

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит a_i секунд, на продажу двух билетов b_i секунд, трёх билетов c_i секунд. Напишите программу, которая подсчитает минимальное время, за которое можно обслужить всех покупателей.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

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

Первое число содержит количество покупателей в очереди n (1 ≤ n ≤ 5000). Далее идет n троек натуральных чисел a_i, b_i, c_i. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.

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

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

№	Ввод	Вывод
1	5 5  10  15 2  10  15 5  5  5 20  20  1 20  1  1	12
2	2 3 4  5 1  1  1	4

Решение

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

#include <iostream>

#define SIZE 5000

using namespace std;

int n, sum, i, a[SIZE][3], res[3];

 

int main(){

cin >> n;

for(i = 0; i < n; i++)

   cin >> a[i][0] >> a[i][1] >> a[i][2];

n--;

res[2] = a[n][0];

res[1] = min(res[2] + a[n-1][0], a[n-1][1]);

res[0] = min(a[n-2][2],

           min(a[n-2][1] + a[n][0],

               a[n-2][0] + res[1]));

 

for(i = n - 3; i > -1; i--){

   res[2] = min(res[0] + a[i][0],

               min(res[1] + a[i][1],

                   res[2] + a[i][2]));

   swap(res[0], res[2]);

   swap(res[2], res[1]);

}

cout<<(n > 1 ? res[0] : res[2-n]);

}

Задача №283.  Дом (Винница, 2010)

Лимит времени 1 секунды. Лимит использования памяти 128 MiB.

Новый русский Витек приватизировал участок в Междолине размером m квадратов с севера на юг и n квадратов с запада на восток. Он решил построить в пределах этого участка дом размером a квадратов с севера на юг и b – с запада на восток. Некоторые квадраты радиоактивны, и Витек не хочет на них строить дом. Кроме того, Витек хочет, чтобы расстояния от стен до границ участка выражалась целым числом квадратов. Долго выбирал он место для дома, но так и не выбрал – слишком много вариантов. А сколько? Начал наш герой считать, но не сумел – плохо математику учил. Помогите ему.

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

Напишите программу, которая считывает числа m, n, a, b, k (1 ≤ a ≤ m ≤ 5000, 1 ≤ b ≤ n ≤ 5000, 0 ≤ k ≤ m * n), где m, n – размеры участка, a и b – размеры дома, k – количество радиоактивных квадратов, а затем k неповторяющихся пар чисел i и j (1 ≤ i ≤ m, 1 ≤ j ≤ n), которые определяют координаты радиоактивных квадратов.

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

Вывести искомое количество способов расположения дома.

Пример

Ввод	Вывод
57 2 4 3 2 5 3 3 3 6	5

Решение

 

 

Комбинаторика

Комбинаторика - один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике.