Harus Berapa Game Lagi?
| |
| |
Several years ago I was playing Spider Solitaire on my computer all the
time. Sometimes I won, sometimes I lost. Then I stopped playing Spider
Solitaire and started participating in programming competitions. After
a few years I happened to start my old solitaire program again. I was
pleased to discover
that with the skill I gained during the years I am now able to win each
and every game of Spider Solitaire.
However, the program still remembers some of my previous games and thus
the statistics don't necessarily reflect my current perfect skills.
The program displays the statistics in the following way:
Games played: X
Games won: Y (Z %)
The number Z is the percentage of games I won, rounded down to the nearest integer. For example, if X=53 and Y=47, then Z=88.
(The
value Y/X is roughly equal to 0.8868, which means that I won roughly
88.68% of the games I played. 88.68% rounded down to an integer is
88%.)
You will be given two ints played and won - the
number of games I played so far, and the number
of games I won so far. Return the smallest positive integer G such that
if I now win G games in a row the displayed value of Z will increase.
If this is impossible, return -1 instead. |
Problem ini muncul di Single Round Match (SRM) TopCoder 2 hari yang lalu. Pertama kali baca soal ini, algoritma yang terpikir oleh 'orang normal' adalah:
1. Jika played == won return -1.
2. Hitung persentase kemenangan, misal persen = won*100/played.
3. Buat sebuah variabel yang menampung game harus kita mainkan, misal tambah.
4. Selama (jumlah game menang (won) + pertandingan tambahan (tambah)) *100 / played + tambah masih sama dengan persen, tambah = tambah + 1.
5. return tambah.
Nah, jika yang terpikirkan adalah algoritma seperti diatas, maka pada saat Challenges Phase, pasti kamu kena Challenges. :)
Kita bisa saja menaikkan persentase dari 1 ke 2, dari 68 ke 69, bahkan dari 98 ke 99. Tapi kita nggak akan bisa menaikkan persentase dari 99 ke 100. Hal ini karena bila persentase==100, artinya kita memenangi seluruh pertandingan. Jadi kita harus menghandle dengan statement:
Jika persen >= 99 return -1
Sudah benarkan solusi kita sampai saat ini? Ternyata belum. :) Untuk soal ini, dibatasi time limit adalah 2 second. Jadi kita gak akan bisa melakukan loop terus menerus apabila diberikan sebuah case dimana played = 1,000,000,000, won = 980,000,000. Disini kita harus menambahkan 1,000,000,000 games. Maka akan terjadi 1,000,000,000 looping.
Nah, menurut misof, salah satu anggota topcoder juga, ada 2 kategori cara untuk menyelesaikan problem ini. Yang pertama cara hacker, yang kedua cara programmer, yang ketiga cara jago matematik. :)
Cara Hacker:
int howManyGames (int played, int won) {
int currentDisplay = display(played,won);
if (currentDisplay >= 99) return -1;
int g;
for (g=1; ; g+=1000)
if (display(played+g,won+g) > currentDisplay)
break;
// We already crossed the boundary.
// Now we return one step back and find its exact position.
g-=1000;
for ( ; ; g++)
if (display(played+g,won+g) > currentDisplay)
return g;
}Cara Programmer:
int howManyGames (int played, int won) {
int currentDisplay = display(played,won);
if (currentDisplay >= 99) return -1;
long minG = 0, maxG = 1;
while (display(played+maxG,won+maxG) == currentDisplay)
maxG *= 2;
while (maxG - minG > 1) {
long midG = (maxG + minG) / 2;
if (display(played+midG,won+midG) == currentDisplay)
minG = midG;
else
maxG = midG;
}
return maxG;
}