11489 - Integer Game

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
aha2007
New poster
Posts: 10
Joined: Sun Jan 21, 2007 10:38 am

11489 - Integer Game

Post by aha2007 » Fri Sep 19, 2008 1:09 pm

Anyone give me any hints:) Really cool Problem

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11489 - Integer Game how to solve?

Post by andmej » 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!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11489 - Integer Game how to solve?

Post by peterkwan » 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;
}

LayCurse
New poster
Posts: 11
Joined: Sun Feb 25, 2007 3:14 pm
Location: Kyoto, Japan

Re: 11489 - Integer Game how to solve?

Post by LayCurse » Sat Sep 20, 2008 2:25 pm

peterkwan wrote:I am getting WA all the time. Please help to give some critical inputs. Thanks.
Try this.
input:
6
443
4444
44444
44455
44555
45555
output:
Case 1: T
Case 2: S
Case 3: T
Case 4: S
Case 5: S
Case 6: T

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11489 - Integer Game how to solve?

Post by peterkwan » 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;
}

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11489 - Integer Game

Post by Obaida » Sun Jan 25, 2009 12:11 pm

Some one can explain these case???
INPUT:

Code: Select all

2
44455
44555
OUTPUT:

Code: Select all

S
S
Why???
The problem statement says if the number of digits in N is odd then S wins otherwise T wins.
I am confused. :-?
try_try_try_try_&&&_try@try.com
This may be the address of success.

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11489 - Integer Game

Post by peterkwan » Sun Jan 25, 2009 2:30 pm

Obaida wrote:Some one can explain these case???
INPUT:

Code: Select all

2
44455
44555
OUTPUT:

Code: Select all

S
S
Why???
I am confused. :-?
This is because:
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.
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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11489 - Integer Game

Post by sohel » Sun Jan 25, 2009 2:46 pm

Obaida wrote:Some one can explain these case???
INPUT:

Code: Select all

2
44455
44555
OUTPUT:

Code: Select all

S
S
Why???
The problem statement says if the number of digits in N is odd then S wins otherwise T wins.
I am confused. :-?
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."

Hope it clears up things!

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 11489 - Integer Game

Post by ssavi » Wed Jul 01, 2015 9:11 pm

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 . Here is my Code: -

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;
}
Please Help Me Out ..
I know I am a Failure Guy . :(

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 11489 - Integer Game

Post by Zyaad Jaunnoo » Tue Feb 28, 2017 2:16 pm

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 .
.
.
Your code is almost correct.. But, you missed a "break" statement when picking a move.

INPUT

Code: Select all

1
2354456456587544678986756467889867
OUTPUT

Code: Select all

Case 1: S

Post Reply

Return to “Volume 114 (11400-11499)”