PROBLEM LINK:
In case the contest did not have two separate pages for Div-1 and Div-2, you can delete one of these above lines.
Author: Sandeep Singh
Tester: Soham Chakrabarty
Editorialist: Sandeep SIngh
DIFFICULTY:
EASY
PREREQUISITES:
knowledge of tic-tac-toe and basics of game theory.
QUICK EXPLANATION:
If the first turn selects the mid, then selecting any corner in the second turn will lead to a draw. If the first turn is a corner, then the second turn should be the center to lead to a draw. For other choices in the second turn, Sheldon wins.
EXPLANATION:
Realize that Leonard can never win the game. Since Sheldon and Leonard play optimally, the result of the game depends on the first two turns by Amy and Penny.
The only two possible outcomes are - draw and Sheldon wins. Since Amy chooses odd numbers, she will either choose the centre or a corner.
In case she selects any corner, for the game to lead to a draw in an optimal play, Penny should choose the centre. For any other choice, there is always a way for Sheldon to win the game.
In the same way, If the first choice is the center, for a tie game, Penny should pick a corner or else there is always a way for Sheldon to win the game.
For more detailed analysis refer to this
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
void solve(){
int A,B;
cin>>A>>B;
string result="draw";
if(A==5){
if(!(B&1))
result="sheldon";
}
else{
if(B!=5)
result="sheldon";
}
cout<<result<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("ip5.in","r",stdin);
freopen("op5.out","w",stdout);
#endif
int t;
cin>>t;
while(t--)
solve();
}
Tester's Solution
def check(x):
return (x==1 or x==3 or x==7 or x==9)
t=int(input())
while(t):
t-=1
a,b=map(int,input().split())
if check(a):
if (b!=5):
print("sheldon")
else:
print("draw")
elif a==5:
if check(b):
print("draw")
else:
print("sheldon")
else:
print("draw")