From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- semestr-4/sieci/warsztaty8/185551.cpp | 41 ++++ semestr-4/sieci/warsztaty8/185786.cpp | 59 +++++ semestr-4/sieci/warsztaty8/185814.cpp | 64 +++++ semestr-4/sieci/warsztaty8/185880.cpp | 131 ++++++++++ semestr-4/sieci/warsztaty8/185951.cpp | 109 +++++++++ semestr-4/sieci/warsztaty8/185952.cpp | 113 +++++++++ semestr-4/sieci/warsztaty8/185992.cpp | 117 +++++++++ semestr-4/sieci/warsztaty8/186033.cpp | 101 ++++++++ semestr-4/sieci/warsztaty8/186164.cpp | 270 +++++++++++++++++++++ .../Twierdzenie_o_pierwiastkach_wymi.pdf | Bin 0 -> 3774800 bytes semestr-4/sieci/warsztaty8/dat0-check.cpp | 58 +++++ semestr-4/sieci/warsztaty8/dat0-check.e | Bin 0 -> 19240 bytes semestr-4/sieci/warsztaty8/dat0-gen.sh | 107 ++++++++ semestr-4/sieci/warsztaty8/mie1.cpp | 64 +++++ semestr-4/sieci/warsztaty8/prz8-wzo2.cpp | 177 ++++++++++++++ semestr-4/sieci/warsztaty8/prz9.cpp | 97 ++++++++ semestr-4/sieci/warsztaty8/psp0.cpp | 44 ++++ semestr-4/sieci/warsztaty8/w8.pdf | Bin 0 -> 95186 bytes semestr-4/sieci/warsztaty8/wie5.cpp | 158 ++++++++++++ semestr-4/sieci/warsztaty8/wie5.pdf | Bin 0 -> 73787 bytes 20 files changed, 1710 insertions(+) create mode 100644 semestr-4/sieci/warsztaty8/185551.cpp create mode 100644 semestr-4/sieci/warsztaty8/185786.cpp create mode 100644 semestr-4/sieci/warsztaty8/185814.cpp create mode 100644 semestr-4/sieci/warsztaty8/185880.cpp create mode 100644 semestr-4/sieci/warsztaty8/185951.cpp create mode 100644 semestr-4/sieci/warsztaty8/185952.cpp create mode 100644 semestr-4/sieci/warsztaty8/185992.cpp create mode 100644 semestr-4/sieci/warsztaty8/186033.cpp create mode 100644 semestr-4/sieci/warsztaty8/186164.cpp create mode 100644 semestr-4/sieci/warsztaty8/Twierdzenie_o_pierwiastkach_wymi.pdf create mode 100644 semestr-4/sieci/warsztaty8/dat0-check.cpp create mode 100644 semestr-4/sieci/warsztaty8/dat0-check.e create mode 100644 semestr-4/sieci/warsztaty8/dat0-gen.sh create mode 100644 semestr-4/sieci/warsztaty8/mie1.cpp create mode 100644 semestr-4/sieci/warsztaty8/prz8-wzo2.cpp create mode 100644 semestr-4/sieci/warsztaty8/prz9.cpp create mode 100644 semestr-4/sieci/warsztaty8/psp0.cpp create mode 100644 semestr-4/sieci/warsztaty8/w8.pdf create mode 100644 semestr-4/sieci/warsztaty8/wie5.cpp create mode 100644 semestr-4/sieci/warsztaty8/wie5.pdf (limited to 'semestr-4/sieci/warsztaty8') diff --git a/semestr-4/sieci/warsztaty8/185551.cpp b/semestr-4/sieci/warsztaty8/185551.cpp new file mode 100644 index 0000000..5d5af6a --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185551.cpp @@ -0,0 +1,41 @@ +#include +using namespace std; +typedef long long ll; +#define pb push_back +#define st first +#define nd second + +const int N = 1000007; + +map M; +ll tab[N]; +vector v; +queue > q; + +int main () { + ios_base::sync_with_stdio(false); + cin.tie(0); + ll n, a=-1, b=0; + M[0]=1; + cin>>n; + for(int i=0; i>tab[i]; + } + sort(tab, tab+n); + for(int i=0; i0) q.push({u.st+a, u.nd}); + } + while(!q.empty()) M[q.front().st]+=q.front().nd, q.pop(); + v.pb(a); + } + b++; + } + cout< +using namespace std; + +string jednosci[20] = {"", "jeden ", "dwa ", "trzy ", "cztery ", "piec ", "szesc ", "siedem ", "osiem ", "dziewiec "}; +string setki[20] = {"", "sto ", "dwiescie ", "trzysta ", "czterysta ", "piecset ", "szescset ", "siedemset ", "osiemset ", "dziewiecset "}; +string dziesiatki[20] = {"", "", "dwadziescia ", "trzydziesci ", "czterdziesci ", "piecdziesiat ", "szescdziesiat ", "siedemdziesiat ", "osiemdziesiat ", "dziewiecdziesiat "}; +string nastki[20] = {"dziesiec ", "jedenascie ", "dwanascie ", "trzynascie ", "czternascie ", "pietnascie ", "szesnascie ", "siedemnascie ", "osiemnascie ", "dziewietnascie "}; +string mil[20] = {"milionow ", "milionow ", "miliony ", "miliony ", "miliony ", "milionow ", "milionow ", "milionow ", "milionow ", "milionow "}; +string tys[20] = {"tysiecy ", "tysiecy ", "tysiace ", "tysiace ", "tysiace ", "tysiecy ", "tysiecy ", "tysiecy ", "tysiecy ", "tysiecy "}; + +string do_stu(int n) { + string odp=""; + if(n!=0) { + odp+=setki[n/100]; + int dzies=(n/10)%10; + if(dzies!=1) { + odp+=dziesiatki[dzies]; + odp+=jednosci[n%10]; + } + else odp+=nastki[n%10]; + } + return odp; +} + +string miliony(int n) { + string odp=""; + if(n==1) return "milion "; + if(n==0) return ""; + odp+=do_stu(n); + int dzies = (n/10)%10; + if(dzies==1) odp+="milionow "; + else odp+=mil[n%10]; + return odp; +} + +string tysiace(int n) { + string odp=""; + if(n==1) return "tysiac "; + if(n==0) return ""; + odp+=do_stu(n); + int dzies = (n/10)%10; + if(dzies==1) odp+="tysiecy "; + else odp+=tys[n%10]; + return odp; +} + +int main () { + ios_base::sync_with_stdio(false); + cin.tie(0); + int n; + cin>>n; + if(n==0) { + cout<<"zero"; + return 0; + } + string wynik= miliony(n/1000000)+tysiace((n/1000)%1000)+do_stu(n%1000); + cout< +using namespace std; + +string Jedn[] = {"","jeden","dwa","trzy","cztery","piec","szesc","siedem","osiem","dziewiec"}; +string Nasc[] = {"dziesiec","jedenascie","dwanascie","trzynascie","czternascie","pietnascie","szesnascie","siedemnascie","osiemnascie","dziewietnascie"}; +string Dzie[] = {"","","dwadziescia","trzydziesci","czterdziesci","piecdziesiat","szescdziesiat","siedemdziesiat","osiemdziesiat","dziewiecdziesiat"}; +string Setk[] = {"","sto","dwiescie","trzysta","czterysta","piecset","szescset","siedemset","osiemset","dziewiecset"}; + +string fragment(int liczba){ + string ret; + int s = liczba/100, d = (liczba/10)%10, j = liczba%10; + ret += Setk[s]; + if(Setk[s] != "") ret += " "; + + if(d == 1) ret += Nasc[j]; + else{ + ret += Dzie[d]; + if(Dzie[d] != "") ret += " "; + ret += Jedn[j]; + } + return ret; +} + +string miliony(int ile){ + if(ile == 0) return ""; + if(ile == 1) return "milion"; + int d = ile%10, j = (ile/10)%10; + if((d >= 2 && d <= 4) && j != 1) return "miliony"; + return "milionow"; +} + +string tysiace(int ile){ + if(ile == 0) return ""; + if(ile == 1) return "tysiac"; + int d = ile%10, j = (ile/10)%10; + if((d >= 2 && d <= 4) && j != 1) return "tysiace"; + return "tysiecy"; +} + +int main(){ + int n; + string wyr; + cin >> n; + int mln = n/1000000, tys = (n/1000)%1000, jed = n%1000; + + if(n == 0){ + cout << "zero"; + return 0; + } + + wyr = fragment(mln); + if(wyr != "jeden") cout << wyr; + if(wyr != "" && wyr != "jeden") cout << " "; + cout << miliony(mln); + if(wyr != "") cout << " "; + + wyr = fragment(tys); + if(wyr != "jeden") cout << wyr; + if(wyr != "" && wyr != "jeden") cout << " "; + cout << tysiace(tys); + if(wyr != "") cout << " "; + + cout << fragment(jed); +} \ No newline at end of file diff --git a/semestr-4/sieci/warsztaty8/185880.cpp b/semestr-4/sieci/warsztaty8/185880.cpp new file mode 100644 index 0000000..2643585 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185880.cpp @@ -0,0 +1,131 @@ +#include +using namespace std; + +void dziesiatki ( int x); +void sety ( int x); + +string od1do9[]= { "zero", "jeden", "dwa", "trzy", "cztery", "piec", "szesc", "siedem", "osiem", "dziewiec"}; +string od10do19[]= { "dziesiec", "jedynascie", "dwanascie", "trzynascie", "czternascie", "pietnascie", "szesnascie", "siedemnaœcie", "osiemnascie", "dziewietnascie"}; +string od20do90[]= {"", "dwadziescia", "trzydziesci", "czterdziesci", "piecdziesciat", "szescdziesciat", "siedemdziesiat", "osiemdziesiat", "dziewiecdziesiat"}; +string od200do900[]= { "", "dwiescie", "trzysta", "czterysta", "piecset", "szescset", "siedemset", "osiemset", "dziewiecset"}; + +void miliony ( int x) { + if ( x==1) { + cout<<"milion "; + return; + } + + dziesiatki(x); + if ( x >= 2 && x<=4) { + cout<<"miliony "; + } else { + cout<<"milionow "; + } +} + +void tysiace ( int x) { + if ( x==1) { + cout<<"tysiac "; + } else { + if ( x==100) { + cout<<"sto tysiecy"; + } else { + if ( x<10) { + if ( x<=4) { + cout<=10 && x<=99) { + dziesiatki(x); + } else { + cout<=10) { + dziesiatki(x); + } + else { + if ( x%100>=1 && x%100<=9) { + cout<=10) { + dziesiatki(x); + } else { + if (x!=0) { + cout<>n; + if ( n>=1000000) { + miliony ( n/1000000); + } + n=n%1000000; + if ( n>=1000) { + tysiace( n/1000); + } + n=n%1000; + + sety (n); +} + +//b³edy 999999 diff --git a/semestr-4/sieci/warsztaty8/185951.cpp b/semestr-4/sieci/warsztaty8/185951.cpp new file mode 100644 index 0000000..df7c356 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185951.cpp @@ -0,0 +1,109 @@ +#include +using namespace std; + +int max_miesiac[12]={31,28,31,30,31,30,31,31,30,31,30,31}; +string dzien[2]={"dzien","dni"}; +string godziny[3]={"godzina","godziny","godzin"}; +string minuty[3]={"minuta","minuty","minut"}; +string sekundy[3]={"sekunda","sekundy","sekund"}; + +string wypisz(int a, char wyz) +{ + int dz=a/10; + int j=a%10; + if(wyz=='g'){ + if(j==1 and dz==0){ + return godziny[0]; + }else{ + if(j>=2 and j<=4 and (dz>=2 or dz==0)){ + return godziny[1]; + }else{ + return godziny[2]; + } + } + } + if(wyz=='m'){ + if(j==1 and dz==0){ + return minuty[0]; + }else{ + if(j>=2 and j<=4 and (dz>=2 or dz==0)){ + return minuty[1]; + }else{ + return minuty[2]; + } + } + } + if(wyz=='s'){ + if(j==1 and dz==0){ + return sekundy[0]; + }else{ + if(j>=2 and j<=4 and (dz>=2 or dz==0)){ + return sekundy[1]; + }else{ + return sekundy[2]; + } + } + } + return ""; +} + +int main(){ +int rok,mies,dni,godz,mi,sek; +long long time1=0,time2=0; +char p; +cin>>rok>>p>>mies>>p>>dni>>godz>>p>>mi>>p>>sek; +time1=time1+sek+(mi*60)+(godz*3600)+((dni-1)*86400); +for(int i=0;i>rok>>p>>mies>>p>>dni>>godz>>p>>mi>>p>>sek; +cin>>p; +time2=time2+sek+(mi*60)+(godz*3600)+((dni-1)*86400); +for(int i=0;i0){ + if(dni==1){ + cout<0){ + cout<0){ + cout<0){ + cout< +using namespace std; + +int tab[13]= {31,28,31,30,31,30,31,31,30,31,30,31}; + +int czas(string dt,string g) +{ + int lata,msc,dni; + long long c1,c2; + lata=dt[0]*1000+dt[1]*100+dt[2]*10+dt[3]-'0'*1111-1900; + msc=dt[5]*10+dt[6]-11*'0'; + dni=0; + c1=(dt[8]*10+dt[9]-11*'0'-1)*86400; + c1+=(g[0]*10+g[1]-11*'0')*3600; + c1+=(g[3]*10+g[4]-11*'0')*60; + c1+=g[6]*10+g[7]-11*'0'; + for(int i=0; i> dt >> g; + long long w1=czas(dt,g); + cin >> dt >> g; + int n; + cin >> n; + long long w2=czas(dt,g); + long long w=w2-w1; + int d=w/86400; + w%=86400; + int h=w/3600; + w%=3600; + int m=w/60; + w%=60; + int s=w; + if(d!=0) + { + cout << d << ' '; + if(d==1) + { + cout << "dzien "; + } + else + { + cout << "dni "; + } + } + if(h!=0) + { + cout << h << ' '; + if(h==1) + { + cout << "godzina "; + } + else if(h%10>=2 && h%10<=4 && (h<=11 || h>=15)) + { + cout << "godziny "; + } + else + { + cout << "godzin "; + } + + } + if(m!=0) + { + cout << m << ' '; + if(m==1) + { + cout << "minuta "; + } + else if(m%10>=2 && m%10<=4 && (m<=11 || m>=15)) + { + cout << "minuty "; + } + else + { + cout << "minut "; + } + + } + if(s!=0) + { + cout << s << ' '; + if(s==1) + { + cout << "sekunda "; + } + else if(h%10>=2 && h%10<=4 && (h<=11 || h>=15)) + { + cout << "sekundy "; + } + else + { + cout << "sekund "; + } + + } + cout << "\n"; +} + + + + diff --git a/semestr-4/sieci/warsztaty8/185992.cpp b/semestr-4/sieci/warsztaty8/185992.cpp new file mode 100644 index 0000000..491f748 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/185992.cpp @@ -0,0 +1,117 @@ +#include +using namespace std; + +void dziesiatki ( int x); +void sety ( int x); + +string od1do9[]= { "zero", "jeden", "dwa", "trzy", "cztery", "piec", "szesc", "siedem", "osiem", "dziewiec"}; +string od10do19[]= { "dziesiec", "jedenascie", "dwanascie", "trzynascie", "czternascie", "pietnascie", "szesnascie", "siedemnascie", "osiemnascie", "dziewietnascie"}; +string od20do90[]= {"", "dwadziescia", "trzydziesci", "czterdziesci", "piecdziesiat", "szescdziesiat", "siedemdziesiat", "osiemdziesiat", "dziewiecdziesiat"}; +string od200do900[]= { "", "dwiescie", "trzysta", "czterysta", "piecset", "szescset", "siedemset", "osiemset", "dziewiecset"}; + +void miliony ( int x) { + if ( x==1) { + cout<<"milion "; + return; + } + dziesiatki(x); + if ( ( x >= 2 && x<=4) || ( x%10 >= 2 && x%10<=4) ) { + cout<<"miliony "; + return; + } else { + cout<<"milionow "; + return; + } + +} + +void tysiace ( int x) { + if ( x==1) { + cout<<"tysiac "; + return; + } + if ( x==100) { + cout<<"sto tysiecy"; + return; + } + if ( x<10) { + if ( x<=4) { + cout<=10 && x<=99) { + dziesiatki(x); + if ( x%10>=2 && x%10<=4) { + cout<<"tysiece "; + return; + } + cout<<"tysiecy "; + return; + } + cout<=10 ) { + dziesiatki(x); + return; + } + if (x!=0 && x<10) { + cout<>n; + if ( n>=1000000) { + miliony ( n/1000000); + } + n=n%1000000; + if ( n>=1000) { + tysiace( n/1000); + } + n=n%1000; + sety (n); +} diff --git a/semestr-4/sieci/warsztaty8/186033.cpp b/semestr-4/sieci/warsztaty8/186033.cpp new file mode 100644 index 0000000..85911e3 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/186033.cpp @@ -0,0 +1,101 @@ +#include + +using namespace std; + +#define st first +#define nd second +#define pb push_back +#define sz(x) (int)(x).size() +#define ll long long +ll mod=1000000007; +int inf=1000000007; +ll infl=1000000000000000007; + +int seg[4*600007]; +int lazy[4*600007]; +int pot=1; + +void push(int v,int sz) +{ + if(lazy[v]!=0) + { + seg[2*v]=sz/2*lazy[v]; + lazy[2*v]=lazy[v]; + seg[2*v+1]=sz/2*lazy[v]; + lazy[2*v+1]=lazy[v]; + } + lazy[v]=0; +} + +void ins(int u,int a,int b,int l,int r,int v) +{ + if(a<=l&&b>=r) + { + lazy[u]=v; + seg[u]=(r-l+1)*v; + return ; + } + if(l>b||r=r) return seg[u]; + if(l>b||rmapa; +int l[100007]; +int r[100007]; + +int main() +{ + ios_base::sync_with_stdio(0); + cin.tie(0); + cout.tie(0); + int n,h,ans=2; + cin>>n>>h; + setS; + S.insert(1); + S.insert(h); + for(int i=1;i<=n;i++) + { + cin>>l[i]>>r[i]; + l[i]++; + if(l[i]!=h) S.insert(l[i]+1); + if(l[i]!=1) S.insert(l[i]-1); + if(r[i]!=h) S.insert(r[i]+1); + if(r[i]!=1) S.insert(r[i]-1); + S.insert(l[i]); + S.insert(r[i]); + } + int it=0; + mapa.reserve(sz(S)+2); + for(auto x:S) mapa[x]=++it; + for(int i=1;i<=n;i++) + { + l[i]=mapa[l[i]]; + r[i]=mapa[r[i]]; + } + while(pot + +using namespace std; + +#define st first +#define nd second +#define pb push_back +#define sz(x) (int)(x).size() +#define ll long long +ll mod=1000000007; +int inf=1000000007; +ll infl=1000000000000000007; + +int a[77][77]; +int id[77][77]; +int id1[77][77]; +int id2[77][77]; +setG[15007]; +int cap1[3507][3507]; +unordered_mapcap[15007]; +int o[15007]; +bool odw[15007]; +int s=1,t; +char ans[77][77][3][3]; + +bool dfs(int v) +{ + //cout<>n>>m; + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + cin>>a[i][j]; + for(int k=0;k<3;k++) for(int l=0;l<3;l++) ans[i][j][k][l]='.'; + if(a[i][j]!=0) ans[i][j][1][1]='O'; + sum[(i+j)%2]+=a[i][j]; + } + } + if(sum[0]!=sum[1]) gg(); + edge(1,2,sum[0]); + int it=2; + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + if(a[i][j]==0) continue; + id[i][j]=++it; + if(a[i][j]==2) + { + id1[i][j]=++it; + id2[i][j]=++it; + if((i+j)%2) + { + edge(id[i][j],id1[i][j],1); + edge(id[i][j],id2[i][j],1); + } + else + { + edge(id1[i][j],id[i][j],1); + edge(id2[i][j],id[i][j],1); + } + } + } + } + it+=2; + t=it; + edge(it-1,it,sum[0]); + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + if(a[i][j]==0) continue; + if((i+j)%2) edge(2,id[i][j],a[i][j]); + else edge(id[i][j],it-1,a[i][j]); + } + } + for(int i=1;i<=n;i++) + { + for(int j=1;j<=m;j++) + { + if((i+j)%2==0||a[i][j]==0) continue; + if(a[i-1][j]!=0) connect(i,j,i-1,j); + if(a[i+1][j]!=0) connect(i,j,i+1,j); + if(a[i][j-1]!=0) connect(i,j,i,j-1); + if(a[i][j+1]!=0) connect(i,j,i,j+1); + } + } + if(flow()!=sum[0]) gg(); + //cout< +using namespace std; + +typedef long long ll; +typedef long double ld; +typedef pair ii; +typedef vector vi; +typedef vector vii; +const int inf=0x3f3f3f3f; +const ll INF=0x3f3f3f3f3f3f3f3f; + +#define FOR(i, b, e) for(int i=b; i<=e; i++) +#define FORD(i, b, e) for(int i=b; i>=e; i--) +#define SIZE(x) ((int)x.size()) +#define pb push_back +#define st first +#define nd second +#define sp ' ' +#define ent '\n' + +ifstream out, wzor, in; + +int main(int argc, char *argv[]){ + assert(argc>=4); + + out.open(argv[1]); + wzor.open(argv[2]); + in.open(argv[3]); + + vector ans, user; + string pom; + while(wzor>>pom) ans.pb(pom); + while(out>>pom) user.pb(pom); + FOR(i, 1, 5) in>>pom; + + if(ans!=user) + { + if(pom != "0" && pom != "1" && pom != "3" && pom != "5"){ + cout << "Zla odpowiedz\n"; + exit(1); + } + int d=0, g=0, m=0, s=0; + FOR(i, 0, SIZE(ans)-1){ + if(ans[i][0]=='d') d=stoi(ans[i-1]); + if(ans[i][0]=='g') g=stoi(ans[i-1]); + if(ans[i][0]=='m') m=stoi(ans[i-1]); + if(ans[i][0]=='s') s=stoi(ans[i-1]); + } + if(SIZE(user)!=4 || stoi(user[0])!=d || stoi(user[1])!=g || stoi(user[2])!=m || stoi(user[3])!=s){ + cout << "Zla odpowiedz\n"; + exit(1); + } + } + + cout << "OK\n"; + exit(0); +} diff --git a/semestr-4/sieci/warsztaty8/dat0-check.e b/semestr-4/sieci/warsztaty8/dat0-check.e new file mode 100644 index 0000000..b0dcc41 Binary files /dev/null and b/semestr-4/sieci/warsztaty8/dat0-check.e differ diff --git a/semestr-4/sieci/warsztaty8/dat0-gen.sh b/semestr-4/sieci/warsztaty8/dat0-gen.sh new file mode 100644 index 0000000..a1640b1 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/dat0-gen.sh @@ -0,0 +1,107 @@ +#!/bin/bash + +echo -e "2019-01-08 00:00:00\n2019-01-09 00:00:00\n1" > dat1a.in +echo -e "2019-01-25 00:00:00\n2019-02-13 00:00:00\n1" > dat1b.in +echo -e "2019-01-25 00:00:00\n2019-03-13 00:00:00\n1" > dat1c.in +echo -e "2020-01-25 00:00:00\n2020-03-13 00:00:00\n1" > dat1d.in +echo -e "2000-01-25 00:00:00\n2000-03-13 00:00:00\n1" > dat1e.in +echo -e "2019-01-25 00:00:00\n2019-02-27 00:00:00\n1" > dat1f.in +echo -e "2019-01-25 00:00:00\n2019-03-27 00:00:00\n1" > dat1g.in +echo -e "2020-01-25 00:00:00\n2020-03-27 00:00:00\n1" > dat1h.in +echo -e "2000-01-25 00:00:00\n2000-03-27 00:00:00\n1" > dat1i.in +echo -e "2003-01-01 00:00:00\n2004-01-01 00:00:00\n1" > dat1j.in +echo -e "2004-01-01 00:00:00\n2005-01-01 00:00:00\n1" > dat1k.in +echo -e "2000-01-01 00:00:00\n2001-01-01 00:00:00\n1" > dat1l.in +echo -e "1999-01-01 00:00:00\n2000-01-01 00:00:00\n1" > dat1m.in +echo -e "1900-01-01 00:00:00\n2099-12-31 00:00:00\n1" > dat1n.in +echo -e "1945-04-17 00:00:00\n1974-01-17 00:00:00\n1" > dat1o.in +echo -e "2019-02-09 00:00:00\n2030-09-01 00:00:00\n1" > dat1p.in +echo -e "1992-11-13 00:00:00\n2049-01-13 00:00:00\n1" > dat1q.in + +echo -e "2019-01-08 00:00:00\n2019-01-09 00:00:00\n2" > dat2a.in +echo -e "2019-01-25 00:00:00\n2019-02-13 00:00:00\n2" > dat2b.in +echo -e "2019-01-25 00:00:00\n2019-03-13 00:00:00\n2" > dat2c.in +echo -e "2020-01-25 00:00:00\n2020-03-13 00:00:00\n2" > dat2d.in +echo -e "2000-01-25 00:00:00\n2000-03-13 00:00:00\n2" > dat2e.in +echo -e "2019-01-25 00:00:00\n2019-02-27 00:00:00\n2" > dat2f.in +echo -e "2019-01-25 00:00:00\n2019-03-27 00:00:00\n2" > dat2g.in +echo -e "2020-01-25 00:00:00\n2020-03-27 00:00:00\n2" > dat2h.in +echo -e "2000-01-25 00:00:00\n2000-03-27 00:00:00\n2" > dat2i.in +echo -e "2003-01-01 00:00:00\n2004-01-01 00:00:00\n2" > dat2j.in +echo -e "2004-01-01 00:00:00\n2005-01-01 00:00:00\n2" > dat2k.in +echo -e "2000-01-01 00:00:00\n2001-01-01 00:00:00\n2" > dat2l.in +echo -e "1999-01-01 00:00:00\n2000-01-01 00:00:00\n2" > dat2m.in +echo -e "1900-01-01 00:00:00\n2099-12-31 00:00:00\n2" > dat2n.in +echo -e "1945-04-17 00:00:00\n1974-01-17 00:00:00\n2" > dat2o.in +echo -e "2019-02-09 00:00:00\n2030-09-01 00:00:00\n2" > dat2p.in +echo -e "1992-11-13 00:00:00\n2049-01-13 00:00:00\n2" > dat2q.in + +echo -e "2000-01-01 00:00:00\n2000-01-01 00:00:01\n3" > dat3a.in +echo -e "2000-01-01 00:00:00\n2000-01-01 00:01:00\n3" > dat3b.in +echo -e "2000-01-01 00:00:00\n2000-01-01 01:00:00\n3" > dat3c.in +echo -e "2000-01-01 00:00:00\n2000-01-01 03:17:29\n3" > dat3d.in +echo -e "2000-01-01 00:00:00\n2000-01-01 19:15:59\n3" > dat3e.in +echo -e "2000-01-01 00:00:00\n2000-01-01 23:59:59\n3" > dat3f.in +echo -e "2000-01-01 00:00:01\n2000-01-01 00:01:00\n3" > dat3g.in +echo -e "2000-01-01 00:00:01\n2000-01-01 01:00:00\n3" > dat3h.in +echo -e "2000-01-01 00:00:01\n2000-01-01 03:17:29\n3" > dat3i.in +echo -e "2000-01-01 00:00:01\n2000-01-01 19:15:59\n3" > dat3j.in +echo -e "2000-01-01 00:00:01\n2000-01-01 23:59:59\n3" > dat3k.in +echo -e "2000-01-01 02:01:01\n2000-01-01 03:17:29\n3" > dat3l.in +echo -e "2000-01-01 04:01:01\n2000-01-01 19:15:59\n3" > dat3m.in +echo -e "2000-01-01 04:17:39\n2000-01-01 23:59:59\n3" > dat3n.in +echo -e "2000-01-01 02:01:57\n2000-01-01 03:17:29\n3" > dat3o.in + +echo -e "2000-01-01 00:00:00\n2000-01-01 00:00:01\n4" > dat4a.in +echo -e "2000-01-01 00:00:00\n2000-01-01 00:01:00\n4" > dat4b.in +echo -e "2000-01-01 00:00:00\n2000-01-01 01:00:00\n4" > dat4c.in +echo -e "2000-01-01 00:00:00\n2000-01-01 03:17:29\n4" > dat4d.in +echo -e "2000-01-01 00:00:00\n2000-01-01 19:15:59\n4" > dat4e.in +echo -e "2000-01-01 00:00:00\n2000-01-01 23:59:59\n4" > dat4f.in +echo -e "2000-01-01 00:00:01\n2000-01-01 00:01:00\n4" > dat4g.in +echo -e "2000-01-01 00:00:01\n2000-01-01 01:00:00\n4" > dat4h.in +echo -e "2000-01-01 00:00:01\n2000-01-01 03:17:29\n4" > dat4i.in +echo -e "2000-01-01 00:00:01\n2000-01-01 19:15:59\n4" > dat4j.in +echo -e "2000-01-01 00:00:01\n2000-01-01 23:59:59\n4" > dat4k.in +echo -e "2000-01-01 02:01:01\n2000-01-01 03:17:29\n4" > dat4l.in +echo -e "2000-01-01 04:01:01\n2000-01-01 19:15:59\n4" > dat4m.in +echo -e "2000-01-01 04:17:39\n2000-01-01 23:59:59\n4" > dat4n.in +echo -e "2000-01-01 02:01:57\n2000-01-01 03:17:29\n4" > dat4o.in + +echo -e "1917-06-04 13:25:19\n2045-04-19 11:17:39\n5" > dat5a.in +echo -e "1992-07-02 00:05:19\n2019-01-08 17:53:13\n5" > dat5b.in +echo -e "1900-01-01 00:00:00\n2099-12-31 23:59:59\n5" > dat5c.in +echo -e "1900-01-01 23:59:59\n2099-12-31 00:00:00\n5" > dat5d.in +echo -e "1959-10-13 17:14:40\n1965-10-25 19:10:53\n5" > dat5e.in +echo -e "2059-04-30 01:15:49\n2071-03-01 10:07:13\n5" > dat5f.in +echo -e "2010-02-19 20:49:10\n2061-02-28 15:40:49\n5" > dat5g.in + +echo -e "1917-06-04 13:25:19\n2045-04-19 11:17:39\n6" > dat6a.in +echo -e "1992-07-02 00:05:19\n2019-01-08 17:53:13\n6" > dat6b.in +echo -e "1900-01-01 00:00:00\n2099-12-31 23:59:59\n6" > dat6c.in +echo -e "1900-01-01 23:59:59\n2099-12-31 00:00:00\n6" > dat6d.in +echo -e "1959-10-13 17:14:40\n1965-10-25 19:10:53\n6" > dat6e.in +echo -e "2059-04-30 01:15:49\n2071-03-01 10:07:13\n6" > dat6f.in +echo -e "2010-02-19 20:49:10\n2061-02-28 15:40:49\n6" > dat6g.in + +echo -e "2010-10-10 11:59:59\n2010-11-02 10:22:21\n5" > dat5h.in +echo -e "1999-12-31 23:59:59\n2000-01-02 01:01:00\n5" > dat5i.in +echo -e "1985-01-15 21:55:53\n2009-11-12 23:21:10\n5" > dat5j.in +echo -e "2042-04-12 13:14:15\n2042-05-06 01:36:48\n5" > dat5k.in +echo -e "1931-01-01 23:01:58\n1931-01-01 23:59:58\n5" > dat5l.in +echo -e "2002-11-30 01:01:02\n2053-03-04 02:46:42\n5" > dat5m.in +echo -e "2022-02-22 22:59:23\n2022-03-01 04:03:26\n5" > dat5n.in +echo -e "1974-12-12 13:41:42\n2052-07-12 15:14:37\n5" > dat5o.in +echo -e "1922-12-31 23:59:59\n2022-01-02 00:00:00\n5" > dat5p.in + +echo -e "1997-01-12 22:59:23\n1997-02-15 00:01:26\n6" > dat6h.in +echo -e "1999-10-12 10:00:00\n2004-04-04 10:10:00\n6" > dat6i.in +echo -e "1923-03-14 11:22:53\n2009-11-12 11:21:34\n6" > dat6j.in +echo -e "2022-12-31 00:01:02\n2022-12-31 01:01:02\n6" > dat6k.in +echo -e "1988-11-11 12:11:59\n1989-01-01 11:10:02\n6" > dat6l.in +echo -e "2002-11-30 01:01:02\n2053-03-04 01:46:42\n6" > dat6m.in +echo -e "2022-02-22 22:59:23\n2022-03-01 03:03:26\n6" > dat6n.in +echo -e "1974-12-12 13:41:42\n2052-07-12 11:14:37\n6" > dat6o.in +echo -e "1922-12-31 23:59:59\n2022-01-02 20:00:00\n6" > dat6p.in + +g++ dat0-check.cpp -o dat0-check.e -O2 -std=c++11 diff --git a/semestr-4/sieci/warsztaty8/mie1.cpp b/semestr-4/sieci/warsztaty8/mie1.cpp new file mode 100644 index 0000000..f7eef7e --- /dev/null +++ b/semestr-4/sieci/warsztaty8/mie1.cpp @@ -0,0 +1,64 @@ +#include +#include +#include +using namespace std; + +#define EPS 0.000001 + +int main() { + int numLiquids, reqCon, liquid[101]; + double sumSubst=0, sumLiquid=0, actCon; + + fill(liquid,liquid+101,0); + + scanf("%d%d",&numLiquids,&reqCon); + + for (int i=0;i0)) { + double perc=(double)i/100, toSub=(double)((double)reqCon*sumLiquid-100*sumSubst)/((double)reqCon-(double)100*perc); + + toSub=min(toSub,(double)liquid[i]); + + sumLiquid-=toSub; + sumSubst-=(toSub*i)/100; + } + if ((actCon>(double)reqCon)&&(liquid[100-i]>0)) { + double perc=(double)(100-i)/100, toSub=(double)((double)reqCon*sumLiquid-100*sumSubst)/((double)reqCon-(double)100*perc); + + toSub=min(toSub,(double)liquid[100-i]); + + sumLiquid-=toSub; + sumSubst-=(toSub*(100-i))/100; + } + + if (sumLiquid==0) { + printf("0.000\n"); + return 0; + } + actCon=(sumSubst/sumLiquid)*100; + + if (fabs((double)reqCon-actCon) + +using namespace std; + +const int MAXN = 70; +int tab[MAXN][MAXN]; +char out[3*MAXN][3*MAXN]; +int N, M; + +int id(int x, int y, int strona){ //0 - prawo, 1 - g�ra, 2 - lewo, 3 - d�� + if(strona == 0){ + if(x+1 >= N) return -1; + if(tab[x+1][y] == 0) return -1; + if(tab[x+1][y] == 1) return 5*(MAXN*(x+1)+y); + if(tab[x+1][y] == 2) return 5*(MAXN*(x+1)+y); + if(tab[x+1][y] == 3) return 5*(MAXN*(x+1)+y)+2; + if(tab[x+1][y] == 4) return 5*(MAXN*(x+1)+y)+2; + } + if(strona == 1){ + if(y+1 >= M) return -1; + if(tab[x][y+1] == 0) return -1; + if(tab[x][y+1] == 1) return 5*(MAXN*x+y+1); + if(tab[x][y+1] == 2) return 5*(MAXN*x+y+1)+1; + if(tab[x][y+1] == 3) return 5*(MAXN*x+y+1)+3; + if(tab[x][y+1] == 4) return 5*(MAXN*x+y+1)+3; + } + if(strona == 2){ + if(x-1 < 0) return -1; + if(tab[x-1][y] == 0) return -1; + if(tab[x-1][y] == 1) return 5*(MAXN*(x-1)+y); + if(tab[x-1][y] == 2) return 5*(MAXN*(x-1)+y); + if(tab[x-1][y] == 3) return 5*(MAXN*(x-1)+y); + if(tab[x-1][y] == 4) return 5*(MAXN*(x-1)+y); + } + if(strona == 3){ + if(y-1 < 0) return -1; + if(tab[x][y-1] == 0) return -1; + if(tab[x][y-1] == 1) return 5*(MAXN*x+y-1); + if(tab[x][y-1] == 2) return 5*(MAXN*x+y-1)+1; + if(tab[x][y-1] == 3) return 5*(MAXN*x+y-1)+1; + if(tab[x][y-1] == 4) return 5*(MAXN*x+y-1)+1; + } +} + +set real_v; +vector edges[5*MAXN*MAXN+5]; +int match[5*MAXN*MAXN+5]; +bool mark[5*MAXN*MAXN+5]; +bool dfs(int v){ + if(real_v.count(v) == 0) return false; + if(mark[v]) return false; + mark[v] = true; + for(auto &u : edges[v]) + if(match[u] == -1 || dfs(match[u])) + return match[v] = u, match[u] = v, true; + return false; +} + +int main(){ + cin >> N >> M; + for(int i = 0; i < N; i++){ + for(int j = 0; j < M; j++){ + cin >> tab[i][j]; + } + } + + for(int i = 0; i < N; i++){ + for(int j = 0; j < M; j++){ + if(tab[i][j] == 1){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)].push_back(id(i, j, k)); + } + real_v.insert(5*(MAXN*i+j)); + } + if(tab[i][j] == 2){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)+(k%2)].push_back(id(i, j, k)); + } + real_v.insert(5*(MAXN*i+j)), real_v.insert(5*(MAXN*i+j)+1); + } + if(tab[i][j] == 3){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)+k].push_back(id(i, j, k)); + edges[5*(MAXN*i+j)+k].push_back(5*(MAXN*i+j)+4); + edges[5*(MAXN*i+j)+4].push_back(5*(MAXN*i+j)+k); + } + real_v.insert(5*(MAXN*i+j)), real_v.insert(5*(MAXN*i+j)+1), real_v.insert(5*(MAXN*i+j)+2), real_v.insert(5*(MAXN*i+j)+3), real_v.insert(5*(MAXN*i+j)+4); + } + if(tab[i][j] == 4){ + for(int k = 0; k < 4; k++){ + if(id(i, j, k) != -1) edges[5*(MAXN*i+j)+k].push_back(id(i, j, k)); + } + real_v.insert(5*(MAXN*i+j)), real_v.insert(5*(MAXN*i+j)+1), real_v.insert(5*(MAXN*i+j)+2), real_v.insert(5*(MAXN*i+j)+3); + } + } + } + + /*for(int i = 0; i < 5*MAXN*MAXN+5; i++){ + if(!edges[i].empty()){ + cerr << "Edges of " << i << ": "; + for(int v : edges[i]) cerr << v << " "; + cerr << "\n"; + } + }*/ + + for(int i = 0; i < 5*MAXN*MAXN+5; i++) match[i] = -1; + for(int i = 0; i < 5*MAXN*MAXN+5; i++) + if(match[i] == -1){ + memset(mark, false, sizeof mark); + dfs(i); + } + + for(int i : real_v) if(match[i] == -1){ + cout << "NIE"; + return 0; + } + + for(int i = 0; i < N; i++){ + for(int j = 0; j < M; j++){ + if(tab[i][j] == 1){ + int str; + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)] == id(i, j, k)){ + str = k; + } + out[3*i+1][3*j+1] = 'O'; + if(str == 0) out[3*i+2][3*j+1] = 'X'; + if(str == 1) out[3*i+1][3*j+2] = 'X'; + if(str == 2) out[3*i][3*j+1] = 'X'; + if(str == 3) out[3*i+1][3*j] = 'X'; + } + if(tab[i][j] == 2){ + int strh, strv; + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)] == id(i, j, k)){ + strh = k; + } + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)+1] == id(i, j, k)){ + strv = k; + } + out[3*i+1][3*j+1] = 'O'; + if(strh == 0) out[3*i+2][3*j+1] = 'X'; + if(strv == 1) out[3*i+1][3*j+2] = 'X'; + if(strh == 2) out[3*i][3*j+1] = 'X'; + if(strv == 3) out[3*i+1][3*j] = 'X'; + } + if(tab[i][j] == 3){ + int str; + for(int k = 0; k < 4; k++) if(match[5*(MAXN*i+j)+4] == 5*(MAXN*i+j)+k){ + str = k; + } + out[3*i+1][3*j+1] = 'O'; + out[3*i+2][3*j+1] = 'X'; + out[3*i+1][3*j+2] = 'X'; + out[3*i][3*j+1] = 'X'; + out[3*i+1][3*j] = 'X'; + if(str == 0) out[3*i+2][3*j+1] = '.'; + if(str == 1) out[3*i+1][3*j+2] = '.'; + if(str == 2) out[3*i][3*j+1] = '.'; + if(str == 3) out[3*i+1][3*j] = '.'; + } + if(tab[i][j] == 4){ + out[3*i+1][3*j+1] = 'O'; + out[3*i+2][3*j+1] = 'X'; + out[3*i+1][3*j+2] = 'X'; + out[3*i][3*j+1] = 'X'; + out[3*i+1][3*j] = 'X'; + } + } + } + + for(int i = 0; i < 3*N; i++){ + for(int j = 0; j < 3*M; j++){ + if(!out[i][j]) cout << "."; + else cout << out[i][j]; + } + cout << "\n"; + } +} diff --git a/semestr-4/sieci/warsztaty8/prz9.cpp b/semestr-4/sieci/warsztaty8/prz9.cpp new file mode 100644 index 0000000..952daac --- /dev/null +++ b/semestr-4/sieci/warsztaty8/prz9.cpp @@ -0,0 +1,97 @@ +// solution written by Michal 'misof' Forisek +#include +#include +#include +#include +using namespace std; + +#define FOREACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it) + +class MaximumMatching { + int left_size, right_size; + vector< vector > right_to_left; + + public: + MaximumMatching() { left_size=right_size=0; right_to_left.clear(); } + void add_edge(int left, int right); + vector< pair > maximum_matching(); +}; + +void MaximumMatching::add_edge(int left, int right) { + if (left==-1 || right==-1) return; + if (left_size <= left) left_size = left+1; + if (right_size <= right) { right_size = right+1; right_to_left.resize(right_size); } + right_to_left[right].push_back(left); +} + +vector< pair > +MaximumMatching::maximum_matching() { + int L = left_size, R = right_size; + vector match(L,-1); + for (int r=0; r from(L,-1); + queue Q; + FOREACH(it,right_to_left[r]) { Q.push(*it); from[*it]=*it; } + while (!Q.empty() && !found) { + int l = Q.front(); Q.pop(); + if (match[l]==-1) { + found = true; + while (from[l]!=l) { match[l] = match[from[l]]; l = from[l]; } + match[l]=r; + } else { + FOREACH(it,right_to_left[ match[l] ]) if (from[*it]==-1) { Q.push(*it); from[*it]=l; } + } + } + } + vector< pair > result; + for (int i=0; i > A; // the map of the island + +int ENCODE(int r, int c, int n) { return (C*r+c)*5+n; } +int LEFT(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,0); else return ENCODE(r,c,1); } +int RIGHT(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,0); else return ENCODE(r,c,3); } +int TOP(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]==2) return ENCODE(r,c,1); else return ENCODE(r,c,0); } +int BOTTOM(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,A[r][c]-1); else return ENCODE(r,c,2); } +#define VERTEX(r,c,dir) ( ((r<0) || (c<0) || (r>=R) || (c>=C)) ? -1 : dir(r,c) ) + +int main() { + // read the input + cin >> R >> C; + A.resize(R, vector(C) ); + for (int r=0; r> A[r][c]; + + // create the bipartite graph + MaximumMatching MM; + for (int r=0; r > matching = MM.maximum_matching(); + if (2*matching.size() != expected_size) { cout << "NIE" << endl; return 0; } + + // from the edges of the matching, reconstruct the map + set< pair > edges; + FOREACH(it,matching) { edges.insert(make_pair(it->first,it->second)); edges.insert(make_pair(it->second,it->first)); } + vector output(3*R, string(3*C,'.')); + for (int r=0; r +#include +using namespace std; +#define rand_mod 1000000033 +int rozm, zapy, ds[200000], dl; +typedef long long LL; +LL sum, wcz[200000], rand_plus, ele[6]; +bool cmp(int x, int y) +{ + return wcz[x] < wcz[y]; +} +int main() +{ + scanf("%d%Ld", &rozm, &rand_plus); + scanf("%d", &zapy); + for (int i = 0; i < zapy; ++i) + { + scanf("%Ld%Ld", wcz + 2 * i, wcz + 2 * i + 1); + --wcz[2 * i]; + } + for (int i = 0; i < 2 * zapy; ++i) + ds[i] = i; + sort(ds, ds + 2 * zapy, cmp); + while (dl < 2 * zapy && !wcz[ds[dl]]) + ++dl; + + for (int i = 1; i <= rozm; ++i) + { + ele[0] = (ele[1] * ele[1]) % rand_mod; + ele[0] += ((ele[2] + ele[3]) * (ele[2] + ele[3])) % rand_mod; + ele[0] += (ele[4] * ele[5]) % rand_mod; + ele[0] += (rand_plus * rand_plus) % rand_mod; + ele[0] += i % rand_mod; + ele[0] %= rand_mod; + sum += ele[0]; + while (dl < 2 * zapy && wcz[ds[dl]] == i) + wcz[ds[dl++]] = sum; + for (int i = 4; i >= 0; i--) ele[i+1] = ele[i]; + ele[0] = 0; + } + for (int i = 0; i < zapy; ++i) + printf("%Ld\n", wcz[2 * i + 1] - wcz[2 * i]); + return 0; +} diff --git a/semestr-4/sieci/warsztaty8/w8.pdf b/semestr-4/sieci/warsztaty8/w8.pdf new file mode 100644 index 0000000..91676f4 Binary files /dev/null and b/semestr-4/sieci/warsztaty8/w8.pdf differ diff --git a/semestr-4/sieci/warsztaty8/wie5.cpp b/semestr-4/sieci/warsztaty8/wie5.cpp new file mode 100644 index 0000000..0821777 --- /dev/null +++ b/semestr-4/sieci/warsztaty8/wie5.cpp @@ -0,0 +1,158 @@ +#include + +using namespace std; +typedef long long ll; + +mt19937 rng(rand()); +const int MAXDEG = 10000; +long long poly[MAXDEG+1]; +int deg; + +int gcd(int a, int b){ + return !b ? a : gcd(b, a%b); +} + +struct rat{ + int sign; + int num, den; + + void cancel(){ + int d = gcd(num, den); + this->num /= d; + this->den /= d; + } + + rat(int a, int b){ + this->sign = 1; + if(a == 0){ + this->sign = 0; + this->num = 0; + this->den = 1; + return; + } + if(b < 0){ + this->sign = -1; + } + this->den = abs(b); + if(a < 0){ + this->sign = -(this->sign); + } + this->num = abs(a); + cancel(); + } + + bool operator<(const rat &x) const { + if(this->sign != x.sign) return this->sign < x.sign; + + bool abs_less; + long long int left = (long long)(this->num) * (long long)(x.den); + long long int right = (long long)(x.num) * (long long)(this->den); + abs_less = left < right; + + if(left == right) return false; + if(this->sign == -1) return !abs_less; + if(this->sign == 0) return false; + if(this->sign == 1) return abs_less; + } + + bool operator==(const rat &x) const { + return this->sign == x.sign && this->num == x.num && this->den == x.den; + } + + friend ostream& operator<<(ostream &stream, const rat &x){ + if(x.sign == -1) stream << '-'; + stream << x.num << "/" << x.den; + return stream; + } +}; + +ll W(rat x, int mod){ + ll out = 0; + ll den_pow = 1; + ll num = x.num; + ll den = x.den; + if(x.sign == -1) num = mod-num; + for(int i = deg; i >= 0; i--){ + out += (poly[i]*den_pow)%mod; + if(i) out *= num; + out %= mod; + den_pow = (den_pow * den)%mod; + } + //cerr << x << " " << mod << " " << out << endl; + return out; +} + +bool check(rat x){ + for(int i = 0; i < 20; i++){ + int p = uniform_int_distribution(2, 1000000000)(rng); + if(W(x, p)){ + //cerr << x << " " << p << endl; + return false; + } + } + return true; +} + +vector< int > nums; +vector< int > dens; +vector< rat > candidates_mult; +vector< rat > candidates; +void cands(){ + for(int i = 1; i*i <= abs(poly[0]); i++){ + if(abs(poly[0]) % i) continue; + nums.push_back(i); + nums.push_back(-i); + nums.push_back(poly[0]/i); + nums.push_back(-poly[0]/i); + } + + for(int i = 1; i*i <= abs(poly[deg]); i++){ + if(abs(poly[deg]) % i) continue; + dens.push_back(i); + dens.push_back(poly[deg]/i); + } + + //cerr << nums.size() << " * " << dens.size() << " = " << (nums.size())*(dens.size()) << endl; + + for(int p : nums){ + for(int q : dens){ + candidates_mult.push_back({p, q}); + } + } + sort(candidates_mult.begin(), candidates_mult.end()); + candidates.push_back(candidates_mult[0]); + for(int i = 1; i < candidates_mult.size(); i++){ + if(!(candidates_mult[i-1] == candidates_mult[i])){ + candidates.push_back(candidates_mult[i]); + } + } + + //for(rat r : candidates) cerr << r << endl; +} + +vector< rat > s; +void solve(){ + if(!poly[0]){ + s.push_back({0, 1}); + int k = 0; + while(poly[k] == 0) k++; + for(int i = 0; i <= deg-k; i++) poly[i] = poly[i+k]; + deg -= k; + } + + cands(); + for(rat c : candidates) if(check(c)) s.push_back(c); + sort(s.begin(), s.end()); + cout << s.size() << "\n"; + for(rat i : s) cout << i << " "; +} + +int main(){ + ios_base::sync_with_stdio(0); + cin.tie(0); + cout.tie(0); + + cin >> deg; + for(int i = 0; i <= deg; i++) cin >> poly[deg-i]; + solve(); +} diff --git a/semestr-4/sieci/warsztaty8/wie5.pdf b/semestr-4/sieci/warsztaty8/wie5.pdf new file mode 100644 index 0000000..cd5637b Binary files /dev/null and b/semestr-4/sieci/warsztaty8/wie5.pdf differ -- cgit v1.2.3