2014 оны улсын мэдээлэл зүйн олимпиадын 2 ын даваа багш нарын бодлогууд

За сайн байцгаана уу, багш нарын бодлогийн анализийг хийх гэж үзлээ хэхэ

Бодлогуудын өгүүлбэрийг энд дараад харж болно.



Эхний бодлого "Геометр прогресс" -ийн хувьд (1<=k<m<=100)  тул k аас m дүгээр тоонуудаа үүсгэж байгаад өгөгдсөн N ширхэг тооноосоо хайгаад тоолж болно. N<=100000 тул шууд хайхад амжина. Гэхдээ N тоонуудаа эрэмбэлж байгаад бинар хайлт хийгээд тоолвол илүү хурдасна. Бичсэн source оо хамт хийв.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

long long member, A[100005];
int n, b, q, k, m, sum, i;

bool search(long long num)
{
  int x, y, z;    
   
  x = 0;
  y = n-1;
  while (x <= y)
  {
    z = (x+y)/2;
    if (A[z] == num) return 1;
    if (num < A[z]) y = z-1;
      else x = z+1;  
  }  
  return 0;
}

main()
{
  freopen("geometer.in", "r", stdin);
  freopen("geometer.out", "w", stdout);
 
  scanf("%d %d %d",&n,&b,&q);
  scanf("%d %d",&k,&m);
  for (i=0; i<n; i++)
    scanf("%lld",&A[i]);
  sort(A,A+n);
  member = b;
  for (i=2; i<=k; i++)
    member = member*q;
 
  sum = 0;
  for (i=k; i<=m; i++)
  {
    if (search(member)) sum++;
    member = member*q;
    if (member > A[n-1]) break;
  }
  printf("%d\n",sum);

}

Дараагийн бодлого "16 суурьтай палиндром тоо" -н дээр өгөгдсөн тоон дээрээ 1 ээс эхлээд ижил хэмжээгээр нэмж үүссэн тоогоо 16 тын тооллын системд шилжүүлээд палиндром эсэхийг шалгаад дараа нь хасч шалгаад явахад  хугацаандаа амжина гэж бодож байна.

Жишээ нь : n тоо өгөгдөх үед n+1 -ийг шалгаад дараа нь n-1 ииг шалгаад дараа нь n+2 , n-2 , n+3 гэх мэт шалгаад хамгийн эхэнд бодлогийн нөхцөлийг хангасан нь манай шийд болно гэсэн үг.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

vector <int> a;    

bool checker(int x)
{
  int i, l;
  a.clear();
  while (x != 0)   
  {
    a.push_back(x%16);    
    x = x/16;
  }
  l = a.size();
  for (i=0; i<l/2; i++)
    if (a[i] != a[l-i-1]) return 0;
  return 1;  
}

main()
{
  int i, t, num, j;      
      
  freopen("palind16.in", "r", stdin);
  freopen("palind16.out", "w", stdout);

  scanf("%d", &t);
  for (i=1; i<=t; i++)  
  {
    scanf("%d", &num);  
    j = -1;
    while (i)
    {
      j++;
      if (checker(num+j)) { printf("%d\n", num+j); break;}
      if (checker(num-j) && num-j>0) { printf("%d\n", num-j); break;}
    }
  }
}

Сүүлчийн бодлого "Битийн дараалал" - ын хувьд DP хэрэглэж бодож болно. A[0][i] гэдэг нь 0 оор төгссөн i урттай дарааллын тоо ба A[1][i] нь 1 ээр төгссөн i урттай дарааллын тоог хадгалдаг гэж үзъе. Эндээс манай хариу A[0][N]+A[1][N] байна гэсэн үг. A[0][i] нь i-1 урттай 0 ээр төгссөн боломжуудын ард 0 ийг нэмж боломж үүсгэж болно. Мөн i-1 урттай 1 ээр төгссөн боломжуудын ард 0 ийг нэмж боломж үүсгэж ба эндээс боломж давхардаж тоологдохгүй нь харагдаж байна. Иймд A[0][i]=A[0][i-1]+A[1][i-1] гэсэн үг. Харин A[1][i] нь i-1 урттай 0 ээр төгссөн боломжуудын ард 1 ийг нэмж боломжуудыг үүсгэж болно. Харин i-1 урттай 1 ээр төгссөн боломжуудын ард 1 нэмж боломж үүсгэж болохгүй. Учир нь бодлогийн нөхцөлд 1 -ийн цифр дараалж орж болохгүй. Иймд A[1][i]=A[0][i] гэсэн үг. Эндээс бичээд үзэхэд N тооны хувьд бодлогийн хариу N+2 дахь фибоначчийн харагдана. Гэхдээ (1<=N<=100) тул урт тооны үйлдэл хийнэ.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int A[3][50]={0}, n, i, j, i0, i1, i2, d, dig0, dig1, dig2, r, ii;

main()
{
  freopen("bit.in", "r", stdin);
  freopen("bit.out", "w", stdout);
  
  scanf("%d",&n);
  
  A[0][0] = 1; dig0 = 0;
  A[1][0] = 1; dig1 = 0;
  i0 = 0; i1 = 1; i2 = 2;
  for (i=0; i<n; i++)
  {
    r = 0;
    dig2 = max(dig0, dig1);
    for (j=0; j<=dig2; j++)  
    {
      A[i2][j] = (A[i1][j] + A[i0][j] + r)%10;
      r = (A[i1][j] + A[i0][j] + r)/10;  
    }
    if (r) { dig2++; A[i2][dig2]=r; }
    ii = i0; i0 = i1; i1 = i2; i2= ii;
    d = dig0; dig0 = dig1; dig1 = dig2; dig2 = d;
  }
  for (i = dig1; i>=0; i--)
    printf("%d",A[i1][i]);
}

Анх удаагаа анализ хийж байгаа болхоор алдаа гаргасан байж магад .

Бичсэн Б. Гантүшиг ;)