1124 : ชั่งสินค้า (balance)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
คุณเป็นพ่อค้าที่ตระเวนขายสินค้าไปตามเมืองต่างๆ ในการชั่งสินค้าแต่ละชิ้นนั้น คุณจะใช้ตาชั่งสองแขนและตุ้มน้ำหนักเป็นอุปกรณ์ในการชั่ง เนื่องจากคุณทราบว่าสินค้าที่ขายจะมีน้ำหนักเป็นจำนวนเต็มเสมอ และจะมีน้ำหนักไม่เกิน 1,000,000,000 หน่วย คุณจะเตรียมตุ้มน้ำหนักขนาดตั้งแต่ 1 หน่วย 2 หน่วย 3 หน่วย ไปเรื่อยๆ จนถึง 1,000,000,000 หน่วย ซึ่งมีจำนวนมากและสร้างความลำบากในการพกพาระหว่างเดินทางเป็นอย่างมาก
วันหนึ่ง คุณได้เดินทางไปพบหมาป่าสาวตัวหนึ่ง เธอได้ขอร่วมเดินทางไปกับคุณ และเนื่องจากเธอเป็นหมาป่าที่ฉลาดมาก เมื่อเธอเห็นตุ้มน้ำหนักจำนวนมากมายมหาศาลของคุณ จึงได้บอกว่า คุณไม่จำเป็นจะต้องใช้ตุ้มน้ำหนักมากขนาดนี้ ใช้เพียงแค่ 20 อันก็เพียงพอแล้ว คือใช้ตุ้มน้ำหนักที่ขนาดเป็นกำลังของ 3 ทั้งหมด นั่นคือขนาด 1 หน่วย 3 หน่วย 9 หน่วย ไปเรื่อยๆ จนถึง 319 = 1,162,261,467 หน่วย
ตัวอย่างเช่น ถ้าคุณมีสินค้าน้ำหนัก 10 หน่วย คุณสามารถชั่งสินค้าได้โดยการนำสินค้าวางไว้บนตาชั่งข้างซ้าย แล้วนำตุ้มน้ำหนักขนาด 9 หน่วยและ 1 หน่วย วางไว้บนตาชั่งข้างขวา ก็จะทำให้ตาชั่งสมดุล ดังนั้น คุณจึงใช้ตุ้มน้ำหนักทั้งหมด 2 อัน และสิ่งของบนตาชั่งแต่ละข้างจะมีน้ำหนักรวมข้างละ 10 หน่วย
หรือถ้าคุณมีสินค้าน้ำหนัก 20 หน่วย คุณก็จะสามารถชั่งได้โดยการนำสินค้าและตุ้มน้ำหนักขนาด 9 หน่วยและ 1 หน่วย วางไว้บนตาชั่งข้างซ้าย แล้วนำตุ้มน้ำหนักขนาด 27 หน่วยและ 3 หน่วย วางไว้บนตาชั่งข้างขวา ก็จะทำให้ตาชั่งสมดุล ดังนั้น คุณจึงใช้ตุ้มน้ำหนักทั้งหมด 4 อัน และสิ่งของบนตาชั่งแต่ละข้างจะมีน้ำหนักรวมข้างละ 30 หน่วย
หมาป่าสามารถพิสูจน์ได้ว่า ไม่ว่าสินค้าจะมีน้ำหนักเท่าใด ก็จะสามารถนำไปชั่งบนตาชั่งสองแขนให้สมดุลได้เสมอ และจะมีวิธีชั่งได้เพียงวิธีเดียวเท่านั้น (การสลับตาชั่งข้างซ้ายกับข้างขวาถือว่าเป็นวิธีเดียวกัน) เมื่ออธิบายจนคุณเชื่อแล้ว หมาป่าก็จากคุณไป
แม้ว่าคุณจะพอเข้าใจ แต่คุณคิดเลขได้ไม่เร็วเท่าหมาป่า ในการขายสินค้าชิ้นหนึ่ง คุณต้องการทราบว่า ในการชั่งสินค้าชิ้นนั้น จะต้องใช้ตุ้มน้ำหนักทั้งหมดกี่อัน และเมื่อชั่งแล้ว ตาชั่งแต่ละข้างจะมีน้ำหนักรวมข้างละเท่าไร
งานของคุณ
จงเขียนโปรแกรมเพื่อรับน้ำหนักของสินค้า และคำนวณหาจำนวนตุ้มน้ำหนักที่ต้องใช้ในการชั่งสินค้าด้วยตาชั่งสองแขน และน้ำหนักรวมของสิ่งของบนตาชั่งข้างหนึ่ง
ข้อมูลนำเข้า
มีบรรทัดเดียว ซึ่งระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000,000) แทนน้ำหนักของสินค้า
ข้อมูลส่งออก
วันหนึ่ง คุณได้เดินทางไปพบหมาป่าสาวตัวหนึ่ง เธอได้ขอร่วมเดินทางไปกับคุณ และเนื่องจากเธอเป็นหมาป่าที่ฉลาดมาก เมื่อเธอเห็นตุ้มน้ำหนักจำนวนมากมายมหาศาลของคุณ จึงได้บอกว่า คุณไม่จำเป็นจะต้องใช้ตุ้มน้ำหนักมากขนาดนี้ ใช้เพียงแค่ 20 อันก็เพียงพอแล้ว คือใช้ตุ้มน้ำหนักที่ขนาดเป็นกำลังของ 3 ทั้งหมด นั่นคือขนาด 1 หน่วย 3 หน่วย 9 หน่วย ไปเรื่อยๆ จนถึง 319 = 1,162,261,467 หน่วย
ตัวอย่างเช่น ถ้าคุณมีสินค้าน้ำหนัก 10 หน่วย คุณสามารถชั่งสินค้าได้โดยการนำสินค้าวางไว้บนตาชั่งข้างซ้าย แล้วนำตุ้มน้ำหนักขนาด 9 หน่วยและ 1 หน่วย วางไว้บนตาชั่งข้างขวา ก็จะทำให้ตาชั่งสมดุล ดังนั้น คุณจึงใช้ตุ้มน้ำหนักทั้งหมด 2 อัน และสิ่งของบนตาชั่งแต่ละข้างจะมีน้ำหนักรวมข้างละ 10 หน่วย
หรือถ้าคุณมีสินค้าน้ำหนัก 20 หน่วย คุณก็จะสามารถชั่งได้โดยการนำสินค้าและตุ้มน้ำหนักขนาด 9 หน่วยและ 1 หน่วย วางไว้บนตาชั่งข้างซ้าย แล้วนำตุ้มน้ำหนักขนาด 27 หน่วยและ 3 หน่วย วางไว้บนตาชั่งข้างขวา ก็จะทำให้ตาชั่งสมดุล ดังนั้น คุณจึงใช้ตุ้มน้ำหนักทั้งหมด 4 อัน และสิ่งของบนตาชั่งแต่ละข้างจะมีน้ำหนักรวมข้างละ 30 หน่วย
หมาป่าสามารถพิสูจน์ได้ว่า ไม่ว่าสินค้าจะมีน้ำหนักเท่าใด ก็จะสามารถนำไปชั่งบนตาชั่งสองแขนให้สมดุลได้เสมอ และจะมีวิธีชั่งได้เพียงวิธีเดียวเท่านั้น (การสลับตาชั่งข้างซ้ายกับข้างขวาถือว่าเป็นวิธีเดียวกัน) เมื่ออธิบายจนคุณเชื่อแล้ว หมาป่าก็จากคุณไป
แม้ว่าคุณจะพอเข้าใจ แต่คุณคิดเลขได้ไม่เร็วเท่าหมาป่า ในการขายสินค้าชิ้นหนึ่ง คุณต้องการทราบว่า ในการชั่งสินค้าชิ้นนั้น จะต้องใช้ตุ้มน้ำหนักทั้งหมดกี่อัน และเมื่อชั่งแล้ว ตาชั่งแต่ละข้างจะมีน้ำหนักรวมข้างละเท่าไร
งานของคุณ
จงเขียนโปรแกรมเพื่อรับน้ำหนักของสินค้า และคำนวณหาจำนวนตุ้มน้ำหนักที่ต้องใช้ในการชั่งสินค้าด้วยตาชั่งสองแขน และน้ำหนักรวมของสิ่งของบนตาชั่งข้างหนึ่ง
ข้อมูลนำเข้า
มีบรรทัดเดียว ซึ่งระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000,000) แทนน้ำหนักของสินค้า
ข้อมูลส่งออก
มีบรรทัดเดียว ระบุจำนวนตุ้มน้ำหนักที่ต้องใช้ และน้ำหนักรวมของสิ่งของบนตาชั่งข้างหนึ่ง
การให้คะแนน
โจทย์โดย: สุธี เรืองวิเศษ
การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 100,000
ที่มา
การแข่งขัน IOI Thailand League เดือนกรกฏาคม 2553ที่มา
โจทย์โดย: สุธี เรืองวิเศษ
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 10 | 2 10 |
| 20 | 4 30 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 17 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)