Hak Cipta Dilindungi Undang-undang
SOLUSI UJIAN OLIMPIADE SAINS NASIONAL 2013 CALON PESERTA INTERNATIONAL OLYMPIAD IN INFORMATICS (IOI) 2014 HARI KE-2
INFORMATIKA Waktu : 5 jam
KEMENTERIAN PENDIDIKAN DAN KEBUDAYAAN DIREKTORAT JENDERAL PENDIDIKAN MENENGAH DIREKTORAT PEMBINAAN SEKOLAH MENENGAH ATAS TAHUN 2013
Mengosongkan Matriks Batas Waktu: 1 detik Batas Memori: 32 MB #include #include #include #include
using namespace std; int i,j,n,m,ctr,minim,maxim,ans; int a[30][30]; int halo1[300007],halo2[300007],halo3[300007]; char s[1007]; bool sama; void proses(int com, int x, int y) { int i,j,yow; if (com == 1) { ans++; halo1[ans] = 1; halo2[ans] = x; halo3[ans] = y; for (i=1 ; i<=n } if (com == 2) { ans++; halo1[ans] = 2; halo2[ans] = x; halo3[ans] = y; for (i=1 ; i<=n } if (com == 3) { ans++; halo1[ans] = 3; halo2[ans] = x; halo3[ans] = y; yow = 1; for (i=1 ; i<=y for (j=1 ; j<=m 1000000007; }
; i++) a[i][x] = (a[i][x] + y) % 1000000007;
; i++) a[i][x] = (a[i][x] - y) % 1000000007;
; i++) yow = ((long long)yow * 2) % 1000000007; ; j++) a[x][j] = ((long long)a[x][j] * yow) %
/* printf("%d %d %d\n",halo1[ans],halo2[ans],halo3[ans]); for (i=1 ; i<=n ; i++) { for (j=1 ; j<=m ; j++) printf(" %d",a[i][j]); printf("\n"); } // scanf("%d",&yow); */ } int main() { gets(s); scanf("%d%d",&n,&m); for (i=1 ; i<=n ; i++) { for (j=1 ; j<=m ; j++) scanf("%d",&a[i][j]);
Solusi Hari-2 - 1
} for (j=1 ; j<=m ; j++) { //printf("KOLOM = %d\n",j); sama = true; minim = a[1][j]; maxim = a[1][j]; for (i=1 ; i<=n ; i++) { if (a[i][j] != a[1][j]) { sama = false; //printf("%d %d\n",i,j); } minim = min(minim,a[i][j]); maxim = max(maxim,a[i][j]); } //printf("%d\n",sama); while (!sama) { while (minim == 0) { proses(1,j,1); minim = a[1][j]; maxim = a[1][j]; for (i=1 ; i<=n ; i++) { minim = min(minim,a[i][j]); maxim = max(maxim,a[i][j]); } } for (i=1 ; i<=n ; i++) { minim = a[1][j]; maxim = a[1][j]; int k; for (k=1 ; k<=n ; k++) { minim = min(minim,a[k][j]); maxim = max(maxim,a[k][j]); } ctr = 0; while (a[i][j] * (1 << (ctr+1)) <= maxim) ctr++; if (ctr != 0) proses(3,i,ctr); } sama = true; for (i=1 ; i<=n ; i++) if (a[i][j] != a[1][j]) sama = false; if (!sama) { minim = a[1][j]; maxim = a[1][j]; for (i=1 ; i<=n ; i++) { minim = min(minim,a[i][j]); maxim = max(maxim,a[i][j]); } proses(2,j,minim-1); } } if (a[1][j] != 0) proses(2,j,a[1][j]); }
Solusi Hari-2 - 2
printf("%d\n",ans); for (i=1 ; i<=ans ; i++) printf("%d %d %d\n",halo1[i],halo2[i],halo3[i]); }
Solusi Hari-2 - 3
Kontes Menari Batas Waktu: 2 detik Batas Memori: 32MB #include #include #include #include #include #include
#include #include #include #include #include
<string>
using namespace std; #define REP(i,n) for (int i = 0, _n = (int)n; i < _n; i++) #define FOR(i,a,b) for (int i = (int)a, _b = (int)b; i <= _b; i++) #define RESET(c,v) memset(c, v, sizeof(c)) #define FOREACH(i,c) for (typeof((c).end()) i = (c).begin(); i != (c).end(); ++i) typedef long long ll; #define pb push_back #define mp make_pair const int MAX = 15; int N, R, Y, J; int K[MAX]; char T[MAX][5]; bool used[MAX]; int cur[MAX]; int cnt[100002]; void go(int r) { if (r == R) { int res = 0; int add = 0; REP(i, R) { int val = K[cur[i]]; if (i && T[cur[i-1]][0] == 'P') val *= 2; if (i && T[cur[i-1]][0] == 'L') val /= 2; res += val + add; if (T[cur[i]][0] == 'Y') add = Y; } cnt[res]++;
Solusi Hari-2 - 4
return; } REP(i, N) if (!used[i]) { cur[r] = i; used[i] = true; go(r+1); used[i] = false; } } int main() { scanf("%*s%*d"); scanf("%d%d%d%d", &N, &R, &Y, &J); REP(i, N) scanf("%d%s", &K[i], T[i]); go(0); for (int i = 100000; i >= 0; i--) cnt[i] += cnt[i+1]; REP(i, J) { int h; scanf("%d", &h); printf("%d\n", cnt[h+1]); } }
Solusi Hari-2 - 5
Cuti Liburan Batas Waktu: 2 detik Batas Memori: 32MB #include #include #include #include #include #include
#include #include #include #include #include
<string>
using namespace std; #define REP(i,n) for (int i = 0, _n = (int)n; i < _n; i++) #define FOR(i,a,b) for (int i = (int)a, _b = (int)b; i <= _b; i++) #define RESET(c,v) memset(c, v, sizeof(c)) #define FOREACH(i,c) for (typeof((c).end()) i = (c).begin(); i != (c).end(); ++i) typedef long long ll; #define pb push_back #define mp make_pair const int MAX = 100, INF = 999999999; int N, P, Q; int B[MAX], D[MAX], W[MAX]; int dp[MAX][505+1][MAX+1][2]; int DP(int i, int berat, int warna, int sudah) { if (i == N) return warna >= Q ? 0 : -INF; if (i && W[i] != W[i-1] && sudah) return DP(i, berat, warna, 0); if (dp[i][berat][warna][sudah] == -1) { dp[i][berat][warna][sudah] = DP(i+1, berat, warna, sudah); if (berat + B[i] <= P) dp[i][berat][warna][sudah] = max(dp[i][berat][warna][sudah], D[i] + DP(i+1, berat + B[i], warna + 1 - sudah, 1)); } return dp[i][berat][warna][sudah]; } int main() { scanf("%*s%*d"); scanf("%d%d%d", &N, &P, &Q); REP(i, N)
Solusi Hari-2 - 6
scanf("%d%d%d", &B[i], &D[i], &W[i]); REP(i, N) REP(j, N-1) if (W[j] > W[j+1]) { swap(B[j], B[j+1]); swap(D[j], D[j+1]); swap(W[j], W[j+1]); } RESET(dp, -1); int res = DP(0, 0, 0, 0); printf("%d\n", res < 0 ? -1 : res); }
Solusi Hari-2 - 7
Pabrik Kue Batas Waktu: 3 detik Batas Memori: 64MB #include #include #include #include #include #include #include #include #include
<string> <memory.h>
#define MP make_pair #define PII pair #define RESET(c,x) memset(c, x, sizeof(c)) using namespace std; char dummy[100]; // algorithm parameters #define CHECKINGPERIOD 10 #define STOPCHECKING 400 #define #define #define #define
NCAKE 100 NSELCACHE 10 MINK 1 MAXK 20
#define MAXT 1000 #define F first #define S second #define oo 1000111000 int binary[NCAKE + 5][MAXT + 5]; int freq[NCAKE + 5][MAXT + 5]; PII sorted[NCAKE + 5]; pair <double, int> sortedP[NCAKE + 5]; int T; int K[NCAKE + 5]; double P[NCAKE + 5][MAXK + 5]; int ctr[MAXT + 5]; template inline T ABS(T x) { if (x < 0) return -x; return x; } int main() { // read subsoal gets(dummy); scanf("%d", &T); RESET(freq, 0); RESET(binary, 0);
Solusi Hari-2 - 8
for (int t1 = 0; t1 < T; t1++) { if (t1 <= STOPCHECKING) { // check periods for (int i = 0; i < NCAKE; i++) { int mn = oo; for (int k = MINK; k <= MAXK; k++) { int fault = 0; for (int t = k; t < t1; t++) { if (ABS(freq[i][t] - freq[i][t - k]) == 1) { fault++; } } if (fault < mn) { mn = fault; K[i] = k; } } } } //predict P for (int i = 0; i < NCAKE; i++) { for (int k = 0; k < K[i]; k++) { ctr[k] = 0; P[i][k] = 0; } for (int t = 0; t <= t1; t++) { P[i][t % K[i]] += 1.0 * freq[i][t]; ctr[t % K[i]]++; } for (int k = 0; k < K[i]; k++) { P[i][k] /= ctr[k]; } } for (int i = 0; i < NCAKE; i++) { sortedP[i] = MP(P[i][t1 % K[i]], i); } sort(sortedP, sortedP + NCAKE); reverse(sortedP, sortedP + NCAKE); printf("%d\n", NSELCACHE); for (int i = 0; i < NSELCACHE; i++) { printf("%d\n", sortedP[i].S + 1); } fflush(stdout); // UPDATE BINARY int nOrders; scanf("%d", &nOrders); for (int i = 0; i < nOrders; i++) { int x; scanf("%d", &x); x--; binary[x][t1] = 1; } // Update freq and fr2 for (int i = 0; i < NCAKE; i++) { if (t1 > 0) {
Solusi Hari-2 - 9
freq[i][t1] = freq[i][t1 - 1]; } freq[i][t1] += binary[i][t1]; if (t1 >= 1) { freq[i][t1] -= binary[i][t1 - 1]; } } } /* for (int i = 0; i < NCAKE; i++) { printf("[%d|%d] : ", i + 1, K[i]); for (int t = 0; t < K[i]; t++) { printf("%.2lf ", P[i][t]); } printf("\n"); } */ return 0; }
Solusi Hari-2 - 10
