Регистрирайте сеРегистрирайте се

Национална Олимпиада, 2 кръг, група B (2008), решения


 
   Форум за математика Форуми -> Информатика/Компютри
Предишната тема :: Следващата тема  
Автор Съобщение
krassi__holmz
Начинаещ


Регистриран на: 01 Mar 2008
Мнения: 7

Репутация: 4Репутация: 4Репутация: 4Репутация: 4
гласове: 3

МнениеПуснато на: Sun Mar 02, 2008 12:05 am    Заглавие: Национална Олимпиада, 2 кръг, група B (2008), решения

Национална Олимпиада, 2 кръг, група B (2008)

Този пост е с решения на задачите. Който има въпроси и допълнения, да пише.

Задачите са тук:
http://keleved.com/2008/noi2/NOI_2008_IIkrag_publ.pdf

1. Трябва ни бърз начин, по който да намираме к-тата цифра след десетичната запетая на правилна дроб a/b.
Нека
a/b = 0.xyz

Тогава:

x = (10 * a) div b;
y = 10 * (10 * a % b) div b;
z = 10 * (10^2 * a % b) div b;
...
k-тата цифра е 10*(10^(k-1) * a % b) div b.

В този случай к е от висок порядък (10^18 ) , следователно ни трябва бърз начин за повдигане в степен по модул.

Да разгледаме двоичното представяне на к:
[tex]k = \sum_{i = 0}^t 2^ik_i[/tex]
Тогава
[tex]a^k%b = a^{(2^0)}^{k_0}a^{(2^1)}^{k_1}...a^{(2^t)}^{k_t}[/tex]

Това е и ключът към бързото повдигане на степен.

И накрая остава да се напише кода:
Код:

/*
dfrac.cpp
by krassi_holmz
2008
*/
#include <stdio.h>

#define num long long

num modpow(num a, num k, num b){
   //returns a^k % b
   num r = 1;
   for(int i = 0; (1LL << i) <= k; i++){
      if((k >> i) % 2){
         r *= a;
         r %= b;
      }
      a *= a;
      a %= b;
   }
   return r;
}

num gcd(num a, num b){
   if(a == 1 || b == 1) return 1;
   if(a == 0) return b;
   if(b == 0) return a;
   if(a > b) return gcd(a % b, b);
   else return gcd(b % a, a);
}

int main(){
   num a, b, k, p, gc, newa;
   scanf("%lld %lld %lld %lld", &a, &b, &k, &p);
   a %= b;
   gc = gcd(a, b);
   a /= gc;
   b /= gc;
   /*
   now a and b are coprime
   first digit - 10a/b
   second 10*10a/b
   kth - 10*(10^k-1)a/b
   */
   newa = modpow(10, k - 1, b);
   newa *= a;
   newa %= b;
   /*
   now we should output the first p digits of newa/b
   */
   for(int i = 0; i < p; i++){
      printf("%d", (int)((10*newa)/b));
      newa *= 10;
      newa %= b;
   }
   printf("\n");

   return 0;
}

------------------------------------------------
2. За тази задача не съм сигурен какво точно ще е авторското решение, но предлагам нещо бързо, което работи вярно със огромна вероятност - хеширане.
Идеята е така да се хешират плочките, че хеш - стойностите на 2 еднакви (завъртяни и/или обърнати) плогки да са еднакви.
Когато хешираме едномерни последователности - например низове, често използваме една много удобна хеш функция:
[tex]H(A) = \sum_{i = 0}^l A_iP^i%M[/tex], където M и P са прости числа, M >> P.
Подобна функция може да се състави и за матрици:
[tex]H(A) = \sum_{i = 0}^n\sum_{j = 0}^m A_{\{i,j\}}P^iQ^j%M[/tex]
За да отразим еднаквите плочки, ще модифицираме малко хеш-функцията - трикът е да не умножаваме само по P^iQ^j, а и по съответните коефициенти за клетките, получени след отражение и ротация на Аij.
След като намерим хеш-стойността на всяка плочка, пъхаме я в един std::set и най-накрая броим различните елементи в сет-а.

Ето кода:
Код:

/*
plates.cpp
by krassi_holmz
2008
*/
#include <stdio.h>
#include <set>
using namespace std;

#define num long long
#define MAXN 32

//hash - specific defines
#define M 10000019LL
#define P 997LL
#define Q 1009LL

num PQ[MAXN][MAXN];   //PQ[i][j] stores P^i * Q^j mod M

int n, a[MAXN][MAXN];

num hash(){
   /*
   hashes the content of a.
   Standard 2D hash function is
   H = Sum a[i][j] P^i Q^j, but this
   function distinguishes every matrix.
   We need to make the simular matrixes undestinguishable, so
   we will add the corresponding hashes:
   H = Sum a[i][j] (P^(i) Q^(j) + P^(j) Q^(i) + P^(n - 1 - i) Q^j + P^j Q^(n - 1 - i) + ...)
   */
   int i, j, ip, jp;
   num res = 0;
   for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
         if(a[i][j]){
            ip = n - 1 - i;
            jp = n - 1 - j;
            res += PQ[i][j] + PQ[j][i] + PQ[ip][j] + PQ[j][ip] + PQ[i][jp] + PQ[jp][i] + PQ[ip][jp] + PQ[jp][ip];
            res %= M;
         }
   return res;
}

void PQinit(){
   //initializes PQ matrix
   int i, j;
   PQ[0][0] = 1;
   for(i = 1; i < MAXN; i++){
      PQ[i][0] = P * PQ[i - 1][0];
      PQ[i][0] %= M;
   }
   for(j = 1; j < MAXN; j++)
      for(i = 0; i < MAXN; i++){
         PQ[i][j] = Q * PQ[i][j - 1];
         PQ[i][j] %= M;
      }
}

int main(){
   set<num> s;
   int i, j, p, m;
   char ch;
   PQinit();
   scanf("%d %d", &m, &n);
   for(p = 0; p < m; p++){
      for(i = 0; i < n; i++)
         for(j = 0; j < n; j++){
            scanf(" %c", &ch);
            a[i][j] = ch - '0';
         }
      s.insert(hash());
   }
   printf("%d\n", s.size());
   return 0;
}

------------------------------------------------
3. Стандартна задача - решава се с динамично оптимиране. Нека A[0..n-1] са стойностите на марките и с C[n] означим минималния брой марки за получаване на n.
Очевидно C[n] се е получило като към C[n - k] се е прибавило 1, където марката k участва в C[n]. Оттук:
C[n] = 1 + min(p element of A) (C[n - p]).
Началното условие е C[0] = 0.
Кодирането е праволинейно:
Код:

/*
stamps.cpp
by krassi_holmz
2008
*/
#include <stdio.h>

#define MAXN 3050
#define MAXS 5050

int a[MAXN], c[MAXS];

int main(){
   int i, j, s, n, m;
   scanf("%d %d", &s, &n);
   for(i = 0; i < n; i++){
      scanf("%d", &a[i]);
   }
   c[0] = 0;
   for(i = 1; i <= s; i++){
      c[i] = i;   //using only ones
      for(j = 0; j < n; j++)
         if(i - a[j] >= 0 && c[i - a[j]] + 1 < c[i])
            c[i] = c[i - a[j]] + 1;
   }
   printf("%d\n", c[s]);
   return 0;
}
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
Покажи мнения от преди:   
   Форум за математика Форуми -> Информатика/Компютри Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.