[SOLUTION] The Cake Is a Lie solution codeforces – There is a n×mn×m grid. You are standing at cell (1,1)(1,1) 

The Cake Is a Lie solution codeforces

The Cake Is a Lie solution codeforces

There is a n×mn×m grid. You are standing at cell (1,1)(1,1) and your goal is to finish at cell (n,m)(n,m).

You can move to the neighboring cells to the right or down. In other words, suppose you are standing at cell (x,y)(x,y). You can:

  • move right to the cell (x,y+1)(x,y+1) — it costs xx burles;
  • move down to the cell (x+1,y)(x+1,y) — it costs yy burles.

Can you reach cell (n,m)(n,m) spending exactly kk burles?

Input : The Cake Is a Lie solution codeforces

The first line contains the single integer tt (1t1001≤t≤100) — the number of test cases.

The first and only line of each test case contains three integers nnmm, and kk (1n,m1001≤n,m≤1000k1040≤k≤104) — the sizes of grid and the exact amount of money you need to spend.

Output : The Cake Is a Lie solution codeforces

For each test case, if you can reach cell (n,m)(n,m) spending exactly kk burles, print YES. Otherwise, print NO.

You may print every letter in any case you want (so, for example, the strings yEsyesYes and YES are all recognized as positive answer).

The Cake Is a Lie solution codeforces
Example: The Cake Is a Lie solution codeforces

input

6
1 1 0
2 2 2
2 2 3
2 2 4
1 4 3
100 100 10000

output

YES
NO
YES
NO
YES
NO
Note: The Cake Is a Lie solution codeforces

In the first test case, you are already in the final cell, so you spend 00 burles.

In the second, third and fourth test cases, there are two paths from (1,1)(1,1) to (2,2)(2,2)(1,1)(1,1)  (1,2)(1,2)  (2,2)(2,2) or (1,1)(1,1)  (2,1)(2,1)  (2,2)(2,2). Both costs 1+2=31+2=3 burles, so it’s the only amount of money you can spend.

In the fifth test case, there is the only way from (1,1)(1,1) to (1,4)(1,4) and it costs 1+1+1=31+1+1=3 burles.

The Cake Is a Lie solution codeforces

Program code: Chef and Hills solution

C++

#include <bits/stdc++.h>
using namespace std;
#define inf 1000000001
typedef long l;
typedef long long ll;
const ll INF = 1e18L + 5;
# define MOD 1000000007
# define PI 3.14
#define vi vector<int>
#define vl vector<l>
#define vll vector<ll>
#define pb push_back
#define pob pop_back
#define f first
#define s second
#define ml map<l,l>
#define mll map<ll,ll>
#define mcl map<char,ll>
# define umll unordered_map<ll,ll,custom_hash>
# define umcl unordered_map<char,l>
#define pll pair<ll,ll>
#define mp make_pair 
# define forl(i,range) for(l i=0;i<range;i++)
# define forll(i,range) for(ll i=0;i<range;i++)
// int ans=upper_bound(start,end ,value)-start;
// auto itr=uper_bound(start,end ,value)-vector.begin();
// for (ll i = 0; i < s1.size() && j < s2.size(); i++) if (s1[i]==s2[j]) j++;//subsequence
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}

size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
ll myceil(ll num,ll den)
{
if ((num >= 0 and den > 0) or ( num <= 0 and den < 0))
return num%den == 0 ? num/den : num/den + 1;
return num / den;
}
ll myfloor(ll num,ll den)
{
if ((num >= 0 and den > 0) or ( num <= 0 and den < 0))
return num%den == 0 ? num/den : num/den;
int ans = num / den;
return num % den == 0 ? ans : ans - 1;
}
ll gcd(unsigned long long x, unsigned long long y) { //returns hcf of two long long ints
if (x == 0) return y;
return gcd(y % x, x);
}
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
if (a == 0) 
{ 
*x = 0; 
*y = 1; 
return b; 
} 
ll x1, y1; // To store results of recursive call 
ll gcd = gcdExtended(b%a, a, &x1, &y1); 
*x = y1 - (b/a) * x1; 
*y = x1; 
return gcd; 
} 
unsigned long long findGCD(vector<unsigned long long> &v) 
{ 
unsigned long long result = v[0]; 
for (ll i = 1; i <v.size() ; i++) 
{ 
result = gcd(v[i], result); 

if(result == 1) 
{ 
return 1; 
} 
} 
return result; 
} 
ll lcm(ll a,ll b){
return((a*b)/gcd(a,b));

}
bool sortbysec(ll a,ll b)
{
return (a>b);
}
vll primeFactors(ll n)
{
vll ans;
while (n % 2 == 0) {ans.pb(2);n = n / 2;}
for (ll i = 3; i <= sqrt(n); i = i + 2) {
while (n % i == 0) {ans.pb(i);n = n / i;}}
if (n > 2)ans.pb(n);return ans;
}
bool isPrime(ll n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
// time complexity root of n
if (n%2 == 0 || n%3 == 0) return false;
for (ll i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
vll all_prime(ll n)
{ vll sieve(n+1,0);
for (ll x = 2; x <= n; x++) 
{
if (sieve[x]) continue;
for (int u = 2*x; u <= n; u += x)
{
if(sieve[u]==0)
{
sieve[u]=x;
}
}
}
return sieve;
}
ll power(ll x,ll n)
{
if(n==0)return 1;
ll temp=power(x,n/2);
if(n%2==0) return temp*temp;
else return x*temp*temp;
}
unsigned long long powerper(unsigned long long x, ll y, ll p)
{
unsigned long long res = 1; 
x = x % p;
while (y > 0)
{
if (y & 1)// If y is odd, multiply x with result
res = (res * x) % p;
y = y >> 1; // y = y/2 // y must be even now
x = (x * x) % p;
}
return res;
}
unsigned long long modInverse(unsigned long long n, ll p)// Returns n^(-1) mod p
{
return powerper(n, p - 2, p);
}
unsigned long long nCrModPFermat(unsigned long long n,ll r, ll p, unsigned long long fac[])// Returns nCr % p using Fermat's little
{
if (n < r)
return 0;
if (r == 0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
return (fac[n] * modInverse(fac[r], p) % p
* modInverse(fac[n - r], p) % p)
% p;
}
/*fac[0] = 1;
for (ll i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % MOD;*/
/* ****************************GRAPH ALGO******************************************************************************* */
void dfs(vector<vector<ll>> &v, vector<ll> &df, ll seen[], ll i){ //Also outputed resultant dfs

df.pb(i);
for(ll j=0; j<v[i].size(); j++){
if(seen[v[i][j]]==0){seen[v[i][j]]=seen[i]; dfs(v, df, seen, v[i][j]);}
}
}
bool BFS(vector<vector<ll>> &adj, ll src, ll dest, ll n,ll pred[], ll dist[])
{
list<ll> queue;
bool visited[n];
for (ll i = 0; i < n; i++) {
visited[i] = false;
dist[i] = INF;
pred[i] = -1;
}
visited[src] = true;
dist[src] = 0;
queue.push_back(src);
while (!queue.empty()) {
ll u = queue.front();
queue.pop_front();
for (ll i = 0; i < adj[u].size(); i++) {
if (visited[adj[u][i]] == false) {
visited[adj[u][i]] = true;
dist[adj[u][i]] = dist[u] + 1;
pred[adj[u][i]] = u;
queue.push_back(adj[u][i]);

if (adj[u][i] == dest)
return true;
}
}
}
//cout<< dist[dest];
/*vector<int> path;
int crawl = dest;
path.push_back(crawl);
while (pred[crawl] != -1) {
path.push_back(pred[crawl]);
crawl = pred[crawl];
}*/
return false;
}
ll findConnComp(vector<vector<ll>> &v, ll seen[], ll n){
ll j=0;
vector <ll> df;
for(ll i=0; i<n;i++)seen[i]=0;
for(ll i=0; i<n; i++){
if(!seen[i]){seen[i]=++j; dfs(v, df, seen, i);}
}
return j;
}
vll dijkstra_set(vector<vector<pair<ll, ll>>> &adj, ll src, ll V)//vertex,weight
{
set< pair<ll, ll> > setds;// weight,vertex
vector<ll> dist(V, INF); 

setds.insert(make_pair(0LL, src)); 
dist[src] = 0; 

vll parent(V);
parent[src]=src;
while (!setds.empty()) 
{ 
pair<ll, ll> tmp = *(setds.begin()); 
setds.erase(setds.begin()); 

ll u = tmp.second; 
for (auto it = adj[u].begin(); it != adj[u].end(); it++) 
{ 

ll v = (*it).first; 
ll weight = (*it).second; 

if (dist[v] > dist[u] + weight) 
{ parent[v]=u;
if (dist[v] != INF) 
setds.erase(setds.find(make_pair(dist[v], v))); 

dist[v] = dist[u] + weight; 
setds.insert(make_pair(dist[v], v)); 
} 
} 
}
return dist;
//return parent;
}
void printpath(vll & v1, ll dest)
{
if(v1[dest]==dest)
{ cout<<dest<<' ';
return;
}
printpath(v1,v1[dest]);
cout<<dest<<' ';
}
//*************************************************SEGMENT TREE*****************************************************************
// intitially passing fun(a,tree,0,n-1,1)
// size of tree=4*n// currently calculationg sum
void SegTreeBuild(ll a[], ll tree[], ll start, ll end, ll v){
if(start==end){
tree[v]=a[start];
return;
}
ll mid=(start+end)/2;
SegTreeBuild(a,tree,start,mid,2*v);
SegTreeBuild(a,tree,mid+1,end,2*v+1);

tree[v]=tree[2*v]+tree[2*v+1];
}
void SegTreeUpdate(ll a[], ll tree[], ll start, ll end, ll v, ll idx, ll val){
if(start==end){
a[idx]=val;
tree[v]=val;
return;
}
ll mid=(start+end)/2;
if(idx>mid){
SegTreeUpdate(a,tree,mid+1,end,2*v+1,idx,val);
}else{
SegTreeUpdate(a,tree,start,mid,2*v,idx,val); 
}
tree[v]=tree[2*v]+tree[2*v+1];
}
ll SegTreeQury(ll tree[], ll start, ll end, ll v, ll left, ll right){
if(start>right || end<left){ //completely outside
return 0;
}
if(start>=left && end<=right){ // completely inside
return tree[v];
}
ll mid=(start+end)/2; //partially inside or outside
ll ans1 = SegTreeQury(tree,start,mid,2*v,left,right) ;
ll ans2 = SegTreeQury(tree,mid+1,end,2*v+1,left,right) ;
return ans1+ans2;
}
void SegTreeLazy(ll tree[], ll lazy[], ll low, ll high , ll startR ,ll endR ,ll v, ll val){
if(low>high)return;
if(lazy[v]!=0){
tree[v]+=lazy[v];
if(low!=high){ // leaf node
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
}
lazy[v]=0;
}
if(startR>high || endR< low)return;//completely outside
if(startR<=low && endR>=high){ // completely overlap
tree[v]+=val;
if(low!=high){
lazy[2*v]+=val;
lazy[2*v+1]+=val;
}
return;
}
// partial overlap
ll mid=(low+high)/2;
SegTreeLazy(tree,lazy,low,mid,startR,endR,2*v,val);
SegTreeLazy(tree,lazy,mid+1,high,startR,endR,2*v+1,val);
tree[v]=min(tree[2*v],tree[2*v+1]);
}
/* ************************************************************************************************************** */
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;cin>>t;
while(t--){
ll n,m,k;
cin>>n>>m>>k;
ll x=(n-1)+(m-1)*n;
ll y=(m-1)+(n-1)*m;
// cout<<x<<" "<<y<<"\n";
ll ma=max(x,y);
ll mi=min(x,y);
if(k>=mi && k<=ma)cout<<"YES\n";
else cout<<"NO\n";
}
}

JAVA

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;


import java.math.*;
import java.io.*;
import java.text.*;
import java.math.BigInteger;
public class Main {

static class pair{
int x;
int y;
public pair(int a,int b) {
this.x=a;
this.y=b;
}
}
public static boolean[] sieve(long n)
{
boolean[] prime = new boolean[(int)n+1];
Arrays.fill(prime,true);
prime[0] = false;
prime[1] = false;
long m = (long)Math.sqrt(n);
for(int i=2;i<=m;i++)
{
if(prime[i])
{
for(int k=i*i;k<=n;k+=i)
{
prime[k] = false;
}
}
}
return prime;
} 

public static boolean[] primeseive(long n) {
boolean prime[]=new boolean[(int)n+1];

Arrays.fill(prime, true);

prime[0]=false;
prime[1]=false;

int m=(int) Math.sqrt(n);

for(int i=2;i<m;i++) {
if(prime[i]) {

for(int k=i*i;k<=n;k+=i) {
prime[k]=false;
}
}
}

return prime;
}


static long GCD(long a,long b)
{
if(b==0)
{
return a;
}
return GCD(b,a%b);
}


static long gcdnik(long a,long b)
{
if(b==0)
{
return a;
}
return GCD(b,a%b);
}


static long CountCoPrimes(long n)
{
long res = n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
while(n%i==0)
{
n/=i;
}
res-=res/i;
}
}
if(n>1)
{
res-=res/n;
}
return res;
}



static boolean prime(int n)
{
for(int i=2;i*i<=n;i++)
{
if(i%2==0 ||i%3==0)
{
return false;
}
}
return true;
}
static String userIdGeneration(String input1,String input2,int input3,int input4) {
if(input1.length()==input2.length()) {
String arr[]=new String[2];

arr[0]=input1;
arr[1]=input2;

Arrays.sort(arr);
char c=arr[0].charAt(0);
String output=c+arr[1];

String k=Integer.toString(input3);

char d=k.charAt(input4-1);

output+=d;

char e=k.charAt(k.length()-input4);
output+=e;
String res="";
for(int i=0;i<output.length();i++) {
if(Character.isUpperCase(output.charAt(i))){
res+=Character.toLowerCase(output.charAt(i));
}
else {
res+=Character.toUpperCase(output.charAt(i));
}
}
return res;
}


else {
String arr[]=new String[2];
arr[0]=input1.length()>input2.length()?input2:input1;
arr[1]=input1.length()>input2.length()?input1:input2;

char c=arr[0].charAt(0);

String output=c+arr[1];

String k=Integer.toString(input3);

char d=k.charAt(input4-1);

output+=d;

char e=k.charAt(k.length()-input4);
output+=e;
String res="";
for(int i=0;i<output.length();i++) {
if(Character.isUpperCase(output.charAt(i))){
res+=Character.toLowerCase(output.charAt(i));
}
else {
res+=Character.toUpperCase(output.charAt(i));
}
}
return res;
}

}
static int length(int len) {

if(len==1) {
return 1;
}
else if(len==2) {
return 3;
}
else if(len==3) {
return 6;
}
else if(len==4) {
return 10;
}
return 0;
}


public static int LargestFour(int arr[]) {
Arrays.sort(arr);

int n=arr.length;
int count=0;
int sum=0;
for(int i=n-1;i>=1;i--) {
sum+=arr[i];

count++;
if(count==4) {
break;

}

}

if(count<4) {
sum+=arr[0];
}

return sum;
}
//Nikunj Gupta
public static void insertionSort(int array[]) { 
int n = array.length; 
for (int j = 1; j < n; j++) { 
int key = array[j]; 
int i = j-1; 
while ( (i > -1) && ( array [i] > key ) ) { 
array [i+1] = array [i]; 
i--; 
} 
array[i+1] = key; 
} 
}




static String solve23(int n) {
int k=0;
while(true) {
if(n-2020*k<0) {
return "NO";
}
if((n-2020*k)%2021==0) {
return "YES";
}
k++;
}


}



static void solve(int n,int k) {


if(n==1) {
System.out.println(0);
return;
}
int p=(k+1)/2;

System.out.println((k-p)+(n-k));

for(int j=p;j<k;j++) {
System.out.print(j+" ");
}
for(int j=k+1;j<=n;j++) {
System.out.print(j+" ");
}

System.out.println();
}



static int row[]= {1,0};
static int col[]= {0,1};
static ArrayList<String>l=new ArrayList<>();
public static void main(String[] args) throws IOException{

Scanner s=new Scanner(System.in);

int op=s.nextInt();

long mod=1000000007;
while(op>0) {

int n=s.nextInt();
int m=s.nextInt();
int k=s.nextInt();


int dp[][]=new int[n+1][m+1];

dp[1][1]=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(i==1&&j==1) {
dp[i][j]=0;
}
else if(j==1) {
dp[i][j]=1+dp[i-1][j];
}
else {
dp[i][j]=dp[i][j-1]+i;
}

}



}

if(dp[n][m]==k) {
System.out.println("YES");
}else {
System.out.println("NO");
}


op--;
}

}





private static void printsubsequences(String c, String st) {
// TODO Auto-generated method stub


if(c.length()==0) {
System.out.println(st);
return;
}


printsubsequences(c.substring(1),st+c.charAt(0));
printsubsequences(c.substring(1),st);


}

private static boolean compare(HashMap<Character, Integer> smap, HashMap<Character, Integer> pmap) {
// TODO Auto-generated method stub

for(char ch:smap.keySet()) {
if(smap.get(ch)!=pmap.get(ch)) {
return false;
}
}
return true;
}


private static boolean BinarySearch(int search, int[] val, int n)
{
// TODO Auto-generated method stub

int start=0;
int end=val.length-1;
while(start<=end) {
int mid=(start+end)/2;


if(val[mid]==search) {
return true;
}
else if(val[mid]<search) {
start=mid+1;
}
else {
end=mid-1;
}

}
return false;
}





static long findGCD(ArrayList<Long> arr,long start, long n) 
{ 
long result = arr.get((int)start); 
for (int i = (int)start+1; i < n; i++) 
result = GCD(arr.get(i), result); 

return result; 
} 




static long re(long n)
{
n+=1;
while(n%10==0)
{
n/=10;
}
return n;
}




//xor range query
static long xor(long n)
{

if(n%4==0)
{
return n;
}
if(n%4==1)
{
return 1;
}
if(n%4==2)
{
return n+1;
}
return 0;
}

static long xor(long a,long b)
{
return xor(b)^xor(a-1);
}





static void swap(char c,char p)
{
char t = c;
c = p;
p = t;
}

static long max(long n,long m)
{
return Math.max(n,m);
}
static long min(long n,long m)
{
return Math.min(n,m);
}

// double nd() throws IOException
// {
// return Double.parseDouble(in.next());
// }
// int ni() throws IOException
// {
// return Integer.parseInt(in.next());
// }
// 
// long nl() throws IOException
// {
// return Long.parseLong(in.next());
// }
// 
// String si() throws IOException
// {
// return in.next();
// }
// 
// 


static int abs(int n)
{
return Math.abs(n);
}

static class Scanner 
{
StringTokenizer st;
BufferedReader br;

public Scanner(InputStream s){ br = new BufferedReader(new InputStreamReader(s));}

public String next() throws IOException 
{
while (st == null || !st.hasMoreTokens()) 
{
st = new StringTokenizer(br.readLine());
}
return st.nextToken();
}

public int nextInt() throws IOException {return Integer.parseInt(next());}

public long nextLong() throws IOException {return Long.parseLong(next());}

public String nextLine() throws IOException {return br.readLine();}

public boolean ready() throws IOException {return br.ready();}


}


}



class Pair implements Comparable<Pair>
{
int x,y;
public Pair(int x,int y)
{
this.x = x;
this.y = y;
}
public int compareTo(Pair o)
{
return this.y-o.y;
}
}

 

PYTHON

for s in[*open(0)][1:]:n,m,k=map(int,s.split());print('YNEOS'[k!=n*m-1::2])

 

The Cake Is a Lie solution codeforces

The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces. The Cake Is a Lie solution codeforces, The Cake Is a Lie solution codeforces

Also read : Flower Sequence solution codechef 2021 

Leave a Comment