Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT138E/ 1. Đề bài PTIT138E spoj Cho trước một số nguyên, người ta sẽ làm tròn số này theo quy tắc sau: Nếu số đó lớn hơn 10 thì sẽ được làm tròn đến số hàng chục gần nhất Sau đó nếu kết quả lớn hơn 100 thì làm tròn đến số […]
spoj
P167PROE spoj PTIT – ROUND 7E – Phương trình
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P167PROE/ 1. Đề bài P167PROE spoj Cho , hãy đếm số nghiệm nguyên dương của phương trình: Input Dòng đầu chứa số nguyên T là số bộ test (T <= 100); T dòng sau, mỗi dòng chứa số nguyên dương n (n <= 106). Output Gồm T dòng, mỗi dòng là số lượng nghiệm […]
PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
Nguồn đề bài: http://vn.spoj.com/PTIT/problems/PTIT016E/ 1. Đề bài PTIT016E spoj Kỳ thi ACM/ICPC được tổ chức giữa các trường đại học ở Việt Nam. Mỗi trường sẽ chọn ra một đội gồm 3 thí sinh để thi đấu. Để chuẩn bị tốt cho kỳ thi, trường XYZ đã có kế hoạch tập huấn cho sinh viên với chủ […]
PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016D/ 1. Đề bài PTIT016D spoj Một dãy gồm n số nguyên không âm a1, a2,…, an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng […]
Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016C/ 1. Đề bài PTIT016C spoj An rất thích những gì có tính thứ tự nên muốn tìm các số nguyên dương mà chữ số ở vị trí chẵn thì là số chẵn còn chữ số ở vị trí lẻ thì là số lẻ. Hãy giúp An thực hiện công việc trên. Input Dòng […]
PTIT127A spoj PTIT – Tổ chức kì thi
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT127A/ 1. Đề bài PTIT127A spoj Một cuộc thi gồm có M nữ và N nam đăng kí. Ban tổ chức cần xếp đội cho các thí sinh theo quy tắc như sau: Mỗi đội gồm 2 nữ và 1 nam. Tuy nhiên, ban tổ chức cần K người để tham gia vào công […]
Cây khung nhỏ nhất QBMST spoj: Kruskal, Prim heap
Code QBMST được viết bằng thuật toán Kruskal Pascal Mình đã bỏ một số phần thừa trong sách TLGK Chuyên tin Thuật toán kruskal dưới đây được biểu diễn đồ thị bằng danh sách cạnh trong lí thuyết đồ thị:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | const fi=''; nmax=15500; type data=longint; var f:text; u,v,c:array[1..nmax] of data; root:array[1..nmax] of data; n,m:data; procedure docfile; var i:data; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to m do readln(f,u[i],v[i],c[i]); close(f); end; procedure swap(var a,b:data); var z:data; begin z:=a; a:=b; b:=z; end; procedure quicksort(l,r:data); var i,j,mid:data; begin i:=l; j:=r; mid:=c[(l+r) div 2]; repeat while c[i] < mid do i:=i+1; while c[j] > mid do j:=j-1; if i<= j then begin swap(u[i],u[j]); swap(c[i],c[j]); swap(v[i],v[j]); i:=i+1; j:=j-1; end; until i>j; if i<r then quicksort(i,r); if j>l then quicksort(l,j); end; function findroot(x:data):data; begin if root[x]<>x then root[x]:=findroot(root[x]); exit(root[x]); end; procedure union(x,y:data); begin root[x]:=y; end; procedure kruskal; var i,ur,uv:data; t:longint; begin for i:=1 to n do root[i]:=i; t:=0; for i:=1 to m do begin ur:=findroot(u[i]); uv:=findroot(v[i]); if ur<>uv then begin union(ur,uv); t:=t+c[i]; end; end; writeln(t); end; begin docfile; Quicksort(1,m); kruskal; end. |
Code QBMST được viết bằng Prim Heap Pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | const fi=''; nmax=11000; mmax=30000; maxc=50000; type data=longint; var f:text; adj,adc:array[0..2*mmax+2] of data; tmp,tmpc,head,u,v,C,heap,pos,d:array[0..mmax+1] of data; dd:array[0..nmax+1] of boolean; n,m,k,s,t,nheap:data; procedure swaps(u,v:data); var k,i,j:data; begin k:=0; for i:=u to v do begin inc(k); tmp[k]:=adj[i]; tmpc[k]:=adc[i]; end; for i:=u to v do begin adj[i]:=tmp[k]; adc[i]:=tmpc[k]; dec(K); end; end; procedure swap(var a,b:data); var z:data; begin z:=a; a:=b; b:=z; end; procedure upheap(i:data); begin if (i div 2=0) or (d[heap[i]]>d[heap[i div 2]]) then exit; swap(heap[i],heap[i div 2]); swap(pos[heap[i]],pos[heap[i div 2]]); upheap(i div 2); end; procedure downheap(i:data); var j:data; begin j:=i*2; if j>nHeap then exit; if (j<nHeap) and (d[heap[j]]>d[heap[j+1]]) then inc(j); if d[heap[i]]<=d[heap[j]] then exit; swap(heap[i],heap[j]); swap(pos[heap[i]],pos[heap[j]]); downheap(j); end; procedure push(x:data); begin inc(nHeap); heap[nHeap]:=x; upheap(Nheap); end; function pop:data; begin pop:=Heap[1]; heap[1]:=heap[nheap]; dec(nheap); downheap(1); end; Procedure update(i:longint); Begin if (i=1) or (d[heap[i]]>d[heap[i div 2]]) then exit; swap(heap[i],heap[i div 2]); swap(pos[heap[i]],pos[heap[i div 2]]); update(i div 2); End; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); read(f,n,m); fillchar(head,sizeof(head),0); for i:=1 to m do begin read(f,u[i],v[i],c[i]); inc(head[u[i]]); inc(head[v[i]]); end; for i:=1 to n+1 do head[i]:=head[i-1]+head[i]; for i:=1 to m do begin adj[head[u[i]]]:=v[i]; adc[head[u[i]]]:=c[i]; dec(head[u[i]]); adj[head[v[i]]]:=u[i]; adc[head[v[i]]]:=c[i]; dec(head[v[i]]); end; close(f); for i:=1 to n do swaps(head[i]+1,head[i+1]); end; procedure prim; var i,j,u,v,res:data; begin for i:=1 to n do begin heap[i]:=i; pos[i]:=i; d[i]:=maxc; end; d[1]:=0; fillchar(dd,sizeof(dd),false); nHeap:=n; Update(1); repeat u:=pop; dd[u]:=true; for v:=head[u]+1 to head[u+1] do if (not dd[adj[v]]) and (d[adj[v]]>adc[v]) then begin d[adj[v]]:=adc[v]; upheap(pos[adj[v]]); end; until nheap=0; res:=0; for i:=1 to n do res:=res+d[i]; writeln(res); end; begin docfile; prim; end. |
P167PROD spoj PTIT – ROUND 7D – ABC
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P167PROD/ 1. Đề bài P167PROD spoj Cho đẳng thức a + b = c, trong 3 số này có 1 số bị mờ đi một chữ số (được thay bằng dấu ?), hãy tìm chữ số đó. Input Dòng đầu chứa một số nguyên không âm a; Dòng thứ hai chứa một số nguyên […]
PBCSEQ SPOJ – Các đoạn nguyên
Nguồn đề bài: http://vn.spoj.com/problems/PBCSEQ/ 1. Đề bài PBCSEQ SPOJ Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được […]
NKTEAM spoj – Team Selection
Nguồn đề bài: http://vn.spoj.com/problems/NKTEAM/ 1. Đề bài NKTEAM spoj Các trưởng đoàn đội tuyển tin học vùng Balkan muốn chọn ra những thí sinh mạnh nhất trong khu vực từ N thí sinh (3 ≤ N ≤ 100000). Các trưởng đoàn tổ chức 3 kỳ thi, mỗi thí sinh sẽ tham dự cả 3. Biết rằng không […]