Задача A-Гра
Легко бачити, що парність числа приводить до виграшу першого гравця, а не парність числа – до виграшу другого. Щоб взнати парність числа, достатньо перевірити на парність його останню цифру.
#include<iostream> #include<cstdio> #include<fstream> using namespace std; int main() { char s[1001]; int k,n,j; ifstream fi; fi.open("a.txt"); ofstream fo; fo.open("a.out"); fi>>k; for(int i=0;i<k;i++) { fi>>s; j=0; while(s[j]!='\0')j++; if(s[j-1]%2==0)fo<<1;else fo<<2; } }
Слід зауважити, що у С++ реалізовано багато засобів отримати останній символ рядка. Вхідний тест до цієї задачі був дещо «авантюрний» і спровокував багато нарікань. На мою думку, будь-який вхідний тест повинен продемонструвати формат вхідних та вихідних даних, а не вказувати на правильне рішення.
Задача B-Кількість трикутників
Розв’язок, який має складність О(N) у цій задачі проходить усі тести і його реалізація досить проста. До багатьох задач можна застосувати такий підхід: прорахувати декілька простих випадків, по отриманій послідовності побудувати рекурентне співвідношення. Для нашої задачі це буде виглядати так: N=1 трикутників 1 N=2 трикутників 5 N=3 трикутників 14 Звідси можна помітити таке: 5=22+1 а 14=32+5, тому для і-го кроку маємо: S=S+i2 Для того, щоб отримати шукану кількість трикутників, потрібно знайти суму такого виразу: S=1+4+9+...+n2. Якщо згадати математику, то сума такої послідовності рівна: S=n∙(n+1)∙(n+2)/6. Програмна реалізація така: #include <stdio.h> int main() { long long s=1; int n; scanf("%d",&n); s = s*n*(n+1)*(2*n+1)/6; printf("%I64d\n",s); }
Задача C-Коефіцієнт
Перемножим три многочлени: (1+x+x2+...+xn)∙(1+x+x2+...+xn)∙(1+x+x2+...+xn). Без зведення подібних дістанемо суму добутків виду: xp∙xq∙xr, де p, q, r цілі числа, які задовольняють умову: 0≤p≤n, 0≤q≤n, 0≤r≤n. Коефіцієнт при xn
буде лише при умові: p+q+r=n, це рівняння в цілих числах і має n+1
розв’язок при р=0, n розв’язків при p=1, та n-1 розв’язок при p=2 і т.
д. Отже шуканий коефіцієнт рівний: n+1+n+n-1+n-2+...+1=(n+1)∙(n+2)/2.
#include <stdio.h> int main() { long long s=1; int n; scanf("%d",&n); s = s*(n+1)*(n+2)/2; printf("%I64d\n",s); }
Задача D-Кількість прогресій
Нехай маємо число n. Кількість прогресій, які містять одне число, яке відмінне від нуля, рівне: n div 1, кількість прогресій, які містять два числа, що теж відмінні від нуля, буде рівна: n div 2, аналогічно отримаємо такі числа: n div 3, n div 4,…, n div n. Просумувавши, отримаємо шукану відповідь. Програмна реалізація на С++ така: #include<iostream> #include <stdio.h> #include <math.h> using namespace std; int main() { long long i,n,n1,s=0; cin>>n; n1 = (int)sqrt(n); for(i=1;i<=n1;i++) s += n/i; s = 2*s - n1*n1; cout<<s<<'\n'; }
Задача E-Математичні мандри
Це класична задача на динаміку. Тільки у ній потрібно по результату (кількість шляхів) – отримати номер комірки двомірної матриці. Оскільки розміри матриці невеликі, то можна спочатку заповнити матрицю, а потім шукати відповідну комірку. Один із варіантів реалізації на С++ такий: #include<iostream> #include<memory.h> using namespace std; int main() { long long a[21][21]; int n; memset(a,0,sizeof(a)); cin>>n; if(n==1)cout<<'1'<<' '<<'2'<<'\n';else { for(int i=1;i<21;i++)a[i][1]=a[1][i]=1; for(int i=2;i<21;i++) for(int j=2;j<21;j++) { a[i][j]=a[i][j-1]+a[i-1][j]; if (a[i][j]==n){cout<<i<<' '<<j<<'\n'; i=21;break;} } } }
|