 Регистрирайте се
Национална Олимпиада, 2 кръг, група B (2008), решения
|
| Предишната тема :: Следващата тема |
| Автор |
Съобщение |
krassi__holmz
Начинаещ
Регистриран на: 01 Mar 2008
Мнения: 7
  
гласове: 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;
}
|
|
|
| Върнете се в началото |
|
 |
Реклама
|
| Пуснато на: Заглавие: Реклама |
|
|
|
|
|
| Върнете се в началото |
|
|
|
|
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
|
|
Меню
