Ajattelin tehdä tällaisen ketjun. Eli ideana, että sanotaan tehtävä ja sitten seuraavien pitää coodaa se.
Sitten voidaan myös vertailla erilaisia toteutuksia ja antaa kommentteja ja parannusehdotuksia jne. :)
Aloitan:
Coodaa segmenttipuu, johon voi laittaa yksittäisiä arvoja ja josta voi kysellä summia väleiltä.
Lisäys: Voi, voi. Viisi minuuttia mennyt ja kukaan ei ole vielä koodannut. Alan jo huolestua.
Tässä N tarkoittaa lukujen määrää, laita(k, x) muuttaa kohdan k luvuksi x ja summa(a, b) laskee lukujen summan välillä a..b.
#define N (1<<20)
int p[2*N]
void laita(int k, int x) {
k += N;
p[k] = x;
for (k = k/2; k >= 1; k /= 2) p[k] = p[2*k]+p[2*k+1];
}
int summa(int a, int b) {
a += N; b += N;
int t = 0;
while (a <= b) {
if (a%2 == 1) {t += p[a]; a++};
if (b%2 == 0) {t += p[b]; b--};
a /= 2; b /= 2;
}
return t;
}Seuraava tehtävä: Toteuta lyhyt, toimiva ja tehokas koodi maksimivirtauksen laskemiseen.
Ihan hyvältä koodilta vaikuttaa. Itse olisin tehnyt summa-funktion näin:
int summa(int a, int b) {
a+=N;b+=N;
int t=0;
//while TÄSSÄ wtf?!
for(;a<=b;a>>=1,b>>=1) { //eikös näillä ole OIKEASTI joku ihan OIKEA ero vai oonko ihan väärässä nyt? no ei ole oleellisin muutos koodissa kyllä
if(a%2) t+=p[a++]; //ehkä tärkein muutos edelliseen koodiin verrattuna
if(b%2==0) t+=p[b--];
}
return t;
}Summaongelmaan parempi ratkaisu ois käyttää taulukkoa D, missä D(0)=0 ja D(i) on lukujen a1, a2, ..., ai summa. Sitten välin i..j summan saa vakioajassa laskemalla D(j)-D(i-1). Segmenttipuu on paska.
Yksittäisten arvojen "laittaminen" jää tosin puuttumaan...
#include <vector>
#include <cstring>
using namespace std;
const int N=1024;
vector<int> es[N]; // kaarten vieruslistat
int cap[N][N]; // jäännöskapasiteetit
int S,T; // alku- ja loppusolmut
bool used[N];
int dfs(int n, int f) {
if (n==T) return f;
used[n]=1;
int a=0;
for(int i: es[n]) if (!used[i] && cap[n][i] && (a=dfs(i, min(f, cap[n][i])))) {
cap[n][i] -= a;
cap[i][n] += a;
return a;
}
return 0;
}
int flow() {
int r=0;
for(int a; memset(used,0,sizeof(used)), a=dfs(S, 1e9); r+=a);
return r;
}Tehtävä: toteuta sudokun ratkaisija.
Lisäys:
Antin laita-funktion voisi mielestäni toteuttaa mukavammin näin:
void laita(int k, int x) {
for(x-=p[k+=N]; k; k/=2) p[k]+=x;
}Deffi: Ite oot paska. Segmenttipuu on hienoin juttu koko koodauksessa. Ainakin 100000x hienompi kuin KEHÄJONOT ETTÄ OO HILJAA VAAN.
Sisuaskin koodi on ehkä vielä enemmän hienoin kuin segmenttipuut (jos ajatellaan ihan tuollaista normaalia kuitenkin tai siis missä no joo ehkä tajusitte) <33333333333333 Voisin katsella tuota koko yön :333
Apua ja tuo laita-funktio. IIIIIIH <333333
Lisäys:
#include <iostream>
using namespace std;
int t[9][9];
int a1[3][3],a2[9],a3[9];
bool ratkaise(int x) {
if(x==81) return 1;
if(t[x/9][x%9]!='.') return ratkaise(x+1); //puuttui puolipiste QAQ
for(int i=1; i<10; ++i) {
int q=x/27;
int w=(x%9)/3;
if(~(a1[q][w]|a2[x/9]|a3[x%9])&1<<i) {
a1[q][w]|=1<<i;
a2[x/9]|=1<<i;
a3[x%9]|=1<<i;
t[x/9][x%9]=i;
if(ratkaise(x+1)) return 1;
a1[q][w]^=1<<i;
a2[x/9]^=1<<i;
a3[x%9]^=1<<i;
}
}
return 0;
}
int main() {
// . jos ei tiedetä lukuu
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
char q;
cin>>q;
if(q!='.') {
q-='0';
a1[i/3][j/3]|=1<<q;
a2[i]|=1<<q;
a3[j]|=1<<q;
}
t[i][j]=q;
}
}
if(ratkaise(0)) {
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
cout<<t[i][j]<<' ';
}
cout<<'\n';
}
cout<<'\n';
}
}edit1: hubs bugi
edit2: käänsin ja suoritin ja löysin bugin saankohan nyt korjaa senkin no ehkä muuten vain ärsyttäisi muita tai emt
Ihan elegantti ratkaisu kllp, plussaa siitä että rekursio hoidettu yhdellä muuttujalla eikä turhaan x:ää ja y:tä erikseen.
Seuraava tehtävä:
Uolevi on ottanut osaa kukkienkasvatuskilpailuun. Hän on kuitenkin harmikseen kohdannut visaisen ongelman: muut kilpailijat yrittävät vakoilla Uolevia kasvatuspuuhissaan. Uolevi onkin päättänyt pystyttää kukkien ympärille aidan, joka pitäisi kilpailijoiden uteliaat katseet loitolla. Uoleville olisi tärkeää käyttää mahdollisimman paljon aikaa kukkien hoitoon, joten aidan pystyttämisen hän haluaisi tehdä nopeasti.
Uolevilla on myös lista kukkien kokonaislukukoordinaateista. Auta Uolevia valitsemaan aidan pylväille sellaiset pisteet, että yksikään kukka ei jää aidan ulkopuolelle (ajattellaan, että äärettömän lähelle kukkaa voi pystyttää aidan). Laudat pylväiden välissä ovat aina suoria. Tiedetään myös, että Uolevi pystyy pystyttämään aitaa tietyn määrän aikayksikössä. Aidan pitäisi siis olla lisäksi mahdollisimman lyhyt.
Vastoin kuin kllp luulee, niin whitespacen järkevä käyttö on suotavaa myös koodatessa. Varsinkin kun yrittää tehdä muka-tiivistä koodia käyttämällä bittioperaattoreita ja muita lieveilmiöitä.
a1[q][w]|=1<<i;
a2[x/9]|=1<<i;
a3[x%9]|=1<<i;
t[x/9][x%9]=i;
if(ratkaise(x+1)) return 1;
a1[q][w]^=1<<i;
a2[x/9]^=1<<i;
a3[x%9]^=1<<i;
/*
* Sama lukukelpoisesti esitettynä:
*/
a1[q][w]| = 1 << i;
a2[x/9]| = 1 << i;
a3[x%9]| = 1 << i;
t[x/9][x%9] = i;
if (ratkaise(x+1)) {
return 1;
}
a1[q][w] ^= 1 << i;
a2[x/9] ^= 1 << i;
a3[x%9] ^= 1 << i;Muuten ihan kiva, mutta kyseessä ei ole toimiva koodi (siis niinku tuo sun koodi).
Lisäys:
Vähän sama kuin koodaisi:
if(a= =1) a+ =1;
Kaikkea se whitespace-uskovaisuus teettääkin...
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <string.h>
using namespace std;
struct v
{
double x,y;
v(double a, double b):x(a),y(b){}
v():x(0),y(0){}
};
double abs(v a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
v operator - (v a,v b)
{
v c;
c.x=a.x-b.x;
c.y=a.y-b.y;
return c;
}
double ristitulo(v o,v a, v b) //laskee vektoreiden (a-o) ja (b-O) ristitulon
{
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
vector<v> pisteet;
vector<v> convex_hull;
bool pk(v a,v b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
void monotoneChain()
{
sort(pisteet.begin(),pisteet.end(),pk);
convex_hull.resize(pisteet.size());
int k=0;
for(int i=0;i<pisteet.size(); i++)
{
while(k>=2&&ristitulo(convex_hull[k-2],convex_hull[k-1],pisteet[i])<0)
k--;
convex_hull[k++]=pisteet[i];
}
for(int i=pisteet.size()-2, t = k-1;i>=0; i--)
{
while(k>=t&&ristitulo(convex_hull[k-2],convex_hull[k-1],pisteet[i])<0)
k--;
convex_hull[k++]=pisteet[i];
}
convex_hull.resize(k-1);
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
double a,b;
cin>>a>>b;
pisteet.push_back(v(a,b));
}
monotoneChain();
cout<<endl;
for(vector<v>::iterator it=convex_hull.begin();it!=convex_hull.end();it++)
cout<<it->x<<" "<<it->y<<endl;
return 0;
}kukkakasvatuskilpailutehtävä^^^^^
Tälläinen coodi löytyi arkistoijeni syövereistä. Aika bloatti kyllä ;_;
Koodissahan siis muodostetaan convex hull kukkien sijainneille.
Lisäys:
Tehtävä:
Tee algoritmi joka etsii tehokkaasti pienimmän luvun a jolle pätee
a%n=n-1, kun n kuuluu [1,b] ja b on luku joka algolle annetaan.
OliO kirjoitti:
Tehtävä:
Tee algoritmi joka etsii tehokkaasti pienimmän luvun a jolle pätee
a%n=n-1, kun n kuuluu [1,b] ja b on luku joka algolle annetaan.
ghci> let b = 100 ghci> foldl1 lcm [1 .. b] - 1 69720375229712477164533808935312303556799 ghci> all (\n -> it `mod` n == n - 1) [1 .. b] True
Tehtävä:
Toteuta tehokkaasti seuraavat funktiot valitsemallasi kielellä.
// Kaikille // 0 <= K <= N, // 0 <= rank < choose(N, K) // pätee: // rank_subset(N, K, unrank_subset(N, K, rank)) == rank /** * 0 <= K <= N * subset on N kokoinen taulukko, jonka arvoista tasan K on true * 0 <= paluuarvo < choose(N, K) */ int rank_subset(int N, int K, boolean[] subset); /** * 0 <= K <= N * 0 <= rank < choose(N, K) * paluuarvo on N kokoinen taulukko, jonka arvoista tasan K on true */ boolean[] unrank_subset(int N, int K, int rank);
choose(N, K) = N! / (K! * (N-K)!), kts. binomikerroin
Ongelma kannattaa ratkaista ensin yleisesti algoritmitasolla. Jos haluaa, voi tehdä lisäksi erityisen optimoidun koodin joillekin tietyille arvoille; esimerkiksi tapaus (N,K) = (39,7) vastaa lottorivejä, ja hyvästä ratkaisusta voi olla hyötyä Putkapostissa 45.
Hidaskin toteutus voi olla kätevä joihinkin tarkoituksiin! Pari esimerkkiä:
// Arvotaan satunnainen lottorivi
satunnainen_rivi = unrank_subset(39, 7, rand() % MAX);
// Käydään läpi kaikki eri lottorivit
for (int i = 0; i < MAX; ++i) {
rivi = unrank_subset(39, 7, i);
...
}Määritetään rank_subset(n,k,subset) = monesko k:n kokoinen osajoukko subset on kun joukot järjestetään "aakkosjärjestykseen". Sääntöjen mukaisesti en ole kääntänyt joten ehkä toimii ehkä ei.
int choose[64][64]; // binomikertoimet
int rank_subset(int N, int K, const bool* S) {
int r=0;
for(int i=0; i<N; ++i) if (S[i]) r += choose[N-i-1][K--];
return r;
}
void unrank_subset(int N, int K, int rank, bool* S) {
for(int i=0; i<N; ++i)
if (rank >= choose[N-i-1][K]) S[i] = 1, rank -= choose[N-i-1][K--];
else S[i] = 0;
}Tehtävä: koodaa laskin joka kykenee laskemaan lausekkeita kuten "2*16/(1+5)-5*2" ja huomioi laskujärjestyksen oikein.
#!/usr/bin/python3
print(eval(input("Lauseke: ")))Oho, väärä kieli. En jaksa koodata C:llä.
Ihan hauska ratkaisu, Metabolix. Aika bloatti kyllä mutta menköön tämän kerran kun ei vaadittu nopeampaa. Muista antaa uusi tehtävä seuraavalle ratkaisun yhteydessä!
Koodasin nyt kuitenkin myös C:llä. En jaksanut ajatella, joten käytin rekursiota. Ohjelma lopettaa lausekkeen lukemisen, kun kohtaa odottamattoman merkin, joten lausekkeet voi lopettaa esimerkiksi puolipisteeseen. Jos lausekkeen loppuessa sulut eivät täsmää, tulee virheilmoitus.
#include <stdio.h>
#include <stdlib.h>
double laske() {
double summa();
return summa();
}
double luku_tai_sulut() {
double a;
if (scanf("%lf", &a) == 1) {
return a;
}
if (getchar() == '(') {
a = laske();
if (getchar() == ')') {
return a;
}
}
printf("Virhe lausekkeessa.\n");
exit(1);
}
double kerto() {
double a, b;
char op;
a = luku_tai_sulut();
while (scanf(" %1[/*]", &op) == 1) {
b = luku_tai_sulut();
if (op == '*') {
a *= b;
} else {
a /= b;
}
}
return a;
}
double summa() {
double a, b;
char op;
a = kerto();
while (scanf(" %1[-+]", &op) == 1) {
b = kerto();
if (op == '+') {
a += b;
} else {
a -= b;
}
}
return a;
}
int main() {
printf("%lg\n", laske());
return 0;
}Antti Administraattorilla on N tietokonetta, jotka on kytketty verkoksi. Jokaisella koneella on määrätty kapasiteetti Ki, joka kertoo, montako tiedostoa koneen muistiin mahtuu. Verkossa siirrettävä tiedosto voi joka sekunti siirtyä jollekin naapurikoneista, kuitenkin niin, että minkään koneen kapasiteetti ei ylity. Siirrettäessä tiedosto häviää aiemmalta koneelta. Jos kohdekoneen kapasiteetti on jo täynnä, siirrettävä tiedosto katoaa iäksi.
Antti haluaa lähettää M tiedostoa koneelta A koneelle B. Krakkeri-Kalle yrittää estää tämän käynnistämällä verkkohyökkäyksen koneelta C: aluksi koneella C on yksi saastunut tiedosto, ja joka sekunti jokainen saastunut kone kopioi saastuneen tiedoston jokaiselle naapurilleen, jolloin Antin käytössä oleva kapasiteetti koneilla vähenee. Kallen tiedostot eivät siis poistu koneelta. Kallen tiedostot liikkuvat verkossa aina Antin tiedostojen jälkeen, eli jos Antti ja Kalle lähettävät tiedostoja samalle koneelle, Antin tiedostot tallennetaan ensin.
Laadi ohjelma, joka laskee kaikille M tiedostolle verkossa sellaiset reitit koneelta A koneelle B, että Antti saa tiedostonsa siirrettyä Kallen hyökkäyksestä huolimatta. Huomaa, että aina tällaisia reittejä ei ole!
Esimerkki: Kolme konetta on ketjuna A-C-B, ja kunkin kapasiteetti on 2. Antti siirtää yhden tiedoston koneelta A koneelle B. Aluksi koneella A on Antin tiedosto ja koneella C Kallen tiedosto. Antin tiedosto siirtyy koneelle C, jolloin koneella C on yksi Antin tiedosto ja yksi Kallen tiedosto. Kallen tiedosto taas kopioituu koneille A ja B, jolloin jokaisella koneella on yksi Kallen tiedosto. Seuraavaksi Antin tiedosto siirtyy koneelle B, jolloin Antti voittaa. (Samalla Kallen tiedosto kopioituu koneelta C koneelle A ja päinvastoin, jolloin niillä kummallakin on kaksi Kallen tiedostoa. Koneelle B Kalle ei saa toista tiedostoa, koska Antin tiedosto ehtii sinne ensin ja kone täyttyy.)
Resurssirajat voi valita kykyjen mukaan, kuitenkin mielellään N > 10 ja M > 10 ja Ki <= M.
Tein nyt yksinkertaistuksella että en laske lopullisia reittejä vaan palautan vain että onnistuuko vai eikö. Reittien generoinnin voi joku viitseliäs lisätä melko helposti generoitujen taulukoiden perusteella. En myöskään jaksanut kommentoida, testata tai kääntää koodia, joten käyttö enterprice-sovelluksissa omalla vastuulla.
#include <vector>
#include <utility>
using namespace std;
vector<vector<int>> es;
vector<int> to;
vector<int> cap;
vector<bool> used;
bool dfs(int n) {
if (!n) return 1;
used[n]=1;
for(int i: es[n]) if (cap[i] && !used[to[i]] && dfs(to[i])) {
--cap[i], ++cap[i^1];
return 1;
}
return 0;
}
void join(int a, int b, int c) {
es[a].push_back(to.size());
to.push_back(b);
cap.push_back(c);
es[b].push_back(to.size());
to.push_back(a);
cap.push_back(0);
}
// syöte
int N, M;
vector<int> K;
vector<vector<int>> E;
int A,B,C;
bool solve() {
vector<int> ss(N);
ss[C]=1;
es.resize(1+N);
while(K[B]-ss[C]>=M) {
int k = es.size();
es.resize(k+2*N);
for(int i=0; i<N; ++i) if (K[i]>ss[i]) {
join(k-N+i,k+i,M);
join(k+i,k+i+N,K[i]-ss[i]);
for(int j: E[i]) join(k-N+i,k+j,M);
}
join(k+B+N,0,M);
while(used.clear(),used.resize(es.size()),dfs(1+A))
if (!--M) return 1;
for(int i=0; i<N; ++i) if (ss[i]) for(int j: E[i]) ++ss[j];
}
return 0;
}Tehtävä: Toteuta Huffmanin koodaus. Itse pakkausta/purkua ei tarvitse toteuttaa, vaan riittää määrittää kaikille annetussa tiedostossa esiintyville merkeille pakkauksessä käytettävät bittijonot.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
struct S {
int F,A,L,R;
};
vector<S> v;
bool c(int a, int b) {
return v[a].F>v[b].F;
}
vector< vector<bool> > lol(1000);
void e(int k, vector<bool> & a) {
if(v[k].L==-1 && v[k].R==-1) {
lol[v[k].A]=a;
return;
}
a.push_back(0);
e(v[k].L, a);
a[a.size()-1]=1;
e(v[k].R, a);
a.pop_back();
}
int main() {
vector<int> h;
string s;
getline(cin, s);
map<char, int> f;
for(int i=0; i<s.size(); ++i) {
++f[s[i]];
}
S q;
q.L=-1;
q.R=-1;
for(map<char, int>::iterator it=f.begin(); it!=f.end(); ++it) {
q.F=it->second;
q.A=it->first;
h.push_back(v.size());
v.push_back(q);
}
make_heap(h.begin(), h.end(), c);
for(;h.size()>1;) {
int a,b;
a=h[0];
pop_heap(h.begin(), h.end(), c);
h.pop_back();
b=h[0];
pop_heap(h.begin(), h.end(), c);
h.pop_back();
q.F=v[a].F+v[b].F;
q.L=a;
q.R=b;
h.push_back(v.size());
v.push_back(q);
push_heap(h.begin(), h.end(), c);
}
vector<bool> a;
e(h[0], a);
for(int i=0; i<lol.size(); ++i) {
if(lol[i].size()) {
cout<<char(i)<<' ';
for(int j=0; j<lol[i].size(); ++j) {
cout<<lol[i][j];
}
cout<<'\n';
}
}
}Ehkä toimii, ehkä ei ;_; Käänsinkin ja testailin, mutta en silti tiedä Q_Q
En uskalla vielä edes laittaa uutta tehtävää T_T
En kyllä edes tietäisi vielä mitään tehtävää QAQ
Tehtävä: Tee ohjelma, jolla voi ratkaista yhtälöitä muotoa ax + by = c, jossa a,b,c,x,y kokonaislukuja. Syötteenä ohjelmalle annetaan kolme lukua: a, b ja c. Ohjelman tulisi etsiä kaikki lukuparit (x,y), joilla yhtälö toteutuu tai ilmoittaa, että ratkaisua ei ole. Voit itse päättää tarkemmin ratkaisun muotoilun.
#include <stdio.h>
#include <stdlib.h>
long gcd(long a, long b) {
return (b == 0) ? a : gcd(b, a % b);
}
void eea(long a, long b, long c, long *x, long *y) {
long d[2][3];
int eka, toka;
d[0][0] = 1; d[0][1] = 0; d[0][2] = a;
d[1][0] = 0; d[1][1] = 1; d[1][2] = b;
eka = 0; toka = 1;
while (d[toka][2] != c) {
long q = d[eka][2] / d[toka][2];
d[eka][0] = d[eka][0] - q * d[toka][0];
d[eka][1] = d[eka][1] - q * d[toka][1];
d[eka][2] = d[eka][2] - q * d[toka][2];
eka ^= 1; toka ^= 1;
}
*x = d[toka][0]; *y = d[toka][1];
}
int main(int argc, char *argv[]) {
long a, b, c, x, y;
a = atoi(argv[1]); b = atoi(argv[2]); c = atoi(argv[3]);
if (a < b) { a ^= b; b ^= a; a ^= b; }
if (c % gcd(a, b) == 0) {
eea(a, b, gcd(a, b), &x, &y);
x *= c / gcd(a, b);
y *= c / gcd(a, b);
printf("%ldx + %ldy = %ld\n", a, b, c);
printf("x = %ld + %ldt\n", x, b / gcd(a, b));
printf("y = %ld - %ldt\n", y, a / gcd(a, b));
} else printf("ei ratkee\n");
return 0;
}Ei sovi kovin hyvin "koodaa kääntämättä" formaattiin, mutta menkööt.
Tehtävä
Uolevi suojaa tietokoneohjelmansa salasanalla. Salasana on 32-bittinen kokonaisluku, joka annetaan syötteeksi funktiolle f. Salasanan tulkitaan olevan oikein, jos funktio kuvaa salasanan luvuksi 0x1337C0DE. Tehtävänäsi on selvittää Uolevin salasana, kun funktiolla tiedetään olevan seuraavat ominaisuudet (0 ≤ x < 232, 0 ≤ y < 232):
f on bijektio: f(x)=f(y), jos ja vain jos x=y.f on additiivinen: f(x^y)=f(x)^f(y), missä ^ on XOR.f(0)=0.Tai toisin sanoen selkokielellä: jokainen ykkösbitti syötteessä kääntää tietyn joukon bittejä tuloksessa. Nämä bittijoukot on annettu alla olevan koodin A-taulukossa. Selvitä, mitkä syötteen bitit pitää asettaa ykkösiksi, että funktion tulokseksi tulee 0x1337C0DE.
#include <stdio.h>
#include <stdint.h>
uint32_t A[32] = {
0xB8BC6765, 0xAA09C88B, 0x8F629757, 0xC5B428EF, 0x5019579F,
0xA032AF3E, 0x9B14583D, 0xED59B63B, 0x01C26A37, 0x0384D46E,
0x0709A8DC, 0x0E1351B8, 0x1C26A370, 0x384D46E0, 0x709A8DC0,
0xE1351B80, 0x191B3141, 0x32366282, 0x646CC504, 0xC8D98A08,
0x4AC21251, 0x958424A2, 0xF0794F05, 0x3B83984B, 0x77073096,
0xEE0E612C, 0x076DC419, 0x0EDB8832, 0x1DB71064, 0x3B6E20C8,
0x76DC4190, 0xEDB88320
};
uint32_t f(uint32_t x) {
uint32_t y, i;
y = 0;
for (i = 0; i < 32; i++) {
if (x & 1)
y ^= A[i];
x >>= 1;
}
return y;
}
int main(int argc, char *argv[]) {
uint32_t salasana;
printf("Anna salasana: 0x"); fflush(stdout);
scanf("%x", &salasana);
if (f(salasana) == 0x1337C0DE) {
printf("oikein!\n");
} else printf("väärin!\n");
return 0;
}Algoritmin olisi toivottavaa toimia polynomisessa ajassa salasanan pituuden suhteen. Bruteforce on häpeällinen ratkaisu.
Seuraava funktio g on funktio f:n käänteisfunktio:
uint32_t B[32];
uint32_t C[32];
uint32_t g(uint32_t s) {
for (int i = 0; i < 32; i++) {
for (int j = 0; j < 32; j++) {
B[i] ^= ((A[j]>>i)&1)<<j;
}
C[i] = (s>>i)&1;
}
for (uint32_t b = 0x80000000; b >= 1; b >>= 1) {
int q;
for (int i = 0; i < 32; i++) {
if ((B[i]&b) && (B[i]^b)<b) q = i;
}
for (int i = 0; i < 32; i++) {
if (!(B[i]&b) || i == q) continue;
B[i] ^= B[q];
C[i] ^= C[q];
}
}
uint32_t t = 0;
for (uint32_t i = 0; i < 32; i++) {
if (C[i]) t ^= B[i];
}
return t;
}Tehtävä
Sinulle annetaan merkkijono, joka muodostuu n (1 ≤ n ≤ 5000) merkistä A..Z, sekä kokonaisluku k (0 ≤ k ≤ n-2). Saat muokata merkkijonoa rajattomasti operaatiolla, jossa kaksi merkkiä, joiden välissä on k merkkiä, vaihdetaan keskenään. Montako erilaista merkkijonoa voit muodostaa tällä tavalla? Ilmoita vastaus modulo 1000000007.
Esimerkiksi jos merkkijono on ABBC ja k = 1, niin voit muodostaa 4 merkkijonoa: ABBC, ACBB, BBAC ja BCAB.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define K_MAX 100000
int muisti[256][K_MAX+1];
int main()
{
string s;
int k;
cin>>s>>k;
int n=s.size();
for(int i=0;i<n;i++)
{
muisti[s[i]][i%(k+1)]++;
}
long long vastaus=1;
for(int i=0;i<k+1;i++)
{
int ker=1;
long long osavastaus_ala=1;
for(int e='A'; e<='Z';e++)
{
int q=1;
long long osavastaus_yla=1;
while(muisti[e][i])
{
osavastaus_yla*=ker;
osavastaus_ala*=q;
long long a=__gcd(osavastaus_yla,osavastaus_ala);
osavastaus_yla/=a;
osavastaus_ala/=a;
osavastaus_yla%=1000000007;
q++;ker++;
muisti[e][i]--;
}
vastaus*=osavastaus_yla;
vastaus%=1000000007;
}
}
cout<<vastaus<<endl;;
return 0;
}Ja tämähän toimii niin että muodostu k+1 ryhmää jotka eivät voi vaihtaa kirjaimia keskenään. Sitten vaan lasketaan erilaiset permutaatiot.
EDIT: muokkasin koodini toimimaan paremmin(/huonommin)
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll exp(ll a, ll b) {
ll t=1;
for(;b;b/=2) {
if(b&1) {
t*=a;
t%=MOD;
}
a*=a;
a%=MOD;
}
return t;
}
int main() {
int k;
cin>>k;
string a;
cin>>a;
ll s=1;
for(int i=0; i<a.size(); ++i) {
int m['Z']={0};
ll q=0;
for(int j=i; a[j]!=0 && j<a.size(); j+=k+1) {
++m[a[j]-'A'];
++q;
a[j]=0;
}
ll w=1;
for(int i=1; i<=q; ++i) {
w*=i;
w%=MOD;
}
ll e=1;
for(int i=0; i<'Z'; ++i) {
for(ll j=1; j<=m[i]; ++j) {
e*=j,e%=MOD;
}
}
s*=(w*exp(e, MOD-2))%MOD;
s%=MOD;
}
cout<<s<<'\n';
}Tuossa minunkin ratkaisuni. Emt toimiiko.
Tehtävä: Petteri Peelo pitää neliöistä ja neliöiden rakentamisesta. Eräänä päivänä Petterille tuli kuitenkin ongelma: Hänelle oli jäänyt vain yhdenlaisia rakennuspalikoita jäljelle. Koska petteri rakastaa kaikenkokoisia neliöitä, tulee hän kaikkein onnellisimmaksi kun hän saa rakennettua mahdollisimman monta neliötä.
Tehtävänäsi on etsiä pienin neliö joka voidaan rakentaa annetunmuotoisista paloista. Syötteenä saat palikan muodot vapaavalintaisessa muodossa, esimerkiksi:
100
100
100
110
tai
(0,0),(0,1),(0,2),(0,3),(1,3).
Tarkennus tehtävään: Tarkoituksena ei ole etsiä kovinkaan tehokasta menetelmää pienimmän neliön saavuttamiseksi, vaan vain yleinen menetelmä joka onnistuu siinä(mielellään hieman nopeampi kuin brute kuitenkin). Itqpotqraivarien takia muutan tehtävää niin ettei tarvitse etsiä kuin neliö joka on pienempi kuin 40(<-- sivun pituus). Jos ei ole, tulosta -1.
Ei ole nyt C-kääntäjää käsillä, joten käytän aacoodia:
Va,ka: palikat, kalikat. Goto: pelle peloton: talo. Ot-yhteys: pelle peloton. Hkr: robotti. Send: cmd: rakenna, tyyppi:neliö. Va,ka: neliöt. Send-tänne.
Edit: oli syntaxi virhe (nyt korjattu)
Tehtävä
OliOn tehtävä uudelleen
Vähän clean codea suomeksi:
#include <vector>
#include <algorithm>
using namespace std;
/**
* Laskee annetuista lukujoukoista eksaktin peitteen.
* Funktio saa parametrinaan luvun N ja joukon rivejä.
* Jokainen rivi sisältää kokonaislukuja väliltä 0..N-1,
* ja funktio valitsee sellaisen rivien osajoukon että jokainen
* luku 0..N-1 kuuluu tasan yhteen valittuun riviin.
* Funktio palauttaa valittujen rivien indeksit rivit-taulukossa,
* tai tyhjän listan jos ratkaisua ei ole olemassa.
*/
vector<int> eksaktiPeite(int N, vector<vector<int>> rivit);
typedef pair<int,int> P;
typedef vector<P> V;
V siirra(V v, int x, int y) {
for(P& p: v) p.first+=x, p.second+=y;
return v;
}
V normalisoi(V v) {
int x=1e9, y=1e9;
for(P p: v) x = min(x, p.first), y = min(y, p.second);
return siirra(v, -x, -y);
}
vector<V> rakennaNelio(V pala) {
vector<V> perusPalat;
for(int i=0; i<2; ++i) {
for(int j=0; j<4; ++j) {
perusPalat.push_back(normalisoi(pala));
for(P& p: pala) p = P(p.second, -p.first);
}
for(P& p: pala) p = P(-p.first, -p.second);
}
sort(perusPalat.begin(), perusPalat.end());
perusPalat.erase(unique(perusPalat.begin() perusPalat.end()), perusPalat.end());
for(int s=1; s<40; ++s) {
vector<V> palat;
for(V v: perusPalat) {
int x=0,y=0;
for(P p: v) x=max(x,p.first), y=max(y,p.second);
for(int i=0; x+i<s; ++i) for(int j=0; y+j<s; ++j)
palat.push_back(siirra(v,i,j));
}
vector<vector<int>> rivit;
for(V& v: palat) {
vector<int> u;
for(P p: v) u.push_back(s*p.first + p.second);
rivit.push_back(u);
}
vector<int> peite = eksaktiPeite(s*s, rivit);
if (!peite.empty()) {
vector<V> tulos;
for(int i: peite) tulos.push_back(palat[i]);
return tulos;
}
}
return {};
}Tehtävä: Toteuta edellisen koodin alussa kuvattu eksaktiPeite-funktio haluamallasi ohjelmointikielellä (muokaten funktion parametrien ja paluuarvon tyyppejä tarpeen mukaan). Voit käyttää esim. Knuthin Dancing Links -algoritmia (tai sitten perinteikästä raakaa voimaa jos tuo tuntuu liian monimutkaiselta).
Tässä kamala sekoitus raakaa voimaa ja Dancing Links -räpellystä. Hyi olkoon. En ole aivan varma toimiiko. N-queen ongelmasta antoi oikeita vastauksia, mutta sen jälkeen jouduin tekemään muutoksia koodiin, että kelpaisi tähän vastauksksi.
#include <iostream>
#include <vector>
#define NN 1000
#define MM 1000
using namespace std;
struct S {
int L,R,U,D;
};
S v[NN][MM];
int yk[MM];
int sarakkeita=0;
/*
* palautettavaVectori sisältää eksaktiPeitteen palauttaman vectorin
*/
vector<int> palautettavaVectori;
int e(int x, int y, int d, int N) {
palautettavaVectori.push_back(x);
int lol=0;
vector<pair<int, int> > pois;
for(int q = y; q != y || !lol; q = v[x][q].R) {
lol=1;
int lol2=0;
int maara=0;
int raja=yk[q];
for(int w = x; maara<=raja; w = v[w][q].U, ++maara) {
lol2 = 1;
if(w == 0) {
int left = v[w][q].L;
int right = v[w][q].R;
v[w][left].R = right;
v[w][right].L = left;
--sarakkeita;
}
int lol3 = 0;
for(int e = q; e != q || !lol3; e = v[w][e].R) {
lol3 = 1;
pois.push_back(make_pair(w, e));
if(w!=0) --yk[e];
int up = v[w][e].U;
int down = v[w][e].D;
v[up][e].D = down;
v[down][e].U = up;
if(w == 0 || w == x) break;
}
if(v[w][q].U==w) {
break;
}
}
}
if(!sarakkeita) return 1;
int pk=-1;
int pm=1e9;
//tämä on nolo... anteeksi...
for(int i = 0; i<N; i=v[0][i].R) {
if(yk[i] && yk[i] < pm) {
pm = yk[i];
pk = i;
}
if(v[0][i].R<i) break;
}
int ma=0;
if(pk != -1) {
for(int i = v[0][pk].U; i != 0; i = v[i][pk].U) {
if(e(i, pk, d+1, N)) return 1;
}
}
lol = 0;
for(int q = y; q != y || !lol; q = v[x][q].R) {
lol=1;
int lol2=0;
int maara=0;
for(int w = x; (w != x || !lol2); w = v[w][q].U) {
lol2 = 1;
if(w == 0) {
int left = v[w][q].L;
int right = v[w][q].R;
v[w][left].R = q;
v[w][right].L = q;
++sarakkeita;
}
int lol3 = 0;
for(int e = q; e != q || !lol3; e = v[w][e].R) {
lol3 = 1;
if(w!=0) ++yk[e];
int up = v[w][e].U;
int down = v[w][e].D;
v[up][e].D = w;
v[down][e].U = w;
if(w== 0 || w == x) break;
}
}
}
palautettavaVectori.pop_back();
return ma;
}
bool t[NN][MM];
vector<int> eksaktiPeite(int N, vector< vector<int> > rivit) {
//rivienMaara-muuttuja sisaltaa rivien lukumaaran
int rivienMaara = rivit.size();
sarakkeita=N;
for(int i = 0; i < rivienMaara; ++i) {
for(int j = 0; j < rivit[i].size(); ++j) {
t[i][rivit[i][j]]=1;
}
}
for(int i=0; i<N; ++i) {
v[0][i].R=(i+1)%(N);
v[0][i].L=(i+N-1)%(N);
}
int edu=0;
int edr=-1;
for(int i=0; i<N; ++i) {
edu=0;
for(int j=1; j<=rivienMaara; ++j) {
if(t[j-1][i]) {
++yk[i];
v[edu][i].D=j;
v[j][i].U=edu;
edu=j;
}
}
v[0][i].U=edu;
v[edu][i].D=0;
}
for(int i = 1; i <= rivienMaara; ++i) {
int edl = 0;
int eka = -1;
int lol=0;
for(int j = 0; j%N != eka; ++j, ++lol) {
int jj=j%N;
if(eka!=-1 && t[i-1][jj]) {
v[i][jj].L=edl;
v[i][edl].R=j;
}
if(t[i-1][jj]) {
if(eka == -1) eka = jj;
edl = jj;
}
if(lol > N && eka == -1) {
break;
}
}
if(eka != -1) {
v[i][edl].R = eka;
v[i][eka].L = edl;
}
}
int ma=0;
for(int i=1; i<=rivienMaara; ++i) {
for(int j=0; j<N; ++j) {
if(t[i-1][j]) {
if(e(i, j, 0, N)) {
return palautettavaVectori;
}
}
}
}
cout<<ma<<'\n';
return palautettavaVectori;
}Itse väkersin tuohon eksaktipeitteeseen pari päivää sitten tällaisen yksinkertaisen ja varmaankin isommilla joukoilla melko epätehokkaan lähestymistavan, mutta en jaksanut laittaa tuolloin kun en keksinyt mitään kivaa uutta tehtävää:
using System;
using System.Collections.Generic;
using System.Linq;
class ep {
public static List<int> eksaktiPeite(int N, List<List<int>> rivit)
{
return eksaktiPeite(N, rivit, new HashSet<int>(), null, 0);
}
private static List<int> eksaktiPeite(int N, List<List<int>> rivit, HashSet<int> käytetytRivit, List<int> löydetyt, int seuraavaRiviIx)
{
if (löydetyt != null && rivit[seuraavaRiviIx].Intersect(löydetyt).Any()) { return null; }
var uusiLöydetyt = (löydetyt == null)
? new List<int>()
: löydetyt.Concat(rivit[seuraavaRiviIx]).ToList();
if (uusiLöydetyt.Count == N) { return käytetytRivit.ToList(); }
for (int riviIx = 0; riviIx < rivit.Count; riviIx++)
{
if (!käytetytRivit.Contains(riviIx))
{
käytetytRivit.Add(riviIx);
var tulos = eksaktiPeite(N, rivit, käytetytRivit, uusiLöydetyt, riviIx);
if (tulos != null) { return tulos; }
käytetytRivit.Remove(riviIx);
}
}
return null;
}
}Toivottavasti nyt ei ole jo vanhan toistoa, mutta aihe on vain niin I-H-A-N-A!
Tehtävä: Uolevin kukkienkasvatus etenee varsin hienosti. Kukkia pitää tietysti muistaa myös kastella, ja Uolevilla onkin siihen hieno kastelukannu. Uolevin kastelukannu on siitä erikoinen, että sillä voi valita kukkamaalta jonkin suorakulmion muotoisen alueen ja kastella sitä tietyllä määrällä vettä.
Uolevin ystävä, professori Viherkasvi neuvoo Uolevia kastelemaan kukkia järjestelmällisesti niin, että kukat saisivat kaikki yhtä paljon vettä. Uolevia ei kuitenkaan moinen kiinnosta: hän kastelee sellaisia alueita kuin häntä huvittaa.
Tästä seuraa kuitenkin ongelmia. Uolevin kasvimaa on kohtuullisen suuri: 10^9 x 10^9 kasvijuttuyksikköä. Uolevilla onkin nyt vaikeuksia laskea tehokkaasti, paljonko eri alueet ovat saaneet vettä. Kirjoita Uoleville ohjelma, joka ratkaisee ongelman.
Syöte:
Ensimmäisellä rivillä kokonaisluku q, joka kertoo kyselyiden määrän.
Kyselyitä on kahta tyyppiä (tyyppien järjestys voi olla mikä tahansa):
Tyyppi yksi (rivi alkaa kirjaimelle A): Uolevi kastelee alueen jollakin määrällä vettä. Alueen kaksi kärkipistettä ilmoitetaan neljällä kokonaisluvulla x1, y1, x2, y2. Alueen jokaisen kukkayksikön saaman veden määrän ilmoittaa kokonaisluku v. Tässä ohjelma ei tulosta mitään.
Tyyppi kaksi (rivi alkaa kirjaimella B): Uolevi haluaa tietää, paljonko tietty alue on saanut vettä. Alueen kaksi kärkipistettä ilmoitetaan neljällä kokonaisluvulla x1, y1, x2, y2. Tässä kohtaa ohjelman tulisi siis tulostaa alueen yhteensä saama vesimäärä.
Ohjelma voi lukea ensin kaikki syötteet ja tulostaa vasta sitten.
Voit olettaa, että kyselyitä tyyppiä yksi on noin 100 000 ja kyselyitä tyyppiä kaksi on noin 100 000. Ohjelman tulisi toimia pahimmassakin tapauksessa muutamassa sekunnissa.
Selvennyksenä vielä: kaikki ohjelman käsittelemät "alueet" ovat suorakulmion muotoisia.
Vinkki: 1. 2d-segmenttipuu 2. Emt mikä se termi oikeasti on, mutta jos jotenkin "harvasti" toteuttaisi 3. En tiedä suomenkielistä termiä, mutta ehkä lazy segment tree auttaa
EDIT: Nyt on ehkä vähän selkeämpi?
EDIT2: Juuh elikkäs vaihdoin vielä vähän noita syötteen ylärajoja... Jos haluatte olla varmoja, niin suosittelen odottamaan huomiseen. :Dd
EDIT3:
Tehtävän haastavuuden vuoksi riittää ratkaisu tapauksessa, jossa tyypin 1 kyselyissä x1 = x2 ja y1 = y2 eli alueen pinta-ala on 1
Edit: Voidaan varmaan olettaa että kaikki rivit A tulee ennen ekaa riviä B.
Edit 2: Okei, kirjoitit että syötteet voi tulla missä järjestyksessä vaan (siis B voi tulla ennen A:ta) ja että ohjelma _voi_ lukea kaikki syötteet ja tulostaa vasta sitten. Nyt näkisin että ohjelma antaa eri tulokset jos tulostellaan sitä mukaa kun B:tä tulee vs. jos luetaan ensin kaikki (A:t) sisään.
Ennen editointia olleet kysymykset, joihin tuli jo tarkennus:
(Eli mitä algoritmi saa syötteenä ja palauttaa, tarkalleen ottaen?
Onko tässä jokin suurempi idea kuin pyöräyttää läpi suorakulmioiden leikkauksia ja niiden summia?
Eikö tyypissä A pitäisi myös kertoa mikä se jokin vesimäärä on (per kukka esimerkiksi?))
Ei pitäisi riippua ohjelman tulostus tuosta. Lähinnä ajattelin mainita koordinaattien pakkaamisen vuoksi, jos joku haluaisi siten tuota tehdä.
Tässä on moniulotteinen ratkaisu siltä varalta että Uolevi siirtyy 3- tai vaikka 4-ulotteisten peltojen viljelyyn. Ei ole testattu muuta kuin 1- ja 2-ulotteisissa tapauksissa mutta pitäisi toimia aina induktion nojalla.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#ifndef DIM
#define DIM 2
#endif
vector<int> xs[DIM];
int roundTo2(int n) {
while(n&(n-1)) n+=n&-n;
return n;
}
template<class T, int D>
struct SegTree {
SegTree<T,D> *children=0;
T value;
template<class F>
void doRange(int a, int b, int from, int to, F f) {
int xa=xs[D-1][a], xb=xs[D-1][b];
if (xb <= from) return;
if (xa >= to) return;
if (xa>=from && xb<=to) {
f.in(value, xa, xb);
} else {
f.border(value, max(xa, from), min(xb, to));
int m = (a+b)/2;
if (!children) children = new SegTree[2];
children[0].doRange(a, m, from, to, f);
children[1].doRange(m, b, from, to, f);
}
}
template<class F>
void doRange(int from, int to, F f) {
doRange(0, xs[D-1].size()-1, from, to, f);
}
};
template<int D>
struct Box {
int x1,x2;
Box<D-1> rest;
void read(bool second) {
int& x = second?x2:x1;
cin>>x;
xs[D-1].push_back(x);
rest.read(second);
}
};
template<> struct Box<0> {
void read(bool) {}
};
template<int D> struct SumNode;
template<int D>
struct AddSum {
Box<D-1> box;
ll amount;
void in(SumNode<D>& n, int a, int b) {
n.sum.add(box, amount);
}
void border(SumNode<D>& n, int a, int b) {
n.parentSum.add(box, amount * (b-a));
}
};
template<int D>
struct GetSum {
Box<D-1> box;
ll& res;
void in(SumNode<D>& n, int a, int b) {
res += n.parentSum.get(box);
border(n,a,b);
}
void border(SumNode<D>& n, int a, int b) {
res += n.sum.get(box) * (b-a);
}
};
template<int D>
struct SumTree {
SegTree<SumNode<D>,D> tree;
void add(Box<D> box, ll amount) {
tree.doRange(box.x1, box.x2, AddSum<D>{box.rest, amount});
}
ll get(Box<D> box) {
ll res=0;
tree.doRange(box.x1, box.x2, GetSum<D>{box.rest, res});
return res;
}
};
template<>
struct SumTree<0> {
ll sum=0;
void add(Box<0>, ll amount) {
sum += amount;
}
ll get(Box<0>) {
return sum;
}
};
template<int D>
struct SumNode {
SumTree<D-1> sum, parentSum;
};
struct Q {
char c;
Box<DIM> box;
int v;
};
int main() {
int q;
cin>>q;
vector<Q> qs(q);
for(Q& q: qs) {
cin>>q.c;
q.box.read(0);
q.box.read(1);
if (q.c=='A') cin>>q.v;
}
for(auto& v: xs) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
SumTree<DIM> tree;
for(Q q: qs) {
if (q.c=='A') tree.add(q.box, q.v);
else cout<<tree.get(q.box)<<'\n';
}
}Tehtävä:
On annettu korkeintaan 50 lukua väliltä [-1017, 1017], ja luku S väliltä [-5*1018, 5*1018].
Valitse annetuista luvuista osajoukko, jonka summa on mahdollisimman suuri mutta korkeintaan S. Ohjelman pitäisi tuottaa ratkaisu 50 luvulla korkeintaan minuutissa.
Jaetaan joukko puoliksi, lasketaan puoliskojen kaikkien osajoukkojen summat, lajitellaan, valitaan paras osajoukkopari.
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
// Osajoukon summa ja bittimaski.
struct sum {
long value, mask;
bool operator < (const sum& t) const {
return value < t.value;
}
sum operator + (const sum& t) const {
return sum {value + t.value, mask | t.mask};
}
};
int main() {
long n, s;
std::vector<long> values;
// Luetaan arvot.
std::cin >> n >> s;
for (int i = 0; i < n; ++i) {
long v;
std::cin >> v;
values.push_back(v);
}
// Jaetaan joukko puoliksi ja lasketaan molemmista kaikki summat.
long n1 = n / 2, n2 = n - n1;
std::vector<sum> sums[2];
sums[0].resize(1 << n1);
sums[1].resize(1 << n2);
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < 1L << i; ++j) {
sums[0][(1L << i) + j] = sums[0][j] + sum {values[i], 1L << i};
}
}
for (int i = 0; i < n2; ++i) {
for (int j = 0; j < 1L << i; ++j) {
sums[1][(1L << i) + j] = sums[1][j] + sum {values[n1 + i], 1L << (n1 + i)};
}
}
// Laitetaan toiset summat nousevaan ja toiset laskevaan järjestykseen.
std::sort(sums[0].begin(), sums[0].end());
std::sort(sums[1].rbegin(), sums[1].rend());
// Etsitään paras summapari.
sum best {std::numeric_limits<long>::min()};
for (auto a = sums[0].begin(), b = sums[1].begin(); a != sums[0].end() && b != sums[1].end();) {
if (a->value + b->value <= s) {
if (a->value + b->value > best.value) {
best = *a + *b;
}
++a;
} else {
++b;
}
}
// Tulostetaan vastaus: paras summa = arvo1 + ... + arvoN.
std::cout << best.value;
const char* str = " = ";
for (int i = 0; i < n; ++i) if (best.mask & (1L << i)) {
std::cout << str << values[i];
str = " + ";
}
std::cout << std::endl;
}Lauseke voi sisältää laskutoimituksia +, -, * ja /, sulkuja ja yksikirjaimisia muuttujia a-z, jotka ovat positiivisia reaalilukuja. Montako merkitykseltään erilaista enintään N merkin mittaista lauseketta näistä voidaan muodostaa? (Esimerkiksi lausekkeet a ja b ovat merkitykseltään erilaiset mutta a ja b*a/b sekä a*(b/b)/c*c ovat supistettuna sama lauseke.)
Aihe on jo aika vanha, joten et voi enää vastata siihen.