Hak Cipta Dilindungi Undang-undang
SOLUSI UJIAN OLIMPIADE SAINS NASIONAL 2013 CALON PESERTA INTERNATIONAL OLYMPIAD IN INFORMATICS (IOI) 2014 HARI KE-1
INFORMATIKA Waktu : 5 jam
KEMENTERIAN PENDIDIKAN DAN KEBUDAYAAN DIREKTORAT JENDERAL PENDIDIKAN MENENGAH DIREKTORAT PEMBINAAN SEKOLAH MENENGAH ATAS TAHUN 2013
Tebak Himpunan Batas Waktu: 1 detik Batas Memory: 32 MB #include #include #include #include #include #include #include #include #include #include #include
<string> <stack> <map>
#define #define #define #define
REP(a,b) for (int a=0; a=c; a--) RESET(a,b) memset(a, b, sizeof a)
#define #define #define #define #define #define #define #define #define
EPS 1e-9 INF 2123123123 LL long long F first S second MP make_pair PB push_back PII pair PDD pair<double,double>
#define __ puts("") using namespace std; int n,k,q; char sc[1000]; void on(){ bool ada[105]; RESET(ada,0); REP(i,n){ printf("1 %d\n", i+1); fflush(stdout); scanf("%s", sc); if (sc[0] != 't'){ ada[i] = 1; } } int cnt = 0; REP(i,n){ if (ada[i]) cnt++; } printf("%d", cnt); REP(i,n){ if (ada[i]) printf(" %d", i+1);
Solusi Hari-1 - 1
} printf("\n"); fflush(stdout); //must be true } void ologn(){ int ki,ka,tgh,ans; //ONE ki = 1; ka = n; while (ki <= ka){ tgh = (ki + ka) >> 1; //ada: tgh? printf("1 %d\n", tgh); fflush(stdout); int h = 0; scanf("%s", sc); if (sc[0] != 't'){ h = 1; } if (h){ ans = tgh; ki = tgh + 1; }else{ ka = tgh - 1; } } printf("%d", ans); FOR(i,1,ans){ printf(" %d", i); } printf("\n"); fflush(stdout); //must be true } void grim(){ //eleminate all 0s bool ada[105]; FOR(i,1,n){ ada[i] = 1; } FOR(i,1,n){ FOR(j,i+1,n){ printf("2 %d %d\n", i, j); fflush(stdout); scanf("%s", sc); if (sc[0] == 't'){ //haha! ada[i] = 0; ada[j] = 0; }
Solusi Hari-1 - 2
} } //odd 0 or even 0? int cnt = 0; int h0 = 0; FOR(i,1,n){ if (ada[i]) cnt++; else h0++; } printf("%d", cnt); FOR(i,1,n){ if (ada[i]) printf(" %d", i); } printf("\n"); fflush(stdout); scanf("%s", sc); if (sc[0] == 'y'){ //sweet, even 0 return; }else{ //some work needed, it is odd 0! int liar = -1; FOR(i,1,n){ if (ada[i]){ printf("%d", cnt-1); FOR(j,1,n){ if (j != i && ada[j]){ printf(" %d", j); } } printf("\n"); fflush(stdout); bool h = 0; scanf("%s", sc); if (sc[0] == 'y'){ return; } } } } } int main(){ gets(sc); scanf("%d %d %d", &n, &k, &q); if (k == 1){ if (q > n){ on(); }else{ ologn(); } }else{ grim(); } return 0; }
Solusi Hari-1 - 3
Berbaris Sebelum Masuk Batas Waktu: 1 detik Batas Memory: 32 MB
#include #include #include #include #include #include #include #include #define S 1000 #define N 1000 using namespace std; char asal[100]; int kasus,banyak; pair batas[N+5]; vector orang[S+5]; bool ada[S+5]; int jawab[N+5],prev[N+5]; bool cf(const int &a,const int &b) { return (batas[a] <= batas[b]); } int main() { assert(scanf("%s %d",asal,&kasus) == 2); assert(scanf("%d",&banyak) == 1); assert(1 <= banyak && banyak <= N); assert(0 <= kasus && kasus <= 4); assert(strcmp(asal,"Subsoal") == 0); if (kasus == 3) assert(banyak <= 8); memset(ada,0,sizeof(ada)); for (int i=0,sem;i,vector<pair >,greater<pair > > pq;
Solusi Hari-1 - 4
for (int j=0;j<masuk;++j) { prev[j] = jawab[j]; jawab[j] = 0; } int indeks1 = 0; int indeks2 = 0; for (int j=0;j<masuk + orang[i].size();++j) { while (indeks2 < (int)orang[i].size() && batas[orang[i][indeks2]].first == j) { pq.push(make_pair(batas[orang[i][indeks2]].second,orang[i][indeks2])); ++indeks2; } if (pq.size() > 0) { jawab[j] = pq.top().second; pq.pop(); } else { jawab[j] = prev[indeks1]; ++indeks1; } } masuk += orang[i].size(); } assert(masuk == banyak); printf("%d",jawab[0]+1); for (int i=1;i
Solusi Hari-1 - 5
Lipat Kertas Batas Waktu: 0,2 detik Batas Memory: 32 MB
#include #include #include #include #include
<stack>
using namespace std; int n,i,x,size,sub; int pos[1000007],bracket[1000007]; bool valid,udah[1000007]; char s[100]; int st[1000007]; int main() { scanf("%s%d",s,&sub); // Kasus scanf("%d",&n); if if if if
(sub (sub (sub (sub
== == == ==
3) 4) 5) 6)
assert(2 assert(2 assert(2 assert(2
<= <= <= <=
n n n n
&& && && &&
n n n n
<= <= <= <=
1000); 4); 1000); 100000);
for (i=1 ; i<=n ; i++) { scanf("%d",&x); assert(1 <= x && x <= n); //printf("%d\n",i); assert(udah[x] == false); udah[x] = true; pos[x] = i; // Simpan posisinya saja } valid = true; for (i=2 ; i<=n ; i+=2) { bracket[pos[i]] = i; bracket[pos[i-1]] = i; } for (i=1 ; i<=n ; i++) if (bracket[i] != 0) { if (size == 0 || bracket[i] != st[size-1]) { st[size] = bracket[i]; size++; } else size--; } if (size != 0) valid = false; for (i=1 ; i<=n ; i++) bracket[i] = 0; size = 0; for (i=3 ; i<=n ; i+=2) { bracket[pos[i]] = i;
Solusi Hari-1 - 6
bracket[pos[i-1]] = i; } for (i=1 ; i<=n ; i++) if (bracket[i] != 0) { if (size == 0 || bracket[i] != st[size-1]) { st[size] = bracket[i]; size++; } else size--; } if (size != 0) valid = false; if (!valid) printf("INVALID\n"); else { for (i=1 ; i
Solusi Hari-1 - 7
Menggelindingkan Kubus Batas Waktu: 0,2 detik Batas Memory: 32 MB
#include #include #include #include #include <stack> #include #include <map> #include <set> #include #include <sstream> #include <string> #include #include #include #include using namespace std; #define fi first #define sc second #define MP make_pair #define pb push_back #define PI acos(-1.0) //alternative #define PI (2.0 * acos(0.0)) #define vi vector #define vii vector #define ALL(c) (c).begin(), (c).end() #define RESET( c,a ) memset( (c), a, sizeof(c) ) #define REP( a,b,c ) for ( int a=b, _c=c; a<_c; ++a ) #define RED( a,b,c ) for ( int a=b, _c=c; a>=_c; --a ) #define REPI( it, c ) for ( __typeof( (c).begin() ) it=(c).begin(); it!=(c).end(); ++it ) const int big = 2000000000; const double INF = 1e9; const double EPS = 1e-9; typedef long long LL; typedef pair pii; typedef pair pLL; #define _DEBUG 1 #ifdef _DEBUG #define DEBUG printf #else #define DEBUG if (0) printf #endif // NTU The Lyons' Template //---------------------------------------------------------------------class dice { public: int i[6];
Solusi Hari-1 - 8
dice() { REP(x,0,6) i[x]=0; } dice( int a[] ) { REP(x,0,6) i[x]=a[x]; } dice rot( int a ) { int z = i[0]; dice ret; REP(x,0,6) ret.i[x] = i[x]; if (a==1) //utara { ret.i[0] = i[4]; ret.i[4] = i[1]; ret.i[1] = i[2]; ret.i[2] = z; } else if (a==2) //timur { ret.i[0] = i[3]; ret.i[3] = i[1]; ret.i[1] = i[5]; ret.i[5] = z; } else if (a==3) //selatan { ret.i[0] = i[2]; ret.i[2] = i[1]; ret.i[1] = i[4]; ret.i[4] = z; } else if (a==4) //barat { ret.i[0] = i[5]; ret.i[5] = i[1]; ret.i[1] = i[3]; ret.i[3] = z; } return ret; } bool operator== (dice cmp) { REP(x,0,6) if (i[x] != cmp.i[x]) return false; return true; } }; bool ud[8][8][8][8][8][8]; bool cek( dice a ) { bool &lho = ud[a.i[0]][a.i[1]][a.i[2]][a.i[3]][a.i[4]][a.i[5]], ret = lho; if (!lho) lho = true; return ret; }
Solusi Hari-1 - 9
int main() { int S; scanf("Subsoal %d", &S); int i[6], h[6]; REP(x,0,6) scanf("%d", &h[x]); REP(x,0,6) scanf("%d", &i[x]); if (S==1) printf("2\n"); else if (S==2) printf("3\n"); else if (S==3) { if ((i[0]==2) && (i[1]==2)) printf("0\n"); else printf("1\n"); } else if (S==4) { if (i[0]==2) printf("0\n"); else if (i[1]==2) printf("2\n"); else printf("1\n"); } else { RESET( ud,0 ); dice cur = dice(h), fin = dice(i); queue q; int o = 0; q.push( cur ); while (!q.empty()) { int SZ = q.size(); while (SZ--) { cur = q.front(); q.pop(); if (!cek(cur)) { if (cur == fin) { printf("%d\n",o); return 0; } } q.push( cur.rot(1) ); q.push( cur.rot(2) ); q.push( cur.rot(3) ); q.push( cur.rot(4) ); } ++o; } } return 0; }
Solusi Hari-1 - 10
