### 11489 - Integer Game

Posted:

**Fri Sep 19, 2008 1:09 pm**Anyone give me any hints:) Really cool Problem

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=42&t=42316

Page **1** of **1**

Posted: **Fri Sep 19, 2008 1:09 pm**

Anyone give me any hints:) Really cool Problem

Posted: **Fri Sep 19, 2008 6:10 pm**

There's an O(n) solution.

Invisible text follows:

First determine if the first player can remove a number.

If he can, then notice than from now on the only possible numbers than can be removed are 3, 6, or 9. Also notice that it's completely equivalent to delete any removable number, because you won't get any extra advantage if you choose 9 instead of 3 or whatever. The only thing that matters is that it must be divided evenly by 3.

From this, you can count the number of removable digits and determine the winner by the parity of the count.

Good luck!

Invisible text follows:

First determine if the first player can remove a number.

If he can, then notice than from now on the only possible numbers than can be removed are 3, 6, or 9. Also notice that it's completely equivalent to delete any removable number, because you won't get any extra advantage if you choose 9 instead of 3 or whatever. The only thing that matters is that it must be divided evenly by 3.

From this, you can count the number of removable digits and determine the winner by the parity of the count.

Good luck!

Posted: **Sat Sep 20, 2008 12:58 pm**

I am getting WA all the time. Please help to give some critical inputs. Thanks.

Code: Select all

```
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int i=0; i<n; i++) {
string s;
cin >> s;
int n2 = s.size();
cout << "Case " << (i+1) << ": ";
// cout << s << " - ";
if (n2==1)
cout << "S" << endl;
else if (n2==2)
cout << "T" << endl;
else {
int sum = 0, n1 = 0;
for (int j=0;j<n2;j++) {
int c=(s[j]-'0');
sum+=c;
if (c%3==0) n1++;
}
if (n1==n2) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else if (sum%3==0) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else if (n2-n1<=2) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else if ((n2-n1)%3==2) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else {
if (n1%2==0)
cout << "S" << endl;
else
cout << "T" << endl;
}
}
}
return 0;
}
```

Posted: **Sat Sep 20, 2008 2:25 pm**

Try this.peterkwan wrote:I am getting WA all the time. Please help to give some critical inputs. Thanks.

input:

output:6

443

4444

44444

44455

44555

45555

Case 1: T

Case 2: S

Case 3: T

Case 4: S

Case 5: S

Case 6: T

Posted: **Sun Sep 21, 2008 5:32 am**

LayCurse, thanks for your input. I modified my code and finally passed the test case above. However, I am still getting WA. Could somebody helps what test case my code below will fail? Thanks a lot.

Code: Select all

```
#include <iostream>
using namespace std;
main() {
int n;
cin >> n;
for (int i=0; i<n; i++) {
string s;
cin >> s;
int n2 = s.size();
cout << "Case " << (i+1) << ": ";
// cout << s << " - ";
if (n2==1)
cout << "S" << endl;
else if (n2==2)
cout << "T" << endl;
else {
int sum = 0, n1 = 0;
string s1="", s2="";
for (int j=0;j<n2;j++) {
int c=(s[j]-'0');
if (c%3==0) n1++;
else {
if (c%3==1)
s1+=s[j];
else
s2+=s[j];
sum+=c;
}
}
if (n1==n2) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else if (sum%3==0) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else if ((n2-n1)==1) {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
else if ((n2-n1)==2) {
cout << "T" << endl;
}
else {
if (sum%3==2 && s2.size()>=1) {
if (n1%2==0)
cout << "S" << endl;
else
cout << "T" << endl;
}
else if (sum%3==1 && s1.size()>=1) {
if (n1%2==0)
cout << "S" << endl;
else
cout << "T" << endl;
}
else {
if (n1%2==0)
cout << "T" << endl;
else
cout << "S" << endl;
}
}
}
}
return 0;
}
```

Posted: **Sun Jan 25, 2009 12:11 pm**

Some one can explain these case???

**INPUT:**
**OUTPUT:**
Why???

Code: Select all

```
2
44455
44555
```

Code: Select all

```
S
S
```

I am confused.The problem statement says if the number of digits in N is odd then S wins otherwise T wins.

Posted: **Sun Jan 25, 2009 2:30 pm**

This is because:Obaida wrote:Some one can explain these case???

INPUT:Code: Select all

`2 44455 44555`

OUTPUT:Why???Code: Select all

`S S`

I am confused.

Since S moves first, the obvious way is to remove the redundant digit (4 in the first case and 5 in the second case). After removing the digit, there is no way for T to remove a digit to remain the resulting sum to be a multiple of 3. Therfore, S wins.A player can remove a particular digit if the sum of digits of the resulting number is a multiple of 3 or there are no digits left.

Posted: **Sun Jan 25, 2009 2:46 pm**

You should continue reading on from that sentence. The next sentence that follows goes like this : "To make the game more interesting, we apply one additional constraint. A player can remove a particular digit if the sum of digits of the resulting number is a multiple of 3 or there are no digits left."Obaida wrote:Some one can explain these case???

INPUT:Code: Select all

`2 44455 44555`

OUTPUT:Why???Code: Select all

`S S`

I am confused.The problem statement says if the number of digits in N is odd then S wins otherwise T wins.

Hope it clears up things!

Posted: **Wed Jul 01, 2015 9:11 pm**

Code: Select all

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, caseno=0;
char a[1005];
scanf("%d",&t);
getchar();
for(int k=0; k<t; k++)
{
gets(a);
int digsum = 0, res;
for(int i=0; i<strlen(a); i++)
{ digsum = digsum + (a[i]-'0'); }
int s = 0;
int t = 0;
for(int i=0; i<strlen(a); i++)
{
if(a[i]!='0')
{
res = digsum - (a[i]-'0');
if(res%3==0)
{
a[i]='0';
digsum = res;
if(s==t)
s++;
else
t++;
}
}
}
//cout<<s<<t<<endl;
if(s>t)
printf("Case %d: S\n", ++caseno);
else
printf("Case %d: T\n", ++caseno);
}
return 0;
}
```

Posted: **Tue Feb 28, 2017 2:16 pm**

Your code is almost correct.. But, you missed a "break" statement when picking a move.ssavi wrote:Why It is Getting WA?? I have Checked All The Tests of Samples , uDebug and OJ Borads . All are Ok . But I am getting WA .

.

.

Code: Select all

```
1
2354456456587544678986756467889867
```

Code: Select all

```
Case 1: S
```