Легко бачити, що парність числа приводить до виграшу першого гравця, а не парність числа – до виграшу другого. Щоб взнати парність числа, достатньо перевірити на парність його останню цифру.
#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;}
}
}
}
Для нашої задачі це буде виглядати так:
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;}
}
}
}
