Module ৪ · if, switch আর loop

Problem: if, switch আর loop

FreeProblemlesson ৭ / ৯

এই lesson-এ যা শিখবে

অজানা দৈর্ঘ্যের input পড়তে পারবে এই দশটায় লাগা তিনভাবে: আগে একটা count, একটা sentinel, অথবা input ফুরিয়ে না যাওয়া পর্যন্ত।
প্রতিটা problem-এর জন্য ঠিক loop-এর আকার বেছে নিতে পারবে, আর উত্তর জানামাত্র loop থামাতে পারবে break, একটা flag বা একটা labelled break দিয়ে।
Submit করার আগেই hidden test-এর কিনারাগুলো নিজে test করতে পারবে: n = 1, ঠিক সীমার উপরের একটা value, একটা ফাঁকা input আর সবচেয়ে বড় মাপ।

দশটা problem, Node 22-এ hidden test দিয়ে grade হয়, মানে Playground যে JavaScript চালায় সেটাই। এদের প্রত্যেকটার সাথে এই module-এই দেখা হয়েছে। steps-goal ছিল lesson 01-এ, আর letter-grade, day-name আর sum-until-zero ছিল lesson 02-এ। Lesson 03-এ ছিল fizzbuzz, min-max-average, guessing-game আর count-primes, lesson 04-এ till-commands, আর first-pair-sum ছিল CP আর Interview Pack-এ।

Problem 1, 2 আর 5 (steps-goal, letter-grade আর fizzbuzz) সবার জন্য free। বাকি সাতটা Pro problem: প্রতিটা problem আলাদা করে lock করার ব্যবস্থা আসবে পরের একটা release-এ, আর তার আগ পর্যন্ত দশটাই খোলা। Module test-এ দুটো problem আছে, fizzbuzz আর min-max-average, তাই এ দুটো এখানে আগে সমাধান করে রাখা কাজের।

Bob loop লেখে, sample চালায়, submit করে দেয়। Zara আগে নিজের program চালিয়ে দেখে n = 1 দিয়ে, একটাও আন্দাজ ছাড়া একটা input দিয়ে, আর ঠিক 90 নম্বর দিয়ে। এই set-এ hidden test-গুলো থাকে loop-এর দুই মাথায়। ওরা ধরে প্রথম pass, শেষ pass, আর সেই pass যেখানে loop-এর থামার কথা ছিল।

Loop কীভাবে বোঝে তালিকা শেষ

Starter পুরো input-কে token-এ ভাগ করে। Token হলো space বা line break-এর মাঝখানের এক টুকরো text। next() পরের token-টা দেয়, আর nextInt() ওটাকে সংখ্যা বানায়। Token পড়া একটা loop-এর আরও একটা জিনিস লাগে: কখন পড়া থামাতে হবে সেটা বোঝার উপায়।

এই দশটা problem তিনটা উপায় ব্যবহার করে। বেশিরভাগ আগে একটা count দেয়: n পড়ো, তারপর n বার loop চালাও। sum-until-zero ব্যবহার করে একটা sentinel, মানে এমন একটা বিশেষ value যেটা শেষ চিহ্নিত করে আর নিজে data-র অংশ না; এখানে সেটা প্রথম 0। guessing-game আর till-commands পড়ে input শেষ না হওয়া পর্যন্ত, কোনো count বা sentinel ছাড়াই।

Program input-এর শেষটা দেখে কীভাবে? Token ফুরিয়ে গেলে next() দেয় undefined, আর nextInt() দেয় NaN। এই ছোট program-টা দুটোই দেখায়, input-এর জায়গায় দুটো token-এর একটা array নিয়ে।

const tokens = ["7", "3"];
let at = 0;
const next = () => tokens[at++];

console.log(next(), next(), next());
console.log(Number(undefined));

7 3 undefined
NaN

তাই input শেষ না হওয়া পর্যন্ত পড়া loop token-টাকেই test করে: while (token !== undefined)। যে loop একটা token বেশি পড়ে, সে undefined পায়, ওটাকে NaN বানায়, আর যে যোগফল ছোঁয় সেটাই নষ্ট করে।

তিনটা সারিই শেষ হয় এমন একটা বাক্সে, যেটাকে loop-কে চিনতে হবে কিন্তু data হিসেবে ব্যবহার করা যাবে না। Count আগে থেকেই বলে দেয় বাক্সটা কোথায়; sentinel আর undefined জানায় শুধু ওখানে পৌঁছালে।

এই দশটায় loop-এর আকারগুলো

প্রতিটা problem-এ লাগে চার রকম loop-এর একটা। Lesson 04-এর flowchart এগুলো বেছে নেয় একই প্রশ্ন দিয়ে: count কি জানা, আর আগেভাগে থামতে হবে কি?

গোনা একটা for loop। steps-goal, letter-grade, day-name, fizzbuzz আর min-max-average আগে n পড়ে, তাই loop ঠিক n বার চলে।
Sentinel সহ একটা while loop। sum-until-zero loop-এর আগে একটা সংখ্যা পড়ে, আর loop-এর test সংখ্যাটা ব্যবহারের আগেই ওটাকে check করে।
Input শেষ না হওয়া পর্যন্ত একটা while loop। guessing-game আর till-commands token-টা undefined কি না দেখে, আর দুটোই আগেভাগে থামতেও পারে।
দুটো nested loop। count-primes সংখ্যাগুলোর উপর চলা একটা loop-এর ভেতরে গুণিতক কাটে, আর first-pair-sum প্রতিটা জোড়া চেষ্টা করে।

Loop-এর ভেতরে সিদ্ধান্তগুলো হয় একটা if আর else if chain দিয়ে (letter-grade, fizzbuzz), নয়তো একটা switch দিয়ে (day-name, till-commands)। দুটোই প্রথম মিলে যাওয়াতে থেমে যায়, তাই test-গুলোর ক্রমও উত্তরের অংশ।

আগেভাগে থামা: break, একটা flag আর একটা label

তিনটা problem input শেষ হওয়ার আগেই থামে। guessing-game থামে ঠিক আন্দাজে, till-commands থামে close-এ, আর first-pair-sum থামে প্রথম জোড়ায়। প্রত্যেকটার লাগে আলাদা যন্ত্র।

break সবচেয়ে কাছের loop বা switch থেকে বের হয়, আর শুধু ওটা থেকেই। একটা loop-এর ভেতরে বসা switch-এর ভেতরে একটা break বের হয় switch থেকে, আর loop চলতেই থাকে। তাই যে থামাটা switch-এর ভেতরে থাকে, তার লাগে একটা flag, মানে loop-এর test যে boolean পড়ে, নয়তো loop-এর গায়ে একটা label।

Label হলো loop-এর সামনে colon দেওয়া একটা নাম, যেমন search:। তখন break search; ওই loop থেকে বের হয়, ওর ভেতরের আরেকটা loop থেকে লিখলেও। একটা উত্তর যখন একসাথে দুটো loop শেষ করে, তখন এটা ব্যবহার করো। নিচের Example 3 এটা দেখায়, অন্য একটা problem-এ।

Hidden test যে কিনারাগুলো ধরে

প্রতিটা problem-এ 11 থেকে 15টা hidden test, আর প্রতিটা test file 1 MiB-এর নিচে থাকে। এরা চলে সবচেয়ে ছোট input থেকে, constraints যতটা বড় হতে দেয় আর judge-এ যতটা আঁটে ততটা পর্যন্ত। এই দুইয়ের মাঝখানে বসে আছে সেই কিনারাগুলো, যেগুলো নিয়ে এই module তোমাকে সাবধান করেছে। Table-টা ওদের নাম বলে দেয়, যাতে তুমি আগেই ওগুলো চালিয়ে দেখতে পারো।

Problem	Access	Test	Hidden test যা চালায়
`steps-goal`	Free	12	n = 1, লক্ষ্য 0 আর 100000, ঠিক লক্ষ্যের উপর আর এক step কম দিন, 100000টা দিন
`letter-grade`	Free	11	59 আর 60, 89 আর 90, 0 আর 100, -1 আর 101, -1000 আর 1000, -5 থেকে 105 পর্যন্ত প্রতিটা নম্বর, 100000টা নম্বর
`day-name`	Pro	11	সাতটা দিনই দুই ক্রমে, 0, 8 আর negative সংখ্যা, -1000 আর 1000, 100000টা সংখ্যা
`sum-until-zero`	Pro	12	সবার আগে একটা 0, 0-এর পরে সংখ্যা, কয়েকটা 0, কয়েক লাইনে ছড়ানো সংখ্যা, 1000000-এর 100000টা সংখ্যা
`fizzbuzz`	Free	13	n = 1, 2, 3 আর 5, 15-এর দুই পাশে 14 আর 16, 30 আর 45, n = 100000
`min-max-average`	Pro	14	n = 1, সব negative, সব positive, সব সমান, 1.6666666666666667 আর 0.00001 গড়, দুই মাথা 1000000000 আর -1000000000
`guessing-game`	Pro	12	একটাও আন্দাজ নেই, প্রথমবারেই ঠিক, কখনো ঠিক না, ঠিক আন্দাজের পরেও আন্দাজ, 100-এর বিপক্ষে 9 আর 1000, 100000টা আন্দাজ
`till-commands`	Pro	14	শুধু `close`, ফাঁকা till, কোনো sale-এর আগে `total`, 0-এর নিচে মোট, অচেনা শব্দ হিসেবে `sales` আর `closed`, `close`-এর পরে command, 100000টা command
`count-primes`	Pro	13	n = 1, 2, 3 আর 4, 25 আর 49, 97, 1000000, 14999981 আর 15000000
`first-pair-sum`	Pro	15	জোড়া সহ আর জোড়া ছাড়া n = 2, এমন সংখ্যা যেটা নিজের সাথেই জোড়া বাঁধত, একদম শেষে জোড়া, পরের i অথচ ছোট j, জোড়াহীন n = 5000

ছোট কিনারাগুলো Playground-এ চালিয়ে দেখো। ওর stdin বাক্সে সর্বোচ্চ 10000টা অক্ষর ধরে, তাই সবচেয়ে বড় test-গুলো ওখানে আঁটে না। এই সীমাটা বাক্সের, judge-এর না। তাছাড়া একটা কিনারা নিয়ে নিজে লেখা একটা test বড় test-এর চেয়ে বেশি কথা বলে।

এই দশটা problem-এ যে রূপগুলো লাগে

const n = nextInt();                       read a count first
for (let i = 0; i < n; i++) { ... }        the body runs n times
for (let i = 1; i <= n; i++) { ... }       i takes 1, 2, ... n, n included
let x = nextInt();                         read before a sentinel loop...
while (x !== 0) { ... x = nextInt(); }     ...and again at the end of each pass
let t = next();                            undefined once the input ends
while (t !== undefined) { ... t = next(); }
if (a) { ... } else if (b) { ... } else { ... }   the first true test wins
switch (v) { case 1: ... break; default: ... }    v === each case, top down
case 6: case 7: ...                        two cases share one body
break;                                     leave the nearest loop or switch
outer: for (...) { for (...) { break outer; } }   leave both loops
i % 3 === 0                                i is a multiple of 3

নিচের প্রতিটা starter এই track-এর নির্দিষ্ট starter। ওর লাইনগুলো যেমন আছে রাখো, আর নিজের code লেখো comment যেখানে বলে সেখানে।
প্রতিটা উত্তরের জন্য output-এর একটা লাইন push করো। শব্দগুলো print হয় statement যেভাবে লেখে হুবহু সেভাবে, ছোট-বড় হাতের অক্ষরও একই।
out-এ push করা number print হয় String() যেভাবে print করে সেভাবে, তাই কখনো হাতে format করতে হয় না।

Example 1: আগেভাগে থামা একটা গোনা loop

Zara দিনে n বার ফোনের battery-র লেভেল লিখে রাখে। ও চায় 20-এর নিচের প্রথম reading-টা, আর ওটা পেয়ে গেলে পড়া থামিয়ে দিতে।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
let checked = 0;
let found = false;

for (let i = 1; i <= n; i++) {
  const level = nextInt();
  checked++;
  if (level < 20) {
    out.push("first low " + level + " at reading " + i);
    found = true;
    break;
  }
}
if (!found) {
  out.push("never low");
}
out.push("readings checked " + checked);

console.log(out.join("\n"));

first low 19 at reading 4
readings checked 4

এই output input 6 আর 85 60 41 19 12 50-এর জন্য। Loop ছয়টা pass-এর জন্য তৈরি ছিল, আর break ওটাকে চারটার পরেই শেষ করে দিল। Flag found loop-এর পরের code-কে জানায় loop কোন পথে শেষ হলো, তাই never low print হয় শুধু তখন, যখন কোনো reading-ই কম ছিল না।

Run in Compiler

Example 2: input শেষ না হওয়া পর্যন্ত পড়া loop-এর ভেতরে একটা switch

Amara-র driving simulator ট্রাফিক লাইটের রং পড়ে, প্রতি token-এ একটা, input শেষ না হওয়া পর্যন্ত। দুটো বানান একই লাইট বোঝায়, তাই ওদের case-গুলো একটা body ভাগাভাগি করে।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let lights = 0;
let colour = next();

while (colour !== undefined) {
  lights++;
  switch (colour) {
    case "green":
      out.push("go");
      break;
    case "amber":
    case "yellow":
      out.push("slow down");
      break;
    case "red":
      out.push("stop");
      break;
    default:
      out.push("unknown " + colour);
  }
  colour = next();
}
out.push("lights " + lights);

console.log(out.join("\n"));

go
slow down
stop
unknown blue
slow down
lights 5

এই output input green amber red blue yellow-এর জন্য। amber আর yellow একই body-তে পৌঁছায়, কারণ case "amber":-এর নিজের কোনো body নেই, ও গড়িয়ে পরেরটায় চলে যায়। এখানে প্রতিটা break শুধু switch থেকে বের হয়, আর while loop চলতে থাকে যতক্ষণ না next() দেয় undefined।

Run in Compiler

Example 3: দুটো nested loop আর একটা labelled break

Kenji-র cinema app সারি ধরে ধরে প্রথম খালি seat খোঁজে। Input হলো সারির সংখ্যা আর প্রতি সারিতে seat-এর সংখ্যা, তারপর প্রতিটা ভরা seat-এর জন্য 1 আর খালি seat-এর জন্য 0।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const rows = nextInt();
const seats = nextInt();
let checked = 0;
let answer = "no free seat";

search: for (let r = 1; r <= rows; r++) {
  for (let s = 1; s <= seats; s++) {
    const taken = nextInt();
    checked++;
    if (taken === 0) {
      answer = "free seat: row " + r + ", seat " + s;
      break search;
    }
  }
}
out.push(answer);
out.push("seats checked " + checked);

console.log(out.join("\n"));

free seat: row 2, seat 3
seats checked 7

এই output input 3 4, তারপর সারি 1 1 1 1, 1 1 0 1 আর 0 1 1 1-এর জন্য। break search; seat 7-এ দুটো loop থেকেই বের হয়ে যায়, তাই সারি 3-এর খালি seat-এর দিকে কেউ তাকায়ই না। সাধারণ একটা break বের হতো শুধু ভেতরের loop থেকে, আর সারি 3-ও খোঁজা হয়ে যেত।

Run in Compiler

এটা কোথায় কাজে লাগে

HTTP/1.1-এর chunked transfer encoding। যে server উত্তরটা stream করে পাঠায়, সে ওটা পাঠায় টুকরো টুকরো করে, প্রতিটার আগে তার size, আর size 0-এর একটা টুকরো body শেষ করে। ওই 0 একটা sentinel, হুবহু sum-until-zero-এর আকার।
Node-এর readline module। এটা একটা stream লাইন ধরে ধরে পড়ে, আর input শেষ হলে একটা close event পাঠায়। Node-এ লেখা command-line tool ওই event-কেই নিজের "input শেষ না হওয়া পর্যন্ত" test হিসেবে ব্যবহার করে।
Unix-এর head tool। head -n 10 নিজের input-এর প্রথম দশটা লাইন print করে থেমে যায়, input যত লম্বাই হোক। এটা আগেভাগে বের হওয়া একটা গোনা loop।
Array.prototype.find। ECMAScript specification এটাকে এমন একটা loop হিসেবে সংজ্ঞায়িত করে, যেটা test পাশ করা প্রথম element-টা ফেরত দেয় আর এর পরের কিছুর দিকে তাকায় না। Module 7 এটা ব্যবহার করে; ভেতরে এটা guessing-game-এরই আগেভাগে বের হওয়া।

যে ভুলগুলো সবাই করে

১. একটা token বেশি পড়া।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
let sum = 0;
for (let i = 0; i <= n; i++) {
  sum += nextInt();
}
out.push(sum);

console.log(out.join("\n"));

NaN

এটা input 3 আর 4 5 6-এর output। i = 0 আর i <= n দিয়ে loop চলে চারবার, আর চার নম্বর nextInt() দেয় NaN। কোনো error নেই, তাই টের পাবে শুধু judge-এর Wrong Answer দেখে। এই ভুলটা তুমিও করবে, কারণ 1 থেকে গুনলে <= n ঠিকই দেখায়। 0 থেকে গুনলে < n, 1 থেকে গুনলে <= n।

২. Loop শেষ করার জন্য switch-এর ভেতরে break।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let word = next();
while (word !== undefined) {
  switch (word) {
    case "stop":
      break;
    default:
      out.push(word);
  }
  word = next();
}

console.log(out.join("\n"));

ready
set
go

Input এখানে ready set stop go, আর go কখনোই print হওয়ার কথা না। break বের হয়েছে switch থেকে, যেটা ওর সবচেয়ে কাছে ছিল, আর loop পড়েই চলেছে। এই ভুলটা তুমিও করবে, কারণ দুই জায়গাতেই break মানে "থামো"। Loop শেষ করো ওর test-এ একটা flag দিয়ে, নয়তো loop-এর গায়ে একটা label বসিয়ে সেই label সহ break লেখো।

৩. Sentinel-কে data হিসেবে গোনা।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

let count = 0;
let total = 0;
let age = 0;
do {
  age = nextInt();
  count++;
  total += age;
} while (age !== -1);
out.push(count + " ages, total " + total);

console.log(out.join("\n"));

3 ages, total 39

Input 20 20 -1, যেখানে -1 শেষ চিহ্নিত করে, তাই উত্তর 2টা বয়স আর মোট 40। do...while loop নিজের test-এর আগে body চালায়, তাই test দেখার আগেই -1 গোনা আর যোগ করা হয়ে গেছে। While loop-এর আগে একবার পড়ো, আর প্রতিটা pass-এর শেষ লাইনে আবার পড়ো।

৪. 0 থেকে শুরু হওয়া চলতি minimum।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

const n = nextInt();
let coldest = 0;
for (let i = 0; i < n; i++) {
  const t = nextInt();
  if (t < coldest) {
    coldest = t;
  }
}
out.push("coldest " + coldest);

console.log(out.join("\n"));

coldest 0

Input 3 আর 5 8 3। কোনো reading-ই 0 ছিল না, তবু 0 জিতে গেল, কারণ কেউ ওকে হারাতে পারেনি। 0-এর নিচের কোনো value থাকলে program ঠিকই চলে, আর এজন্যই negative সংখ্যাওয়ালা sample ভুলটা লুকিয়ে রাখে। চলতি minimum বা maximum শুরু করো প্রথম পড়া value থেকে।

মাথা খাটাও

Zara একটা পরিকল্পনা নিয়ে guessing-game খেলে। ও সবসময় এখনও সম্ভব সংখ্যাগুলোর ঠিক মাঝেরটা আন্দাজ করে, আর প্রতিটা higher বা lower-এর পরে সেই অর্ধেকটা ফেলে দেয় যেখানে গোপন সংখ্যা থাকতে পারে না। গোপন সংখ্যা 1 থেকে 1000000000-এর যেকোনোটা হতে পারে।

Zara-র সবচেয়ে বেশি কয়টা আন্দাজ লাগতে পারে? Bob বলে, এক million-ও লাগতে পারে।

প্রতিটা ভুল আন্দাজের পরে বড়জোর অর্ধেক সংখ্যা সম্ভব থাকে। কয়বার অর্ধেক করলে 1000000000টা সংখ্যা নেমে একটায় আসে?

Problem 1: steps-goalসহজFree

Zara-র step counter প্রতিদিন ও কত step হাঁটল সেটা লিখে রাখে, আর ওর লক্ষ্য দিনে g step। প্রতিটা দিনের জন্য ও জানতে চায় লক্ষ্য পূরণ হলো কি না, আর শেষে জানতে চায় কয় দিন হলো। Input পড়ো starter-এর nextInt() দিয়ে।

Input. প্রথম লাইনে n আর লক্ষ্য g। দ্বিতীয় লাইনে n-টা পূর্ণসংখ্যা: ক্রম অনুযায়ী প্রতিদিনের step।

Output. n + 1-টা লাইন। ক্রম ধরে প্রতিটা দিনের জন্য print করো met, যদি ওই দিনের step কমপক্ষে g হয়, নইলে short। শেষ লাইনে থাকবে কয় দিন লক্ষ্য পূরণ হয়েছে।

Constraints. 1 <= n <= 100000। 0 <= g <= 100000। 0 <= step <= 100000।

Sample. Input 5 8000 আর 7500 8000 12030 0 9100 দিলে ছয় লাইনে short, met, met, short, met আর 3।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

ঠিক g step-এর একটা দিনের জন্য "কমপক্ষে" মানে কী? কোন তুলনার operator এটা বলে?

Hint 2

আগে n আর g পড়ো। তারপর n বার loop চালাও: একটা দিন পড়ো, একটা শব্দ push করো, আর যে দিনগুলো গোনার মতো সেগুলোতে একটা counter-এ 1 যোগ করো। Counter-টা push করো একবারই, loop-এর পরে।

Solution

n বার চলা একটা for loop প্রতিটা দিন nextInt() দিয়ে পড়ে আর >= দিয়ে তুলনা করে, যেটা "কমপক্ষে"-র operator। লক্ষ্য পূরণের দিন push করে met আর 0 থেকে শুরু হওয়া একটা counter-এ 1 যোগ করে, আর counter push হয় loop-এর পরে। g = 0 হলে প্রতিটা দিনই met, 0 step-এর দিনও।

>=-এর জায়গায় > লিখলে sample-এর 8000 step-এর দিনটা short হয়ে যায়, আর sample সেটা ধরে ফেলে। Step-গুলো next() দিয়ে পড়লে text মেলানো হয়, আর "12030" >= "8000" false, কারণ "1" আসে "8"-এর আগে। steps && steps >= g-এর মতো test লক্ষ্য 0 হলেও 0 step-এর দিনকে short বলে, আর একটা hidden test ঠিক এটাই চালায়।

Problem 2: letter-gradeসহজFree

Maria ওর ক্লাসের পরীক্ষা 100-এর মধ্যে নম্বর দিয়ে দেখে, তারপর প্রতিটা নম্বরকে একটা letter grade বানায়। কয়েকটা নম্বর ভুল টাইপ হয়েছে, যেমন 101 বা -1, আর ও চায় ওগুলোকে grade না দিয়ে আলাদা করে চিহ্নিত করতে। Input পড়ো starter-এর nextInt() দিয়ে।

Input. প্রথম লাইনে n। দ্বিতীয় লাইনে n-টা পূর্ণসংখ্যা, মানে নম্বরগুলো।

Output. n-টা লাইন, প্রতিটা নম্বরের জন্য একটা, input-এর ক্রমে। 90 থেকে 100 হলে print করো A, 80 থেকে 89 হলে B, 70 থেকে 79 হলে C। 60 থেকে 69 হলে D, আর 0 থেকে 59 হলে F। নম্বর 0-এর নিচে বা 100-এর উপরে হলে print করো invalid।

Constraints. 1 <= n <= 100000। -1000 <= নম্বর <= 1000।

Sample. Input 7 আর 95 89 70 65 59 101 -1 দিলে সাত লাইনে A, B, C, D, F, invalid আর invalid।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

যে test আগে চলে, সে-ই তার পরের সবকিছু ঠিক করে দেয়। প্রথম test যদি জিজ্ঞেস করে নম্বর কমপক্ষে 60 কি না, তাহলে 95-এর কী হয়?

Hint 2

আগে invalid নম্বরগুলো বাদ দাও। তারপর ভাগগুলো test করো উপর থেকে নিচে, A আগে, যাতে পরের প্রতিটা test-এর শুধু নিজের ভাগের নিচের মাথাটা লাগে।

Solution

if আর else if chain প্রথম true শর্তে থেমে যায়। 0-এর নিচের আর 100-এর উপরের নম্বর বাদ গেলে mark >= 90 মানে কেবল 90 থেকে 100। পরের test mark >= 80 মানে কেবল 80 থেকে 89, কারণ 90 আর তার উপরের নম্বর ওখানে পৌঁছায়ই না। এমন চারটা test আর F-এর জন্য শেষে একটা else প্রতিটা বৈধ নম্বর সামলায়।

>=-এর জায়গায় > দিলে সীমার প্রতিটা নম্বর এক letter নিচে নেমে যায়, তাই 70 হয়ে যায় D আর sample ফেল করে। Invalid test হিসেবে mark >= 100 লিখলে পুরো 100 হয়ে যায় invalid, আর mark <= 0 একই কাজ করে 0-এর সাথে; hidden test দুই মাথাই চালায়। নিচ থেকে উপরে লেখা chain, মানে 60-এর test আগে, 60 থেকে 100-এর প্রতিটা নম্বরের জন্য print করে D।

Problem 3: day-nameসহজPro

David-এর calendar app একটা দিনকে রাখে একটা সংখ্যা হিসেবে: 1 মানে Monday আর 7 মানে Sunday। ও প্রতিটা দিনের নাম চায়, দিনটা weekend কি না জানতে চায়, আর 1 থেকে 7-এর বাইরের সংখ্যাকে bug হিসেবে চিহ্নিত করতে চায়। Input পড়ো starter-এর nextInt() দিয়ে।

Input. প্রথম লাইনে n। দ্বিতীয় লাইনে n-টা পূর্ণসংখ্যা।

Output. n-টা লাইন, প্রতিটা সংখ্যার জন্য একটা, input-এর ক্রমে: দিনের ইংরেজি নাম, একটা space, তারপর 1 থেকে 5 হলে weekday আর 6 বা 7 হলে weekend। অন্য যেকোনো সংখ্যার জন্য print করো invalid। নামগুলো হলো Monday, Tuesday, Wednesday, Thursday, Friday, Saturday আর Sunday।

Constraints. 1 <= n <= 100000। -1000 <= প্রতিটা সংখ্যা <= 1000।

Sample. Input 4 আর 1 6 7 9 দিলে চার লাইনে Monday weekday, Saturday weekend, Sunday weekend আর invalid।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

সাতটা দিনের দুটোর দ্বিতীয় শব্দ একই। একটা switch-এর দুটো case কি একটা body ভাগাভাগি করতে পারে?

Hint 2

সংখ্যাটার উপর switch করো। প্রতিটা weekday-র case নিজের নাম বসায় আর একটা break দিয়ে শেষ হয়। Weekend-এর দুটো case একটার নিচে আরেকটা বসে, একটাই body নিয়ে, আর default case ধরে এমন প্রতিটা সংখ্যা যেটা কোনো দিন না।

Problem 4: sum-until-zeroসহজPro

Kenji-র দোকানের scanner সারাদিনের দামের ওঠানামা পাঠায় একটার পর একটা সংখ্যা হিসেবে, আর একটা 0 দিয়ে বোঝায় তালিকা শেষ। 0-এর পরেও scanner হাবিজাবি পাঠাতে থাকে, আর Kenji-কে সেগুলো বাদ দিতে হয়। Input পড়ো starter-এর nextInt() দিয়ে।

Input. Space বা line break দিয়ে আলাদা করা কিছু পূর্ণসংখ্যা। তালিকা শেষ হয় প্রথম 0-তে, ওই 0 তালিকার অংশ না, আর ওর পরে যা আছে সব বাদ। অন্তত একটা 0 সবসময় থাকে।

Output. দুই লাইন: প্রথম 0-এর আগে কয়টা সংখ্যা এসেছে, আর ওদের যোগফল।

Constraints. প্রথম 0-এর আগে সর্বোচ্চ 100000টা সংখ্যা। প্রতিটা সংখ্যা -1000000 থেকে 1000000-এর মধ্যে।

Sample. Input 5 -2 7 0 4 4 দিলে দুই লাইনে 3 আর 10।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

কয়টা সংখ্যা আসবে তুমি জানো না। তালিকা যে শেষ, সেটা বলে কে, আর সেই সংখ্যাটা কি তালিকার অংশ?

Hint 2

Loop-এর আগে একটা সংখ্যা পড়ো। সংখ্যাটা শেষের চিহ্ন না হওয়া পর্যন্ত loop চলুক। প্রতিটা pass-এ ওটাকে গোনো, যোগ করো, আর শেষ ধাপে পরের সংখ্যাটা পড়ো।

Problem 5: fizzbuzzসহজFree

Alice ওর প্রথম interview-এর জন্য তৈরি হচ্ছে, আর সেখানে শুরুর প্রশ্নটাই FizzBuzz। ও 1 থেকে n পর্যন্ত গোনে, কিন্তু কিছু সংখ্যার জায়গায় শব্দ বসায়। n পড়ো starter-এর nextInt() দিয়ে।

Input. এক লাইনে n।

Output. n-টা লাইন, 1 থেকে n পর্যন্ত প্রতিটা i-এর জন্য একটা। i যদি 3 আর 5 দুটোরই গুণিতক হয়, print করো FizzBuzz। শুধু 3-এর গুণিতক হলে Fizz, আর শুধু 5-এর গুণিতক হলে Buzz। নইলে print করো সংখ্যা i নিজেই।

Constraints. 1 <= n <= 100000।

Sample. Input 15 দিলে পনেরো লাইনে 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14 আর FizzBuzz।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

15 হলো 3-এর গুণিতক। if আর else if chain-এ 3-এর test আগে থাকলে 15 প্রথমে কোন test-এ আটকায়?

Hint 2

i গোনো 1 থেকে n পর্যন্ত, দুই মাথাই সহ। আগে 15-এর গুণিতক কি না দেখো, তারপর 3-এর, তারপর 5-এর, আর তিনটার একটাও true না হলে i নিজেকেই push করো।

Solution

i % 3 === 0 true হয় যখন 3 দিয়ে i ভাগ করলে কিছুই বাকি থাকে না। যে সংখ্যা 3 আর 5 দুটো দিয়েই ভাগ যায়, সেটা 15 দিয়েও ভাগ যায়। তাই 15-এর test আগে আসতেই হবে, নইলে 3-এর test 15-কে ধরে push করে দেয় Fizz। Loop শুরু হয় 1 থেকে আর n-ও ধরে, তাই ঠিক n বার চলে, আর i নিজেকে push করলেও চলে, কারণ out.join ওটাকে text বানায়।

15-এর test শেষে থাকলে sample-এর লাইন 15 print করে Fizz। i < n দেওয়া loop এক লাইন আগে থেমে যায়, আর 0 থেকে শুরু হওয়া loop প্রথমেই print করে FizzBuzz, কারণ 0 প্রতিটা সংখ্যার গুণিতক। সবচেয়ে বড় hidden test 100000টা লাইন চায়, যেটা starter-এর একটাই console.log local machine-এ মোটামুটি এক সেকেন্ডের দশ ভাগের এক ভাগে print করে।

Problem 6: min-max-averageমাঝারিPro

Amara-র program একটা sensor-এর reading-গুলো একবারই পড়ে, এক pass-এ। ও ওদের সম্পর্কে চারটা তথ্য চায়: কয়টা আছে, সবচেয়ে ছোটটা, সবচেয়ে বড়টা আর গড়। Input পড়ো starter-এর nextInt() দিয়ে।

Input. প্রথম লাইনে n। দ্বিতীয় লাইনে n-টা পূর্ণসংখ্যা।

Output. চার লাইন। লাইন 1 হলো count, একটা space আর n। লাইন 2 হলো min, একটা space আর সবচেয়ে ছোট সংখ্যা, আর লাইন 3 হলো max, একটা space আর সবচেয়ে বড়টা। লাইন 4 হলো average, একটা space আর যোগফলকে n দিয়ে ভাগ করা ফল, JavaScript যেভাবে number print করে সেভাবে (String() যা দেয়)।

Constraints. 1 <= n <= 100000। প্রতিটা সংখ্যা -1000000000 থেকে 1000000000-এর মধ্যে, তাই যোগফল একটা নিখুঁত পূর্ণসংখ্যা থাকে।

Sample. Input 5 আর 4 -3 12 7 1 দিলে চার লাইনে count 5, min -3, max 12 আর average 4.2।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

সব সংখ্যা positive হলে, 0 থেকে শুরু হওয়া চলতি minimum কী বলে? আর সব সংখ্যা negative হলে, 0 থেকে শুরু হওয়া চলতি maximum?

Hint 2

প্রথম সংখ্যাটাকেই minimum, maximum আর যোগফলের শুরু ধরো। তারপর বাকি n - 1-টা সংখ্যার উপর loop চালাও, আর একই pass-এ তিনটাই update করো।

Problem 7: guessing-gameমাঝারিPro

Bob একটা program-এর সাথে সংখ্যা আন্দাজের খেলা খেলে, আর program-টা একটা গোপন সংখ্যা জানে। Bob-এর আন্দাজ আসে একটার পর একটা, যতক্ষণ না মেলে বা ফুরিয়ে যায়, আর প্রতিটা ভুল আন্দাজের পরে program বলে higher না lower। Input পড়ো starter-এর nextInt() আর next() দিয়ে।

Input. প্রথম সংখ্যাটা গোপন সংখ্যা s। তারপর আসে আন্দাজগুলো, space বা line break দিয়ে আলাদা, input শেষ না হওয়া পর্যন্ত। একটা আন্দাজও না থাকতে পারে।

Output. ক্রম ধরে প্রতিটা আন্দাজের জন্য এক লাইন। আন্দাজটা গোপন সংখ্যা হলে print করো correct in k, যেখানে k হলো এ পর্যন্ত পড়া আন্দাজের সংখ্যা, এটা সহ; তারপর থামো, এর পরের সব আন্দাজ বাদ। গোপন সংখ্যা আন্দাজের চেয়ে বড় হলে print করো higher, ছোট হলে lower। ঠিক আন্দাজ ছাড়াই input শেষ হলে print করো not found after k, যেখানে k হলো পড়া আন্দাজের সংখ্যা, 0-ও হতে পারে।

Constraints. 1 <= s <= 1000000000। সর্বোচ্চ 100000টা আন্দাজ, প্রতিটা 1 থেকে 1000000000।

Sample. Input 50 আর 25 75 50 10 দিলে তিন লাইনে higher, lower আর correct in 3।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

আন্দাজ যে শেষ, তোমার program সেটা বোঝে কীভাবে? Token ফুরিয়ে গেলে next() কী দেয়?

Hint 2

গোপন সংখ্যা পড়ো, তারপর একটা while loop-এ আন্দাজ পড়ো, যতক্ষণ না token হয় undefined। প্রতিটা আন্দাজ পড়ার সাথে সাথে গোনো। ঠিক আন্দাজে লাইনটা push করো, সাথে সাথে loop থেকে বের হও, আর মনে রাখো যে পেয়ে গেছ।

Problem 8: till-commandsমাঝারিPro

Kenji-র দোকানের till input শেষ না হওয়া পর্যন্ত command পড়ে। ও একটা চলতি মোট রাখে, যেটা শুরু হয় 0 থেকে আর 0-এর নিচেও নামতে পারে। প্রতিটা command-এর শব্দ পড়ো starter-এর next() দিয়ে, আর প্রতিটা amount nextInt() দিয়ে।

Input. Space বা line break দিয়ে আলাদা করা command, input শেষ না হওয়া পর্যন্ত। sale x মোটের সাথে x যোগ করে, আর refund x মোট থেকে x বাদ দেয়। total মোটটা print করে, আর close মোটটা print করে run শেষ করে দেয়। অন্য যেকোনো শব্দ একটা অচেনা command, যার পরে কোনো amount থাকে না।

Output. total-এর জন্য print করো total, একটা space আর মোটটা। close-এর জন্য print করো closed, একটা space আর মোটটা; এর পরের সব command বাদ। অচেনা শব্দের জন্য print করো unknown, একটা space আর শব্দটা। close ছাড়াই input শেষ হলে শেষ লাইনে print করো no close।

Constraints. সর্বোচ্চ 100000টা command। প্রতিটা amount 1 থেকে 1000000-এর একটা পূর্ণসংখ্যা। Command-এর শব্দে শুধু ছোট হাতের অক্ষর থাকে।

Sample. Input sale 250 sale 100 refund 50 total tip close sale 5 দিলে তিন লাইনে total 300, unknown tip আর closed 300।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

কোন command-এর পরে amount থাকে, আর কোনটার পরে থাকে না? একটা অচেনা শব্দের পরের token-টা কী?

Hint 2

Input শেষ না হওয়া পর্যন্ত প্রতি pass-এ একটা শব্দ পড়ো, আর ওটার উপর switch করো। শুধু sale আর refund-এর case একটা amount পড়ে। switch-এর ভেতরের break বের হয় শুধু switch থেকে, তাই close-এর loop শেষ করার অন্য একটা উপায় লাগে।

Problem 9: count-primesকঠিনPro

Maria জানতে চায় দেড় কোটি পর্যন্ত কয়টা prime আছে, আর Kenji বলে computer সোজা গুনে ফেলতে পারে। Prime হলো 1-এর চেয়ে বড় এমন পূর্ণসংখ্যা, যাকে শুধু 1 আর সে নিজেই ভাগ করতে পারে। n পড়ো starter-এর nextInt() দিয়ে।

Input. এক লাইনে n।

Output. দুই লাইন: n-এর সমান বা ছোট prime কয়টা, আর ওদের মধ্যে সবচেয়ে বড়টা। কোনো prime না থাকলে (n < 2) দ্বিতীয় লাইন হবে none।

Constraints. 1 <= n <= 15000000।

Sample. Input 30 দিলে দুই লাইনে 10 আর 29।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

15000000 পর্যন্ত প্রতিটা সংখ্যার ভাজক খুঁজে দেখলে উত্তর ঠিকই আসে। কিন্তু এতে কত সময় লাগে, আর judge কতক্ষণ অপেক্ষা করে?

Hint 2

প্রশ্নটা উল্টে দাও। প্রতিটা সংখ্যার কোনো ভাজক আছে কি না জিজ্ঞেস না করে, প্রতিটা prime-কে দিয়ে ওর নিজের গুণিতকগুলো কাটিয়ে দাও। 0 থেকে n পর্যন্ত প্রতিটা সংখ্যার জন্য একটা true বা false flag রাখো, আর শেষে যে flag-গুলো এখনও true সেগুলো গোনো।

Problem 10: first-pair-sumকঠিনPro

একটা mock interview-তে Alice পায় কিছু সংখ্যার একটা তালিকা আর একটা target। ওকে খুঁজে বের করতে হবে প্রথম এমন দুটো position, যাদের সংখ্যা দুটো যোগ করলে target হয়। Input পড়ো starter-এর nextInt() দিয়ে।

Input. প্রথম লাইনে n আর target t। দ্বিতীয় লাইনে n-টা পূর্ণসংখ্যা, a1 থেকে an।

Output. এক লাইন। 1 থেকে গোনা এমন প্রথম দুটো position i < j, যেখানে ai + aj = t, print করো i j আকারে। "প্রথম" মানে সবচেয়ে ছোট i, আর সেই i-এর জন্য সবচেয়ে ছোট j। এমন কোনো জোড়া না থাকলে print করো none।

Constraints. 2 <= n <= 5000। -1000000000 <= ai <= 1000000000। -2000000000 <= t <= 2000000000।

Sample. Input 6 10 আর 3 8 5 7 2 5 দিলে 1 4: 3 + 7 হলো 10, আর 8 + 2 আর 5 + 5-এর জোড়া আসে পরে।

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

Run in Compiler

Hint 1

Position i-এর সাথে কোন কোন position j জোড়া বাঁধতে পারে? j কি i নিজেই হতে পারে, বা i-এর আগের কোনো position?

Hint 2

সংখ্যাগুলো রেখে দাও, তারপর দুটো nested loop: i প্রতিটা position-এর উপর, আর j শুধু i-এর পরের position-গুলোর উপর। জোড়াগুলো এই ক্রমেই check করো, আর প্রথম মিলেই দুটো loop থেকে বের হয়ে যাও।

সচরাচর যে প্রশ্নগুলো আসে

আমার program-এর শেষ লাইনে NaN print হয়। এটা আসে কোথা থেকে?

তোমার loop input-এ যতগুলো token আছে তার চেয়ে একটা বেশি পড়েছে। তখন next() দেয় undefined, Number(undefined) হলো NaN, আর NaN যে যোগফল ছোঁয় সেটাই নষ্ট করে। Loop-এর test দেখো: 0 থেকে শুরু হলে i < n চলে n বার, আর i <= n চলে n + 1 বার।
Playground-এ আমার count-primes দিব্যি চলল। Judge তাহলে Time Limit Exceeded বলে কেন?

Playground একটা run থামায় 10 সেকেন্ড পরে, আর judge একটা JavaScript program-কে প্রতি test-এ দেয় 2 সেকেন্ড। n = 15000000-এ শুধু এখন পর্যন্ত পাওয়া prime দিয়ে ভাগ করা trial division-এর Playground-এর দুই run-এ লেগেছে প্রায় 4 সেকেন্ড: ওখানে শেষ হয়, কিন্তু judge-এর জন্য অনেক বেশি ধীর। যে program ছোট test-গুলো পাশ করে আর শুধু সবচেয়ে বড়টায় ফেল করে, সেটা সাধারণত ভুল না, ধীর।
এখানে দেখানো loop-গুলোর বদলে কি for...of, forEach বা Math.min ব্যবহার করতে পারি?

Judge শুধু তোমার output পড়ে, তাই যেকোনো ঠিক program পাশ করে। for...of চলে তোমার নিজের বানানো একটা array-র উপর। forEach-এর আগেভাগে থামার কোনো উপায় নেই, তাই guessing-game বা first-pair-sum-এ ওটা মানায় না; lesson 04 দেখায় কেন। Array method-গুলো ঠিকমতো শেখায় Module 7।
কিছু statement "space বা line break" বলে কেন?

Starter পুরো input-কে token-এ ভাগ করে, তাই ওর কাছে line break আর space একই জিনিস। sum-until-zero, guessing-game আর till-commands সেটা বলে দেয়, আর ওদের hidden test দুটোই ব্যবহার করে। যে program শুধু প্রথম লাইন পড়ে, সে পরের লাইনের প্রতিটা সংখ্যা হারায়।
আমার program sample পাশ করে। তাহলে hidden test কেন ফেল করে?

Sample একটাই ছোট উদাহরণ, statement বোঝানোর জন্য বাছা। Hidden test-এ আরও থাকে n = 1, ঠিক সীমার উপরের value, পড়ার মতো কিছুই নেই এমন input আর সবচেয়ে বড় মাপ। উপরের কিনারার table ওদের নাম বলে দেয়; submit করার আগে ছোটগুলো Playground-এ চালিয়ে দেখো।

মূল কথা

Input n দিলে পড়ো count দিয়ে, কোনো value তালিকা শেষ করলে sentinel দিয়ে, আর কিছুই না থাকলে পড়ো যতক্ষণ না next() দেয় undefined।
Statement যে তুলনা বলে সেটাই লেখো: "কমপক্ষে" মানে >=, আর 80 থেকে 89-এর মতো ভাগ দুই মাথাই ধরে।
else if chain-এ বা switch-এ ক্রমই উত্তর ঠিক করে: 3-এর আগে 15 test করো, আর ইচ্ছে করে body ভাগ না করলে প্রতিটা case break দিয়ে শেষ করো।
উত্তর জানামাত্র থামো: break বের হয় একটা loop থেকে, labelled break দুটো থেকে, আর switch-এর ভেতরের break শুধু switch থেকে।
চলতি minimum বা maximum শুরু করো প্রথম value থেকে, আর এমন algorithm বাছো যেটা judge-এর 2 সেকেন্ডে আঁটে, যেমন sieve।
আরও গভীরে: CP আর Interview Pack, nested loop, আগেভাগে বের হওয়া আর bug gallery (Pro)।

এরপর আসছে cheat sheet, যেটা পুরো module-কে এক পাতায় আনে, আর module test: দশটা প্রশ্ন আর এই set-এর দুটো problem, fizzbuzz আর min-max-average। তারপর Module 5 খোলে function।

lesson ৭ শেষ

সব problem accepted হলেই lesson শেষ।

৩ টা free problem-এর মধ্যে ০ টা accepted

পরেরটা: Cheat sheet: এক পাতায় if, switch আর loop

পরের lesson