PAJAPONG - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Mladen Puzic

Tester: Michael Nematollahi

Editorialist: Taranpreet Singh

DIFFICULTY:

PREREQUISITES:

Basic Math.

PROBLEM:

You are given the number of points scored by Chef and Paja being X and Y in a game of Ping Pong. You are also given integer K. For first K games, Chef serves, for next K games, Paja serves, then for next K games, Chef serves and so on.

Find out who shall take the next serve.

EXPLANATION

Since Chef has X points and Paja has Y points, We know a total of X+Y games have been played till now. That’s all we need to find out who serves in next game.

Let’s number games played till now from 0 to X+Y-1, so we want to find who serves in game numbered X+Y. Let us write Z = X+Y as

We can see that for every 2*K games, Chef serves in first K games, Paja serves in next K games. So, We can easily state that the person serving in game i shall be the person serving in game (i-2*K*c) where c \geq 0 and (i-2*K*c) \geq 0 holds. Hence, we can easily reduce that person serving in game X+Y is same as person serving in game Z = (X+Y) \% (2*K).

Now, we have 0 \leq Z < 2*K and we want to know who serves in game Z. We know, Chef serves in games in range [0, K-1] and Paja serves in games in range [K, 2*K-1] out of first 2*K games, we can easily check whether Z lies in [0, K-1] or [K, 2*K-1] and print answer accordingly.

Bonus Problem:
Find out the number games in which Chef has served, if Chef scored X points and Paja scored Y points.

TIME COMPLEXITY

Time complexity is O(1) per test case.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
	int T; cin >> T;
	while(T--) {
	    int X, Y, K;
	    cin >> X >> Y >> K;
	    long long totalPoints = X+Y; ///we are only interested in the total number of points
	    long long pointRemainder = totalPoints%(2*K); ///how many points since Chef last started serving
	    if(pointRemainder < K) { ///if in current round, Chef hasn't served K times, then he serves
	        cout << "Chef\n";
	    } else { ///otherwise, Paja serves
	        cout << "Paja\n";
	    }
	}
	return 0;

}
Tester's Solution
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		int x, y, k; cin >> x >> y >> k;
		int sm = x+y;
		sm /= k;
		if (sm&1)
			cout << "Paja\n";
		else
			cout << "Chef\n";
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class PAJAPONG{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long x = nl(), y = nl(), k = nl();
	    long d = x+y;
	    if((d/k)%2 == 0)pn("Chef");
	    else pn("Paja");
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new PAJAPONG().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

2 Likes

My approach is slight different

first calculate (x+y)/k
Let h=(x+y)/k

if h is even answer is Chef
If h is odd answer is Paja

1 Like

Then you have to mod it by 2

h=((x+y)/k)%2

they are same as testers solution

The question Paja Pong is same as “Chef and Serves problem” of Codechef October challenge 2018 . The solution is also same . The difference is “Paja” comes in place of “Cook” :sweat_smile:

https://www.codechef.com/OCT18B/problems/CHSERVE

2 Likes